Re: New LR parser generation algorithm

Francois Pottier <Francois.Pottier@inria.fr>
9 May 2006 00:48:27 -0400

          From comp.compilers
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)
| List of all articles for this month |
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.