Shift/reduce conflict in java cup - dangling else issue

Question

I am getting the following error:

Warning : *** Shift/Reduce conflict found in state #116
between Statement ::= Matched (*) 
and     Unmatched ::= IF LPAREN Condition RPAREN Matched (*) ELSE Unmatched 
and     Matched ::= IF LPAREN Condition RPAREN Matched (*) ELSE Matched 
under symbol ELSE
Resolved in favor of shifting.

Now, i am aware of the dangling else problem, and i have tried making the grammar unambiguous:

Statement ::= Matched | Unmatched ;


Matched ::= IF LPAREN Condition RPAREN Matched ELSE Matched
            |
            Others
             ;

Unmatched ::= IF  LPAREN Condition RPAREN Statement 
              | 
              IF  LPAREN Condition RPAREN Matched ELSE Unmatched
              ;

Is there any way to resolve this problem without the precedence operator, or is there something else wrong with the grammar?

Answer 1

There is nothing wrong with the grammar presented in the question, so my guess is that the shift/reduce conflict is the result of an interaction with another production.

The idea of splitting statements into Matched and Unmatched:

Statement ::= Matched | Unmatched ;

is precisely to ensure that an else is correctly matched with the nearest unmatched if. A Matched statement cannot be extended with an else clause; an Unmatched statement could have been. So we require that else tokens in the grammar cannot follow Unmatched statements, thus avoiding prematurely reducing a statement which might have been extended with an else clause.

So inside the If statement, the else can only follow a Matched statement. The statement itself is Unmatched if it doesn't have an else clause, or if the else clause itself is Unmatched. Thus, we have three productions:

Unmatched_If ::= IF LPAREN Condition RPAREN Statement
               | IF LPAREN Condition RPAREN Matched ELSE Unmatched ;
Matched_If   ::= IF LPAREN Condition RPAREN Matched ELSE Matched ;

But this isn't the whole story, because there are other possible compound statements. Consider, for example, a while statement. If the language has such a construct, the grammar probably includes something like this:

While        ::= WHILE LPAREN Condition RPAREN Statement ; /* Wrong! */

That won't work, because a while statement can also be Unmatched, in precisely the same way that an if...else statement can be: if the interior Statement is Unmatched.

For example, consider

while (x) if (y) do_x_and_y;

With the incorrect While production above, that would be reduced as follows:

   WHILE LPAREN Condition RPAREN Unmatched_If
-> WHILE LPAREN Condition RPAREN Statement
-> Matched

But that violates the requirement that Unmatched cannot be followed by else. Matched can be followed by else, but in this case the Matched ends with Unmatched_If. And consequently, we have a shift/reduce conflict:

if (w)
  while (x) if (y) do_this;
else do_that;

This could be parsed as

IF ( Condition:[w] ) Matched:[while(x)if(y)do_this;] ELSE Statement:[do_that;]

But that is not actually the intended parse. (The indentation might lead us to think that it was the programmer's intent, but it is not the intent of the language designer.) The else should match the second if, not the first one, leading to:

if (w)
  while (x)
    if (y) do_this; else do_that;

So we need to distinguish between matched and unmatched While statements, not just matched and unmatched If statements:

Unmatched_While ::= WHILE LPAREN Condition RPAREN Unmatched ;
Matched_While   ::= WHILE LPAREN Condition RPAREN Matched ;

With that, while (x) if (y) do_x_and_y; will be parsed as an Unmatched_While, and so it can no longer be part of the productions which start IF LPAREN Condition RPAREN Matched ELSE...

Of course, the same will need to be done for other compound statements, such as for statements.

So the final result will be something like:

Matched   ::= Matched_If
            | Matched_While
            | Matched_For
            | ...
            | Simple_Statement
            ;
Unmatched ::= Unmatched_If
            | Unmatched_While
            | Unmatched_For
            | ...
            ;