# [antlr-interest] Re: Nondeterminism problem

Oliver Zeigermann oliver at zeigermann.de
Fri Dec 19 16:41:37 PST 2003

```Terence Parr wrote:
> On Friday, December 19, 2003, at 08:39 AM, Oliver Zeigermann wrote:
>
>>>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?
>>
>>I browsed around the SLK site a bit and guess SLK *nearly* is able to
>>solve the SLL(k) computation in polynomial time instead of exponential.
>
>
> Howdy :)
>
> This is not possible in theory for k>1 because each lookahead set is
> O(|T|^k) in the worst case.  In practice it's not as bad, but can
> quickly explode for k>2.  The algorithm is irrelevant...this is min
> requirement just to store a *single* lookahead set.
>
>
>>As far as I understand it uses the fact SLL(k) computation for any
>>*fixed* k is polynomial only.
>
>
> Actually, it can never be polynomial in theory.  The sequence of tokens
> is combinatoric.  Sometimes in practice you can make it do k=7 as I've
> done with antlr on small grammars.
>

I have this reference from

first paragraph, but have no access to the primary source. I do not want
to make this a research topic, but can anyone verify the link?

The primary source seems to be:

Aho, Alfred V., S.C. Johnson, and Jeffrey D. Ullman (1975).
"Deterministic Parsing of Ambiguous Grammars." Communications of the
ACM, 18(8), pp. 441-452.

>> So SLK begins to create a table assuming
>>the grammar is SLL(1). If it detects an ambiguity it augments it with
>>SLL(2), etc. How does ANTLR do it?
>
>
> ANTLR does the same thing and that technique has been known for at
> least 30 years (modulating the lookahead depth).
>
>
>>>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.
>>
>>Yes, but isn't the creation time for such a parser exponential in
>>respect to k?
>
>
> Yep.  Any parser that does SLL or LALL or LL will be exponential for
> k>1.  LL is non linear (can't remember exact order at the moment) even
> for k=1 due to rule replication.
>
> Approximate parsers are always non-exponential, but non linear.  They
> are essentially O(|G|xk) or perhaps a little higher where |G| is the
> size of the grammar.
>
>
>>>s : Z (a | ) B ;
>>>
>>>a : A;
>>>
>>>t : X a A ;
>>
>>Ah, this is interesting. *Obviously this shows LALL' grammars are not a
>>subset of SLL grammars*!
>
>
> Correct.  SLL has less precise lookahead computation.
>
> However, I made a mistake in this grammar I just realized...tried to
> simplify.  Here is an LALL(1) grammar that should not be SLL(k).
>
> s : (a|C) B ;
>
> a : A|;
>
> t : a C ;
>
> The problem is that computing lookahead for first alt of subrule you go
> like this:
>
> LOOK(a) == FIRST(a) == {A} U FOLLOW(a)  == A // SLL
>
> whereas an LALL computation will use the fact that it knows which
> context in which 'a' will be invoked and use only the first
> FOLLOW=={B}.  So LALL(1) should compute {A,B} for lookahead of first
> alt of subrule and SLL(1) would compute {A,B,C}, which collides with C
> of second alt.  Sorry for the incorrect grammar.  BTW, LALL'(1) ==
> LALL(1) grammar and language.  They are identical functionally and
> hence equivalent in power trivially.
>
>
>
>
> Ah.  That's different.
>
>
>> As far as I understand from the above there
>>is always a way to rephrase your LL grammar to SLL to parse any LL
>>language, is this correct?
>
>
> For k=1, SLL(k)==LL(k).  But this is not true for LL(k) languages with
> k>1.
>
>
>> Is it always possible to make a LL grammar
>>LALL', parsing the same language?
>
>
> I'm not certain, but I'd say no: there must be LL(k) languages that are
> not LALL'(k).
>
>
>> If not the LALL' languages indeed seem
>>to be a subset of the SLL languages, right?
>
>
> No because LL(k) strictly stronger than SLL(k) languages and grammars.
> LALL' weaker than LALL for grammars, but I don't know for languages.  I
> never established that result, sorry.  Therefore, I don't think the
> relationship is so obvious.  The only thing that is clear is that SLK's
> claims about being strongest non-LL(k) parsers is wrong due to PCCTS's
> LALL(k) parsers.

OK. Is there anything I could read to clear my mind? Is there anyone who
touched this before in a theoretical way? My mind needs relief and a
little bit of rest, but I will have to find this out before :( Any hints?

Oliver

> Ter
> --
> 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 pure link sharing
>
>
>
>
>
>
>
> 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/
>
>
>

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/

```