CODEWITHSUNDEEP
javaantlrgrammarantlr3left-recursion
Morpheus
Morpheus

Reputation: 1750

Antlr remove left recursion while keeping math-expressions and bool-expressions separately

I'm getting this famous error

rule has non-LL(*) decision due to recursive rule invocations

for following simple grammar. 

expr
    :   INTEGER         
    |   '(' expr '+' expr ')'
    ;

bool_expr
    :   '(' bool_expr 'and' bool_expr ')'
    |   '(' expr '<' expr ')'
    ;

INTEGER
    : '0'..'9'+
    ;
WS  
    : (' ' | '\t' | ('\r')? '\n')+ {$channel = HIDDEN; }
    ;

I already went through following answers which were no help.

  1. This Question : I don't want to combine the mathematical expressions and boolean expression into one, so I don't have to verify it via AST. I'm trying to keep these two expression separately.

  2. This Question The Wikipedia is not helping me to understand this specific situation. And I don't think I can simplify this grammar than this.

  3. This Question Here I think we have a different situation.

I can't understand what is the left recursion here. I don't see any A-->Ab|b or something like that. Can anyone please help me to solve this.

Please note following.

Upvotes: 2

Views: 442

Answers (1)

Zakaria Jaiathe
Zakaria Jaiathe

Reputation: 70

The problem is that you have '(' at the begining of the two alts in bool_expr.

A-->'('AB|'('B is contains also a problem of recursivity. @see the generated parser.

The solution is to add the backtracking option to your grammar:

options {
backtrack=true;
}

Upvotes: 1

Related Questions