[antlr-interest] Re: Nondeterminism problem

[Oliver Zeigermann]

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/