[antlr-interest] Re: Nondeterminism problem
Oliver Zeigermann
oliver at zeigermann.de
Fri Dec 19 08:49:34 PST 2003
Oliver Zeigermann wrote:
> sarah2geller at yahoo.com wrote:
>
>>--- In antlr-interest at yahoogroups.com, Terence Parr <parrt at c...>
>>wrote:
>>
>>
>>>On Monday, December 15, 2003, at 01:31 AM, Oliver Zeigermann wrote:
>>>
>>>
>>>>I guess this is a misunderstanding, Sarah does not claim LALL(k)
>>
>>is a
>>
>>
>>>>subset of SLL(k), but SLK's algorithm is the only that does
>>
>>practical
>>
>>
>>>>SLL(k) near computation. ANTLR does approximate LALL(k), so SLK
>>
>>subset
>>
>>
>>>>ANTLR is not true.
>>>
>>>Hi Oliver,
>>>
>>>Actually "Sarah" does indeed claim SLK is more powerful than any
>>
>>other
>>
>>
>>>LL(k) subset:
>>>
>>>"All other practical LL(k) analysis algorithms work on language
>>>classes that are proper subsets of the strong LL(k) languages. "
>>>
>>>I think you'll find that LALL(k) done by PCCTS is a proper
>>
>>*superset*.
>>
>>
>>>I don't understand "only one that does practical SLL(k) near
>>>computation". Can you rephrase? Again, PCCTS does full LALL(k);
>>
>>my
>>
>>
>>>dissertation was how approximate lookahead can be used to attenuate
>>
>>the
>>
>>
>>>complexity of computation and storage of lookahead. This includes
>>>weaker parser as well as helping to build full LALL(k) parsers.
>>>
>>>Let's see if I can come up with an example that PCCTS will accept,
>>
>>but
>>
>>
>>>is not SLL(k). Ok, this grammar is LALL(1) and even approximate
>>>LALL(1), meaning even ANTLR 2 will handle it no sweat. A Strong LL
>>
>>(k)
>>
>>
>>>analysis should find a nondeterminism upon A in rule s's subrule
>>
>>for
>>
>>
>>>ANY value of k. The problem is in the accuracy of lookahead not
>>
>>the
>>
>>
>>>depth.
>>>
>>>s : Z (a | ) B ;
>>>
>>>a : A;
>>>
>>>t : X a A ;
>>>
>>
>>
>>This incomplete grammar is LL(1). If you add a production like
>>
>>s : t;
>>
>>it is still LL(1).
>>
>
>
> This grammar is not incomplete, is it? Anyway, this grammar actually is
> LL(1), but this is not the point, the point is it is LALR', but not SLL
> which shows LALR' grammars are not a subset of SLL grammars. As this
> seemed to be the intention of the initial claim, it is wrong, isn't it?
Sorry, of course I wanted to say LALL instead of LALR :(
Oliver
Yahoo! Groups Links
To visit your group on the web, go to:
http://groups.yahoo.com/group/antlr-interest/
To unsubscribe from this group, send an email to:
antlr-interest-unsubscribe at yahoogroups.com
Your use of Yahoo! Groups is subject to:
http://docs.yahoo.com/info/terms/
More information about the antlr-interest
mailing list