Re: LALR(1)- but not LR(1)-conflict

salomon@silver.cs.umanitoba.ca (Daniel J. Salomon)
Fri, 3 Feb 1995 22:04:34 GMT

          From comp.compilers

Related articles
LALR(1)- but not LR(1)-conflict holzmuel@kafka.informatik.uni-stuttgart.de (1995-01-31)
Re: LALR(1)- but not LR(1)-conflict adam@index.ping.dk (1995-02-02)
Re: LALR(1)- but not LR(1)-conflict salomon@silver.cs.umanitoba.ca (1995-02-03)
Re: LALR(1)- but not LR(1)-conflict Robert.Corbett@Eng.Sun.COM (1995-02-04)
Re: LALR(1)- but not LR(1)-conflict frederic.tendeau@inria.fr (1995-02-09)
Re: LALR(1)- but not LR(1)-conflict ludemann@netcom.com (1995-02-12)
Re: LALR(1)- but not LR(1)-conflict adam@index.ping.dk (1995-02-18)
| List of all articles for this month |

Newsgroups: comp.compilers
From: salomon@silver.cs.umanitoba.ca (Daniel J. Salomon)
Keywords: parse, LR(1)
Organization: Computer Science, University of Manitoba, Winnipeg, Canada
References: 95-02-024
Date: Fri, 3 Feb 1995 22:04:34 GMT

holzmuel@kafka.informatik.uni-stuttgart.de (Bernd Holzmueller) writes:
> Does anybody know of a concrete example of an LALR(1)-conflict in an existing
> (or hypothetical but semantically meaningful) programming language grammar
> which is *exactly* LALR(1), i.e. the conflict is solved by moving to LR(1)?


The following grammar is the classic example of an LR(1) grammar that
is not LALR(1):


        S -> aEa | bEb | aFb | bFa
        E -> e
        F -> e


This does not, however, translate directly into a common programming
language parsing problem. These days language designers tend to make
their grammars LALR(1) consistent in order to facilitate implementation,
and so the problem will not occur in ordinary situations.


I can remember having an LALR(1) inconsistency in a grammar I was
developing, and I was certain that it would be LR(1) consistent,
but since I did not have an LR(1) parser generator to test my theory, I
did not pursue it further. You might try to look for such an
inconsistency in the published grammar for Modula-3 [Cardelli, et al.,
"Modula-3 Language Definition", ACM SIGPLAN Notices, V.27, #8, Aug
1992]. It seems to have every other conceivable kind of inconsistency. :-)


--
Daniel J. Salomon -- salomon@cs.UManitoba.CA
              Dept. of Computer Science / University of Manitoba
              Winnipeg, Manitoba, Canada R3T 2N2 / (204) 474-8687
--


Post a followup to this message

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