How do I remove left recursion in JavaCC?

Question

I am trying to remove left recursion in JavaCC for expr, which should be defined as:

expr ::= statement binary_op statement
| **(** expr **)**
| identifier **(** arg **)**
| statement

This code causes a left recursion in my program:

void expr() : { }
{

    < LPAREN > simpleExpr() < RPAREN >
    | < IDENTIFIER > <LPAREN > arg() < RPAREN >
    | statement()
}

void simpleExpr() : { }
{
    statement() binary_op() statement()
}

statement is defined as:

statement ::= id | - id | number | false | true | expr

void statement() : { }
{
    < ID > | < NOT_OP > < ID >
    | < DIGIT >
    | < TRUE >
    | < FALSE >
    | expr() 
}

The error I get in my program:

Left recursion detected: "expr... --> statement... --> expr..."

How would I fix this?

There is no left-recursion in the code you've shown. If there is left recursion in your grammar, it must be in the statement rule (or mutually between expr and statement). — sepp2k
Hi, there is a left recursion becuase I get an error in my program. I have updated my question to show the error. — webchatowner
I realized you are right, the left recursion is caused by expr and statement. @sepp2k — webchatowner
Where in the spec is it stated that a statement() can be an expr() ? — Erwin Smout
I have updated the question to what a statement is in the spec. @ErwinSmout — webchatowner

Theodore Norvell Theodore Norvell · Accepted Answer · 2018-10-19T14:38:15

According to your grammar, a statement can be an expr and an expr can be a statement. Therefore the languages generated by these two nonterminal are the same. You don't need both nonterminals. I'd suggest removing the definition of statement and changing the definition of expr to this

void expr() : { }
{
      < ID >
    | < NOT_OP > < ID >
    | < DIGIT >
    | < TRUE >
    | < FALSE >
    | < LPAREN > simpleExpr() < RPAREN >
    | < IDENTIFIER > <LPAREN > arg() < RPAREN > 
}

Then either

replace statement with expr everywhere in the remaining grammar (including the definition of simpleExpr)
or add this rule:
```
void statement() : { }
{
    expr()
}
```

How do I remove left recursion in JavaCC?

2 Answers