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

Robert.Corbett@Eng.Sun.COM (Robert Corbett)
Sat, 4 Feb 1995 03:47:24 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: Robert.Corbett@Eng.Sun.COM (Robert Corbett)
Keywords: parse, LR(1)
Organization: Sun Microsystems Computer Corporation
References: 95-02-024 95-02-039
Date: Sat, 4 Feb 1995 03:47:24 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)?


Adam Dickmeiss <adam@index.ping.dk> wrote:
>This grammar is LR(1) but not LALR(1):
>
>%term a b c d
>%%
>S: A a | b A c | B c | b B a
>A: d
>B: d
>%%
>
>There is a reduce/reduce conflict on rule "A -> d" and rule "B -> d" on
>terminals a and c.
>
>See Aho, et al.: "Compilers, Principles, Techniques, and Tools",


The example given has become the standard example. It has the drawback
of being too simple. This example has misled many people into thinking
that it should be easy to write fast state-splitting algorithms for
LR(1)-parser generation. To get an idea how hard the problem really is,
read the paper


          David Pager
          "On the Incremental Approach to Left-to-right Parsing"
          Tech. Report PE 238
          Information and Computer Sciences Dept.
          University of Hawaii
          1972


Sincerely,
Bob Corbett
--


Post a followup to this message

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