Bottom-Up Parsing Overview
What You'll Learn
You'll discover how bottom-up parsers work by building parse trees from the leaves (tokens) upward to the root (start symbol), the opposite direction of top-down parsing.
The Core Idea
Bottom-up parsing starts with the input tokens and gradually reduces them into higher-level grammar constructs until reaching the start symbol. Unlike top-down parsing (which predicts productions and expands from the start symbol), bottom-up parsing recognizes the right-hand sides of productions in the input and replaces them with their left-hand side nonterminals.
Think of it like assembling a jigsaw puzzle by first connecting small pieces into recognizable groups, then combining those groups into larger sections, and finally putting everything together to complete the picture. You're working from details to the big picture.
Shift-Reduce Parsing
The most common bottom-up technique is shift-reduce parsing, which uses two main actions:
- Shift: Move the next input token onto a stack
- Reduce: When the top of the stack matches the right-hand side of a grammar production, replace (reduce) those symbols with the production's left-hand side
For example, if your grammar has E → E + T and your stack contains E + T, you reduce it to E.
The parser continues shifting and reducing until either the entire input is consumed and the stack contains only the start symbol (success), or no valid moves remain (syntax error).
Why Bottom-Up?
Bottom-up parsers can handle a broader class of grammars than LL(1) parsers. They don't struggle with left recursion and can parse many practical programming language constructs more naturally.
Key Takeaway: Bottom-up parsing builds parse trees from tokens upward using shift-reduce operations, working from specific input patterns toward the general start symbol—the reverse of top-down parsing's approach.