13 May 2003 04:19:45 -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: | Carl Cerecke <cdc@maxnet.co.nz> |

Newsgroups: | comp.compilers |

Date: | 13 May 2003 04:19:45 -0400 |

Organization: | TelstraClear |

References: | 03-04-075 03-05-014 |

Keywords: | parse, LR(1) |

Posted-Date: | 13 May 2003 04:19:45 EDT |

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.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.