Top-Down Parsers

Explore how top-down parsers work by building parse trees from the root downward, understand the challenges of backtracking and ambiguity, and see how predictive parsers solve them.

What is Top-Down Parsing?

In top-down parsing, the parser starts at the root of the parse tree (the start symbol S) and tries to build the tree downward, matching the input left to right.

At each step the parser:

Picks a non-terminal that has not yet been expanded.
Chooses a production rule for it.
Expands the non-terminal into its right-hand side.

It keeps doing this until the leaves of the tree match the input exactly.

Visual intuition — Grammar: S → a B c, B → b | b b, Input: a b b c

Step 1 — Start with the root node S. Step 2 — Expand S → a B c, creating three children.

Step 3 — Attempt B → b (fails)

B expands to a single b. After matching a then b, the parser expects c next — but the remaining input is b c, not c. Mismatch → backtrack.

After matching a and b, the parser expects c but the input shows another b — mismatch → backtrack.

Step 4 — Try B → b b (succeeds ✓)

Backtrack and pick the second production. B expands to two bs. All four tokens match.

The parser starts at the root and works downward, hence "top-down".

Top-Down Parsing with Backtracking

When the parser tries a production and it does not lead to a match, it backtracks — undoes the expansion and tries the next production rule.

Example — Backtracking in Action

Grammar:

Example

S → a b c | a b d

Input: a b d

Example

Attempt 1: S → a b c

Match 'a' ✓

Match 'b' ✓

Expect 'c', see 'd' ✗ → Mismatch

Backtrack: undo the expansion, reset input to start

Attempt 2: S → a b d

Match 'a' ✓

Match 'b' ✓

Match 'd' ✓

Input exhausted → Success ✓

Backtracking works, but it is expensive:

Backtracking may undo large portions of work.
In the worst case, a parser tries every production at every position: exponential time.
Many grammars require exponential backtracking to parse.

Limitations of Backtracking

Limitation	Detail
Slow	Exponential time in the worst case
No side effects	Cannot perform actions (like building the AST) during parsing — must wait
Left recursion causes infinite loop	Parser never terminates
Hard to give good error messages	"Tried everything, nothing worked"

Because of these issues, most real parsers avoid backtracking. They use predictive parsing instead.

Predictive Parsing — No Backtracking

A predictive parser makes parsing decisions using the current input symbol (lookahead) — and it is always right on the first try. It never needs to backtrack.

This works because the grammar is designed (or transformed) so that knowing just one token is always enough to pick the correct production.

How It Works

The parser maintains:

An input buffer — the token stream from the lexer.
A stack — tracking what still needs to be matched.
A parsing table — maps (non-terminal, lookahead token) → production to use.

At each step:

Example

Look at the top of the stack and the current input token.

Case 1: Top is a terminal t and input is t → match: pop t, advance input.

Case 2: Top is a terminal t and input is not t → error.

Case 3: Top is a non-terminal A → look up (A, input) in parsing table.

Use the production found to replace A on the stack.

Case 4: Stack is empty and input is end-of-input → accept ✓

Example

Grammar (LL(1)-ready):

Example

E → T E'

E' → + T E' | ε

T → id

Input: id + id $ ($ = end of input)

Example

Stack Input Action

─────────────────────────────────────────

E $ id + id $ Expand E → T E'

T E' $ id + id $ Expand T → id

id E' $ id + id $ Match id

E' $ + id $ Expand E' → + T E'

+ T E' $ + id $ Match +

T E' $ id $ Expand T → id

id E' $ id $ Match id

E' $ $ Expand E' → ε

$ $ Accept ✓

The parser never backtracks — every decision is made correctly in one step.

Requirements for Predictive Parsing

For predictive parsing to work with a single token of lookahead (LL(1)), the grammar must meet two conditions:

Condition 1 — No Left Recursion

Left-recursive rules cause the parser to loop forever (as we covered in the Left Recursion topic). These must be eliminated first.

Example

E → E + T | T ← has left recursion, must be transformed

E → T E' ← no left recursion ✓

E' → + T E' | ε

Condition 2 — No Common Prefixes (Left Factored)

When two productions share a prefix, the parser cannot decide which to use with one token of lookahead. Left factoring removes the ambiguity.

Example

stmt → if ( expr ) stmt ← two rules, same prefix

| if ( expr ) stmt else stmt

stmt → if ( expr ) stmt stmt' ← factored ✓

stmt' → else stmt | ε

Summary

Requirement	Why It Is Needed
No left recursion	Prevents infinite loops in expansion
No common prefixes (left factored)	Ensures one lookahead token is always enough
Unambiguous grammar	Each string has exactly one parse — no choice conflicts

After applying these transformations, FIRST and FOLLOW sets are computed to build the parsing table.

Top-Down vs. Bottom-Up Parsing

Now that we understand top-down parsing, here is a clear comparison with bottom-up parsing:

Feature	Top-Down (LL)	Bottom-Up (LR)
Builds tree	Root → leaves	Leaves → root
Grammar class	LL(k) — a subset of CFGs	LR(k) — almost all CFGs
Left recursion	Must be eliminated	Handles it naturally
Implementation	Easy — write one function per rule	Needs a parser generator (yacc, bison)
Error messages	Descriptive — knows what it expected	Can be confusing
Lookahead needed	k = 1 usually enough	k = 1 usually enough
Practical use	Handwritten parsers, ANTLR	Generated parsers (most production compilers)

Which Is Better?

Neither is universally better. The choice depends on:

Handwriting the parser? → Top-down (recursive descent) is much easier to write by hand.
Using a parser generator? → Bottom-up (LALR) handles a larger grammar class and is the default in yacc/bison.
Building an IDE or friendly tool? → Top-down gives better error messages.
Maximum performance? → Both are O(n) for practical grammars.

