Bottom-Up Shift-Reduce Parsing

Recursive descent works top-down: it starts at the start symbol and guesses its way toward the leaves. Bottom-up parsing runs the film backwards. It starts with the raw tokens — the leaves — and repeatedly recognises little completed phrases, gluing them into ever-larger subtrees until the whole input has been folded up into the start symbol at the root. Where top-down parsing predicts, bottom-up parsing waits and confirms: it never commits to a production until it has seen the entire right-hand side. That patience is exactly what makes bottom-up parsers strictly more powerful, and it is the foundation of every LR parser (yacc, bison, and friends).

The dominant bottom-up technique is shift-reduce parsing. Picture a stack on the left and the unread input on the right. At every step you make one of two basic moves: push the next input token onto the stack (shift), or recognise that the top few stack symbols form the right-hand side of some production and replace them with its left-hand nonterminal (reduce). Keep going until the stack holds just the start symbol and the input is empty — that is accept.

The stack-and-input model

Write the configuration as stack | remaining input, with a marker (\$) for the end of input. Everything to the left of the bar has been seen and partly digested; everything to the right is still coming. The stack always holds a viable prefix of a right-sentential form — a prefix that could still be extended to a legal sentence. The parser's entire job is to decide, at each configuration, which of the four actions to take.

Shift — move the next input token onto the top of the stack.
Reduce — the top k stack symbols match the body of a production A \to \beta; pop those k symbols and push A in their place (building one internal AST node).
Accept — the stack is just the start symbol and the input is exhausted; announce success.
Error — no legal action applies; the input is not in the language.

A shift defers a decision ("I'll gather more before I judge"); a reduce is the moment of commitment where a subtree is finally built. A run of the parser is therefore a sequence of shifts and reduces, and the reduces — read in the order they happen — spell out the parse.

Handles: the phrase you are allowed to reduce

Not every substring that matches a production body may be reduced. Reducing the wrong one leads to a dead end. The substring you are actually permitted to fold at a given step is called the handle. Formally, for a right-sentential form \gamma = \alpha\beta w (with w a string of terminals), a handle is a production A \to \beta together with the position of that \beta such that replacing it with A yields the previous form in a rightmost derivation. Shift-reduce parsing is, precisely, handle pruning: find the handle, reduce it, repeat.

This connects to a deep symmetry. A shift-reduce parse traces a rightmost derivation in reverse. A top-down parser expands the start symbol forward down to the tokens; a bottom-up parser, by pruning handles, walks a rightmost derivation backward from the tokens up to the start symbol. Each reduce undoes one step of that rightmost derivation, which is why bottom-up parsers are also called LR — Left-to-right scan, Rightmost derivation.

Every reduce in a shift-reduce parse rewrites a handle, and the sequence of reduces, read in reverse, is a rightmost derivation of the input.
The handle always sits at the top of the stack — never buried inside it — which is exactly why a stack is the right data structure.

A full trace: parsing \texttt{id}+\texttt{id}*\texttt{id}

Take the classic ambiguity-free expression grammar E \to E + T \mid T, T \to T * F \mid F, F \to \texttt{id}, and parse \texttt{id}+\texttt{id}*\texttt{id}. Watch how the parser refuses to reduce E + T to E too early: it shifts the * instead, because the pending multiplication must be folded first. Precedence falls out of when the parser chooses to shift instead of reduce.

Step	Stack	Input	Action
1	\$	\texttt{id}+\texttt{id}*\texttt{id}\,\$	shift \texttt{id}
2	\$\,\texttt{id}	+\texttt{id}*\texttt{id}\,\$	reduce F\to\texttt{id}
3	\$\,F	+\texttt{id}*\texttt{id}\,\$	reduce T\to F
4	\$\,T	+\texttt{id}*\texttt{id}\,\$	reduce E\to T
5	\$\,E	+\texttt{id}*\texttt{id}\,\$	shift +
6	\$\,E+	\texttt{id}*\texttt{id}\,\$	shift \texttt{id}
7	\$\,E+\texttt{id}	*\texttt{id}\,\$	reduce F\to\texttt{id}
8	\$\,E+F	*\texttt{id}\,\$	reduce T\to F
9	\$\,E+T	*\texttt{id}\,\$	shift * (not reduce!)
10	\$\,E+T*	\texttt{id}\,\$	shift \texttt{id}
11	\$\,E+T*\texttt{id}	\$	reduce F\to\texttt{id}
12	\$\,E+T*F	\$	reduce T\to T*F
13	\$\,E+T	\$	reduce E\to E+T
14	\$\,E	\$	accept

Read the reduce lines from bottom to top: E\to E+T, T\to T*F, … — that is a rightmost derivation of \texttt{id}+\texttt{id}*\texttt{id} run in reverse. The parser rebuilt the tree from the leaves up, and the crucial move was step 9: with E+T on the stack and * waiting, it chose to shift. Reducing there would have wrongly grouped (\texttt{id}+\texttt{id})*\texttt{id}.

