Cannot use any {} statement in a left-recursive alternative

Question

I am using the Java target. I have the following simple grammar:

    grammmar example;

    alpha :
            alpha 'something'
          | 'otherthing' ;

Now I want my parser to print Hello World for something and Hello World for otherthing whenever it enters the rule alpha. So I would like to modify my grammar in the following way:

    grammmar example;

    alpha :
            {System.out.println("Hello World for something");}
            alpha 'something'
          | {System.out.println("Hello World for otherthing");}
            'otherthing' ;

But this results in the parser throwing the error that the rule term is mutually left-recursive. This error comes due to using any {...} statement in the left-recursive alternative.

What other option do I have as this seems like a bug/could be improved in ANTLR4 ?

Answer 1

ANTLR 4 only supports direct left recursion. What you've done here is hidden the left recursion after an action.

The easiest solution would be to implement a listener for your grammar, and add the println statements in your implementation of enterAlpha.

Here is the grammar code without actions:

alpha
  : alpha 'something'
  | 'otherthing'
  ;

Here is the listener method with the action code:

@Override
public void enterAlpha(AlphaContext ctx) {
  if (ctx.alpha() != null) {
    System.out.println("Hello World for something");
  } else {
    System.out.println("Hello World for otherthing");
  }
}

The condition used in that code might look strange, but due to the way the grammar is written there's no other way to determine in code which alternative was taken in alpha. That situation can (and probably should) be resolved in a few ways to improve code clarity. The following tips can be used separately or in combination.

Option 1: Add explicit lexer rules for the something and otherthing keywords.

alpha
  : alpha Something
  | Otherthing
  ;

Something : 'something';
Otherthing : 'otherthing';

By referencing Something and Otherthing in the alpha rule, ANTLR will generate accessor methods in AlphaContext to provide you with direct access to the TerminalNode instances created for the tokens in the parse tree.

@Override
public void enterAlpha(AlphaContext ctx) {
  if (ctx.Something() != null) {
    System.out.println("Hello World for something");
  } else if (ctx.Otherthing() != null) {
    System.out.println("Hello World for otherthing");
  } else {
    assert ctx.exception != null; // only reachable if a parse error occurred
  }
}

Option 2: Label the outer alternatives of the alpha rule.

This will cause ANTLR to generate separate context classes for each of the alternatives, which allows you to implement the listener/visitor functionality separately as well.

alpha
  : alpha 'something'  # mySomething
  | 'otherthing'       # myOtherthing
  ;

The listener might look like this now:

@Override
public void enterMySomething(MySomethingContext ctx) {
  System.out.println("Hello World for something");
}

@Override
public void enterMyOtherthing(MyOtherthingContext ctx) {
  System.out.println("Hello World for otherthing");
}