What is Top-Down Parsing?

In top-down parsing, the parser starts at the root of the parse tree (the start symbol S) and tries to build the tree downward, matching the input left to right.

At each step the parser:

Picks a non-terminal that has not yet been expanded.
Chooses a production rule for it.
Expands the non-terminal into its right-hand side.

It keeps doing this until the leaves of the tree match the input exactly.

Visual intuition — Grammar: S → a B c, B → b | b b, Input: a b b c

Step 1 — Start with the root node S. Step 2 — Expand S → a B c, creating three children.

Step 3 — Attempt B → b (fails)

B expands to a single b. After matching a then b, the parser expects c next — but the remaining input is b c, not c. Mismatch → backtrack.

After matching a and b, the parser expects c but the input shows another b — mismatch → backtrack.

Step 4 — Try B → b b (succeeds ✓)

Backtrack and pick the second production. B expands to two bs. All four tokens match.

The parser starts at the root and works downward, hence "top-down".

Top-Down Parsing with Backtracking

When the parser tries a production and it does not lead to a match, it backtracks — undoes the expansion and tries the next production rule.

Example — Backtracking in Action

Grammar:

Example

S → a b c | a b d

Input: a b d

Example

Attempt 1: S → a b c

Match 'a' ✓

Match 'b' ✓

Expect 'c', see 'd' ✗ → Mismatch

Backtrack: undo the expansion, reset input to start

Attempt 2: S → a b d

Match 'a' ✓

Match 'b' ✓

Match 'd' ✓

Input exhausted → Success ✓

Backtracking works, but it is expensive:

Backtracking may undo large portions of work.
In the worst case, a parser tries every production at every position: exponential time.
Many grammars require exponential backtracking to parse.

Limitations of Backtracking

Limitation	Detail
Slow	Exponential time in the worst case
No side effects	Cannot perform actions (like building the AST) during parsing — must wait
Left recursion causes infinite loop	Parser never terminates
Hard to give good error messages	"Tried everything, nothing worked"

Because of these issues, most real parsers avoid backtracking. They use predictive parsing instead.

Predictive Parsing — No Backtracking

A predictive parser makes parsing decisions using the current input symbol (lookahead) — and it is always right on the first try. It never needs to backtrack.

This works because the grammar is designed (or transformed) so that knowing just one token is always enough to pick the correct production.

How It Works

The parser maintains:

An input buffer — the token stream from the lexer.
A stack — tracking what still needs to be matched.
A parsing table — maps (non-terminal, lookahead token) → production to use.

At each step:

Example

Look at the top of the stack and the current input token.

Case 1: Top is a terminal t and input is t → match: pop t, advance input.

Case 2: Top is a terminal t and input is not t → error.

Case 3: Top is a non-terminal A → look up (A, input) in parsing table.

Use the production found to replace A on the stack.

Case 4: Stack is empty and input is end-of-input → accept ✓

Example

Grammar (LL(1)-ready):

Example

E → T E'

E' → + T E' | ε

T → id

Input: id + id $ ($ = end of input)

Example

Stack Input Action

─────────────────────────────────────────

E $ id + id $ Expand E → T E'

T E' $ id + id $ Expand T → id

id E' $ id + id $ Match id

E' $ + id $ Expand E' → + T E'

+ T E' $ + id $ Match +

T E' $ id $ Expand T → id

id E' $ id $ Match id

E' $ $ Expand E' → ε

$ $ Accept ✓

The parser never backtracks — every decision is made correctly in one step.

Requirements for Predictive Parsing

For predictive parsing to work with a single token of lookahead (LL(1)), the grammar must meet two conditions:

Condition 1 — No Left Recursion

Left-recursive rules cause the parser to loop forever (as we covered in the Left Recursion topic). These must be eliminated first.

Example

E → E + T | T ← has left recursion, must be transformed

E → T E' ← no left recursion ✓

E' → + T E' | ε

Condition 2 — No Common Prefixes (Left Factored)

When two productions share a prefix, the parser cannot decide which to use with one token of lookahead. Left factoring removes the ambiguity.

Example

stmt → if ( expr ) stmt ← two rules, same prefix

| if ( expr ) stmt else stmt

stmt → if ( expr ) stmt stmt' ← factored ✓

stmt' → else stmt | ε

Summary

Requirement	Why It Is Needed
No left recursion	Prevents infinite loops in expansion
No common prefixes (left factored)	Ensures one lookahead token is always enough
Unambiguous grammar	Each string has exactly one parse — no choice conflicts

After applying these transformations, FIRST and FOLLOW sets are computed to build the parsing table.

Top-Down vs. Bottom-Up Parsing

Now that we understand top-down parsing, here is a clear comparison with bottom-up parsing:

Feature	Top-Down (LL)	Bottom-Up (LR)
Builds tree	Root → leaves	Leaves → root
Grammar class	LL(k) — a subset of CFGs	LR(k) — almost all CFGs
Left recursion	Must be eliminated	Handles it naturally
Implementation	Easy — write one function per rule	Needs a parser generator (yacc, bison)
Error messages	Descriptive — knows what it expected	Can be confusing
Lookahead needed	k = 1 usually enough	k = 1 usually enough
Practical use	Handwritten parsers, ANTLR	Generated parsers (most production compilers)

Which Is Better?

Neither is universally better. The choice depends on:

Handwriting the parser? → Top-down (recursive descent) is much easier to write by hand.
Using a parser generator? → Bottom-up (LALR) handles a larger grammar class and is the default in yacc/bison.
Building an IDE or friendly tool? → Top-down gives better error messages.
Maximum performance? → Both are O(n) for practical grammars.