Me and my team are trying to recreate a C++ type language and we are stuck on a shift-reduce conflict that arises from the non-terminal responsible for function definitions. The grammar goes like:
...
program ::= program variable_declaration SEMICOLON| programa function_declaration SEMICOLON| program function_definition | program type_definition SEMICOLON;
function_definition ::= type IDENTIFIER OPENBRACKET argument_list CLOSEBRACKET block;
block ::= OPENCURLYBRACKET instruction_sequence CLOSECURLYBRACKET;
instruction_sequence ::= instruction_sequence instruction | /*EPS*/;
instruction ::= non_balanced_instruction | balanced_instruction;
balanced_instruction::= IF OPENBRACKET expression CLOSEBRACKET balanced_instruction ELSE balanced_instruction| not_if_instruction;
non_balanced_instruction ::= IF OPENBRACKET expression CLOSEBRACKET instruccion | IF OPENBRACKET expresion CLOSEBRACKET balanced_instruction ELSE non_balanced_instruction ;
not_if_instruction ::= block| while| for| switch| semicolon_instruction;
...
Upper cases mean terminal symbols, while lower cases mean non terminal ones. function_declaration represents prototypes, whereas function_definition refers to the implementation of the function.
The output from CUP is:
Shift/Reduce conflict found in state #197 between instruction ::= balanced_instruction() and non_balanced_instruction ::= IF OPENBRACKET expression CLOSEBRACKET balanced_instruction () ELSE non_balanced_instruction and balanced_instruction ::= IF OPENBRACKET expression CLOSEBRACKET balanced_instruction (*) ELSE balanced_instruction under symbol ELSE
We have been debbugging for days, we are desperate. We found out that the conflict dissapears when we remove the whole non-terminal function_definition.
We tried rebuilding the grammar in small increments until finding the exact non-terminal that caused the conflict.
Any help is truly appreciated :)).