[antlr-interest] Can someone please explain

[mzukowski at yci.com]

The problem is with linear approximate lookahead, I think.  For

A (B)? C D E 

You would think you would get two possibilites:
LA: 1 2 3 4 5
    A B C D E
or  A C D E

So the you would think the test would be (if (LA(1)==A and LA(2)==B and ...)
or (LA(1)=A and LA(2)=C and...).  That would be strict LL, I think.  But
LALL does this:

if (LA(1)==A and (LA(2)==B or LA(2)==C) and (LA(3)==C or LA(3)==D) and ...)

So let's look at the two alternatives:

A (B)? C D E 
LA: 1 2 3 4 5
    A B C D E
or  A C D E

A (B)? C D F
LA: 1 2 3 4 5
    A B C D F
or  A C D F

Now, the empty endings (when B is not there) imply EOF.  So let's look at
what antlr does.

java antlr.Tool test20.g
ANTLR Parser Generator   Version 2.7.2a2 (20020112-1)   1989-2002 jGuru.com
test20.g:4: warning: nondeterminism upon
test20.g:4: 	k==1:A
test20.g:4: 	k==2:B,C
test20.g:4: 	k==3:C,D
test20.g:4: 	k==4:D
test20.g:4: 	k==5:EOF
test20.g:4: 	between alts 1 and 2 of block

See how the or'ing is confusing antlr?  The test for alt 1 is:
if ((LA(1)==A) && (LA(2)==B||LA(2)==C) && (LA(3)==C||LA(3)==D) &&
(LA(4)==D||LA(4)==E) && (LA(5)==EOF||LA(5)==E))

The test for alt 2 is:
if ((LA(1)==A) && (LA(2)==B||LA(2)==C) && (LA(3)==C||LA(3)==D) &&
(LA(4)==D||LA(4)==F) && (LA(5)==EOF||LA(5)==F))

Can you see how this is ambiguous for antlr?  It is intersecting those two
tests and seeing a path through them that is ambigous, though in reality it
is not possible.  This is the drawback of LALL.  Most of the time it works
correctly and is significantly faster.  In fact it will work in this case,
it just mistakenly gives a warning.  The future holds the promise of full LL
and the possibility of antlr automatically recognizing when an ambiguity is
due to LALL and dropping back to LL.

There is also a FAQ on jGuru.com about this somewhere.

Generated source is your friend!

Monty


> -----Original Message-----
> From: Silvain Piree [mailto:s.piree at enneya.com]
> Sent: Friday, June 21, 2002 7:47 AM
> To: antlr-interest at yahoogroups.com
> Subject: Re: [antlr-interest] Can someone please explain
> 
> 
> But B is not a non-terminal .... it's a terminal (a token).
> Silvain
> 
> > The definition you have produced is for Follow set.
> >
> > First(B) ( assuming B is Nonterminal)  is the first tokn of 
> all the string
> > which can be derived from B.
> > >
> > > do I understand correctly that First(B) means the tokens
> > > that can follow B?
> > >
> > > The grammar rule I mentioned is the full grammar!
> > >
> > >     rule:    A (B)? C D E       |     A (B)? C D F   ;
> > >     First(B) = 'C'
> > >     First(C) = 'D'
> > >     Intersection = null
> > >
> > > Silvain
> > >
> > > >  It might be the case in ur grammar that intersection of
> > > > First(B) and First(C) is not null.
> > > >
> > > > > I understand the solution, but I don't understand the problem!
> > > > >
> > > > > Why is making a token optional in both subrules producing
> > > > > a conflict that can not be resolved with regular lookahead?
> > > > >
> > > > > Silvain
> > > > >
> > > > > >  Use syntactic predicate like this
> > > > > >
> > > > > >  (A(B)?)=>A(B)?
> > > > > >
> > > > > > It will remove the warnings but I'm not sure about run time
> > > > > > behaviour... and not sure if you add some new production,
> > > > > > whether i will work or not.
> > > > > >
> > > > > > > I'm getting nondeterminism warnings on my grammar but
> > > > > > > I don't understand why.
> > > > > > >
> > > > > > > Following rule does not cause a problem when using k=5:
> > > > > > >
> > > > > > > rule:    A B C D E       |     A B C D F   ;
> > > > > > >
> > > > > > > But, when I make the B optional then I get a 
> nondeterminism
> > > > > > > warning regardless of lookahead 'k':
> > > > > > >
> > > > > > > rule:    A (B)? C D E       |     A (B)? C D F   ;
> > > > > > >
> > > > > > > Any suggestions would be much appreciated,
> > > > > > >
> > > > > > > Silvain
> > > > >
> > > > >
> > > > >
> > > > >
> > > > >
> > > > >
> > > > > Your use of Yahoo! Groups is subject to
> > > http://docs.yahoo.com/info/terms/
> > > > >
> > > > >
> > > > >
> > > >
> > > >
> > > >
> > > > Your use of Yahoo! Groups is subject to
> > http://docs.yahoo.com/info/terms/
> > > >
> > > >
> > >
> > >
> > >
> > >
> > >
> > > Your use of Yahoo! Groups is subject to
> http://docs.yahoo.com/info/terms/
> > >
> >
> >
> >
> > Your use of Yahoo! Groups is subject to 
http://docs.yahoo.com/info/terms/
>
>



 

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


 

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