Bottom-Up Parsing
Learn how bottom-up parsers build the parse tree from the leaves to the root by reducing input tokens — and why they handle a much larger class of grammars than top-down parsers.
What is Bottom-Up Parsing?
In bottom-up parsing, the parser starts from the input tokens (leaves) and tries to reduce them, step by step, back to the start symbol (root) of the grammar.
It is the exact opposite of top-down parsing:
| Direction | Top-Down | Bottom-Up |
|---|---|---|
| Starts at | Start symbol S | Input tokens |
| Builds tree | Root → leaves | Leaves → root |
| Uses derivation | Leftmost | Rightmost (in reverse) |
| Operation | Expand a non-terminal | Reduce a substring to a non-terminal |
The Core Idea
At each step, the parser looks at a chunk of the current sentence and asks:
"Is there a production whose right-hand side matches this chunk? If so, replace the chunk with the left-hand side."
That replacement is called a reduction. Reducing all the way back to the start symbol means the input is valid.
A First Example
Grammar:
Input: id + id * id
We will reduce step by step. At each step we underline the substring we are about to reduce and show the production used.
The parser walked upward — from id + id * id (all leaves) to E (the root). This is why the technique is called bottom-up.
Handles — The Heart of Bottom-Up Parsing
At every step, the parser must decide which substring to reduce. That substring is called a handle.
Definition
A handle of a right-sentential form is a substring that:
- Matches the right-hand side of some production, and
- Reducing it produces the previous step of a rightmost derivation.
In other words, the handle is the correct place to reduce — the one that will lead the parser back to the start symbol.
Why Not Just Any Match?
Consider the string E + T * id from the grammar above. We could try to reduce in two places:
Picking the wrong substring leads to a dead end. The handle is the unique correct substring.
Handle in Action
Let's reduce id + id using E → E + T, T → F, F → id.
| String | Handle | Production | Result |
|---|---|---|---|
id + id | id (first) | F → id | F + id |
F + id | F | T → F | T + id |
T + id | T | E → T | E + id |
E + id | id | F → id | E + F |
E + F | F | T → F | E + T |
E + T | E + T | E → E + T | E ✓ |
The handle is always at or near the right edge of what the parser has seen so far — that's why bottom-up parsers use a stack to track the current state.
Bottom-Up = Rightmost Derivation in Reverse
Bottom-up parsing produces a rightmost derivation in reverse.
A rightmost derivation expands the rightmost non-terminal at every step (top-down view):
The bottom-up parser performs the same sequence — read bottom to top:
Each reduction undoes one step of the rightmost derivation — the parser is literally running the derivation backwards.
Why Rightmost?
Because the handle of any right-sentential form is always located at or to the right of every other non-terminal that still needs to be reduced. Reducing it is equivalent to reversing the most recent step of a rightmost derivation. This is what gives bottom-up parsers their efficiency — they only ever need to look at the top of a stack, not the entire string.
Building the Parse Tree from the Bottom
Top-down parsing draws the tree from the root downward; bottom-up parsing grows the tree from the leaves upward.
Let's revisit the input id + id with grammar E → E + T, T → F, F → id.
Step 1 — Each input token becomes a leaf.
Step 2 — Reduce each id using F → id. Two new internal nodes appear.
Step 3 — Reduce each F using T → F.
Step 4 — Reduce the leftmost T using E → T, then reduce E + T using E → E + T. The forest joins into one tree.
The parse tree is now complete. Notice how internal nodes were always created after their children existed — that is the defining trait of bottom-up parsing.
Why Bottom-Up? — Advantages and Limitations
Bottom-up parsing is the dominant technique in real-world compiler tools (yacc, bison, GNU Bison, Java CUP). Here is why.
Advantages
| Advantage | Detail |
|---|---|
| Handles a larger grammar class | LR(k) grammars include LL(k) grammars and many that LL cannot handle |
| No left-recursion problem | Left-recursive rules like E → E + T are natural for bottom-up parsers |
| No left-factoring required | Common prefixes do not cause trouble — the decision is made later, on lookahead |
| Better at expression grammars | Operator precedence and associativity fall out naturally |
Limitations
| Limitation | Detail |
|---|---|
| Harder to implement by hand | Tables are large; building them by hand is tedious |
| Less intuitive error messages | The parser only knows what it has seen so far, not what it was trying to build |
| Requires parser-generator tools | Almost always built with yacc/bison/ANTLR rather than handwritten |
| Shift/reduce and reduce/reduce conflicts | Must be detected and resolved during table construction |
Where It's Used
- Yacc/Bison/GNU Bison — LALR(1) parser generators used by C, C++, awk, Perl, PHP, Ruby and many more.
- GCC and Clang — historically used LALR; Clang now uses a hand-written predictive parser, but its grammar was originally designed against bottom-up techniques.
- PostgreSQL and MySQL — their SQL parsers are LALR(1) generated by Bison.
Quick Comparison with Top-Down
Categories of Bottom-Up Parsers
All bottom-up parsers share the same shift/reduce engine — they differ in how they decide which action to take.
Operator-Precedence Parser
Works only on operator grammars (no two non-terminals adjacent, no ε productions). Uses precedence relations between terminals to decide where the handle is. Simple to build by hand, but limited.
→ Covered in Operator Precedence Parsing.
LR(0)
Looks at no input to decide a reduction — uses only the current state of the parser. Very weak; many real grammars are not LR(0).
SLR(1) — Simple LR
LR(0) plus a one-token lookahead, where reductions are decided by the FOLLOW set of the non-terminal being reduced. Easy to build, handles most simple grammars.
→ Covered in Construction of SLR, CLR, LALR Parse Tables.
CLR(1) — Canonical LR
Full LR(1). Each parser state knows exactly which lookahead tokens justify each reduction. Most powerful, but produces very large tables (thousands of states for real languages).
LALR(1) — Look-Ahead LR
CLR(1) with states that share the same items merged together. Produces tables about the same size as SLR but is almost as powerful as CLR. This is the standard used by yacc and bison.
The Hierarchy
Each class strictly contains the one before it — i.e. every LR(0) grammar is SLR(1), every SLR(1) grammar is LALR(1), and so on. The practical sweet spot is LALR(1): it is almost as powerful as CLR(1) but with much smaller tables.