How to fix recursive rule invocation in Antlr3?

Question

I have the following XText grammar which uses ANTLR3 under the hood. In my grammar I want to support cast expressions like TYPE(EXPRESSION) and (TYPE)(EXPRESSION). A Type definition usually contains other types (I think that is the problem but I cannot change this requirement). Besides that I also want to allow parenthesis around expressions.

Is it possible to solve the recursion by left-factoring? I always get the following error message.

[fatal] rule ruleExpression has non-LL(*) decision due to recursive rule invocations reachable from alts 1,2. Resolve by left-factoring or using syntactic predicates or using backtrack=true option.

Model:
    e=Expression;

Expression:
    e=castExpression | e=parExpression | "VAR";

castExpression:
    (Type | '(' Type ')') e=parExpression;

parExpression:
    '(' Expression ')';

Type:
    "MYTYPE" t=Type | "TYPE_ID";

@LucasTrzesniewski it's XText, which uses ANTLR3 under the hood — Bart Kiers

Sven Efftinge Sven Efftinge · Accepted Answer · 2016-04-01T06:32:58

The simplest but not neccessarily the best way to make it work is to put in a syntactic predicate (=>) on the whole castExpression like this:

Expression:
   =>e=castExpression | e=parExpression | "VAR";

But it seems like this is a very reduced excerpt of the actual grammar, so I cannot say if it is a viable solution in the full context. Also note that putting in such a long lookahead can have a bad effect on tooling aspects and performance. And you should be sure to understand the implications of syntactic predicates before adding more of them.

How to fix recursive rule invocation in Antlr3?

1 Answers