Re: New LR parser generation algorithm

Sylvain Schmitz <>
1 May 2006 15:06:26 -0400

          From comp.compilers

Related articles
New LR parser generation algorithm (David R Tribble) (2006-04-30)
Re: New LR parser generation algorithm (Sylvain Schmitz) (2006-05-01)
Re: New LR parser generation algorithm (Sylvain Schmitz) (2006-05-01)
Re: New LR parser generation algorithm (Francois Pottier) (2006-05-09)
| List of all articles for this month |

From: Sylvain Schmitz <>
Newsgroups: comp.compilers
Date: 1 May 2006 15:06:26 -0400
Organization: Compilers Central
References: <>
Keywords: LR(1), parse
Posted-Date: 01 May 2006 15:06:26 EDT

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: <>,
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:
<> (more interesting for your case),
and <>.

Hope that helps,


Post a followup to this message

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