ANTLR: rule Tokens has non-LL(*) decision due to recursive rule invocations reachable from alts 1,2

Question

grammar AdifyMapReducePredicate;

PREDICATE 
    :   PREDICATE_BRANCH
    |   EXPRESSION
    ;

PREDICATE_BRANCH
    :   '(' PREDICATE (('&&' PREDICATE)+ | ('||' PREDICATE)+) ')'
    ;

EXPRESSION 
    :   ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'0'..'9'|'_')*
    ;

Trying to interpret this in ANTLRWorks 1.4 and getting the following error:

[12:18:21] error(211): <notsaved>:1:8: [fatal] rule Tokens 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.
[12:18:21] Interpreting...

When I interepret, I'm trying to interpret a PREDICATE and my test case is (A||B)

What am I missing?

Answer 1

By ANTLR's conventions, parser rule names start with a lower case letter, while lexer rules start with capital letters. So the grammar, as you wrote it, has three lexer rules, defining tokens. This may not be what you want.

The reason for the error message apparently is the ambiguity between these tokens: your input pattern matches the definitions of both PREDICATE and PREDICATE_BRANCH.

Just use names starting in lower case letters instead of PREDICATE and PREDICATE_BRANCH. You may also have to add an extra rule for the target symbol, that is not directly involved in the recursion.

By the way, this grammar is recursive, but not left-recursive, and when using parser rules, it definitely is LL(1).