The bottom-up parsing tutorial introduced shift-reduce parsing as a strategy built around a parsing stack, two basic operations, and the idea of repeatedly finding and reducing a handle. What it left unanswered was a fairly important practical question: how does a parser actually know, at every single step, exactly when to shift and exactly when to reduce, without a human sitting there manually working it out? LR parsing answers that question by building an automatically generated table that tells the parser precisely what to do in every possible situation, based on the grammar alone.
The name LR describes the technique in the same spirit as LL(1) described predictive parsing. The L indicates that input is scanned from left to right, and the R indicates that the parser constructs a rightmost derivation, though it does so in reverse, exactly as described in the previous tutorial on bottom-up parsing. LR parsing is not a single algorithm but a family of closely related techniques, each differing in how much information they track while building their parsing tables, which directly affects how many grammars each variant is capable of handling correctly.
In this tutorial, you will learn what LR(0) items are and how they are grouped into states, how those states are used to build action and goto tables, how a table-driven LR parser actually processes input, and how the three major LR variants, SLR, CLR, and LALR, differ from one another in terms of power, table size, and practical trade-offs.
LL(1) parsing works well for a meaningful subset of grammars, but many useful and natural-looking grammars simply cannot be converted into a conflict-free LL(1) table, even after applying left recursion elimination and left factoring. LR parsing was developed specifically to overcome this limitation, offering a bottom-up, table-driven approach capable of handling a much larger class of grammars, including left-recursive ones, without requiring the same restrictive rewriting.
This broader grammar coverage is precisely why LR parsing, in one of its variants, is the technique most commonly used inside automatically generated parsers for real-world programming languages, even though it is more complex to construct by hand than an LL(1) parser.
The foundation of LR parsing is a concept called an LR(0) item, which is simply a production rule with a special marker, usually written as a dot, placed somewhere on its right-hand side to indicate how much of that production has already been recognized at a given point during parsing.
Production: Statement -> Identifier = Expression LR(0) Items derived from this production: Statement -> . Identifier = Expression Statement -> Identifier . = Expression Statement -> Identifier = . Expression Statement -> Identifier = Expression .
Each of these items represents a different stage of recognizing the same production. The first item indicates that nothing has been matched yet. The second indicates that an identifier has been matched, with an assignment operator still expected next. The final item, with the dot all the way at the end, indicates that the entire right-hand side has been matched, meaning a reduction can now take place.
Individual LR(0) items are grouped together into sets called states, which represent all the different possibilities the parser might currently be considering at a given point. Two operations are used to build these states: closure and goto.
| Operation | Description |
|---|---|
| Closure | Given a set of items, closure adds additional items for any non-terminal that appears immediately after the dot, including items for that non-terminal's own productions with the dot at the very beginning. |
| Goto | Given a state and a grammar symbol, goto computes the new state reached by moving the dot past that symbol in every relevant item, effectively simulating what happens after the parser shifts or reduces past that symbol. |
Grammar:
Statement -> Identifier = Expression
Expression -> Identifier
Starting Item: Statement -> . Identifier = Expression
Closure Result (no change needed here, since the symbol after the dot is a terminal-like Identifier token in this simplified example):
{ Statement -> . Identifier = Expression }
Goto(State, Identifier):
{ Statement -> Identifier . = Expression }
Closure ensures that a state fully captures every possibility the parser needs to consider, including productions for non-terminals that have not yet been expanded, while goto describes how the parser transitions from one state to another as it consumes grammar symbols, whether by shifting a terminal or by completing a reduction that produces a non-terminal.
Starting from an initial state built around the augmented start symbol of the grammar, repeatedly applying closure and goto across every possible grammar symbol eventually produces a complete collection of states, along with the transitions between them. This entire structure is often referred to as the canonical collection of LR(0) items, and it can be visualized as a finite automaton, where each state represents a set of items and each transition represents a goto operation on some grammar symbol.
This automaton forms the structural backbone shared by all three major LR parsing variants. What differs between SLR, CLR, and LALR is not how this collection of states is built, but rather how the resulting states are used to decide exactly when a reduction should occur.
Once the canonical collection of states has been constructed, it is used to build two tables that together drive the actual parsing process: the action table and the goto table.
| Table | Indexed By | Contains |
|---|---|---|
| Action Table | A state and a terminal symbol, including the end marker. | An instruction to shift to another state, reduce using a specific production, accept the input, or report an error. |
| Goto Table | A state and a non-terminal symbol. | The state to move to after a reduction produces that non-terminal. |
During parsing, the parser maintains a stack of states rather than grammar symbols directly, and at every step, it consults the action table using the current state and the next input token to decide exactly what to do next, whether that means shifting, reducing, accepting, or reporting a syntax error.
The general LR parsing algorithm follows a repeating cycle very similar in spirit to the shift-reduce process introduced in the bottom-up parsing tutorial, but with every decision now driven directly by table lookups rather than manual judgment.
Simplified Trace Structure: Stack: State0 Input: id + id $ Action Table Lookup: State0, id -> Shift to State3 Stack: State0 id State3 Input: + id $ Action Table Lookup: State3, + -> Reduce using Factor -> id Stack: State0 Factor StateX Input: + id $ Goto Table Lookup: State0, Factor -> StateX ... parsing continues in this fashion until the input is accepted ...
At every stage, the current state, sitting on top of the stack alongside its corresponding grammar symbol, together with the next input token, uniquely determines the parser's next move. This table-driven approach is what allows LR parsers to run efficiently, since each decision reduces to a simple, constant-time table lookup rather than any kind of search or guesswork.
SLR parsing, short for Simple LR, is the most basic and easiest to construct of the three LR variants. It builds its action table using the canonical collection of LR(0) items directly, and decides when a reduction is valid for a given item by checking whether the next input token belongs to the FOLLOW set of the non-terminal on the left-hand side of that production.
While SLR is relatively straightforward to construct, its reliance on FOLLOW sets, which are computed for a non-terminal as a whole rather than for a specific context in which that non-terminal appears, means it sometimes introduces conflicts for grammars that a more context-sensitive approach could actually handle correctly.
CLR parsing, short for Canonical LR, addresses this limitation by attaching a specific lookahead terminal directly to each item, rather than relying on a non-terminal's overall FOLLOW set. These enhanced items are often called LR(1) items, since each one carries exactly one token of lookahead alongside the usual dot notation.
Because CLR tracks lookahead information separately for every distinct context in which an item can appear, it is capable of correctly parsing a strictly larger class of grammars than SLR, resolving conflicts that SLR's more general FOLLOW-based approach cannot distinguish. This added precision comes at a real cost, however, since CLR parsing tables are typically significantly larger than SLR tables, since many more distinct states are needed to track this additional contextual information.
LALR parsing, short for Look-Ahead LR, aims to strike a practical balance between SLR and CLR. It starts from the same detailed LR(1) items used by CLR, but then merges together states that share the same underlying LR(0) items, differing only in their attached lookahead information, combining their lookaheads into a single merged state.
This merging step dramatically reduces the number of states compared to full CLR parsing, often bringing the table size down close to that of SLR, while still retaining most of the additional parsing power that comes from tracking context-specific lookahead information. Because of this favorable balance between power and table size, LALR parsing is the technique most widely used inside real-world, automatically generated parsers for production programming languages.
| Aspect | SLR | CLR | LALR |
|---|---|---|---|
| Basis for Reduction Decisions | FOLLOW sets of non-terminals. | Lookahead attached to each individual LR(1) item. | Merged lookahead from states sharing the same LR(0) core. |
| Grammar Coverage | Handles the smallest class of grammars among the three. | Handles the largest class of grammars among the three. | Handles a class of grammars nearly as large as CLR, in practice. |
| Table Size | Smallest. | Largest, often significantly so. | Close to SLR in size, despite handling more grammars correctly. |
| Typical Real-World Usage | Used mainly for smaller grammars or teaching purposes. | Used less often in practice due to its large table size. | Widely used inside real-world, automatically generated parsers. |
This comparison highlights why LALR parsing has become the dominant choice for practical compiler construction. It captures nearly all of the extra parsing power that makes CLR so capable, while avoiding the often impractically large tables that a full CLR implementation would require for a grammar as large and complex as a real programming language.
| Mistake | Correct Understanding |
|---|---|
| Assuming SLR, CLR, and LALR build completely different sets of parser states from scratch. | All three variants are built around the same underlying LR(0) item structure, differing mainly in how lookahead information is tracked and used to resolve reduction decisions. |
| Believing LALR parsing is exactly as powerful as CLR parsing in every case. | LALR parsing can, in rare cases, introduce conflicts that CLR would not have, as a side effect of merging states, though this is uncommon for grammars used in typical programming languages. |
| Thinking a larger parsing table is always undesirable, regardless of what it enables. | A larger table, as seen in CLR, allows correct handling of a broader class of grammars, representing a genuine trade-off between table size and grammar coverage, rather than a straightforward downside. |
| Treating the goto table as unrelated to the underlying automaton built from LR(0) items. | The goto table is directly derived from the goto operation used to build the canonical collection of states, describing exactly how the parser transitions between states after a reduction. |
LR parsing provides a fully table-driven approach to bottom-up parsing, built around LR(0) items that track how much of a production has been recognized, grouped into states using closure and goto operations, and ultimately compiled into action and goto tables that drive the entire parsing process. SLR, CLR, and LALR parsing all share this same underlying structure, differing mainly in how precisely they track lookahead information when deciding when a reduction is valid, which directly affects both the size of the resulting tables and the range of grammars each variant can correctly handle. LALR parsing, in particular, strikes a practical balance that has made it the most widely used LR variant in real-world compiler construction.
In this tutorial, you learned what LR(0) items are and how they are grouped into states using closure and goto, how the canonical collection of states forms the backbone of every LR variant, how action and goto tables drive the actual parsing algorithm, and how SLR, CLR, and LALR parsing differ from one another in terms of power, table size, and practical usage. With this foundation in place, you are ready to explore syntax directed translation, where the parse trees and structures built during parsing are used to compute meaningful information about a program as it is being parsed.