[antlr-interest] Re: Nondeterminism problem

[Oliver Zeigermann]

For me it boils down to what is the relation of approximate LALL(k) and 
SLL(k)? Certainly not SLL(k) superset approximate LALL(k) and also not 
the other way round. Can someone clarify for me, please?

Thanks :)

Oliver

Terence Parr 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 ;
> 
> The (a | ) subrule in s needs to see the "local FOLLOW" as B not {A,B} 
> which is the "global FOLLOW" seen by a Strong LL(k) analysis.  Here is 
> the correct prediction for the subrule generated by ANTLR 2.7.2:
> 
>                          switch ( LA(1)) {
>                          case A:
>                          {
>                                  a();
>                                  break;
>                          }
>                          case B:
>                          {
>                                  break;
>                          }
> 
> Duplicating rule a will make this LALL(1) grammar SLL(1) and 
> demonstrates part of the reason LL(k) is exponentially complex in terms 
> of just the parser size (not including lookahead).
> 
> Please correct me if SLL(k) will handle this; I'll go back to the books 
> and start reading again ;)  It *has* been a while since I did formal 
> language stuff ;)
> 
> 
>>>>Why the nondeterminism in the grammar that is strong LL(2)?
> 
> 
>>>Because antlr 2 only does approximate LALL(k) not full LALL(k), but
>>>PCCTS (antlr 1) did full LALL(k) and antlr 3 (coming soon to a theatre
>>>near you) will do that plus LL-regular.
>>>
>>>Your SLK is weaker than PCCTS's LALL(k)...just wanted to clear that 
>>>up.
>>
>>I did not see any evidence Sarah denies this. She simply says for 
>>larger
>>  k PCCTS's (non-approximate) LALL(k) algorithm is impractical, which 
>>is
>>true, isn't it?
> 
> 
> The complexity of any parser (LR or LL based) is exponential in k just 
> to hold a single lookahead set so only a constant improvement can be 
> done.  That said, the constant can make quite a difference!  I applaud 
> their efforts if they have made this very fast.  I'd like to hear about 
> it, but get stonewalled all the time.  I don't like bogus claims and I 
> don't like people who won't reveal who they are.
> 
> Sorry if I seem grouchy...this human was a real "pleasure" over private 
> email when I thanked them for referencing my work and sincerely asked 
> to discuss their algorithms.
> 
> [I apologize for any unnecessary irritability; damn cold virus and a 
> million other things going on this week.]
> 
> Ter "Mr. Too Much Cough Medicine" Parr
> --
> Professor Comp. Sci., University of San Francisco
> Creator, ANTLR Parser Generator, http://www.antlr.org
> Co-founder, http://www.jguru.com
> Co-founder, http://www.knowspam.net enjoy email again!
> Co-founder, http://www.peerscope.com link sharing, pure-n-simple
> 
> 
> 
> 
>  
> 
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ 
> 
> 
> 




 

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/