I got stuck debugging a CUP grammar.
So I have the following grammar in CUP:
/* Integer operators */
precedence left SUM_OP, SUBS_OP;
precedence left PROD_OP, DIV_OP;
/* Boolean operators */
precedence left EQ_OP, LT_OP, GT_OP, LET_OP, GET_OP;
precedence left OR_OP;
precedence left AND_OP;
start with statements;
statements ::= statement:s
| statement:s SEPARATOR
| SEPARATOR // Empty statement
| statement:s SEPARATOR statements:ss
;
statement ::= IF expression:e SEPARATOR statement:s
| IF expression:e statement:s
| IF expression:e SEPARATOR then_statement:then ELSE SEPARATOR statement:els
| IF expression:e then_statement:then ELSE SEPARATOR statement:els
| IF expression:e SEPARATOR then_statement:then ELSE statement:els
| IF expression:e then_statement:then ELSE statement:els
| WHILE expression:e SEPARATOR statement:s
| WHILE expression:e statement:s
| non_if_statement:s
;
then_statement ::= IF expression:e SEPARATOR then_statement:then ELSE SEPARATOR then_statement:els
| IF expression:e then_statement:then ELSE SEPARATOR then_statement:els
| IF expression:e SEPARATOR then_statement:then ELSE then_statement:els
| IF expression:e then_statement:then ELSE then_statement:els
| WHILE expression:e SEPARATOR then_statement:s
| WHILE expression:e then_statement:s
| non_if_statement:s
;
non_if_statement ::= START_BLOCK statements:s END_BLOCK
| declaration:d
| assignment:a
;
// The statement vs then_statement is for disambiguation purposes
// Solution taken from http://goldparser.org/doc/grammars/example-if-then-else.htm
/* Variable manipulation statements */
declaration ::= type:t IDENTIFIER:id
| type:t IDENTIFIER:id ASSIGN_OP expression:rhs
;
assignment ::= variable:lhs ASSIGN_OP expression:rhs
;
/* Variable manipulation auxiliar sintactic elements */
type ::= T_INT
| T_BOOL
| type:t T_ARRAY
;
variable ::= IDENTIFIER:id
| variable:id LBRACKET expression:idx RBRACKET
;
/* Integer or bool expressions */
expression ::= variable:v
| LPAREN expression:e RPAREN
// Int expressions
| INTEGER_LITERAL:c
| expression:op1 SUM_OP expression:op2
| expression:op1 SUBS_OP expression:op2
| expression:op1 PROD_OP expression:op2
| expression:op1 DIV_OP expression:op2
// Bool expressions
| BOOL_LITERAL:c
| expression:op1 OR_OP expression:op2
| expression:op1 AND_OP expression:op2
| NOT_OP expression:op1
| expression:op1 EQ_OP expression:op2
| expression:op1 LT_OP expression:op2
| expression:op1 GT_OP expression:op2
| expression:op1 LET_OP expression:op2
| expression:op1 GET_OP expression:op2
;
The lexer is feeding the following tokens to the CUP analyzer:
int id:i = intLiteral ;
{
if id:i == intLiteral id:i = intLiteral ;
}
while id:i < intLiteral ;
{
id:i = id:i + intLiteral ;
}
if id:i <= intLiteral ;
{
bool id:a ;
bool id:b = boolLiteral ;
}
else ;
{
int id:j = intLiteral ;
}
if id:i >= intLiteral ;
{
id:i = id:i - intLiteral ;
{
id:i = intLiteral + intLiteral ;
}
}
else if id:i > intLiteral id:i = intLiteral ;
else id:i = intLiteral
(Where ; is SEPARATOR and { } deliminate the blocks.
When I run it, I get the following output:
int
id:i
type ::= T_INT
=
intLiteral
;
expression ::= INTEGER_LITERAL
declaration ::= type IDENTIFIER ASSIGN_OP expression
non_if_statement ::= declaration
statement ::= non_if_statement
{
if
id:i
==
variable ::= IDENTIFIER
expression ::= variable
intLiteral
id:i
expression ::= INTEGER_LITERAL
expression ::= expression EQ_OP expression
=
variable ::= IDENTIFIER
intLiteral
;
expression ::= INTEGER_LITERAL
assignment ::= variable ASSIGN_OP expression
non_if_statement ::= assignment
statement ::= non_if_statement
statement ::= IF expression statement
}
statements ::= statement SEPARATOR
while
Error in line 7, column 1 : Syntax error
Error in line 7, column 1 : Couldn't repair and continue parse
(lines with a single word represent a call to the lexer that resulted in the token printed. Lines with a CUP rule represent that rule being matched. Line 7 is the one with the while statement on it.)
It seems like the blocks are the reason for the failure; when I remove all the blocks from what is fed to the grammar everything is parsed as I expect.
However, I fail to see why the blocks are not correctly parsed.
Any ideas on what could be the problem or how to test further?
EDIT: In case you need a detail I might have ommitted to answer, the full code is available in this repo
The way your grammar uses semi-colons is a bit unorthodox. And it's getting you into trouble.
In particular, semi-colons seem to be optional everywhere except between statements. So both of these are OK
while i < 3; i = i + 1; // ex. 1
while i < 3 i = i + 1; // ex. 2
but you cannot write
i = 2 j = 3 // ex. 3
even though that is no more or less ambiguous than ex. 2 above.
The semicolon-less syntaxes look less strange with blocks:
while i < 3; { i = i + 1; } // ex. 4
while i < 3 { i = i + 1; } // ex. 5
{ i = 2 } { j = 3 } // ex. 6 Still illegal
In order to be parsed, example 6 would need to be written with a semi-colon which is, to my eye, ugly and unnecessary:
{ i = 2 } ; { j = 3 } // ex. 7
That's what your parser is complaining about. Even though the statement on lines 2-4 is a brace-enclosed, so there's never any doubt about where it ends, your grammar insists on a semicolon. But the next token is while, not a semicolon, which is a syntax error.