Re: Kannapinn in a Nutshell

Hello again.


In a personal email concerning my previous posting, Carl Cerecke
asked me:


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


No. It's still O(n) because only up to a constant (length of
longest rhs of a grammar rule + 1) number of states on the stack
have to be inspected by the parser to decide what action to
perform next (and also what to push and pop).


Certainly, from the implementation point of view it's more
complex to implement general LR(k) parsers (and their variants).
But that's the price to pay for squeezing redundance out of an
LR machine's states. The gain (at least from a formal point of
view) is that, for realistic grammars, the number of LR machine
states typically drops to round about 1/10th of the corresponding
canonical LR machine's states. Also the number of shift and
reduce actions (and conflicts, if any) typically drops. (Note
that the minimal general LR(k) parser is deterministic iff the
canonical is!)


For a little example, please look at my thesis:
* page 34 shows a little grammar from the chapter on LR Parsing
    in Sippu&Soisalon-Soininen's "Parsing Theory" book
* page 36 shows the canonical LR(1) machine (19 states)
* page 37 shows the actions of the canonical LR(1) parser
    (14 reduce actions, 12 shift actions)
* page 48 shows the minimal general LR(1) machine (8 states)
* page 60 shows the actions of the minimal general LR(1) parser
    (10 reduce actions, 7 shift actions)
* page 78 shows the "compact" (Joachim Durchholz's wording)
    LR(1) machine (13 states) and how it "corresponds" to the
    well-known canonical construction. The corresponding general
    LR(1) parser has 14 reduce actions and 10 shift actions.
* pages 175 and 179 show decision tree structures which is
    what essentially has to be implemented to realize the minimal
    general LR(1) parser (cf. p.60).


One may think about reading _arbitrarily_ deep into the parser
stack to find enough information for making deterministic parser
decisions. Then, of course, the parser runtime is no longer O(n).
    Fortes Galvez, J. (1992): Generating LR(1) parsers of small size.
    In P. Pfahler und U. Kastens (eds.), Proceedings of the 4th
    International Conference on Compiler Construction, CC ’92,
    Paderborn, Germany, pp.16-–29
describes experimental work in that direction.


> Is there an implementation available?


A Master thesis at my home university has done implementation
efforts. Unfortunately, the student ran out of time, so major
questions remained, the gist of his work being, however, that
successful implementation needs really clever compression
techniques. The context of the work was a prototype compiler
generator based on extended affix grammars (no lex&yacc
stuff). Implementation was in Oberon. I don't think it's of much
use for the public.


Regards,
Sönke Kannapinn


--
Dr. Sönke Kannapinn

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