[antlr-interest] Nondeterminism between alts 1 and 2 of block...

[Terence Parr]

Hi.  You've correctly analyzed this as a Human. :)  Unfortunately, for  
the moment, ANTLR generates linear approximate k=2 lookahead not the  
real thing (which has sequence information).  This is a weakness of the  
parsing strategy not your understanding of LL(k).  Sorry.

I'm actually working on the analysis stuff at the moment (full LL(k)  
and semantic predicate hoisting). :)

Ter

On Sunday, May 18, 2003, at 09:31  AM, Thiago F.G. Albuquerque wrote:

> Hi, everybody,
>
> I am facing a problem with a grammar. I was wondering if you could  
> help me.
>
> Here it is:
>
> class MyParser extends Parser;
>
> options
> {
>     k = 2;
> }
>
> //  
> ----------------------------------------------------------------------- 
> ----
>
> exp : func_call         // <-- this is line 185 (the line of the error)
>      | atom
>      ;
>
> func_call : ID "(" (exp ("," exp)*)? ")"
>            ;
>
> atom : variable
>       | "(" exp ")"
>       ;
>
> //  
> ----------------------------------------------------------------------- 
> ----
>
> variable : ID                  // atomic variable
>           | ID ("[" exp "]")+   // array
>           | ID "." variable     // struct
>           ;
>
> //  
> ----------------------------------------------------------------------- 
> -----
>
> Error:
>
> ANTLR Parser Generator   Version 2.7.2   1989-2003 jGuru.com
> test.g:185: warning:nondeterminism between alts 1 and 2 of block upon
> test.g:185:     k==1:ID
> test.g:185:     k==2:"("
>
> I don't understand how can there be nondeterminism here. func_call  
> really
> begins with
>
> ID "("
>
> but it is not possible to generate this sequence of tokens from atom.
>
> Also, I noticed that if I colapse the rules exp and atom into one rule,
> like this:
>
> exp : func_call         // <-- this is line 185 (the line of the error)
>        | variable
>        | "(" exp ")"
>        ;
>
> the problem disapears.
>
> I am puzzled.
>
> Can anybody please explain this to me?
>
> TIA,
> Thiago
>
>
>
>
> Your use of Yahoo! Groups is subject to  
> http://docs.yahoo.com/info/terms/
>
>
>
--
Co-founder, http://www.jguru.com
Creator, ANTLR Parser Generator: http://www.antlr.org
Co-founder, http://www.peerscope.com link sharing, pure-n-simple
Lecturer in Comp. Sci., University of San Francisco


 

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