[antlr-interest] Re: Nondeterminism problem

Terence Parr parrt at cs.usfca.edu
Mon Dec 15 08:55:19 PST 2003


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/ 




More information about the antlr-interest mailing list