[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