If-Else Ambiguity

A shift-reduce conflict that frequently occurs involves the if-else construct. Assume we have the following rules:

stmt:
   IF expr stmt
   | IF expr stmt ELSE stmt
   ...

and the following state:

IF expr stmt IF expr stmt . ELSE stmt

We need to decide if we should shift the ELSE or reduce the IF expr stmt at the top of the stack. If we shift then we have

IF expr stmt IF expr stmt . ELSE stmt
IF expr stmt IF expr stmt ELSE . stmt
IF expr stmt IF expr stmt ELSE stmt .
IF expr stmt stmt .

where the second ELSE is paired with the second IF. If we reduce we have

IF expr stmt IF expr stmt . ELSE stmt
IF expr stmt stmt . ELSE stmt
IF expr stmt . ELSE stmt
IF expr stmt ELSE . stmt
IF expr stmt ELSE stmt .

where the second ELSE is paired with the first IF. Modern programming languages pair an ELSE with the most recent unpaired IF. Consequently the former behavior is expected. This works well with yacc because the default behavior, when a shift-reduce conflict is encountered, is to shift.

Although yacc does the right thing it also issues a shift-reduce warning message. To remove the message give IF-ELSE a higher precedence than the simple IF statement:

%nonassoc IFX
%nonassoc ELSE

   stmt: 
       IF expr stmt %prec IFX
       | IF expr stmt ELSE stmt