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

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
--

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