[antlr-interest] Listing order of NT alternatives on rhs of production appears to affect "accept/reject" of parser for fixed input.
Gavin Lambert
antlr at mirality.co.nz
Wed Nov 12 00:44:10 PST 2008
At 09:48 12/11/2008, Dejas Ninethousand wrote:
>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
As far as I am aware, they are indeed different, since ANTLR tests
the alts in order of appearance (which is why you can use semantic
predicates to choose between two otherwise identical
alternatives).
>a : b | c ;
>
>b : f | d ;
>
>c : e ;
>
>d : D_NAME idl=f? D_TARGET a (resOp=RES res=a)? -> D_NAME $idl?
>D_TARGET a $resOp? $res?;
>
>e : b RCHEVRON b;
>
>f : VERBATUM_IDENTIFIER;
Rules a and e share a common left prefix (b), and as rule c is
equivalent to e, you've just introduced an ambiguity -- on
encountering a "b" (and hence either a "d" or an "f", in turn a
D_NAME or a VERBATUM_IDENTIFIER), should ANTLR follow the first or
second alt in a? Lacking any better information, it will try each
in turn (since you've enabled backtracking) -- another reason why
the order matters.
It's best to factor these sorts of things out so you don't have
this kind of ambiguity. And once you've done that you should be
able to get rid of the backtracking as well :)
More information about the antlr-interest
mailing list