Resolve mutual left recursive grammar

Question

Problem

I'm working on a grammar for the VBA language based on the Microsoft specification using Antlr4. I've tried to stick closely to the grammar specification, but have one mutual left recursion error to resolve due to this. Here is a subset of the full grammar which shows the problem:

lExpression
    :   simpleNameExpression
    |   Me //instanceExpression 5.6.11
    |   memberAccessExpression
    |   indexExpression
    |   dictionaryAccessExpression
    |   withExpression
    ;

memberAccessExpression      :   lExpression '.' unrestrictedName;

indexExpression             :   lExpression '(' argumentList ')';

dictionaryAccessExpression  :   lExpression '!' unrestrictedName;

I could move the sub-expressions into the main lExpression rule to overcome the initial problem but I will cause problems in other rules such as the following:

callStatement               
    :   Call? (simpleNameExpression | memberAccessExpression | indexExpression | withExpression);

Which identifies specific sub-expressions which are permitted in the rule. There are other places where this occurs also, I just chose this one as an example.

Idea 1

Write callStatement like this:

callStatement               
    :   Call? lExpression;

Then find a way to disable lExpression in callStatement from being Me or dictionaryAccessExpression.

Idea 2

Write callStatement like this:

callStatement               
    :   Call? (simpleNameExpression | lExpression '.' unrestrictedName | lExpression '(' argumentList ')' | withExpression);

But I'm not sure that Antlr will like that anyway.

Thoughts

I may be able to use semantic predicates and/or rewrites to improve this but I'm pretty green in this area.

Any thoughts would be much appreciated.

Bart Kiers Bart Kiers · Accepted Answer · 2015-07-12T06:18:24

Could you not just leave memberAccessExpression, indexExpression and dictionaryAccessExpression as they are, so that callStatement can use them, end expand these rules inside lExpression:

lExpression
    :   simpleNameExpression
    |   Me //instanceExpression 5.6.11
    |   lExpression '.' unrestrictedName
    |   lExpression '(' argumentList ')'
    |   lExpression '!' unrestrictedName
    |   withExpression
    ;

memberAccessExpression      :   lExpression '.' unrestrictedName;

indexExpression             :   lExpression '(' argumentList ')';

dictionaryAccessExpression  :   lExpression '!' unrestrictedName;

callStatement
    :   Call? (simpleNameExpression | memberAccessExpression | indexExpression | withExpression)
    ;

[...] Is it possible to use a rewrite rule in lExpression to add the memberAccessExpression etc nodes to the parse tree?

Alas, v4 does not support rewrite rules. However, you can use rule labels so inside your listener or visitor it is clear in which alternative you are:

lExpression
    :   simpleNameExpression               #SimpleNameExpressionAlt
    |   Me                                 #MeExpressionAlt
    |   lExpression '.' unrestrictedName   #MemberAccessExpressionAlt
    |   lExpression '(' argumentList ')'   #IndexExpressionAlt
    |   lExpression '!' unrestrictedName   #DictionaryAccessExpressionAlt
    |   withExpression                     #WithExpressionAlt
    ;

And inside a listener you would then override enterMemberAccessExpressionAlt:

public class YourListener extends YourBaseListener {

  @Override
  public void enterMemberAccessExpressionAlt(YourParser.MemberAccessExpressionAltContext ctx) {
    // ...
  }
}