Motivation
A grammar says which words exist and what structure they have; a parser must recover that structure from the input, reading from left to right and deciding at each point what to do next. Bottom-up parsing keeps a stack of symbols already read and repeatedly decides between two kinds of action: shift, which moves the next input symbol to the stack, and reduce, which replaces the symbols forming the right-hand side of a rule by its left-hand variable. The difficulty is deciding when a reduction is justified. LR parsing answers this using a finite automaton over grammar symbols whose states are sets of partially recognized rules.
This unit develops the LR(0) machinery for small grammars, defines LR(k), and shows with a minimal example why lookahead changes what can be parsed. It does not build tables for arbitrary LR(k) grammars or treat LALR.
Definitions
Definition 3.1.1
(Augmented grammar and end marker)
Given a context-free grammar , its augmented grammar adds a fresh variable and the rule , with as new start. The symbol is the end marker, placed after every input word. Since occurs on no right-hand side, the rule is used exactly once in each derivation, as its first step.
Definition 3.1.2
(LR(0) items, closure and goto)
An LR(0) item is a rule with a marked position in its right-hand side, written for a rule . For a set of items, is the least set such that whenever and is a rule, also . For a grammar symbol ,
The canonical collection is the least family of item sets containing and closed under for all symbols , discarding empty results.
Definition 3.1.3
(Parsing table and shift-reduce parser)
Number the rules and index the states by . The ACTION table has a row for each state and a column for each terminal and for ; the GOTO table has a column for each variable. Entries are defined by:
- if with and , then contains shift ;
- if with , then contains reduce for every ;
- if , then contains accept;
- for variables .
An entry with two or more actions is a conflict: shift/reduce if it contains a shift and a reduce, reduce/reduce if it contains two reductions (and similarly for accept). The grammar is LR(0) by table if no entry contains more than one action.
A parser configuration consists of a stack alternating states and symbols, and the remaining input. Let be the next input symbol (or ). If is shift , push and and advance. If it is reduce , pop entries, let be the state now on top, and push and without advancing. If it is accept, stop with success. A blank entry is an error.
Concept lensStructural
The stack as a path in a finite automaton
View the canonical collection as a deterministic automaton over grammar symbols: states are item sets and the transitions are the gotos. The parser's stack records the path taken from , and a reduction by rewinds that path by steps and then takes the -transition from the state reached. Thus the stack is always a path in a finite graph, and the only infinite resource of the parser is the length of that path.
For the soundness argument below, use a checked reduction: before reducing , verify that the top grammar symbols spell exactly , that enough symbol-state pairs exist, and that the resulting GOTO entry is defined. Otherwise report an error. This explicit guard lets the elementary reverse-derivation proof stand on its own; the usual viable-prefix theorem justifies omitting this check in a fully developed LR implementation.
Definition 3.1.4
(LR(k) grammar)
Let be augmented and . For a terminal string , write for the first symbols of . The grammar is LR(k) if the following holds. Whenever and with terminal strings, and , then , and . Here denotes a step replacing the rightmost variable.
In words: after the stack contents have been seen, the next input symbols determine which rule to reduce and where. The case allows no lookahead for this decision.
Theorems
Theorem 3.1.5
(Closure, goto and the canonical collection are well defined and finite)
For any finite set of items of a finite grammar, exists, is finite, and satisfies . The canonical collection exists and is finite, with at most members where is the number of items of the grammar.
Proof
(Least fixed point of the closure step)
Let and let be together with all items demanded by items of with the dot before . The chain is increasing and every lies in the finite set of items of the grammar, so it stabilizes at a set . This is closed and contains . Any closed contains every by induction on , so is the least such set. Since is already closed and contains itself, the least closed superset of is , which proves idempotence. Each is then a finite set of items. The canonical collection is built by repeatedly adding any goto not already present; every member is a subset of the finite item set, so there are at most possibilities and the process terminates.
Theorem 3.1.6
(Reductions performed by a parser form a rightmost derivation)
Let be an augmented grammar and suppose the shift-reduce parser, run with any parsing table built by the rules above, accepts . Then , and the reductions performed, taken in reverse order, are the steps of one rightmost derivation. In particular .
Proof
(Reading the reductions backwards)
Fix an accepting run on . At each time let be the symbols on the stack and the remaining input (a terminal string), and set . Initially the stack has no symbols, so . A shift moves a terminal from the input to the stack top and leaves unchanged. A reduction by transforms into ; since is terminal, is the rightmost variable of , so is a rightmost step. Chaining these gives a rightmost derivation from the final to . It remains to show the final is . Acceptance happens in a state containing . Because appears on no right-hand side, the only set containing is , and the only transition producing an item is . Moreover is never a goto target, since every goto target contains an item with the dot after at least one symbol, while every item of has the dot at the start. So state occurs only at the stack bottom, and the accepting stack is exactly with remaining input empty. Hence the final is .
Proof X-ray
Why the soundness proof does not need the whole automaton theory
The assumption used is only that a reduction pops exactly the right-hand side of the rule it names and that terminals are the only things shifted. The correctness of table entries (that the dot-items really describe viable prefixes) is not used, so the theorem is a safety statement: whatever the parser accepts is derivable. What it does not say is that every word of the language is accepted, nor that the parser is deterministic. Completeness needs the theory of valid items, which is not developed here, and determinism needs the absence of conflicts.
Proof sketch or proof idea
Theorem 3.1.7
(The parser for )
Augment with and number the rules , . The canonical collection has exactly five states: , , , , , with , , , , , . The table has no conflicts, and the parser accepts exactly when .
Proof
(Items, gotos and traces for the tiny grammar)
The listed item sets and gotos follow directly from the definitions: closure of adds the two rules for ; moving the dot over , and gives , the kernel whose closure adds and , and ; from , the symbol gives , while and return to and . No other gotos exist, so the collection is closed. States contain a single complete item and no item with a terminal after the dot, so their rows have one action each; and contain no complete item, so they have only shifts. Hence there is no conflict. For acceptance we trace. A word is processed by shifts from or to , a shift of to , a reduction by landing in (from ) or in (if , from ), then, if , reductions by , each popping two pairs and replacing them by over the state beneath, finally reaching over , and acceptance on . Conversely, an input outside either exhausts the input in or where has no entry, reads a symbol after , or reaches with a terminal, and in each case meets a blank entry. The reduction in is performed for every lookahead, so such an error may be detected one reduction later than the offending symbol; this is a feature of LR(0).
Theorem 3.1.8
(Lookahead separates LR(0) from LR(1))
The grammar is not LR(0) and is LR(1). The table of its LR(0) automaton has a shift/reduce conflict in the state reached on .
Proof
(The conflict after a, and the LR(1) check)
For , the augmented grammar has items in , and . The first item gives reduce on every terminal, including , and the second gives shift on , so the entry for contains two actions. Take with , , , , and with , , . Then with . For the lookahead condition is vacuous, but , so the grammar is not LR(0). For , , so this pair is not constrained. To verify the LR(1) condition, list all reduction contexts. There are three, each with : the step with , the step with , and the step with . A pair can satisfy only if the second string has the first context's as a prefix. The string is a prefix of neither nor and vice versa, and is not a prefix of . Identical contexts satisfy the conclusion trivially. The only remaining pair is the one treated above, where the lookahead hypothesis fails. So the LR(1) condition holds.
Counterexample mode
Unambiguous does not mean LR(0)
Claim (false): a grammar with exactly one parse tree for every word can be parsed with no lookahead. The grammar is unambiguous, since the two words have trees of different shapes and each word has one. Yet its LR(0) automaton has a state with the complete item and the item , so after reading the parser cannot decide between reducing and shifting . With one symbol of lookahead the decision is forced: reduce on , shift on . Repair: allow lookahead, as in the LR(1) definition. It is a standard fact, not proved here, that LR(k) grammars are unambiguous; this example shows unambiguity alone is not enough for .
Worked examples
Worked example 3.1.9
(The complete table for )
Rules: , . A blank entry is an error.
| State | ||||
|---|---|---|---|---|
| 0 | shift 2 | shift 3 | 1 | |
| 1 | accept | |||
| 2 | shift 2 | shift 3 | 4 | |
| 3 | reduce 2 | reduce 2 | reduce 2 | |
| 4 | reduce 1 | reduce 1 | reduce 1 |
Each row of the reduction states shows the LR(0) trait: a complete item reduces on every terminal. No row has two actions, so the grammar is LR(0) by table.
Worked example 3.1.10
(Parsing aab)
Start with stack and input . Shift : stack , input . Shift : , input . Shift : , input . Reduce by rule (): pop one pair, leaving top state , and push with : . Reduce by rule (): pop two pairs, leaving top state , push : . Reduce by rule again: pop two pairs, leaving , push with : . On the entry in state is accept. The reductions in reverse give , a rightmost derivation, as the soundness theorem predicts. For the word alone the parse is shorter: shift to state , reduce by rule with , and accept.
Worked example 3.1.11
(A conflict that lookahead resolves, and one that it does not)
For , the state after is and the entry for is shift/reduce in the LR(0) table. With lookahead sets, is reducible only when the next symbol can follow , here only , so the conflict disappears. Now take . After the state contains and . The symbols that can follow are and , so reduction on is allowed and shifting is also allowed. The conflict persists with one symbol of lookahead, because the grammar is ambiguous and the two actions correspond to two different parse trees.
Common mistakes
One further point concerns bookkeeping. Do not conflate the stack of symbols with the stack of states: the symbols spell a viable prefix, while the states record the automaton's position, and a reduction pops by the length of the right-hand side measured in symbols.
Common mistake
(Zero lookahead is not zero input)
Do not read "LR(0)" as "the parser never looks at the input". Shifts depend on the next terminal; zero lookahead refers to the decision to reduce, which must be determined by the state alone.
Common mistake
(Goto without closure)
Computing without the closure step loses the items for variables immediately following the dot. For the moved set would give no shift on or .
Common mistake
(More lookahead does not cure ambiguity)
Do not believe that adding more lookahead makes every grammar parseable: ambiguity is independent of the length of lookahead. The example above shows this: its conflict persists for every .
Summary
LR parsing runs a stack-based shift-reduce loop guided by the automaton of item sets. Closure and goto are well defined, and the canonical collection is finite. Whatever such a parser accepts is derivable, and the reductions form a rightmost derivation in reverse. For the table has five states and no conflict; the word is parsed explicitly. The grammar shows that one symbol of lookahead can resolve a conflict that zero lookahead cannot.
Exercises
Quick check
(Construct the canonical collection and the table for the augmented grammar .)
Closures first, then gotos.
Solution · Answer
Number the rules and . States: ; ; ; ; ; ; also and . Table: row 0: shift 2 on , shift 3 on , GOTO is 1; row 1: accept on ; row 2: shift 2 on , shift 3 on , GOTO is 4; row 3: reduce 2 on ; row 4: shift 5 on ; row 5: reduce 1 on . No conflicts.
Quick check
(For that grammar, give the stack and input at each step of parsing .)
Track states and symbols.
Solution · Answer
Stack and remaining input: with ; shift: with ; shift: with ; shift : with ; reduce 2: ; shift : with ; reduce 1 pops three pairs, leaving , push with GOTO: ; shift : with ; reduce 1 pops three pairs, leaving , push : ; accept.
Quick check
(Show that , , has a reduce/reduce conflict in its LR(0) table, and relate it to the grammar.)
Inspect the state after , then .
Solution · Answer
After the state is and , which has two reductions on every column: a reduce/reduce conflict. It reflects ambiguity: has two parse trees, one through and one through .
Quick check
(Prove that for finite item sets , and give an example showing that need not equal as defined above.)
Use minimality of closure.
Solution · Answer
The set contains and is closed, because if an item with the dot before lies in either part, the demanded items lie in the same part. By minimality, . Conversely, is a closed superset of , so it contains , and likewise ; hence . For the example, in the grammar with the definition gives , since no item of has the dot before , while . This is why the definition applies goto to closed item sets, such as the members of the canonical collection.