Parser Comparison — Compiler Construction

Section 1

Parser Evolution Chain

Each parser was invented to solve the limitations of its predecessor. Hover each node to see what problem it solved and what limitation remains.

Recursive Descent

✔ Solved: Intuitive, hand-written

✘ Needs: Left-recursion-free grammar

LL(1)

✔ Solved: Table-driven, systematic

✘ Needs: LL(1) grammar (top-down only)

Top-Down

Lookahead only: top-down limits

LR(0)

✔ Solved: Bottom-up, handles more grammars

✘ Needs: Many shift/reduce conflicts

SLR

✔ Solved: Uses FOLLOW to reduce conflicts

✘ Needs: FOLLOW too coarse-grained

CLR (LR(1))

✔ Solved: Exact lookaheads, no false conflicts

✘ Needs: Enormous state table

LALR

✔ Solved: Merges CLR states, practical size

✘ Needs: Rare reduce/reduce conflicts

💡

Reading the Chain

The top path (Recursive Descent → LL(1)) is Top-Down parsing. The bottom path (LR(0) → SLR → CLR → LALR) is Bottom-Up. Both share the same underlying goal: recognizing valid sentences of a context-free grammar.

Section 2

Master Comparison Table

Every attribute of every parsing strategy, side by side. Scroll horizontally if needed.

Parser	Direction	Strategy	Lookahead	States	Grammar Class	Conflicts	Real-World Use
Recursive Descent	Top-Down	Recursive functions	1+ token (manual)	N/A	LL(k)	Manual backtracking	GCC, Java, Rust, Clang (hand-written)
LL(1)	Top-Down	Table-driven, predict	1 token (FIRST/FOLLOW)	N/A	LL(1)	Table cell conflicts	ANTLR (LL mode), educational tools
LR(0)	Bottom-Up	Shift / Reduce	0 (none)	n states	LR(0)	Many S/R & R/R	Academic only, very limited use
SLR	Bottom-Up	Shift / Reduce + FOLLOW	FOLLOW(A)	n states	SLR(1)	Fewer conflicts	Some simple tools, academic
CLR (LR(1))	Bottom-Up	Shift / Reduce + exact LA	Exact per item	n × k states	LR(1)	Almost none	Rarely used alone (too many states)
LALR	Bottom-Up	Merged CLR states	Merged CLR lookaheads	n states	LALR(1)	Rare R/R	yacc, bison, GCC (older), Ruby, Perl

⚡

Key Takeaway: State Count vs Power

SLR and LALR have the same number of states as LR(0) — they share the same DFA core. CLR can have exponentially more states. LALR gives LR(1) parsing power with LR(0) state count, which is why it dominates real-world tools.

Section 3

Grammar Class Hierarchy

Every grammar class is a subset of the next. A grammar handled by a simpler parser is also handled by all more powerful parsers above it.

All CFGs

LR(1) = CLR grammars

LALR(1) grammars

SLR(1)

LR(0)

LL(1) (overlaps LALR but is a distinct class)

LL(1) ⊂ LALR(1) ⊂ LR(1) ⊂ Unambiguous CFG

Grammar Class Notes

📦

All CFGs

The outermost ring. Context-free grammars include ambiguous grammars, which no deterministic parser can handle without disambiguation rules.

🔮

LR(1) = CLR Grammars

Any unambiguous deterministic CFL can be recognized. CLR handles the most grammars but has the most states.

🎯

LALR(1) — The Sweet Spot

Slightly smaller than LR(1). Almost all programming language grammars fit here. yacc/bison target this class.

⚠️

SLR(1) ⊂ LALR(1)

SLR is strictly a subset of LALR. The canonical example S→L=R|R, L→*R|id fails SLR but works in LALR.

🟢

LL(1) Relationship

LL(1) ⊂ LALR(1). Every LL(1) grammar is also LALR(1). But LALR(1) can handle left-recursive grammars (like E→E+T) that LL(1) cannot. They overlap but are distinct families.

Section 4

Conflict Comparison

Understanding when and why conflicts arise — and how each parser generation reduces them.

⚡ LR(0) Conflicts

Shift/Reduce: A complete item [A→α•] shares a state with an item that has a terminal to shift. Parser doesn't know which to do.

Reduce/Reduce: Two complete items [A→α•] and [B→β•] in the same state. Parser can't choose which production to reduce by.

