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?
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.