[antlr-interest] Re: Nondeterminism problem

[Oliver Zeigermann]

Terence Parr wrote:

> On Sunday, December 14, 2003, at 11:51 AM, sarah2geller wrote:
> 
>>>Part of my confusion is that SLL(k) subset LALL(k) subset LL(k).  I
>>>cite pg 233 of "Parsing Theory II" by Sippu and Soisalon-soininen,
>>>Spring-Verlag 1990: "For k>1, the class of SLL(k) grammars is
>>
>>properly
>>
>>>contained in the class of LALL(k) grammars...".  PCCTS did/does LALL
>>
>>(k)
>>
>>>and thus can generate a larger class of languages than SLK.  Can
>>
>>you
>>
>>>clear up my misunderstanding?
>>>
>>
>>But for what maximum value of k, and in what time?
> 
> 
> That's not my question.  Your claim contradicts well-established 
> parsing theory...how do you respond?

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.

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

Cheers :)

Oliver




 

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/