CODEWITHSUNDEEP
recursionantlr4
Dims
Dims

Reputation: 51239

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

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?

Upvotes: 7

Views: 14573

Answers (3)

Aventerra
Aventerra

Reputation: 11

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

Upvotes: 0

Bart Kiers
Bart Kiers

Reputation: 170298

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

Upvotes: 10

Mike Lischke
Mike Lischke

Reputation: 53532

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.

Upvotes: 4

Related Questions