[antlr-interest] Re: Nondeterminism problem

[Terence Parr]

On Saturday, December 13, 2003, at 11:26 AM, sarah2geller wrote:
> Correct. The grammar is strong LL(2), confirmed by the SLK parser-
> generator (http://parsers.org).

Ahh....the mysterious human behind SLK awakens.  Welcome to the group. 
:)

Care to share with us how your lookahead computation algorithms work?  
The reason I ask is that I'm confused by your statement on your site:

> ... SLK does a complete strong LL(k) analysis of the grammar. The SLK 
> algorithm is the only currently known near-solution to this 
> NP-complete problem . All other practical LL(k) analysis algorithms 
> work on language classes that are proper subsets of the strong LL(k) 
> languages.

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?

Thanks,
Terence
--
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




 

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