[antlr-interest] Listing order of NT alternatives on rhs of production appears to affect "accept/reject" of parser for fixed input.
John B. Brodie
jbb at acm.org
Tue Nov 11 14:59:50 PST 2008
Dejas Ninethousand wrote:
> Hello,
Greetings!
> I believe I have found a peculiar issue in ANTLR. If memory serves, the
> order of alternatives in a grammar should have no effect on the set of
> inputs it accepts. For example I believe:
>
> program : statement_list | expression
>
> is equivalent to:
>
> program : expression | statement_list
>
>....remainder of original message snipped...
Apparently, when backtracking is enabled this is not the case.
Quoting from page 107 of the book "The Definitive ANTLR Reference" by Terence
Parr regarding the backtrack Option, Section 5.3:
"The backtrack option informs ANTLR that, should LL(*) analysis fail, it
should try the alternatives within the decision in the order specified at
parse time, choosing the first alternative that matches."
So when backtracking is enabled, as is the case in your posted problematic
grammar, order does make a difference.
(Hopefully one of the ANTLR maintainers will confirm and/or deny this because
my experience with backtracking is almost non-existant. I work very hard to
ensure that my gramars do not need to backtrack. And IMHO you should too:)
Hope this helps...
-jbb
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20081111/863884a5/attachment.html
More information about the antlr-interest
mailing list