Chapter 4

Parse Trees & Derivations

How grammars generate strings — and why the order of expansion is the fundamental difference between top-down and bottom-up parsing. The critical insight: LR = Rightmost Derivation in Reverse.

Parse Trees Leftmost Derivation Rightmost Derivation LR = Reverse Rightmost
Section 1

What is a Parse Tree?

A parse tree is a visual representation of a derivation. It captures the grammatical structure of an input string, showing which rules were applied to derive it from the start symbol.

🔵

Internal Nodes

Each internal node is a non-terminal. Its children represent the right-hand side of the production rule that was applied.

🟢

Leaf Nodes

Each leaf node is a terminal or ε. Reading leaves left-to-right gives you the original input string.

🟠

Root Node

The root is always the start symbol S (or E in our grammar). Every derivation begins here.

🟣

Unique Tree

An unambiguous grammar produces exactly one parse tree per input string. Ambiguous grammars are problematic for parsers.

🎬 Building the Parse Tree for id + id * id

Parse Tree Construction — LL(1) Grammar
Step 0 / 12
Current sentential form:
E
0 E Start Symbol
🔑 Key Insight: The parse tree is the same regardless of whether we derive leftmost or rightmost. Only the order of node visits differs between derivation strategies — the final tree structure is identical!
Section 2

Leftmost Derivation

In a leftmost derivation, at each step we always expand the leftmost non-terminal. This is the strategy used by top-down parsers (LL(1), recursive descent).

Rule: At each step, find the leftmost non-terminal in the current string and replace it using one of its productions. The highlighted symbol (orange) is the one being expanded.
Leftmost Derivation of id + id * id
Step 0 / 11
🟠 Orange = leftmost non-terminal being expanded
E
Start: E is the only (leftmost) non-terminal
Section 3

Rightmost Derivation

In a rightmost derivation, at each step we always expand the rightmost non-terminal. Crucially, this is what LR parsers simulate — but in reverse!

Rule: At each step, find the rightmost non-terminal in the current string and replace it. The highlighted symbol (purple) is the one being expanded.
⚡ Remember: reading these steps bottom-to-top gives you what an LR parser does!
Rightmost Derivation of id + id * id
Step 0 / 11
🟣 Purple = rightmost non-terminal being expanded
E
Start: E is the only (rightmost) non-terminal
🌳 Same Parse Tree! Notice that both leftmost and rightmost derivations produce the same parse tree. The only difference is the order in which nodes are created. The grammatical structure of the input is unique.
Section 4 — ⚡ The Big Insight

Why Rightmost Derivation Matters

This is the most important connection in all of parsing theory. Understanding it unlocks the intuition behind every LR parser you'll ever encounter.

⚡ The Fundamental Theorem of LR Parsing

LR Parser = Rightmost Derivation Traced in REVERSE

An LR parser reads input Left-to-right and produces a Rightmost derivation in reverse.
Every shift = consuming a terminal. Every reduce = applying a grammar rule backwards.

Rightmost Derivation ↔ LR Parser Trace

Reading the derivation steps bottom-to-top is exactly what an LR parser does. Each reduce action corresponds to one derivation step — reversed.

📜 Rightmost Derivation (top→bottom)
0 E start
1 T E′ E→TE′
2 T + T E′ E′→+TE′
3 T + T ε E′→ε
4 T + F T′ T→FT′
5 T + F * F T′ T′→*FT′
6 T + F * F ε T′→ε
7 T + F * id F→id
8 T + id * id F→id
9 F T′ + id * id T→FT′
10 F ε + id * id T′→ε
11 id + id * id F→id ✓
⟺ READ BOTTOM-TO-TOP
🤖 LR Parser Actions (bottom→top)
1 Shift id shift
2 Reduce F → id reduce
3 Reduce T′ → ε reduce
4 Reduce T → FT′ reduce
5 Shift + shift
6 Shift id shift
7 Reduce F → id reduce
8 Shift * shift
9 Shift id shift
10 Reduce F → id reduce
11 Reduce T/T′/Accept accept

Click to highlight corresponding rows between the derivation and LR trace

🎬 LR Parser Stack Trace for id + id * id

Step Stack Input Action Why (Derivation Link)
🔑 The Aha Moment: Each reduce action in the LR trace corresponds to applying a grammar rule backwards. When we reduce "id → F," we are recognizing that we've just derived "id" from F in the rightmost derivation. The stack accumulates a reversed rightmost sentential form at every step.
Summary

3 Things Every Parser Student Must Know

These three facts are the foundation of everything that follows in LR parsing theory.

⬇️
Leftmost Derivation
Top-down Parsing
Always expand the leftmost non-terminal. This is what LL(1) and recursive-descent parsers do. They predict which rule to apply by looking ahead at the next input token.
⬆️
Rightmost Derivation (Reversed)
Bottom-up (LR) Parsing
LR parsers simulate the rightmost derivation in reverse. They shift tokens onto a stack and reduce when they recognize the right-hand side of a production rule.
🌳
Same Parse Tree
Unique Grammatical Structure
Both derivation orders produce the same parse tree for an unambiguous grammar. The tree is unique — the derivation order only affects how we visit nodes, not the structure.

Derivation Comparison at a Glance

Property Leftmost Derivation Rightmost Derivation
Which NT is expanded? Leftmost non-terminal in string Rightmost non-terminal in string
Associated parser type LL (top-down): LL(1), recursive descent LR (bottom-up): LR(0), SLR, CLR, LALR
Direction of construction Root → leaves (expansion) Leaves → root (reduction, when reversed)
Handles left recursion? ❌ Causes infinite loop ✅ Handles naturally
Grammar power LL(k) grammars (strict subset) LR(k) grammars (much larger set)
Parse tree result ✅ Identical for unambiguous grammars
🔗 What's Next: