[antlr-interest] Re: A parser nondeterminism error I just can't get my head around...

[Xue Yong Zhi]

If you see no-sense nondeterminism errors from Antlr, there is great 
chance that you meet "linear approximate lookahead".

First I recommend the following articles:

http://www.antlr.org/doc/glossary.html#Linear_approximate_lookahead
and related entries in antlr's FAQ.
http://seclib.blogspot.com/2005/11/linear-approximate-lookahead.html

As for your grammar, when you add "INT" into rule "a", and since k=2, 
"whatever follows" rule will apply. In other words, FIRST(a) will 
include "INT whatever_token_follows". And at the same time, "linear 
approximate lookahead" will compress the lookahead set, and FIRST(a) 
will contain "IDENT whatever_token_follows" (therefore "IDENT RPAREN" is 
part of it).

In more details:
After rule "a" mathched "IDENT LPAREN", it will try to see if it should 
enter rule "b" (since b is optional).
For LA(1) == IDENT and LA(2) == RPAREN, it can either:
a) match "IDENT" as b, then match "RPAREN" as exit branch
b) try to match entire "IDENT RPAREN" as rule b , then blow up (since b 
does not accept it)!
But at that moment, antlr does not know where to to becuase "linear 
approximate lookahead" make it think "IDENT RPAREN" is valid lookahead 
set for rule a.(IDENT come from the first alt of rule a, RPAREN comes 
from the third alt of rule a-- remember "whatever follows" rule).


James Matthews wrote:

> 
> works fine with k=2, but
> 
>   a : IDENT LPAREN (b)? RPAREN
>       | LPAREN  a  RPAREN
>       | INT;
> 
>   b:  a
>       | IDENT;
> 
> 
> gives me the error on k=2:
> 
> model.g:118:5: warning:nondeterminism between alts 1 and 2 of block upon
> model.g:118:5:     k==1:IDENT
> model.g:118:5:     k==2:RPAREN
> 
> (and will not work for any k)
> 


-- 
Xue Yong Zhi
http://seclib.blogspot.com