[antlr-interest] pls help

[Terence Parr]

On Thursday, December 13, 2001, at 04:14  PM, leonchiver wrote:

> Hi,
>
> I have following stripped down grammar:
>
> class MyParser extends Parser;
>
> options {
>         k = 2;
> }
>
> startRule :
>         rule
>         (OR rule)*;
> rule :
>         S
>         (X startRule Y)*
>         (X Y)?;
>
> ...
> for which I'm getting the warning:
>
> nd.g:12 warning: nondeterminism upon
> nd.g:12:        k==1:X
> nd.g:12:        k==2:S
> nd.g:12:        between alt 1 and exit branch of block
>
> (line 12 is >>>> (X startRule Y)* <<<<)
>
>
> I just can't figure out where the ambiguity comes from. For k = 1 it's 
> clear
> that the subrules (X startRule Y)* and (X Y)? will generate an ambiguity
> but where from comes the warning for k = 2?
>
> I would be very grateful if someone could explain me where my error
> lies.

The answer lies in the diff between approx and full LL(k) lookahead.  S 
can appear in *a* place at k=2 but not necessarily after X directly.  It 
would be OR S as far as I can guess.  X S is the path that chooses to 
enter loop (X startRule Y)*.  XY is the path choosing (X Y)? but must be 
combined with path that ignores (X Y)?.  OR S is the path ignoring (X 
Y)? and looping in the (OR rule)* to have OR followed by FIRST(rule), 
which is S.    Merging lookahead at k=1 and then k=2 you have k=1: 
{OR,X} then k=2:{S,Y}.  So enter loop induced by X S that intersections 
with lookahead for exit.

This is a limitation of the parser not your understanding.  The solution 
is to shuffle your grammar a bit.

Ter
--
Chief Scientist & Co-founder, http://www.jguru.com
Creator, ANTLR Parser Generator: http://www.antlr.org


 

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/