CD Notes
Comprehensive guide to bottom-up parsing covering shift-reduce parsing, handles, viable prefixes, LR parsing overview, and comparison with top-down parsing approaches.
Introduction
Bottom-up parsing builds the parse tree from leaves (input tokens) up to the root (start symbol). It repeatedly identifies a substring matching the right-hand side of a production (called a handle) and replaces it with the corresponding left-hand side non-terminal. This process is called reduction, and it traces a rightmost derivation in reverse.
Shift-Reduce Parsing Mechanism
Components
- Input buffer: remaining input tokens
- Stack: holds grammar symbols (partial parse tree)
- Actions: Shift, Reduce, Accept, Error
Actions
Shift: Push next input token onto stack
Reduce: Pop RHS symbols, push LHS non-terminal
Accept: Stack has start symbol and input is empty
Error: No valid action available
Example: Grammar E → E+T | T, T → T*F | F, F → id
Input: id + id * id $
Stack Input Action
$ id + id * id $ Shift
$ 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
$ E + id * id $ Reduce F → id
$ E + F * id $ Reduce T → F
$ E + T * id $ Shift (not reduce! * has higher prec)
$ E + T * id $ Shift
$ E + T * id $ Reduce F → id
$ E + T * F $ Reduce T → T*F
$ E + T $ Reduce E → E+T
$ E $ ACCEPT
Handles
| A handle of a right-sentential form γ is a production A | β and a |
| "id+id*id" handle: id at position 1 (F | id) |
| "F+id*id" handle: F at position 1 (T | F) |
| "T+id*id" handle: T at position 1 (E | T) |
| "E+id*id" handle: id at position 3 (F | id) |
| "E+F*id" handle: F at position 3 (T | F) |
| "E+T*id" handle: id at position 5 (F | id) |
| "E+T*F" handle: T*F at position 3-5 (T | T*F) |
| "E+T" handle: E+T at position 1-3 (E | E+T) |
| "E" | DONE |
Viable Prefixes
| Property | A viable prefix never extends past the right end of the handle. |
| Viable prefixes include | E, E+, E+T, E+T*, E+T*F, E+T*id, ... |
| NOT viable | E+T*F+ (extends past handle) |
| If the stack is NOT a viable prefix | error detected. |
Types of Bottom-Up Parsers
| Operator | Simple, for expression grammars only |
|---|---|
| Precedence | Based on precedence relations |
| LR(0) | Simplest LR, few grammars supported |
| SLR(1) | Uses FOLLOW sets for lookahead |
| CLR(1) | Full LR(1), most powerful, large tables |
| (canonical) | |
| LALR(1) | Merges CLR states, practical (yacc) |
LR Parsing Overview
| Parsing | |
|---|---|
| Table | |
| ACTION|GOTO |
Comparison: Top-Down vs Bottom-Up
| Feature | Top-Down | Bottom-Up |
|---|---|---|
| Direction | Root → Leaves | Leaves → Root |
| Derivation | Leftmost | Rightmost (reverse) |
| Grammar class | LL(k) | LR(k) |
| Left recursion | Cannot handle | Handles naturally |
| Power | Less powerful | More powerful |
| Error detect | Early (top-down) | Late (bottom-up) |
| Implementation | Recursive/table | Table-driven |
| Tools | ANTLR, LL parsers | yacc, bison, PLY |
Interview Questions
- Q: Why is bottom-up parsing more powerful than top-down?
A: Bottom-up parsers can handle left-recursive grammars (which top-down cannot) and a larger class of CFGs. LR grammars are a proper superset of LL grammars. The key reason: bottom-up parsers delay the decision of which production to use until they've seen the entire right-hand side, while top-down must decide seeing only the first token.
- Q: What is the significance of handles in bottom-up parsing?
A: The handle identifies exactly which substring to reduce and to what non-terminal, corresponding to one step in the reverse of a rightmost derivation. Finding the correct handle is the central challenge of bottom-up parsing — LR parsing tables encode this decision efficiently.
- Q: Can shift-reduce parsing have conflicts?
A: Yes. Shift-reduce conflict: unclear whether to shift next token or reduce current handle. Reduce-reduce conflict: unclear which of multiple possible reductions to apply. These conflicts mean the grammar is not in the target LR class. Resolution: use stronger parser (SLR→LALR→CLR), rewrite grammar, or add disambiguation rules.
- Q: Why do most practical compilers use bottom-up (LR) parsing?
A: LR parsers handle a larger class of grammars without needing grammar transformations (left factoring, left recursion elimination). They detect errors as soon as possible (at the first token that cannot be part of any valid program). Tools like yacc/bison make LALR(1) parser generation automatic.
- Q: What is the time complexity of LR parsing?
A: O(n) where n is the input length. Each token is shifted exactly once and each reduction takes constant time (table lookup). The stack depth is bounded by the longest rightmost derivation path, which is O(n) in the worst case but typically much smaller.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Bottom-Up Parsing in Compiler Design.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.
Search Terms
compiler-design, compiler design, compiler, design, syntax, analysis, bottom, parsing
Related Compiler Design Topics