Thursday, March 8, 2012

[Tip] Avoiding Shift/Reduce conflict

consider following grammar for C-minus;

selection_stmt      ::= IF '(' expression ')'  statement
                        | IF '(' expression ')' statement ELSE statement ;

This is a "Dangling else" problem that leads to Shift/Reduce conflict when generating a parser ( I am using CUP ).

Warning : *** Shift/Reduce conflict found in state #72
  between selection_stmt ::= IF '(' expression ')' statement (*) 
  and     selection_stmt ::= IF '(' expression ')' statement (*) ELSE statement 
  under symbol ELSE
  Resolved in favor of shifting.

you can solve this problem by two ways. ( or you can re-define the if-else grammar rule with unambiguous if-else rules. I am working on it, hope to update this post after it)

1) adding precedence ELSE:

eg: modify code as given bellow.

precedence left  PLUS, MINUS;
precedence left  TIMES, DIVIDE;
precedence left  ELSE;

2) Allow to resolve in favor of shifting:

you can generate parser code expecting 1(or more) shift/reduce conflict.

eg: add "-expect 1" option to tell expect one shift/reduce conflict.

cup -expect 1 -parser CMinusParser cminus.cup