A shift-reduce driver, given an oracle

The mechanics of shift-reduce parsing are trivial once someone tells you which action to take at each step. Below, an oracle plays the role of the (as-yet-unbuilt) LR table: it looks at the stack and the lookahead and returns the action. The driver just obeys — shifting, reducing, and printing the trace. This is deliberately the whole point of the LR machinery to come: build a real oracle from the grammar.

type Action = | { kind: "shift" } | { kind: "reduce"; lhs: string; rhsLen: number; rule: string } | { kind: "accept" } | { kind: "error" }; // Grammar: E->E+T | T ; T->T*F | F ; F->id // A hand-coded oracle mimicking the precedence-correct LR decisions. function oracle(stack: string[], look: string): Action { const top = stack[stack.length - 1]; const top3 = stack.slice(-3).join(" "); // Reduce F -> id as soon as an id is on top. if (top === "id") return { kind: "reduce", lhs: "F", rhsLen: 1, rule: "F -> id" }; // Reduce T -> T*F when the top three are T * F. if (top3 === "T * F") return { kind: "reduce", lhs: "T", rhsLen: 3, rule: "T -> T*F" }; // Reduce E -> E+T when top three are E + T AND we are NOT about to multiply. if (top3 === "E + T" && look !== "*") return { kind: "reduce", lhs: "E", rhsLen: 3, rule: "E -> E+T" }; // Reduce T -> F, but only when F can't grow into T*F (i.e. next isn't '*'). if (top === "F" && look !== "*") return { kind: "reduce", lhs: "T", rhsLen: 1, rule: "T -> F" }; // Reduce E -> T when a lone T sits below the base and next is + or end. if (top === "T" && stack[stack.length - 2] !== "+" && (look === "+" || look === "$")) return { kind: "reduce", lhs: "E", rhsLen: 1, rule: "E -> T" }; if (top === "E" && look === "$") return { kind: "accept" }; if (look === "$") return { kind: "error" }; return { kind: "shift" }; } function parse(input: string[]): boolean { const stack: string[] = []; let i = 0; for (let guard = 0; guard < 1000; guard++) { const look = input[i] ?? "$"; const act = oracle(stack, look); const view = `[${stack.join(" ")}] . ${input.slice(i).join(" ")}$`; if (act.kind === "shift") { stack.push(look); i++; console.log(`${view.padEnd(28)} shift ${look}`); } else if (act.kind === "reduce") { for (let k = 0; k < act.rhsLen; k++) stack.pop(); stack.push(act.lhs); console.log(`${view.padEnd(28)} reduce ${act.rule}`); } else if (act.kind === "accept") { console.log(`${view.padEnd(28)} ACCEPT`); return true; } else { console.log(`${view.padEnd(28)} ERROR`); return false; } } return false; } parse(["id", "+", "id", "*", "id"]);

The trace it prints matches the table above line for line. The driver contains no intelligence at all — every genuinely hard decision lives inside oracle. Replace that ad-hoc oracle with a table computed from the grammar and you have a real, general parser. Building that table honestly is the entire subject of the next few pages.

You could, and that is essentially what a backtracking bottom-up parser does — with disastrous cost. Several stack tops may look reducible at once, but only one choice keeps you on the path to a valid parse; the others lead to eventual failure and a forced rewind. The genius of LR parsing, due to Donald Knuth in 1965, is that a deterministic finite automaton run over the stack can identify the handle in constant time per step, with no guessing or backtracking, for a remarkably large class of grammars. The DFA's states summarise "everything about the stack that could matter" — the set of viable prefixes seen so far — so the parser always knows whether the top of the stack is a complete handle or merely a prefix of one. That automaton is the star of the LR(0) items page.

A shift-reduce parser is only as good as its oracle, and for some grammar-and-lookahead situations no single correct action exists — the grammar itself is at fault (or too weak for the parsing method). Two kinds of deadlock arise:

Shift-reduce conflict — the parser could either shift the next token or reduce by some production, and both seem legal. The textbook example is the dangling else: after if C then S with an else waiting, should you reduce the if-then now, or shift the else to attach it to this if? Tools resolve this by a default (usually: prefer shift, binding else to the nearest if), but the conflict is real.
Reduce-reduce conflict — two different productions both match the top of the stack, and the parser cannot tell which subtree to build. This usually signals a genuinely ambiguous or badly factored grammar and is the more serious warning.

The whole hierarchy of LR parsers — SLR, LALR, canonical LR(1) — is a graded answer to how much lookahead information you spend to avoid these conflicts. Finding the handle deterministically is the problem; conflicts are what it looks like when you can't.