[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