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 parse tree of id + id * id. Each inner node is numbered by the reduce that builds it: 1 F from the first id, 2 T, 3 E, 4 F and 5 T from the second id, 6 F from the third id, 7 T → T * F, 8 E → E + T at the root. The leaves are built first and the root last.
An LR parser builds the tree bottom up: the numbers are the order of the 8 reduces, and the root E comes last.

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 LR(0) automaton of the expression grammar: 9 states I0 to I8 drawn as boxes with their kernel items, and arrows labelled with the symbol that moves the dot: from I0 on E to I1, on T to I2, on F to I3, on id to I4; I1 on + to I5; I2 on * to I6; I5 on T to I7, on F to I3, on id to I4; I6 on F to I8, on id to I4; I7 on * to I6. The states with a complete item (dot at the end) are green. Three more transitions go back to old states: I5 on F to I3, I5 on id to I4, I6 on id to I4.
The 9 states and 12 goto transitions. A state with a dot at the end of an item (green) can reduce.

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)

stateid+*$ETF
0s4123
1s5acc
2r2s6r2
3r4r4r4
4r5r5r5
5s473
6s48
7r1s6r1
8r3r3r3

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:

#stackinput leftaction
10id + id * id $shift 4
20 id 4+ id * id $reduce F → id
30 F 3+ id * id $reduce T → F
40 T 2+ id * id $reduce E → T
50 E 1+ id * id $shift 5
90 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)

State I2 with the items E → T · and T → T · * F. Row 2 of the LR(0) table: r2 under id, r2 under +, s6 and r2 under *, r2 under $; the * cell is a conflict. Row 2 of the SLR table, using FOLLOW(E) = {+, $}: empty under id, r2 under +, s6 under *, r2 under $; no conflict.
Row 2 before and after: SLR keeps the reduce only under FOLLOW(E) = {+, $}, so the * cell holds only the shift.

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-downLR (SLR), bottom-up
stack holdswhat is still expectedwhat has been read: states and symbols
decidesthe production before reading itthe production after reading all of it
left recursionmust be removedfine (E → E + T is used here)
derivationleftmost, in orderrightmost, in reverse
table rowsnonterminals (5 here)states (9 here)
typical usehand-written recursive descentgenerated 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.

On the mind map

Open the Java & the JVM mind mapJava & the JVMFrom source to bytecode: translate first, or while runningFrom source to bytecodeStartup and class loading: what happens before main()Startup and class loadingJIT compilers: compile hot code using profilesJIT compilersMemory and GC: find and free unreachable objectsMemory and GCCollections: how java.util stores keysCollectionsThreads and memory model: Java threads on real coresThreads and memory modelSpring framework: a container builds your objectsSpring frameworkCompiler vs interpreterCompiler vs interpretercompile once ahead, or decode every runTiny compilerTiny compilerlexer, parser, code generator, VMThree-address codeThree-address codeFold + copy prop make code dead: 15→13Hindley-Milner inferenceHindley-Milner inferenceEquations per node, unify into SStatic vs Dynamic ScopingStatic vs Dynamic ScopingWritten-in vs called-from decides xLL(1) ParsingLL(1) ParsingStack top + one token pick the productionLR parsingShift tokens, reduce handles bottom upjavacjavacsource to type-checked .class bytecodeLambdas and invokedynamicLambdas and invokedynamicfirst call bootstraps, then links onceOpen the Java & the JVM mind mapJava & the JVMtranslate first, or while runningFrom source to bytecodeCompiler vs interpreterCompiler vs interpretercompile once ahead, or decode every runTiny compilerTiny compilerlexer, parser, code generator, VMThree-address codeThree-address codeFold + copy prop make code dead: 15→13Hindley-Milner inferenceHindley-Milner inferenceEquations per node, unify into SStatic vs Dynamic ScopingStatic vs Dynamic ScopingWritten-in vs called-from decides xLL(1) ParsingLL(1) ParsingStack top + one token pick the productionLR parsingShift tokens, reduce handles bottom upjavacjavacsource to type-checked .class bytecodeLambdas and invokedynamicLambdas and invokedynamicfirst call bootstraps, then links once
This page on the Java & the JVM mind map · 35 pages in 7 branches · open it to see the whole map and test yourself in recall mode.