[antlr-interest] Re: Nondeterminism problem

sarah2geller at yahoo.com sarah2geller at yahoo.com
Tue Dec 16 11:20:41 PST 2003


--- 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).

> 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


 

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