LR Parser

An LR parser is a bottom-up parser for context-free grammars that reads the input Left-to-right and produces a Rightmost derivation in reverse. The name "LR" encodes this geometry: the parser consumes tokens from left to right and reconstructs the rightmost derivation by working backward from the leaves of the parse tree toward the root. An LR(k) parser uses k tokens of lookahead to resolve ambiguities in the reduction steps. The canonical LR(1) parser — with one token of lookahead — is the most powerful deterministic parsing technique in practical use, accepting a strictly larger class of grammars than any LL(k) parser for any finite k.

The LR parser is the workhorse of compiler construction. The Unix parser generator Yacc and its modern descendant Bison generate LALR(1) parsers — a practical approximation of LR(1) that uses smaller parsing tables at the cost of rejecting a small number of grammars that full LR(1) would accept. Virtually every industrial-strength compiler for a language with complex syntax — C, C++, Java — uses an LR-derived parser or a generalized variant.

The Shift-Reduce Automaton

An LR parser operates by maintaining a stack of states and symbols. On each step, it consults a parsing table to decide between two actions: shift or reduce.

Shift: Push the current input token onto the stack and advance to the next token. This corresponds to reading more of the input before committing to a grammatical interpretation.
Reduce: Pop a sequence of symbols from the stack — the right-hand side of some grammar production — and replace them with the corresponding left-hand side non-terminal, pushing the new state associated with that non-terminal.

The parser begins with an empty stack and a start state. It shifts tokens until the top of the stack contains a complete right-hand side of some production, then reduces that production to its left-hand side. This cycle continues until the start symbol alone sits on the stack and the input is exhausted — a successful parse. If the parsing table indicates an error at any point, the input does not belong to the grammar.

The parsing table is constructed from the grammar by computing sets of LR items — production rules with a dot indicating how much of the right-hand side has been seen. Each set of items becomes a state in the automaton, and the transitions between states are determined by what symbols can advance the dot. The construction is mechanical but subtle: it encodes a prediction about what grammatical structures might be in progress, given the prefix of input that has already been consumed.

LR Variants: SLR, LALR, and LR(1)

The canonical LR(1) construction produces the largest class of deterministic bottom-up parsers but generates parsing tables that are impractically large for real grammars — often millions of entries for a modest language. Three variants manage this explosion:

SLR (Simple LR) uses FOLLOW sets to resolve conflicts, producing very small tables but rejecting many grammars that LR(1) would accept. It is rarely used in practice.
LALR (Look-Ahead LR) merges states that have the same core set of items but different lookahead symbols, producing tables almost as small as SLR but accepting nearly as many grammars as LR(1). It is the standard for parser generators like Yacc and Bison.
LR(1) retains full lookahead information and accepts the largest class of deterministic grammars. Modern techniques such as IELR(1) and Minimal LR(1) use state merging and splitting to produce tables competitive with LALR in size while retaining full LR(1) power.

The choice between variants is a systems engineering trade-off. LALR(1) has been sufficient for decades because language designers have implicitly tailored their grammars to fit its limitations. But as languages grow more complex — with dependent types, syntax macros, and extensible grammars — the pressure to use more powerful LR variants or generalized parsing techniques increases.

Conflicts and Grammar Engineering

When a grammar is ambiguous or not in the LR class, the parser table construction encounters conflicts:

Shift-reduce conflict: The parser cannot decide whether to shift the next token or reduce a completed production. The classic example is the dangling else: when an "else" is encountered after an "if" without an "else," the parser cannot tell whether the "else" belongs to the inner or outer "if."
Reduce-reduce conflict: Two different productions could be reduced from the same stack contents. This is less common but more serious, as it indicates a fundamental ambiguity in the grammar.

Parser generators resolve conflicts by default rules — typically, prefer shift over reduce, and prefer the first production over the second. These defaults are dangerous: they silently change the grammar's semantics. A compiler writer who does not understand the conflicts in her grammar is a compiler writer who does not understand the language she is parsing.

Conflict resolution is not merely a technical problem. It is a design problem. A grammar with shift-reduce conflicts is a grammar that defers syntactic disambiguation to context — and that context may be semantic, not syntactic. The C language's famous type-name ambiguity (is "T * x" a multiplication or a declaration?) cannot be resolved by an LR parser alone; it requires a symbol table that knows whether "T" is a type name. This is the boundary where pure syntax ends and semantic analysis begins.

The LR parser is often described as more powerful than the LL parser because it accepts more grammars. This description misses the deeper point. The LR parser is more powerful because it delays commitment. It shifts tokens onto the stack without knowing which production they will eventually belong to, carrying multiple hypotheses until the evidence forces a choice. This is not merely a parsing strategy; it is an epistemological stance. The LL parser is a Bayesian with a strong prior; the LR parser is a scientist who waits for the data. The question of which is better is not a question about parsing. It is a question about whether you believe grammatical structure is something you predict or something you discover.