0
$\begingroup$

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
$\endgroup$
  • 1
    $\begingroup$ If your question has to do with the shift-reduce conflict, it would be better to present that grammar rather rhan the one which "works". $\endgroup$ – rici Apr 17 '18 at 0:31
  • $\begingroup$ I make an edit which shows where it is giving me troubles. $\endgroup$ – Felipe Apr 17 '18 at 0:48
  • 1
    $\begingroup$ There is no question here. $\endgroup$ – Raphael Apr 17 '18 at 5:16
  • $\begingroup$ Please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. $\endgroup$ – Raphael Apr 17 '18 at 5:16
  • 1
    $\begingroup$ Please reduce your issue to an MWE, it's infeasible for readers here to digest the whole grammar. $\endgroup$ – Raphael Apr 17 '18 at 5:17
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Adding block as a set of possibilitions to matched statement obligates the function_definition production to have a block inside a block when there is not an if on it. To make such change I'd have to change the funciton_definition too to function_definition : DEFINE data_type ID LPAREN function_definition_args RPAREN statements. Even though it would allow a funciton without braces. $\endgroup$ – Felipe Apr 17 '18 at 14:08
  • $\begingroup$ @felipe: that's not correct. Making block an alternative of statement does not change the definition of block and does not require you to change the definition of function_definition. A block is still a sequence of statements surrounded by a pair of braces. It allows blocks to be nested, but it certainly doesn't require them to be. If you want to ban nested blocks for some reason, that's easy. $\endgroup$ – rici Apr 17 '18 at 15:06
  • $\begingroup$ I didn't get what need to be changed. However it could either nested/non nested sorounded/ no surrounded by braces. $\endgroup$ – Felipe Apr 17 '18 at 16:39
  • $\begingroup$ @felipe: your question would be easier to answer if tou asked a direct question with a clear statement of what you are looking for, ehat you gave tried, and why it didn't do what you expected. Having said that, let me add that you cannot assemble grammars (or computer programs) by assembling different fragments from different sources. $\endgroup$ – rici Apr 17 '18 at 16:46
  • $\begingroup$ I did the following: matched_statement -> IF LPAREN logical_expression RPAREN matched_statement ELSE matched_statement matched_statement -> command matched_statement -> block''' unmatched_statement -> IF LPAREN logical_expression RPAREN matched_statement unmatched_statement -> IF LPAREN logical_expression RPAREN matched_statement ELSE unmatched_statement $\endgroup$ – Felipe Apr 17 '18 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.