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?

score 5 · Accepted Answer · answered Jul 15 '10 at 20:24

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

A nice explanation can be found in this post: http://stackoverflow.com/questions/2842809/lexers-vs-parsers — Gunther, Jul 20 '10 at 08:11

Bart Kiers · Answer 2 · 2010-07-15T20:46:02.643

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

Wow, very complete. I'll try this out, but while I integrate it, could you explain what "left-recursive" actually means and how to identify that something is left-recursive? — Hounshell, Jul 14 '10 at 20:44
@Hounshell, @Gunther is right: it's *not* left recursive since your token PREDICATE_BRANCH matches a `(` before it matches a PREDICATE. Sorry for the confusion! — Bart Kiers, Jul 15 '10 at 20:51

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

2 Answers2

a

b

c (*nix/MacOS)

c (Windows)