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

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 backtra开发者_JAVA百科ck=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?

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).

You don't have a parser rule (parser rules start with a lower case letter), although I'm not sure that last part is necessary when interpreting some test cases in ANTLRWorks.

Anyway, try something like this:

grammar AdifyMapReducePredicate;

parse
  :  (p=predicate {System.out.println("parsed :: "+$p.text);})+ EOF
  ;

predicate 
  :  expression
  ;

expression
  :  booleanExpression
  ;

booleanExpression
  :  atom ((AND | OR) atom)*
  ;

atom
  :  ID
  |  '(' predicate ')'
  ;

AND
  :  '&&'
  ;

OR
  :  '||'
  ;

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

SPACE
  :  (' ' | '\t' | '\r' | '\n') {skip();}
  ;

With the following test class:

import org.antlr.runtime.*;
import org.antlr.runtime.tree.*;
import org.antlr.stringtemplate.*;

public class Main {
    public static void main(String[] args) throws Exception {
        ANTLRStringStream in = new ANTLRStringStream("(A || B) (C && (D || F || G))");
        AdifyMapReducePredicateLexer lexer = new AdifyMapReducePredicateLexer(in);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        AdifyMapReducePredicateParser parser = new AdifyMapReducePredicateParser(tokens);
        parser.parse();
    }
}

which after generating a lexer & parser (a), compiling all .java files (b) and running the test class (c), produces the following output:

parsed :: (A||B)
parsed :: (C&&(D||F||G))

a

java -cp antlr-3.2.jar org.antlr.Tool AdifyMapReducePredicate.g 

b

javac -cp antlr-3.2.jar *.java

c (*nix/MacOS)

java -cp .:antlr-3.2.jar Main

c (Windows)

java -cp .;antlr-3.2.jar Main

HTH