Compilers · Lexing and Parsing
LALR Table Construction and What the Conflicts Mean
How LR(1) item sets become LALR states, what shift-reduce and reduce-reduce conflicts actually report about a grammar, and when a precedence declaration is the correct repair.
A shift-reduce parser reads tokens left to right and maintains a stack of grammar symbols. It never backtracks and never guesses: at each step the table says either shift the next token onto the stack, or reduce the top of the stack by some production, and the choice is determined by the state on top of the stack and the lookahead token. The table is built from the grammar by a construction that, for LALR, keeps the automaton the size of an LR(0) machine while retaining one token of lookahead for the reduce decisions.
That combination is why LALR generators were the default tool for decades. A grammar with a few hundred productions produces a few hundred to a few thousand states, the tables fit comfortably in memory, and the parser runs in time proportional to input length with no search.
Items and the dot
The construction starts from items. An item is a production with a dot marking how much of its right-hand side has been recognised. For a production E → E + T, the four items are E → • E + T, E → E • + T, E → E + • T, and E → E + T •. The dot position encodes both what has been seen and what is expected next.
A state is a set of items closed under a rule: if the dot precedes a nonterminal, every production for that nonterminal is added with its dot at the left. Closure is what makes the automaton track the grammar’s expectations rather than just the symbols consumed.
The goto function takes a state and a symbol and returns the state reached by advancing the dot past that symbol. The canonical LR(0) automaton is the closure of the start item under goto, and its states are sets of items with no lookahead information at all.
From LR(0) to LR(1) and back down to LALR
LR(0) is too weak to be useful, because it reduces whenever a production’s dot reaches the end, without checking whether the next token could actually follow. Canonical LR(1) fixes this by annotating every item with a lookahead set: the terminals that may follow the nonterminal being completed. That construction is correct for a much larger class of grammars, and it produces far more states, sometimes an order of magnitude more than LR(0).
LALR is the middle point. It builds the LR(0) automaton and then computes lookahead sets by propagating them through the item graph, effectively merging LR(1) states that have identical item cores but different lookaheads. The result has the LR(0) state count with lookaheads attached, and it accepts exactly the languages accepted by the corresponding canonical LR(1) machine except in one case: it may introduce a reduce-reduce conflict that canonical LR(1) would not have, because merging can bring two states’ reductions into the same state with overlapping lookaheads.
That is the whole trade. LALR tables are several times smaller than canonical LR(1) tables for the same grammar, because many LR(1) states that differ only in their lookahead sets share a core, and the price is a small class of grammars that are LR(1) but not LALR(1).
The two conflict kinds
A conflict is a state and a lookahead token for which the table has two entries. There are two shapes, and they mean different things.
A shift-reduce conflict says that with this token the parser could either push the token or reduce a completed production. The dangling-else grammar produces the textbook case: after if E then if E then S, with else as lookahead, the parser can shift else to attach it to the inner if or reduce the inner if to a statement and attach else to the outer one. Both parses are derivations of the grammar, so the grammar is ambiguous and the conflict is real.
A reduce-reduce conflict says two different completed productions are both applicable with this lookahead. That is either an ambiguity or, more often, a grammar where two nonterminals derive the same strings in this context, and the table cannot tell which tree to build.
Generators report the state, the token, and the competing actions. That report is the useful artifact; a grammar with conflicts is not necessarily unusable, but every conflict is a place where the parser’s behaviour is not determined by the grammar alone.
Default resolutions and what they hide
The traditional default is to prefer shift over reduce in a shift-reduce conflict, and to prefer the earlier-listed production in a reduce-reduce conflict. Both defaults are silent, and both are how a grammar with an unnoticed ambiguity ships.
Preferring shift resolves dangling else the way the usual languages do: bind to the nearest if. That is the correct resolution for the construct, which is why the default survives. But the same default applied to an expression grammar silently makes the conflicting operators right-associative: with 1 - 2 - 3, the conflict is between shifting the second - and reducing 1 - 2, and shifting builds 1 - (2 - 3) rather than (1 - 2) - 3.
The reduce-reduce default is worse. It picks a production by its position in the file, so reordering two rules changes the parse tree, and the resulting parser may build the wrong node for a construct that appears in tests. A reduce-reduce conflict should be treated as a grammar defect unless it is understood precisely.
Precedence declarations as conflict resolution
The standard repair for expression conflicts is not a grammar rewrite but a declaration. Each terminal is assigned a precedence level and an associativity, and the generator uses that to resolve shift-reduce conflicts between an operator and a production whose rightmost terminal is that operator.
The mechanism is a comparison of the rule’s precedence, taken from its last terminal, against the lookahead token’s precedence. Higher precedence means shift. Lower means reduce. Equal precedence is resolved by associativity: left means reduce, right means shift, and non-associative means report an error.
This is why a yacc-style grammar for expressions can be written with a single ambiguous nonterminal and a list of precedence declarations, and the result parses left-associatively. The grammar is ambiguous; the declarations are the disambiguation, and they are checked at generation time against every conflict they resolve.
The approach has a limit. Precedence declarations work when the conflict’s resolution is genuinely a precedence question between two operators. They do not help a conflict caused by a shared prefix in a statement grammar, and using them there produces a parser whose behaviour happens to match the tests.
A grammar that needs the rewrite
Consider a grammar where a type name and an expression can begin with the same tokens. If T (x) is either a cast or a call, the conflict is not about precedence and cannot be declared away. The grammar must be factored so the parser commits after enough input, or the decision must be moved into the lexer or a semantic predicate, which is the territory of context-dependent lexing.
Another conflict is not about precedence either, and no precedence declaration touches it, because it comes from the merge step in the LALR construction itself. The example is short:
S → a E c | a F d | b F c | b E d
E → e
F → eThe token after a and the token after b are what distinguish the two nonterminals: a e c requires the e to be an E, while a e d requires it to be an F. Canonical LR(1) keeps those two contexts in separate states and has no conflict. LALR builds the same item cores for both, merges them, and the merged state must reduce E → e and F → e on both c and d; that is a reduce-reduce conflict created by the merge, and nothing in the parser’s precedence declarations addresses it. The repairs are canonical LR(1) tables or a grammar rewritten so the two contexts are never merged, and where the conflict is instead about the shape of a list, factoring the list into a head and a repetition removes it at the cost of a new nonterminal and a rule that derives the empty string.
The table collects the conflicts that turn up most, what each one means at the table level, and the repair that addresses it.
| Construct | Naive grammar | Conflict | Repair |
|---|---|---|---|
if/else | nested if without else-matching | shift-reduce on else | shift default is correct |
a - b - c | one expression nonterminal | shift-reduce on - | left precedence |
a = b = c | one expression nonterminal | shift-reduce on = | right precedence |
| LR(1)-but-not-LALR grammar | S: a E c | a F d | b F c | b E d, with E: e, F: e | reduce-reduce on c and d after the cores merge | canonical LR(1) tables, or a grammar whose contexts are not merged |
T (x) cast or call | shared prefix | reduce-reduce | grammar rewrite or symbol table |
Stack behaviour and error detection
The parser’s stack holds states, not symbols; the symbols are recoverable from the states but are usually not stored. Each shift pushes a state. Each reduction pops as many states as the production’s right-hand side has symbols and pushes the goto state for the left-hand side. The number of pops is known from the production, so reduction is a loop with a fixed count.
Errors are detected at the first token for which the table has no entry. That is the definition of an LR parser’s error detection property: it never shifts a token that cannot continue a valid parse, so the error is reported at or before the offending token rather than after the parser has consumed unrelated input. The gap between where the error is detected and where the mistake was made is a separate question, and it is why an LR parser’s diagnostic can name a token that looks perfectly legal while the real problem is earlier.
Recovery typically pops states until one is found that has an action for a synchronising token, such as a semicolon or a closing brace, then shifts that token and continues. The stack-popping is cheap; the hard part is choosing synchronising tokens that do not cause cascading false errors.
Table size and the cost of lookahead
An LALR table has one row per state and one column per terminal, plus a goto table indexed by state and nonterminal. For a grammar with 500 states and 100 terminals, the action table is 50,000 entries; at two bytes each that is 100 kilobytes before any compression, which is the raw size for a grammar of that shape.
Generators compress with the same row-displacement and default-value techniques used for lexer tables, and a table of that size reduces to tens of kilobytes. The compression is why LALR remained practical on machines with small memories and why the format is still used.
Canonical LR(1) for the same grammar might need several thousand states, and the table would be several times larger. The extra power buys grammars that LALR merges into conflict, which in practice is a small set: most programming language grammars are LALR(1) or become so after a mechanical rewrite.
For expression-heavy grammars, a hand-written alternative to any of this is set out in Precedence Climbing for Binary Expressions. For grammars that cannot be made deterministic at all, the generalized approach is described in GLR Parsing and the Graph-Structured Stack.
References
- Compilers: Principles, Techniques, and Tools, 2nd edition — Aho, Lam, Sethi, and Ullman, Addison-Wesley, 2006
- Bison — GNU Parser Generator Manual — GNU Bison project
- Parsing Techniques: A Practical Guide, 2nd edition — Grune and Jacobs, Springer, 2008