Merging states in LALR parser

Question

I was learning LALR parsers from the dragon book (Compilers: Principles, Techniques, and Tools by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman) and I came across the example on page 267. I'll try my best to describe my question without needing the actual book for reference.

The book states that:

I4 and I7 form such a pair, with core $\{C -> d.\}$ . Similarly, I3 and I6 form another pair, with core $\{C -> c.C, C -> .cC, C -> .d\}$ . There is one more pair, I8 and I9 with common core $\{C -> cC.\}$ .

Here, I3 and I6 have the same set of cores $\{C -> c.C, C -> .cC, C -> .d\}$ . My question is, should I combine I3 and I6 if I3 had the set of cores $\{C -> c.C, C -> .cC\}$ and I6 had the set of cores $\{C -> c.C, C -> .cC, C -> .d\}$ ? That is, should the set of cores for the itemsets should be exactly the same for combining them or can one be a proper subset of the other?

Thanks in advance!

Answer 1

No, you can't do that. The definition of LALR parsers is that it has combined(union of lookaheads) states having the same cores but different lookaheads.

So what would happen if you were to combine states based on a subset/superset basis? This would basically mean modifying the grammar, also you run into the possibility of having shift/reduce conflicts. You could easily test out your theory by parsing a string using a LALR parser constructed as per your idea and a CLR parser for the same. Since they have the same parsing power, the string should be parsed by both of them. It might happen that both parsers are able to parse a particular string so you'll have to be select your string carefully.