Bottom-Up Parsing

Bottom-Up Parsing

1. Idea

Bottom-up builds the tree from leaves (input) to root, finding a rightmost derivation in reverse. At each step it locates a handle (right side on stack top) and reduces it. More powerful than top-down — handles left recursion naturally.

2. Shift-Reduce Actions (stack + input)

Action	What happens
Shift	push next input token
Reduce A→β	pop 丨β丨 symbols, push A, emit production
Accept	stack = $S, input =$
Error	no valid move

3. Trace — id+id with E→E+T|T, T→id

stack        input    action
$            id+id$   shift
$id          +id$     reduce T→id
$T           +id$     reduce E→T
$E           +id$     shift +
$E+          id$      shift id
$E+id        $        reduce T→id
$E+T         $        reduce E→E+T
$E           $        accept

Handle is always on stack top when reducing rightmost derivation.

4. Conflicts

• Shift-reduce: both shift and reduce possible (dangling else).
• Reduce-reduce: two reduces possible. Resolved by lookahead (SLR/LR/LALR) or precedence directives.

5. Exam Points

• Trace shift-reduce parse with stack table — 7 marks, very frequent.
• Define handle, shift, reduce, accept — 3-5 marks, frequent.
• Top-down vs bottom-up comparison — 3 marks, frequent.