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

Loring Craymer lgcraymer at yahoo.com
Mon Aug 13 00:31:02 PDT 2007


Actually, you are seeing two problems.  The problem
with your Sample grammar is the capitalization of the
first letter of your parser rules:  they are
interpreted as lexer rules, and the recursion occurs
because the generated Token rule introduces ambiguity
between it and the ParExpression rule.  If you just
lowercase the rule names, your Sample grammar should
work.

The problem with the Java.g grammar is that it was
originally a showcase for the backtracking option.  It
was derived from the canonical LR grammar.  You can
either add "backtracking = true;" to your options
section or (better) start with the ANTLR 2 java
grammar as a basis for your expression parser.

--Loring


--- Chris Lambrou <chris at lambrou.net> wrote:

> 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;}
>     ;
> 



       
____________________________________________________________________________________
Yahoo! oneSearch: Finally, mobile search 
that gives answers, not web links. 
http://mobile.yahoo.com/mobileweb/onesearch?refer=1ONXIC


More information about the antlr-interest mailing list