$LALR(1)$ Parsers

While $LR(1)$ parsers are quite powerful, they can involve a large number of states, and this can cause complications for the implementation. We can reduce the number of states without paying too much of a price in terms of increased conflicts by noting that there will often be two different states whose basic items are the same, but which differ only in lookahead sets.

We can reduce the size of an $LR(1)$ parse table if we combine such states together; the resulting lookahead is the union of the two individual lookaheads. Parse tables constructed from this type of DFA are known as $LALR(1)$ parsers, for Look-Ahead $LR(1)$ parsers. [Stupid name - all $LR(1)$ parsers have lookahead]

Merging two states in this manner will not adversely effect the ${\sf move}$ function, since this does not depend on the lookahead.

Merging states will not add any extra shift/reduce conflicts that were not in the $LR(l)$ parser originally, since shift actions do not depend on lookaheads. However, the number of reduce/reduce conflicts may be increased.