14

This is not my homework, I'm trying to understand LALR(1) grammars. So I found this

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

I wrote the LR items, but I can't figure out why this is an LR(1) grammar and not LALR(1)?

Can anyone help me? Thank you

OrenIshShalom
  • 5,974
  • 9
  • 37
  • 87
Jan Vorcak
  • 19,261
  • 14
  • 54
  • 90

1 Answers1

26

Let's begin by constructing LR(1) configurating sets for the grammar:

 (1)
 S' -> .S [$]
 S  -> .aEa [$]
 S  -> .aFb [$]
 S  -> .bFa [$]
 S  -> .bEb [$]

 (2)
 S' -> S. [$]

 (3)
 S  -> a.Ea [$]
 S  -> a.Fb [$]
 E  -> .e   [a]
 F  -> .e   [b]

 (4)
 E  -> e.   [a]
 F  -> e.   [b]

 (5)
 S  -> aE.a [$]

 (6)
 S  -> aEa. [$]

 (7)
 S  -> aF.b [$]

 (8)
 S  -> aFb. [$]

 (9)
 S  -> b.Fa [$]
 S  -> b.Eb [$]
 E  -> .e   [b]
 F  -> .e   [a]

 (10)
 E  -> e.   [b]
 F  -> e.   [a]

 (11)
 S  -> bF.a [$]

 (12)
 S  -> bFa. [$]

 (13)
 S  -> bE.b [$]

 (14)
 S  -> bEb. [$]

If you'll notice, states (4) and (10) have the same core, so in the LALR(1) automaton we'd merge them together to form the new state

 (4, 10)
 E -> e. [a, b]
 F -> e. [a, b]

Which now has a reduce/reduce conflict in it (all conflicts in LALR(1) that weren't present in the LR(1) parser are reduce/reduce, by the way). This accounts for why the grammar is LR(1) but not LALR(1).

Hope this helps!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • well, you helped me a lot, I realised one mistake a do in an analysis in my pdf, but anyway, I found this [here](http://compilers.iecc.com/comparch/article/95-02-053) and I wanted to prove it to my self, my result is also that it's a valid LARL(1) grammar, so I guess there is a mistake on that website? am I right? – Jan Vorcak Dec 13 '11 at 21:26
  • I guess that would be a mistake on the website, since we just built the LALR automaton and had `bison` check it for us. I would assume that the intent was to find a LALR but not SLR grammar. – templatetypedef Dec 13 '11 at 21:27
  • well, I figured it out, you miss rules E->e and F->e in your analysis, that's why `bison` didn't have any error output – Jan Vorcak Dec 13 '11 at 21:55
  • @Jan Vorcak- Can you explain this in more detail? I definitely factored in these rules (I assume that e means 'epsilon;' is this incorrect?) – templatetypedef Dec 13 '11 at 22:04
  • well, I knew I didn't get something about your analysis, e is a terminal symbol as you can see on the source website, if it's an epsilon, it would be pretty simple grammar, I noticed that in many cases they mark epsilon as lambda character – Jan Vorcak Dec 13 '11 at 22:07
  • 1
    @JanVorcak- Answer updated. Can you take a look at this and see if it explains things better? – templatetypedef Dec 13 '11 at 22:15
  • Thank u it helped a lot but the state S0 is wrong (It is S->bEb not S->bFb) –  Mar 27 '14 at 17:23
  • 1
    Is there a typo in the second line of state 10? It reads `E -> e. [a]`, I think it should be `F -> e. [a]` – Michael Mrozek Jun 14 '15 at 06:29