The idea: build the tree from the leaves up
An LL(1) parser works top-down: it starts from E and guesses, from one token, which production to expand. An LR parser works bottom-up. It reads tokens onto a stack (shift) and, when the top of the stack is the whole right side of a production, it replaces it by the left side (reduce). It does not have to choose a production before it has seen all of its right side. The name says it: read the input Left to right and build a Rightmost derivation, in reverse.
The page uses the expression grammar with left recursion, the natural way to write it. LL(1) cannot use this grammar, LR can. Production 0 is added so the parser knows when it is done.
0 E' → E 1 E → E + T 2 E → T 3 T → T * F 4 T → F 5 F → id
Shift, reduce and handles
The parser has two moves. Shift pushes the next token. Reduce by A → β
pops β from the top of the stack and pushes A. The β it pops is called a handle. The hard
question is when to reduce. With T on the stack and * next, reducing E → T would
be wrong: the T is the start of T * F. The parser needs to know where it is inside the productions. That is
what the states are for.
LR(0) items and states
An item is a production with a dot in it. E → E + · T means: the parser has
read E + and now expects a T. A state is a set of items, built with two operations:
- Closure. If a dot stands before a nonterminal X, the parser may be at the start of any X, so add X → · γ for every X production. Repeat until nothing new is added.
- Goto(I, X). Take the items of I with X after the dot, move the dot over X, and take the closure.
The start state I0 is the closure of E' → · E; it has 6 items. Following every goto from
every state gives 9 states, I0 to I8, and 12 transitions. A state reached a second time is not built again:
goto(I5, F) is I3 and goto(I6, id) is I4. On the canvas the kernel items (the ones goto made) are black and
the closure items are grey. (Demo: LR(0) item sets of the expression grammar)
The ACTION and GOTO table
The table has one row per state. ACTION has one column per token, GOTO one column per nonterminal:
- goto(Ii, a) = Ij on a token a gives ACTION[i, a] = sj (shift, then go to state j);
- goto(Ii, A) = Ij on a nonterminal gives GOTO[i, A] = j;
- a complete item A → β · in Ii gives rk, reduce by production k;
E' → E ·gives acc under$.
Where to put the reduce is the only difference between the table methods. LR(0) puts it under every token. SLR(1) (simple LR) puts it only under the tokens of FOLLOW(A), the tokens that can come right after A (the LL(1) page shows how FOLLOW is computed). Here FOLLOW(E) = {+, $} and FOLLOW(T) = FOLLOW(F) = {+, *, $}. The SLR table fills 26 of the 9 × 7 = 63 cells: 20 ACTION entries and 6 GOTO entries, with no conflict. (Demo: SLR table, reduces only under FOLLOW)
| state | id | + | * | $ | E | T | F |
|---|---|---|---|---|---|---|---|
| 0 | s4 | 1 | 2 | 3 | |||
| 1 | s5 | acc | |||||
| 2 | r2 | s6 | r2 | ||||
| 3 | r4 | r4 | r4 | ||||
| 4 | r5 | r5 | r5 | ||||
| 5 | s4 | 7 | 3 | ||||
| 6 | s4 | 8 | |||||
| 7 | r1 | s6 | r1 | ||||
| 8 | r3 | r3 | r3 |
The parser loop
The stack holds states with the grammar symbols between them, and starts as 0. Each move
looks at the state s on top and the lookahead token a:
- sj: push a and j, move to the next token.
- rk for A → β: pop 2·|β| entries (each symbol with its state). The state u now on top was waiting for an A, so push A and GOTO[u, A]. The lookahead is not used up.
- acc: stop, the input is accepted.
- empty cell: syntax error at this token.
The input id + id * id takes 14 moves: 5 shifts (one per token), 8 reduces and the accept.
The stack is longest just before the reduce by T → T * F, with 11 entries:
0 E 1 + 5 T 7 * 6 F 8. The first moves are:
| # | stack | input left | action |
|---|---|---|---|
| 1 | 0 | id + id * id $ | shift 4 |
| 2 | 0 id 4 | + id * id $ | reduce F → id |
| 3 | 0 F 3 | + id * id $ | reduce T → F |
| 4 | 0 T 2 | + id * id $ | reduce E → T |
| 5 | 0 E 1 | + id * id $ | shift 5 |
| 9 | 0 E 1 + 5 T 7 | * id $ | shift 6 |
Compare moves 4 and 9. In move 4, state 2 sees + and reduces E → T. In move 9, state 7 (also with T on top) sees * and shifts, because the T is the left part of T * F. The state and one token make the choice. Every move takes constant time, so the parse is linear in the input. (Demo: accept id + id * id)
Syntax errors
In id + * id the parser reduces the first id to E, shifts + and reaches state 5, where
only id can come next. ACTION[5, *] is empty, so move 6 reports an error at token 3. LR
parsers find an error at the first token that cannot continue any valid input, as early as an LL(1) parser
does. (Demo: reject id + * id)
Shift-reduce conflicts and how SLR removes them
A cell with two entries is a conflict. State I2 holds E → T · (complete,
wants to reduce) and T → T · * F (wants to shift *). LR(0) puts r2 under every token, so cell
[2, *] gets both s6 and r2: a shift-reduce conflict. State I7 has the same problem with
E → E + T ·. The LR(0) table has 31 filled cells and 2 conflicts, and the parser gets stuck on
id * id at move 4.
SLR asks one more question: can * come after E? FOLLOW(E) = {+, $}, so no. The reduce goes only under +
and $, and [2, *] keeps just s6. Both conflicts disappear, and id * id is accepted in 9 moves.
(Demo: LR(0) table has 2 shift-reduce conflicts, Demo: SLR resolves them, id * id
accepted)
When SLR is not enough
Some conflicts FOLLOW cannot remove. The ambiguous grammar E → E + E | id has 5 states. In I4 the
parser has E + E on top and sees another +. Reducing groups (id + id) + id, shifting groups id + (id + id),
and + is in FOLLOW(E), so cell [4, +] holds s3 and r1. The grammar has two parse trees for
id + id + id, and no LR method fixes that. Parser generators such as yacc and bison let the
author settle such conflicts with precedence and associativity rules (%left '+' means
reduce). (Demo: ambiguous E → E + E, SLR conflict stays)
There are also unambiguous grammars where FOLLOW is too rough, because it lumps together every place A can appear. LR(1) items carry their own lookahead token, and LALR(1), the method of yacc and bison, merges LR(1) states with the same items to keep the table as small as SLR's.
LR versus LL(1)
| LL(1), top-down | LR (SLR), bottom-up | |
|---|---|---|
| stack holds | what is still expected | what has been read: states and symbols |
| decides | the production before reading it | the production after reading all of it |
| left recursion | must be removed | fine (E → E + T is used here) |
| derivation | leftmost, in order | rightmost, in reverse |
| table rows | nonterminals (5 here) | states (9 here) |
| typical use | hand-written recursive descent | generated by yacc, bison |
See also LL(1) parsing, the top-down method with FIRST and FOLLOW sets, CYK parsing, a table method for any context-free grammar in cubic time, the pushdown automaton, the stack machine that an LR parser is, and Inside a Tiny Compiler for where the parser sits in a compiler.
See also the Earley parser, which completes bottom up like LR but keeps every alternative in a chart, so it can parse ambiguous grammars.
See also Three-Address Code, Basic Blocks and Local Optimizations for what a compiler does with the parsed program next.
What the page leaves out
The grammars and inputs are fixed presets, and the page does not draw the parse tree on the canvas. It
leaves out canonical LR(1) and LALR(1) tables, precedence declarations that resolve conflicts, ε
productions, error recovery (yacc's error token), and GLR parsers that follow both sides of a
conflict.