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

[Thiago F.G. Albuquerque]

At 13:14 18/05/03 -0700, you wrote:
>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

Ok, thank you for your answer. But how can I fix this? Is there a 
workaround? I need to write my parser. This example I sent is a 
simplification of a larger grammar I am working on (a project for school). 
Here's an excerpt of the original grammar:

exp : func_call
       | (variable "=") => assignment
       | logical_exp
       ;

logical_exp : rel_exp (("||" | "&&" | "!") rel_exp)*
             ;

rel_exp : add_exp (rel_op add_exp)*
         ;

rel_op : "<" | "<=" | ">" | ">=" | "==" | "!="
        ;

add_exp : mul_exp (( "+" | "-") mul_exp)*
         ;

mul_exp : atom (( "*" | "/" | "%" ) atom)*
         ;

atom : const
      | variable
      | "(" exp ")"
      ;

In this grammar I cannot colapse 'exp' and 'atom' into one rule.

What should I do?

TIA,
Thiago

>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/