Antlr4: The following sets of rules are mutually left-recursive

Question

I am trying to describle simple grammar with AND and OR, but fail with the following error

The following sets of rules are mutually left-recursive

The grammar is following:

expr:
    NAME |
    and |
    or;

and:
    expr AND expr;

or:
    expr OR expr;

NAME : 'A' .. 'B' + ;
OR: 'OR' | '|';
AND: 'AND' | '&';

Simultaneously, the following grammar

expr:
    NAME |
    expr AND expr |
    expr OR expr;

NAME : 'A' .. 'B' + ;
OR: 'OR' | '|';
AND: 'AND' | '&';

does compile.

Why?

Isle

Answer 1

As already mentioned: ANTLR4 only supports direct left recursion. You can label the alternatives to make a distiction in your generated visitor or listener:

expr
 : NAME           #NameExpr
 | expr AND expr  #AndExpr
 | expr OR expr   #OrExpr
 ;

NAME : 'A' .. 'B' + ;
OR   : 'OR' | '|';
AND  : 'AND' | '&';

Note that 'A'..'Z'+ is the old v3 syntax, in v4 you can do this: [A-Z]+

See: https://github.com/antlr/antlr4/blob/master/doc/parser-rules.md#alternative-labels

Ceolaceorl

Answer 2

ANTLR4 supports only direct left recursion (which is already an improvement over previous versions). That means you can have left recursion in a single rule, but not over multiple rules (e.g. rule a uses rule b which uses a as the first rule in an alternative.

Catgut

But I need to have appropriate nodes for each operation like AND and OR in parse tree. How this is possible if one rule will parse all of them? – Isle

You can learn a lot by looking at existing grammars (e.g. github.com/antlr/grammars-v4). You can define your rules so that left recursive parts end up in a single rule or you can do it in a non-recursive way. – Catgut

@MikeLischke It is hard to dig through so many grammar. Can you provide an example on how to solve this using non-recursive way? – Excitability

Answer 3

I know this is after very long time... but your second grammar compiles because you don't have the alternatives rightly parenthised. So

expr: NAME |
    expr AND expr |
    expr OR expr ;

is actually understood by Antlr as:

expr: (NAME | expr) AND (expr | expr) OR expr ;

Following rule actually does not compile:

expr:
    NAME |
    (expr AND expr) |
    (expr OR expr) ;

Discriminant

Yes, in fact any top-level "alternative" of the rule with the left-most symbol modified with +/*/?/() operators will cause Antlr to not refactor the rule to remove recursion. E.g., e: N | (e) AND e | e OR e;, e: N | (e AND e) | e OR e;, e: e? 'a-postfix-op';, e: e* | N; all will be flagged. Antlr (and my own tool that refactors grammars) look for a very specific parse tree of the rule. If it doesn't match exactly the pattern outlined in Aho/Sethi/Ulman p176, the rule will not be refactored, the recursion remains, and the indirect-left recursion check will flag the problem. – Rooster