[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