[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