Root cause: LR(0) reduces on any terminal when an item is complete — no lookahead at all.

            Reduce condition: item [A→α•] ⟹ reduce A→α on ALL terminals
          

🔶 SLR Conflicts

Fewer S/R conflicts: Only reduce on terminals in FOLLOW(A). If the current terminal isn't in FOLLOW(A), no ambiguity with that shift.

Still conflicts when: FOLLOW(A) overlaps with symbols that must be shifted. Classic: S→L=R|R, L→*R|id — because = ∈ FOLLOW(R), and state I2 must both shift '=' and reduce R→L.

            Reduce condition: [A→α•] ⟹ reduce on terminal ∈ FOLLOW(A)
          

🔮 CLR Conflicts

Almost none: Each item carries its own exact lookahead set. [A→α•, {a}] only reduces when the current token is exactly 'a'.

Resolution example: In state I2 for S→L=R|R, L→*R|id: item [R→L•, {$}] only reduces on $, and [S→L•=R, {$}] shifts on '='. No conflict!

            Reduce condition: [A→α•, a] ⟹ reduce only when current token = a
          

🎯 LALR Conflicts

Mostly CLR-level: Shift/reduce conflicts: same as CLR (very rare for unambiguous grammars).

Merge danger — R/R: When two CLR states with different lookaheads are merged, their lookaheads union. If the union creates a case where two different reduces apply to the same token → reduce/reduce conflict.

In practice: almost all well-designed programming language grammars avoid this entirely.

            Reduce condition: [A→α•, merged-LA] on merged lookahead
          

The Canonical Example: S→L=R|R, L→*R|id, R→L

💥

SLR fails here

State I2 contains [S→L•=R] (shift on =) and [R→L•] (reduce). Since = ∈ FOLLOW(R) = {=, $}, SLR says reduce R→L on '='. But we also need to shift '='. Shift/reduce conflict!

I2

S → L•=Rshift '=' ✓

R → L•reduce on FOLLOW(R)='='? ✗

✅

CLR resolves it

CLR tracks exact lookaheads. [R→L•, {$}] only reduces on $, not on '='. [S→L•=R, {$}] shifts on '='. The lookaheads don't overlap — no conflict!

I2 (CLR)

S → L•=R, {$} → shift '=' ✓

R → L•, {$} → reduce on $ only ✓

Section 5

Real-World Parser Reference

Which parsing strategy do major compilers and tools actually use in production?

GCC (C/C++)

🖊 Recursive Descent

GCC's C and C++ front end has been hand-written recursive descent since version 3.4. Chosen for flexibility in handling ambiguous constructs in C++.

Clang / LLVM

🖊 Recursive Descent

Hand-written recursive descent parser for C, C++, and Objective-C. Enables excellent error recovery and IDE tooling integration.

CPython

⚡ PEG Parser

Python 3.9+ uses a PEG (Parsing Expression Grammar) parser generated from Grammar/python.gram. PEG is a top-down technique with unlimited lookahead.

Java (javac)

🖊 Recursive Descent

OpenJDK's javac uses hand-written recursive descent. Java's grammar is designed to be parseable top-down without ambiguity.

Rust (rustc)

🖊 Recursive Descent

Hand-written recursive descent parser in Rust itself. The complexity of Rust's macro system makes a generated parser impractical.

Ruby MRI

📊 LALR (Bison)

Ruby's reference implementation uses a bison-generated LALR(1) parser defined in parse.y. The grammar is famously complex (~2000 lines).

GNU Tools (bash, etc.)

📊 LALR (Bison)

GNU Bash, GNU Make, and many other tools use bison for LALR(1) parsing. Bison is the de facto standard for C-based parser generation.

ANTLR 4

✦ ALL(*)

Adaptive LL(*) — a top-down algorithm that speculatively explores all possible parse paths. Handles ambiguous grammars by choosing the first match.

GCC (older, pre-3.4)

📊 LALR (Bison)

Older GCC used bison-generated LALR(1) parsers. Switched to hand-written RD to better handle C++ template syntax edge cases.

PHP (Zend)

📊 LALR (Bison)

PHP's Zend Engine parser is generated by bison from zend_language_parser.y. Standard LALR(1) grammar for PHP syntax.

Go (gc)

🖊 Recursive Descent

