Shift-Reduce Parsing
Watch a stack and a parse tree build each other — and see exactly where operator precedence is decided.
Skip to the animationA shift-reduce parser holds a stack of grammar symbols and repeatedly makes one of two choices — push the next token, or replace the top of the stack with the left-hand side of a production — until the stack is the start symbol and the input is gone.
Bottom-up parsing
A grammar reads top-down: E can be E + T, and T can be T * F, and so on. A shift-reduce parser works the other way — it starts with the tokens and assembles them into larger and larger subtrees until one tree covers the whole input. It builds the parse tree from the leaves up, and it discovers the derivation in reverse.
The grammar in the animation is the standard expression grammar, and the layering is the entire trick — F is an atom, T is a product of atoms, E is a sum of products. Precedence is built into the shape of the rules:
| Production | Reads as |
|---|---|
| E → E + T | a sum is a sum plus a product |
| E → T | …or just a product |
| T → T * F | a product is a product times an atom |
| T → F | …or just an atom |
| F → id | ( E ) | an atom is a name, or a bracketed sum |
The two moves
- Shift
- Push the next input token onto the stack. What the parser does when it does not yet have enough on the stack to recognise anything.
- Reduce
- The top of the stack matches the right-hand side of some production — pop those symbols and push the left-hand side. Every reduce builds exactly one tree node, with the popped symbols as its children.
- Handle
- The substring at the top of the stack that is the right thing to reduce right now. Finding handles is the whole difficulty; an LR parser precomputes them into a table.
- Accept
- Stack holds only the start symbol and the input is exhausted. The one remaining tree is the parse tree.
Where the difficulty actually is
Watch step 9. The stack holds E + T, which is exactly the right-hand side of E → E + T, so a reduce is legal. But the next token is *, and reducing now would group (id + id) * id — the wrong answer.
So the parser shifts instead, finishes the multiplication, and only reduces the addition afterwards. Operator precedence lives in that choice, not in the productions. The grammar alone is ambiguous about it; the shift-reduce decision resolves it.
- Shift-reduce conflict
- Both moves are legal in the same configuration. Resolved by lookahead, or by declared precedence — yacc-style tools shift by default, which is usually what you want.
- Reduce-reduce conflict
- Two different productions match the stack top. Almost always a sign the grammar itself is wrong.
- The dangling else
- The famous shift-reduce conflict: given
if a then if b then x else y, whichifowns theelse? Shifting attaches it to the nearest one, which is what every mainstream language specifies.
Where the table comes from
A real parser does not guess. It precomputes a table from the grammar, indexed by state and lookahead, that says shift, reduce, accept or error for every configuration. The families differ only in how much context they keep:
| Parser | Table size | Grammars accepted |
|---|---|---|
| LR(0) | smallest | very few — no lookahead at all |
| SLR(1) | small | more, using FOLLOW sets to decide reduces |
| LALR(1) | same as SLR | most real languages — what yacc and bison generate |
| CLR / LR(1) | largest | every LR(1) grammar |
The animation runs the moves without showing the table. The sequence of shifts and reduces is identical either way — the table only decides which move to make, and does it in constant time.
Advantages and disadvantages
Advantages
- Handles a strictly larger class of grammars than any top-down method, including left recursion.
- Linear time in the length of the input, with one stack and a table lookup per step.
- Detects an error at the earliest possible token, which makes for good messages.
Disadvantages
- The tables are far too large and intricate to build by hand — you need a generator.
- Conflicts are reported in terms of item sets, which is a famously unhelpful way to be told your grammar is wrong.
- Recursive-descent parsers are easier to read and debug, which is why several major compilers use them despite the weaker guarantees.
Watch it work
Check yourself
question 1 / 4
One question at a time. Pick an answer to see why it is right or wrong, then move on — there is no score to keep and nothing is saved.