Re: Kannapinn in a Nutshell

Sönke Kannapinn wrote:


> Especially, the thesis proves that, for a given grammar, there exists
> a lattice structure of infinitely many LR(k) parsers which all "behave
> like" the well known Knuth-style canonical LR(k) parser. In the
> English abstract of my thesis (which I encourage comp.compilers
> participants with a "parsing affinity" to read; see the link below) I
> call all these parsers "general LR(k) parsers". (Note that Tomita's
> GLR parsers are a completely different sort or generalization.) The
> "minimal LR(k) parser" in this lattice can effectively be computed by
> applying a minimization algorithm from automata theory. The canonical
> LR(k) parser and the (what you called) CLR(k) parser are merely
> special cases having important special properties that can be (and for
> the canonical case: are) used to simplify the implementation of the
> parser's actions. Notably, the amount of information available in the
> stacked parser states differs as follows:
>
> * _all_ general LR(k) parsers (if deterministic) have enough
> information available at their states such that the stacked
> states and grammar symbols "touched" by the parser actions
> always allow to determine which (shift or reduce) action is to
> be applied. (Reduce actions "touch" _all_ topmost stack states
> and grammar symbols that correspond to the handle plus the
> k-lookahead; shift actions "touch" only the topmost state plus
> the k-lookahead.)


I'm not sure I understand correctly, but doesn't this mean that
it is possible to get a worst case performance greater than O(n)
for some general LR(k) parsers, including the minimal one?


Is there an implementation available?


Cheers,
Carl.

Return to the comp.compilers page.
Search the comp.compilers archives again.