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

[Gavin Lambert]

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 :)