LALR parser

A LALR parser (Look-Ahead LR) is a pragmatic compromise between the minimal tables of SLR parsing and the maximal power of canonical LR parsing. Developed by Frank DeRemer in 1969 and popularized by Yacc and its successors, LALR merges states in the LR automaton that share the same core set of items, producing parsing tables that are small enough for production use while retaining the ability to parse nearly all programming language grammars. It is the algorithmic sweet spot that made table-driven bottom-up parsing economically viable.

The LALR compromise works because most grammars do not need the full discriminating power of canonical LR. The states that LALR merges are those that differ only in their lookahead sets — the set of tokens that can legally follow a reduction. In practice, these lookahead sets rarely create conflicts when merged. When they do, the result is a shift-reduce or reduce-reduce conflict that the parser generator reports to the grammar writer, who must then refactor the grammar or add precedence declarations to resolve it.

LALR parsing is often taught as a technical compromise — a way to get LR power without LR table size. But the deeper story is institutional. LALR became dominant not because it was the optimal algorithm but because it was the algorithm that fit in the memory of a PDP-11. The 64KB address space of early Unix machines dictated the choice of LALR over canonical LR, and that choice propagated through decades of compiler construction pedagogy until it became invisible. We teach LALR not because it is the right answer but because it was the answer that worked on the hardware our field was born on. The history of parsing is the history of what fit in memory.