if-statementgrammarambiguous-grammarcup

If then else ambiguity in CUP


I am constructing a grammar in CUP, and I have ran into a roadblock on defining IF-THEN-ELSE statements.

My code looked like this:

start with statements;

/* Top level statements */
statements ::= statement | statement SEPARATOR statements ;
statement  ::= if_statement | block | while_statement | declaration | assignment ;
block        ::= START_BLOCK statements END_BLOCK ;

/* Control statements */
if_statement    ::= IF    expression THEN statement
                  | IF    expression THEN statement ELSE statement ;
while_statement ::= WHILE expression THEN statement ;

But the CUP tool complained about the ambiguity in the definition of the if_statement.

I found this article describing how to eliminate the ambiguity without introducing endif tokens.

So I tried adapting their solution:

start with statements;

statements ::= statement | statement SEPARATOR statements ;

statement  ::= IF expression THEN statement
             | IF expression THEN then_statement ELSE statement 
             | non_if_statement ;

then_statement ::= IF expression THEN then_statement ELSE then_statement
                 | non_if_statement ; 

// The statement vs then_statement is for disambiguation purposes
// Solution taken from http://goldparser.org/doc/grammars/example-if-then-else.htm

non_if_statement ::= START_BLOCK statements END_BLOCK  // code block
                   | WHILE expression statement        // while statement
                   | declaration | assignment ;

Sadly CUP is complaining as follows:

Warning : *** Reduce/Reduce conflict found in state #57
  between statement ::= non_if_statement (*) 
  and     then_statement ::= non_if_statement (*) 
  under symbols: {ELSE}
  Resolved in favor of the first production. 

Why is this not working? How do I fix it?


Solution

  • The problem here is the interaction between if statements and while statements, which you can see if you remove the while statement production from non-if-statement.

    The problem is that the target of a while statement can be an if statement, and that while statement could then be in the then clause of another if statement:

    IF expression THEN WHILE expression IF expression THEN statement ELSE ...
    

    Now we have a slightly different manifestation of the original problem: the else at the end could be part of the nested if or the outer if.

    The solution is to extend the distinction between restricted statements ("then-statements" in the terms of your link) to also include two different kinds of while statements:

    statement  ::= IF expression THEN statement
                 | IF expression THEN then_statement ELSE statement 
                 | WHILE expression statement
                 | non_if_statement ;
    
    then_statement ::= IF expression THEN then_statement ELSE then_statement
                     | WHILE expression then_statement
                     | non_if_statement ; 
    
    non_if_statement ::= START_BLOCK statements END_BLOCK
                       | declaration | assignment ;
    

    Of course, if you extend your grammar to include other types of compound statements (such as for loops), you will have to do the same thing for each of them.