[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