5.2.6 LR-Family: LALR(1) Table Generation

It is often the case that two states in an LR(1) state have the exact same items except for the lookahead. We can reduce the size of the ultimate table by merging these two states. There are ten pairs of states that can be merged in the items for Section 5.2.5 and Exercise 11. Two of them and their merged states are:

State i                              State j                         State i-j
E  E + · T, {+, $}             E  + · T, { ), + }             E  E + · T, { ), +, $ }
T  · T * F, { $, +, * }        T  · T * F, { ), +, * }        T  · T * F, { ), +, *, $ }
T  · T * F, { $, +, * }        T  · T * F, { ), +, * }        T  · T * F, { ), +,*, $ }
F  · Id, { $,  +, * }          F  · Id, { ), +, * }           F  · Id, { ), +, *, $ }
F  · (E), { $, +, *}           F  · (E), { ), +, *}           F  · (E), { ), +, *, $ }

LALR(1) parsers parse fewer language than do LR(1) parsers.