Re: Tool support for resolving LR conflict

Sylvain Schmitz <schmitz@i3s.unice.fr>
4 Oct 2005 01:43:05 -0400

          From comp.compilers

Related articles
Tool support for resolving LR conflict alpanad@gmail.com (2005-09-07)
Re: Tool support for resolving LR conflict torbenm@diku.dk (2005-09-10)
Re: Tool support for resolving LR conflict 148f3wg02@sneakemail.com (Karsten Nyblad) (2005-09-17)
Re: Tool support for resolving LR conflict alpanad@gmail.com (2005-10-02)
Re: Tool support for resolving LR conflict schmitz@i3s.unice.fr (Sylvain Schmitz) (2005-10-04)
| List of all articles for this month |

From: Sylvain Schmitz <schmitz@i3s.unice.fr>
Newsgroups: comp.compilers
Date: 4 Oct 2005 01:43:05 -0400
Organization: Compilers Central
References: 05-09-02705-09-038 05-09-077 05-10-016
Keywords: LALR, parse

alpanad@gmail.com wrote:
> Is DeRemer's work being used in popular compiler compilers?
Yes. It is arguably the most popular LALR computation technique around,
used in GNU bison, Berkeley YACC, and many others; the Gardens Point
Parser Generator presented a week ago on this newsgroup is yet another
example. And when the technique is not used as such, a similar one is,
and at least their computation of relations closures using SCCs is being
used; for instance, I would be very surprised if Karsten Nybald's
implementation did not.


The application of their SCC technique to detect non LR grammars is not
used as often; I think I have only seen it once, maybe in jikes. Their
conjecture on this point is proven in
Sager, T. J. 1986. A short proof of a conjecture of DeRemer and
Pennello. ACM Trans. Program. Lang. Syst. 8, 2 (Apr. 1986), 264-271.


> A paper by Bermudez and
> Schimpf [...] disproves the claim of DeRemer, that says NQLALR(1) is
> superset of SLR(1).
The false claim does not harm the validity of their work on LALR(1):
after all, they only introduce NQLALR(1) in order to help others
avoiding the mistake of computing NQLALR(1) lookahead sets instead of
the real LALR(1) lookahead sets!


--
Regards,


      Sylvain


Post a followup to this message

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