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

Terence Parr parrt at jguru.com
Sun May 18 22:22:30 PDT 2003


For now, I'd use syntactic predicates...

Terence

On Sunday, May 18, 2003, at 02:42  PM, Thiago F.G. Albuquerque wrote:

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




More information about the antlr-interest mailing list