CFG With unambiguous if-else statement

Question

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

Answer 1

If you insist that the alternatives in a conditional statement be blocks, then the dangling-else ambiguity vanishes.

The dangling else ambiguity is something like this, where the else could be attached to either if:

if (a > 3) if (b > 4) do_something else do_something_else

However, if the statements in the conditional must be surrounded by braces, that is a syntax error. You would have to write either:

if (a > 3) { if (b > 4) { do_something } else { do_something_else } }

or

if (a > 3) { if (b > 4) { do_something } } else { do_something_else }

and both of those are quite explicit about which if the else belongs to.

In effect, a braced statement list (or block, as you refer to it in the context of a while statement) is a matched_statement, and you could just add it to the set of possibilities for that non-terminal. But that's only necessary if you want the braces to be optional; if you're going to require them, then you can scrap all that matched- and unmatched- statement stuff, and just use block in your if statement, just as with your while statement.

In any case, the problem is

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

Since matched_statement -> command (rule 20), the RBRACE in rule 21 induces a shift-reduce conflict. Assuming a command has just been reduced, the parser has to decide whether rule 20 should be applied (a reduce), which is necessary if the input is the start of rule 22, or whether the RBRACE should just be shifted, necessary if the input is the start of rule 21. And it can't know that by just looking at the RBRACE, since that is the same in both rules.

However, as I said, it doesn't matter. You don't need two different non-terminals for a block, and just using block will avoid the problem.