Re: New LR parser generation algorithm

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

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