I am writting a small compiler for a compilers' class. The algorithm is having a shift/reduce conflict when I try to enclose if-else with braces '{', '}'. The non-ambiguous if-else statement I took from the dragon book, which turns to be ambiguous when I add the braces. To build the parser and test it I am using the Ply library written in Python.
The grammar terminals/nonterminals specification is backwards here - Uppercase strings are the terminals and Lowercase are the non-terminals. Also the grammar below is not ambiguous untill you try to enclose the if-else with {} which is tokenized as LBRACE and RBRACE.
Below is the grammar specification:
Rule 0 S' -> program
Rule 1 program -> function_definition program
Rule 2 program -> empty
Rule 3 function_definition -> DEFINE data_type ID LPAREN function_definition_args RPAREN block
Rule 4 function_definition_args -> var_list
Rule 5 function_definition_args -> empty
Rule 6 var_list -> var_declaration COMMA var_list
Rule 7 var_list -> var_declaration
Rule 8 var_declaration -> data_type ID
Rule 9 data_type -> VOID
Rule 10 data_type -> INT
Rule 11 data_type -> FLOAT
Rule 12 data_type -> STRING
Rule 13 data_type -> CHAR
Rule 14 block -> LBRACE statements RBRACE
Rule 15 statements -> statement statements
Rule 16 statements -> empty
Rule 17 statement -> matched_statement
Rule 18 statement -> unmatched_statement
Rule 19 matched_statement -> IF LPAREN logical_expression RPAREN LBRACE matched_statement RBRACE ELSE LBRACE matched_statement RBRACE
Rule 20 matched_statement -> command
Rule 21 unmatched_statement -> IF LPAREN logical_expression RPAREN LBRACE command RBRACE
Rule 22 unmatched_statement -> IF LPAREN logical_expression RPAREN LBRACE matched_statement RBRACE ELSE LBRACE unmatched_statement RBRACE
Rule 23 logical_expression -> logical_term OR logical_term
Rule 24 logical_expression -> logical_term
Rule 25 logical_term -> logical_factor AND logical_factor
Rule 26 logical_term -> logical_factor
Rule 27 logical_factor -> boolean_statement
Rule 28 logical_factor -> NOT logical_factor
Rule 29 logical_factor -> LPAREN logical_expression RPAREN
Rule 30 boolean_statement -> value comparison_op value
Rule 31 boolean_statement -> value
Rule 32 value -> ID
Rule 33 value -> NUMBER
Rule 34 comparison_op -> LESS_THAN
Rule 35 comparison_op -> LESS_EQUAL
Rule 36 comparison_op -> GREATER_THAN
Rule 37 comparison_op -> GREATER_EQUAL
Rule 38 comparison_op -> EQUAL
Rule 39 command -> compound_statement
Rule 40 command -> simple_statement
Rule 41 compound_statement -> WHILE LPAREN logical_expression RPAREN block
Rule 42 simple_statement -> expression
Rule 43 expression -> expression PLUS term
Rule 44 expression -> expression MINUS term
Rule 45 expression -> term
Rule 46 term -> term TIMES factor
Rule 47 term -> term DIVIDE factor
Rule 48 term -> factor
Rule 49 factor -> NUMBER
Rule 50 factor -> ID
Rule 51 factor -> LPAREN expression RPAREN
Rule 52 uminus_expression -> MINUS LPAREN expression RPAREN
Rule 53 empty -> <empty>
Rule 54 function_definition -> DEFINE data_type ID LPAREN function_definition_args RPAREN error
The following change bellow is the one which causes the shif/reduce conflicts
Rule 21 unmatched_statement -> IF LPAREN logical_expression RPAREN LBRACE command RBRACE
Rule 22 unmatched_statement -> IF LPAREN logical_expression RPAREN LBRACE matched_statement RBRACE ELSE LBRACE unmatched_statement RBRACE