[antlr-interest] Re: Nondeterminism problem

[Oliver Zeigermann]

Oliver Zeigermann wrote:

> 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.

OK, finally bought it from the ACM, hope it was worth it ;) What I found 
out is in section 3 where *lower* bounds for LR(k) are computed using 
s-grammars (=simple LL grammars=SLL). The result is the lower bound is 
either polynomial (if k is expressed unary) or exponential (otherwise) 
in time for a *non-deterministic* Turing machine.

This either means
- I made a mistake somewhere
- the claim made in 
http://home.earthlink.net/~parsersinc/doc/conjecture.html is wrong

As this ACM text is pretty clear in stating these results are for 
non-deterministic times, I am afraid the polynomial claim of SLK is 
simply *wrong*. I will be open to any argument provig the opposite.

Cheers :)

Oliver