Re: New LR parser generation algorithm

Sylvain Schmitz <schmitz@i3s.unice.fr>
1 May 2006 15:06:26 -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: Sylvain Schmitz <schmitz@i3s.unice.fr>
Newsgroups: comp.compilers
Date: 1 May 2006 15:06:26 -0400
Organization: Compilers Central
References: <20060501160642.E0E68DA619@ws6-6.us4.outblaze.com>
Keywords: LR(1), parse

David Tribble wrote:
> Yes, the algorithm does merge these two item sets. At that point
> in the algorithm, no r/r conflicts are detected in the resulting merged
> item set, so the two sets are merged.
>
> It is conceivable that the algorithm could be enhanced to perform
> some kind of forward look-ahead to detect r/r conflicts earlier, but this
> could be quite complicated to implement.


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.


>> You might be interested in reading David Pager: _A_Practical_General_
>> _Method_for_Constructing_LR(k)_Parsers_. Acta Inf. 7: 249-268 (1977) and
>> David Pager: _The_lane-tracing_algorithm_for_constructing_LR(k)_parsers_
>> _and_ways_of_enhancing_its_efficiency_. Inf. Sci. 12(1): 19-42 (1977)
>
> Yes, I've heard of Pager's algorithm, but I don't know the details.
> Where can I get a copy of these?


The closest university library is your best shot, otherwise you can buy
an electronic copy from the publishers websites:
<http://dx.doi.org/10.1007/BF00290336> (more interesting for your case),
and <http://dx.doi.org/10.1016/0020-0255(77)90036-6>.


--
Hope that helps,


      Sylvain



Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.