[antlr-interest] Listing order of NT alternatives on rhs of production appears to affect "accept/reject" of parser for fixed input.

Dejas Ninethousand dejas9000 at gmail.com
Tue Nov 11 15:53:06 PST 2008


I disagree.  My interpretation of that that quote is that enabling
backtracking can influence *which* production is used to match an input (by
prioritizing them) however it doesn't say that the set of valid inputs that
can match *some* production changes.

My problem it seems is that in one grammar ordering ANTLR is able to find *some
*match for the input while with the other ordering ANTLR decides *no *match
can be found.  I claim that changing the ordering should not affect whether
*some *match can be found by the parser for a fixed input, irrespective of
what that specific match is.  When ANLTR says no match can be found, I point
to the syntax tree shown in my original email and say "what about that
match?"

-- Matt

On Tue, Nov 11, 2008 at 4:59 PM, John B. Brodie <jbb at acm.org> wrote:

>  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
>
>
>
> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> Unsubscribe:
> http://www.antlr.org/mailman/options/antlr-interest/your-email-address
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20081111/5587728d/attachment.html 


More information about the antlr-interest mailing list