|Kannapinn in a Nutshell firstname.lastname@example.org (Joachim Durchholz) (2003-04-20)|
|Re: Kannapinn in a Nutshell email@example.com (Carl Cerecke) (2003-04-27)|
|Re: Kannapinn in a Nutshell firstname.lastname@example.org (Joachim Durchholz) (2003-04-27)|
|Re: Kannapinn in a Nutshell email@example.com (=?Windows-1252?Q?S=F6nke_Kannapinn?=) (2003-05-06)|
|Re: Kannapinn in a Nutshell firstname.lastname@example.org (Chris F Clark) (2003-05-06)|
|Re: Kannapinn in a Nutshell email@example.com (Carl Cerecke) (2003-05-13)|
|Re: Kannapinn in a Nutshell firstname.lastname@example.org (=?Windows-1252?Q?S=F6nke_Kannapinn?=) (2003-05-14)|
|Re: Kannapinn in a Nutshell email@example.com (=?Windows-1252?Q?S=F6nke_Kannapinn?=) (2003-05-16)|
|Re: Kannapinn in a Nutshell firstname.lastname@example.org (Joachim Durchholz) (2003-06-20)|
|Date:||16 May 2003 19:59:19 -0400|
|Organization:||Siemens Business Services|
|Posted-Date:||16 May 2003 19:59:19 EDT|
In a personal email concerning my previous posting, Carl Cerecke
> 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
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 some
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.
Dr. Sönke Kannapinn
String.concat[ "soenke", ".", "kannapinn", "@", "wincor-nixdorf", ".", "com" ]
Return to the
Search the comp.compilers archives again.