16 May 2003 19:59:19 -0400

Related articles |
---|

Kannapinn in a Nutshell joachim_d@gmx.de (Joachim Durchholz) (2003-04-20) |

Re: Kannapinn in a Nutshell cdc@maxnet.co.nz (Carl Cerecke) (2003-04-27) |

Re: Kannapinn in a Nutshell joachim_d@gmx.de (Joachim Durchholz) (2003-04-27) |

Re: Kannapinn in a Nutshell soenke.kannapinn@wincor-nixdorf.com (=?Windows-1252?Q?S=F6nke_Kannapinn?=) (2003-05-06) |

Re: Kannapinn in a Nutshell cfc@world.std.com (Chris F Clark) (2003-05-06) |

Re: Kannapinn in a Nutshell cdc@maxnet.co.nz (Carl Cerecke) (2003-05-13) |

Re: Kannapinn in a Nutshell soenke.kannapinn@wincor-nixdorf.com (=?Windows-1252?Q?S=F6nke_Kannapinn?=) (2003-05-14) |

Re: Kannapinn in a Nutshell soenke.kannapinn@wincor-nixdorf.com (=?Windows-1252?Q?S=F6nke_Kannapinn?=) (2003-05-16) |

Re: Kannapinn in a Nutshell joachim.durchholz@web.de (Joachim Durchholz) (2003-06-20) |

From: | =?Windows-1252?Q?S=F6nke_Kannapinn?= <soenke.kannapinn@wincor-nixdorf.com> |

Newsgroups: | comp.compilers |

Date: | 16 May 2003 19:59:19 -0400 |

Organization: | Siemens Business Services |

References: | 03-04-075 03-04-081 |

Keywords: | parse |

Posted-Date: | 16 May 2003 19:59:19 EDT |

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

Regards,

Sönke Kannapinn

--

Dr. Sönke Kannapinn

String.concat[ "soenke", ".", "kannapinn", "@", "wincor-nixdorf", ".", "com" ]

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.