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

2
votes

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.

  • I don't have operator precedence, I always use parenthesis
  • I don't want to combine two types of expressions
  • If anyone interested, this works correctly with ANTLR4
1
javaantlrgrammarantlr3left-recursion
Is there a particular reason you're using ANTLR3? ANTLR4 probably accepts this grammar without any problem. - Bart Kiers
@Bart Kiers Yes. Later I need this in C++. And I think ANTLR4 is not supporting C++ targets. Isn't it ? - Morpheus
Btw, I have checked with antlr4 and it accepts this grammar and parses it correctly. And I have updated the answer with it - Morpheus
Why the redundant parentheses? - user207421
@EJP The language syntax is not defined by me. So I have to use those. - Morpheus

1 Answers

1
votes

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;
}