[antlr-interest] Re: Nondeterminism problem

[Oliver Zeigermann]

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.

Oliver



 

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/