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


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

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