Parsing shift-reduce conflict

Question

I am using JavaCUP tool in order to produce a parser for my language. I am trying to write a grammar that matches nested and multiple if_else statements.

Input file

// matches 
if () 
    if ()

    else

    if ()

    else
else

// no match -> modifying grammar leads to shift/reduce conflict
if ()

else

Grammar

expr ::=  if_then_else_statement;

if_then_else_statement ::= IF LPAREN RPAREN if_then_else_statement ELSE if_then_else_statement
                        | ;

This grammar matches nested if_else statements. However it only recognizes the first nested if_else statement of my input file.

I modified my grammar in order to match multiple statements like this:

expr ::=  expr if_then_else_statement;
      | ;

if_then_else_statement ::= IF LPAREN RPAREN if_then_else_statement ELSE if_then_else_statement
                        | ;

The result was a shift/reduce conflict caused by the empty rule (I guess). How can I modify it to support both nested and multiple if_else statements without the use of precedence?

Yes, after modifying it, expr could reduce to expr if_then_else_statement which could reduce to expr if_then_else_statement if_then_else_statement and finally to if_then_else_statement if_then_else_statement. But this works only in theory — pirox22

rici rici · Accepted Answer · 2016-03-14T17:34:04

The usual solution would be something like this:

expr_list ::= | expr_list expr ;
expr ::= if_then_else_statement ;
if_then_else_statement ::= IF LPAREN RPAREN expr ELSE expr ;

That doesn't allow empty else clauses (or empty then clauses) because an empty else clause is ambiguous: there is no way to tell whether the s2 in if () s1 else s2 is the else clause or a statement which follows a complete if statement with an empty else clause.

To resolve that ambiguity, you need statement terminators (eg. semicolon) or if statement terminators (fi and end are common choices) or something else.

Parsing shift-reduce conflict

1 Answers