parsinggrammarlalrlr-grammar

Why is this LR(1) grammar not LALR(1)?

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

Solution

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