Reading a derivation backwards
In guide 2 you built a top-down parser: it started from the start symbol and guessed its way down toward the input, choosing a rule and then trying to match what that rule predicted. Bottom-up parsing runs the same machinery in the opposite direction. It starts from the raw input — the leaves — and works up toward the start symbol, never guessing a rule until it has already seen the whole right-hand side sitting in front of it. Where top-down asks 'which rule should I expand next?', bottom-up asks 'have I just finished building some rule's right-hand side, and if so, can I fold it back into the left-hand side?' Folding finished pieces back is the entire idea.
Here is the cleanest way to picture it. A derivation starts at the start symbol and replaces a variable with a rule's right-hand side, step by step, until only terminals remain — that is the top-down view. A bottom-up parser produces exactly such a derivation, but discovers its steps in reverse, last step first. Each fold the parser makes — replacing a right-hand side by its left-hand side — is one derivation step undone. When the whole input has been folded all the way back to the start symbol, the parser has, in effect, reconstructed a derivation by reading it backwards. That is why bottom-up parsing is sometimes called 'reductive' parsing: every move reduces the string toward the start symbol.
Two moves and a stack
The whole mechanism runs on a stack and exactly two moves, which is why it is called shift-reduce parsing. The stack is the familiar stack of plates you met with the pushdown automaton: you only ever touch the top. To the right of the stack sits the unread input. A shift moves the next input token off the input and pushes it onto the stack — literally setting another plate on the pile. A reduce does the fold: when the symbols on top of the stack match the right-hand side of some rule, you pop them off and push the rule's single left-hand-side variable in their place. That is it: shift, shift, reduce, shift, reduce, until the stack holds only the start symbol and the input is empty.
Let us run it concretely on the expression grammar from guide 1 of the CFG rung: E -> E + T | T, T -> T * F | F, F -> ( E ) | id. We will parse 'id + id * id'. Read the trace below row by row. Notice the rhythm: the parser shifts tokens until the top of the stack matches a right-hand side, then reduces. The deep magic is choosing when to reduce rather than shift one more token — and the trace quietly makes the right choice every time so that '*' binds tighter than '+'.
Shift-reduce parse of id + id * id (rules: E->E+T | T , T->T*F | F , F->(E) | id) STACK INPUT ACTION (empty) id + id * id $ shift id id + id * id $ reduce F -> id F + id * id $ reduce T -> F T + id * id $ reduce E -> T E + id * id $ shift + E + id * id $ shift id E + id * id $ reduce F -> id E + F * id $ reduce T -> F E + T * id $ shift * <-- do NOT reduce E+T yet! E + T * id $ shift id E + T * id $ reduce F -> id E + T * F $ reduce T -> T * F E + T $ reduce E -> E + T E $ ACCEPT The held-back reduce at the marked line is exactly what makes * bind tighter than +. Reading the ACTION column bottom to top spells out a rightmost derivation, run in reverse.
The handle: where to fold, and why it is hard
Look back at that trace and ask the only question that matters: at each step, *should I shift or reduce, and if I reduce, which rule and which symbols?* The right substring to fold at any moment has a name — it is called the handle. Formally, a handle is the right-hand side of a rule sitting in just the right spot so that reducing it takes you one step backward along a rightmost derivation. Find the handle correctly at every step and the parse marches straight to the start symbol. Pick the wrong substring — reduce something that looks like a right-hand side but is not the true handle — and you wander off into a dead end.
Two subtle warnings live inside that definition. First, a handle is not just 'any substring that equals some right-hand side'. In the trace, after 'E + T' appears on the stack with '* id' still waiting, the symbols 'E + T' do form the right-hand side of E -> E + T — yet reducing there would be wrong, because the true handle is further to the right. A substring can match a rule and still not be the handle; the handle depends on the whole context, not just on shape. Second, the handle always sits on top of the stack in a correct shift-reduce parse — that is the deep reason a stack is the right data structure here. You never have to dig.
So all the difficulty of bottom-up parsing collapses into one question: how does the parser know, looking only at the stack top plus maybe one upcoming token, whether it is staring at a handle right now? A naive parser would have to backtrack — try a reduce, fail, undo, try shifting instead. Backtracking is correct but slow. The triumph of the LR family is to answer the handle question deterministically, with no backtracking at all, by precomputing a finite-state table that reads the stack-top context and dictates the move. That table is the subject of the next section.
The LR family and the table that decides
LR parsing is shift-reduce parsing made deterministic. The 'L' means it reads input Left to right; the 'R' means it builds a Rightmost derivation (in reverse, as we saw). The trick is that the set of stack contents a correct parser can ever reach is itself a regular language — and a regular language is recognized by a finite automaton. So an LR parser builds, once and ahead of time, a DFA whose states summarize 'everything about the stack that matters for deciding the next move'. At parse time the parser just feeds the stack through this DFA and lands in a state that says, unambiguously, 'shift' or 'reduce by rule R'.
LR comes in a ladder of strengths, all sharing this skeleton but differing in how much lookahead the table uses. LR(0) uses no lookahead token at all. SLR and LALR(1) use one lookahead token, computed with the FIRST and FOLLOW sets you met in guide 2; LALR(1) is the sweet spot that real tools generate because its tables stay small. Canonical LR(1) is the most powerful one-token version, at the cost of much bigger tables. Do not memorize the alphabet soup — the point is that all of them answer the same handle question, and stronger variants simply distinguish more situations before declaring a conflict.
Why is LR strictly more powerful than the LL parsing of guide 2? Because LR gets to decide much later. An LL(1) parser must commit to which rule it is expanding before seeing the rule's contents — it predicts from the very first token. An LR parser may shift the entire right-hand side onto the stack and only then decide which rule produced it. Seeing the whole production before committing is a huge advantage: every grammar an LL(1) parser can handle, an LR(1) parser can handle too, but not the reverse. In particular LR parsers do not require you to remove left recursion — they actually prefer left recursion, since it keeps the stack shallow.
Conflicts, and the honest limits
Sometimes the table cannot decide. When a state would tell the parser both 'shift' and 'reduce' for the same lookahead, that is a shift-reduce conflict; when it would reduce by two different rules at once, that is a reduce-reduce conflict. A conflict means this particular grammar is not LR for the chosen amount of lookahead — the table genuinely cannot tell, from what it is allowed to see, whether the top of the stack is a handle. The classic everyday example is the 'dangling else': in 'if C then if C then S else S', does the 'else' attach to the inner or the outer 'if'? The grammar permits both, so the table sees both a shift and a reduce.
Real parser generators do not just give up on conflicts — they resolve them with declared precedence and associativity. You tell the tool '* binds tighter than +' and 'else attaches to the nearest if' (the standard rule), and it uses those declarations to pick shift or reduce at each conflicted state. This is exactly the layered-variable trick from the CFG-design guide, but moved out of the grammar and into a side table of preferences. It keeps the grammar small and readable while still forcing the one tree you mean. The next guide on parser generators shows the concrete syntax for these declarations.
One last honest boundary. LR parsers are powerful but they still only handle deterministic context-free languages — the same class accepted by the deterministic pushdown automaton. Not every context-free grammar is LR for any fixed lookahead, and some context-free languages are not deterministic at all, so no LR table exists for them. When you genuinely need to parse such a grammar — including ambiguous ones, or natural language — you reach for the general algorithms CYK and Earley in the next guide, which trade speed for the ability to handle any context-free grammar.