9 May 2006 00:48:27 -0400

Related articles |
---|

New LR parser generation algorithm david@tribble.com (David R Tribble) (2006-04-30) |

Re: New LR parser generation algorithm schmitz@i3s.unice.fr (Sylvain Schmitz) (2006-05-01) |

Re: New LR parser generation algorithm schmitz@i3s.unice.fr (Sylvain Schmitz) (2006-05-01) |

Re: New LR parser generation algorithm Francois.Pottier@inria.fr (Francois Pottier) (2006-05-09) |

From: | Francois Pottier <Francois.Pottier@inria.fr> |

Newsgroups: | comp.compilers |

Date: | 9 May 2006 00:48:27 -0400 |

Organization: | I.N.R.I.A Rocquencourt |

References: | <20060501160642.E0E68DA619@ws6-6.us4.outblaze.com> 06-05-008 |

Keywords: | parse |

Posted-Date: | 09 May 2006 00:48:27 EDT |

Sylvain Schmitz wrote:

*> That's what Pager's algorithm is about, and indeed it's not for the*

*> faint-hearted. I have read about a recent implementation in menhir, a*

*> parser generator for OCaml: <http://cristal.inria.fr/~fpottier/menhir/>,*

*> which might help you out.*

Indeed, Menhir implements Pager's algorithm. The test that decides

whether two states can be merged is actually fairly simple to implement.

The *proof* that this criterion is correct is more involved, and is

found in Pager's paper. One must prove that merging two states does not

introduce conflicts, either now or in the future.

A more difficult aspect is to use data structures that make the

construction sufficiently fast. I construct the LR(0) automaton

first, perform some precomputation over it, and use that as a basis

for the Pager-style LR(1) construction.

--

François Pottier

Francois.Pottier@inria.fr

http://cristal.inria.fr/~fpottier/

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.