[antlr-interest] error(211) in grammars with recursion

Chris Lambrou chris at lambrou.net
Sun Aug 12 19:25:58 PDT 2007


Hi,

I'm trying to create a parser for Java-like expressions, and have started
using the Java.g file presented on the ANTLR web site (
http://www.antlr.org/grammar/1152141644268/Java.g) as a base to work from.
I've been running into error(211) and I'm not sure what the problem is. The
full error text is:

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

I've managed to duplicate the error in a much simpler grammar, shown below.
The grammar is for simple arithmetic rules that only involve numbers, the
plus and minus operators, and parentheses, e.g.  (5 + 9) - (3 + (4 - 1)) -
the key rules that relate to the problem are Expression, UnaryExpression and
ParenthesisedExpression. The error message suggests three approaches to
solving the problem: left-factoring, use of syntactic predicates or use of
the backtrack option. The backtrack option doesn't help (backtrack=true is
already specified), I don't see how left-factoring will help, and I don't
yet understand syntactic predicates, or how they might apply to the problem.

Having searched the mailing list archives, the only relevant comment seems
to be from Gavin Lambert (
http://groups.google.com/group/il-antlr-interest/browse_thread/thread/490707b7757767f3/34a5244b839c5deb?lnk=gst&q=decision+due+to+recursive+rule+invocations+reachable&rnum=3#34a5244b839c5deb)
who explains that the problem is that the grammar is left-recursive. I'm
afraid I don't quite understand the problem, and would appreciate an
explanation and an indication of how the Simple grammar can be modified to
resolve the error.

Chris



grammar Simple;
options {
    k = 2;
    backtrack = true;
    memoize = true;
}

Expression
    : UnaryExpression (Operator UnaryExpression)*
    ;

UnaryExpression
    : Number
    | ParenthesisedExpression  // This is the line that introduces recursion
into the grammar.
    ;

ParenthesisedExpression
    : '(' Expression ')'
    ;

Operator
    : '+' | '-'
    ;

Number
    : ('0'..'9')+
    ;

Whitespace
    : (' ' | '\r' | '\t' | '\f' | '\n')+  {$channel=HIDDEN;}
    ;
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20070813/fc8c0880/attachment.html 


More information about the antlr-interest mailing list