CODEWITHSUNDEEP
antlr4left-recursion
Theodoros Chatzigiannakis
Theodoros Chatzigiannakis

Reputation: 29213

Why is this left-recursive and how do I fix it?

I'm learning ANTLR4 and I'm confused at one point. For a Java-like language, I'm trying to add rules for constructs like member chaining, something like that:

expr1.MethodCall(expr2).MethodCall(expr3);

I'm getting an error, saying that two of my rules are mutually left-recursive:

expression
    : literal
    | variableReference
    | LPAREN expression RPAREN
    | statementExpression
    | memberAccess
    ;

memberAccess: expression DOT (methodCall | fieldReference);

I thought I understood why the above rule combination is considered left-recursive: because memberAccess is a candidate of expression and memberAccess starts with an expression.

However, my understanding broke down when I saw (by looking at the Java example) that if I just move the contents of memberAccess to expression, I got no errors from ANTLR4 (even though it still doesn't parse what I want, seems to fall into a loop):

expression
    : literal
    | variableReference
    | LPAREN expression RPAREN
    | statementExpression
    | expression DOT (methodCall | fieldReference)
    ;
  1. Why is the first example left-recursive but the second isn't?
  2. And what do I have to do to actually parse the initial line?

Upvotes: 0

Views: 159

Answers (2)

Theodoros Chatzigiannakis
Theodoros Chatzigiannakis

Reputation: 29213

For some reason, ANTLRWorks 2 was not responding when my grammar had left-recursion, causing me to (erroneously) believe that my grammar was wrong.

Compiling and testing from commandline revealed that the version with immediate left-recursion did, in fact, compile and parse correctly.

(I'm leaving this here in case anyone else is confused by the behavior of the IDE.)

Upvotes: 0

CoronA
CoronA

Reputation: 8075

The second is left-recursive but not mutually left recursive. ANTLR4 can eliminate left-recursive rules with an inbuilt algorithm. It cannot eliminate mutually left recursive rules. There probably exists an algorithm, but this would hardly preserve actions and semantic predicates.

Upvotes: 1

Related Questions