[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