Go's official compiler uses a hand-written recursive descent parser. Go was designed to be parseable in linear time with a simple grammar.

Perl 5

📊 LALR + hand-written

Perl uses a bison LALR core combined with extensive hand-written code to handle Perl's notoriously complex context-sensitive syntax.

📌

Why Do Most Modern Compilers Use Recursive Descent?

Despite LALR being theoretically powerful, hand-written recursive descent parsers offer better error messages, easier IDE integration, simpler debugging, and the ability to handle context-sensitive constructs (like C++ template ambiguity) that are impossible to express in a pure CFG.

Section 6

Which Parser Should I Use?

Follow this decision tree to choose the right parser for your grammar.

1

Is your grammar left-recursive? (e.g., E → E + T)

→ If YES and you want Top-Down: eliminate left recursion first

If NO (or you're fine with Bottom-Up) → continue ↓

2

Is the grammar LL(1)? (FIRST/FOLLOW table has no conflicts)

→ If YES: Use LL(1) table-driven parser, or Recursive Descent for hand-coding

If NO → continue ↓

3

Is the grammar SLR? (LR(0) automaton has no conflicts after FOLLOW filtering)

→ If YES: Use SLR (rare; most real grammars aren't SLR but not LALR)

If NO → continue ↓

4

Is the grammar LALR(1)? (Merging CLR states produces no R/R conflicts)

→ If YES: Use LALR — this is the industry standard (yacc, bison)

If NO → continue ↓

5

Is the grammar LR(1)? (Canonical CLR table has no conflicts)

→ If YES: Use CLR — powerful but state-table can be large

If NO → continue ↓

6

Grammar is likely ambiguous or requires special handling

→ Consider: disambiguating rules, PEG parsers, GLR parsing, or grammar rewriting

🎯

Practical Recommendation

For a course project or tool: LALR (use bison/yacc) handles nearly all well-designed languages. For a hand-written parser: Recursive Descent is easiest to write, debug, and extend.

Section 7

Quick Reference Card

The essential formulas and rules for every parsing technique — your exam cheat-sheet.

📋 Parsing Algorithms — Quick Reference

FIRST(aβ)

= {a} — terminal starts its own FIRST set

FIRST(ε)

= {ε} — epsilon is in the FIRST of the empty string

FIRST(Aβ)

FIRST(A) \ {ε} ∪ (FIRST(β) if ε ∈ FIRST(A)) — propagate through nullable nonterminals

FOLLOW(S)

Always contains $ (end-of-input marker)

FOLLOW rule 2

A → αBβ: FIRST(β) \ {ε} ⊆ FOLLOW(B)

FOLLOW rule 3

A → αB or A → αBβ with ε ∈ FIRST(β): FOLLOW(A) ⊆ FOLLOW(B)

LL(1) Table

M[A,a] = A→α if a ∈ FIRST(α); or if ε ∈ FIRST(α) and a ∈ FOLLOW(A)

LR(0) Reduce

Item [A→α•] complete → reduce A→α on ALL terminals (no lookahead)

SLR Reduce

Item [A→α•] complete → reduce A→α only when current token ∈ FOLLOW(A)

CLR Reduce

Item [A→α•, a] complete → reduce only when current token = a (exact lookahead)

LALR Reduce

Like CLR but lookaheads are the union of merged CLR states' lookaheads

LR(0) Closure

For [A→α•Bβ], add [B→•γ] for every B→γ production (repeat until fixed point)

GOTO(I, X)

Take all items in I with dot before X, advance dot, then compute closure

Accept condition

Item [S'→S•] in current state + current token = $ → accept

Shift action

Current token 'a' can be shifted → push 'a' and new state, advance input

Reduce action

Pop 2×|α| entries (|α| states + |α| symbols), push A, goto(top-state, A)

State Count & Parsing Complexity

LL(1)

Parsing table size: |NT| × |T| entries. One table, linear parsing O(n). Table construction O(|G|).

LR(0) / SLR

Same DFA: n states. Action table: n × |T|. Goto table: n × |NT|. Parsing: O(n).

CLR (LR(1))

Up to n×k states where k = number of terminals. In practice: can be 3–10× more states than LR(0).

LALR

Same n states as LR(0). Merges CLR states by core, retaining LR(1) lookahead information. Best of both worlds.