[antlr-interest] Re: Nondeterminism problem

[Oliver Zeigermann]

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?

Cheers :)

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/