[antlr-interest] Re: Nondeterminism problem

Oliver Zeigermann oliver at zeigermann.de
Tue Dec 23 14:19:07 PST 2003

Oliver Zeigermann wrote:

> 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
> http://home.earthlink.net/~parsersinc/doc/conjecture.html
> 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.

Sorry, I was wrong, the source is:

Hunt H.B., T.G. Szymanski, and J.D. Ullman (1975). "On the complexity of 
LR(k) testing," CACM, 18:12, pp. 707-716.



Yahoo! Groups Links

To visit your group on the web, go to:

To unsubscribe from this group, send an email to:
 antlr-interest-unsubscribe at yahoogroups.com

Your use of Yahoo! Groups is subject to:

More information about the antlr-interest mailing list