[antlr-interest] Re: Nondeterminism problem

sarah2geller sarah2geller at yahoo.com
Sun Dec 14 11:51:47 PST 2003


--- In antlr-interest at yahoogroups.com, Terence Parr <parrt at c...> 
wrote:
> 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?
> 

But for what maximum value of k, and in what time?

Why the nondeterminism in the grammar that is strong LL(2)?




 

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




More information about the antlr-interest mailing list