Recursive Descent and Predictive Parsing

Learn how to implement a top-down parser by hand using recursive descent, and how predictive parsing eliminates backtracking by using lookahead — making parsing efficient and deterministic.

Recursive Descent Parsing

Recursive descent is the most intuitive way to write a top-down parser. The idea is simple:

Write one parsing function for each non-terminal in the grammar.

Each function reads the input and either successfully recognises the non-terminal or fails. Functions call each other recursively, mirroring the structure of the grammar — hence "recursive descent."

From Grammar to Functions

Grammar:

Example

S → if ( E ) S | id := E

E → E + id | id

Corresponding parsing functions:

Example

function parseS():

if current_token == 'if':

match('if'); match('('); parseE(); match(')'); parseS()

else if current_token == 'id':

match('id'); match(':='); parseE()

else:

error("Expected 'if' or identifier")

function parseE():

match('id')

while current_token == '+':

match('+')

match('id')

The function match(t) checks that the current input token is t, then advances to the next token. If the token does not match, it reports an error.

Why "Recursive"?

The functions call each other recursively to mirror the grammar's recursive structure. For example, if ( E ) S has S nested inside itself — the call to parseS() inside parseS() captures this.

Example

parseS()

└── calls parseE()

└── may loop for E + id + id + ...

└── may call parseS() again (for the nested statement)

Recursive Descent with Backtracking

When a grammar has multiple productions for the same non-terminal that could all match, a recursive descent parser must try each one in order and backtrack if one fails.

Example — Backtracking Recursive Descent

Grammar:

Example

S → c A d

A → ab | a

Input: c a d

Example

parseS():

match('c') → success, consume 'c'

parseA() → try to parse A

parseA() — attempt 1: A → ab

match('a') → success, consume 'a'

match('b') → FAIL: current token is 'd', not 'b'

→ backtrack: restore input to before 'a' was consumed

parseA() — attempt 2: A → a

match('a') → success, consume 'a'

→ return success

match('d') → success, consume 'd'

→ Overall: success ✓

Backtracking requires the parser to remember where it was so it can restore the input position on failure.

The Problem with Backtracking

Backtracking works but is slow. For grammars with many alternatives and deep nesting, the parser may try exponentially many combinations before finding the right one (or giving up with an error).

This is why predictive parsers — which never backtrack — are preferred.

Predictive Recursive Descent (No Backtracking)

A predictive recursive descent parser is like a regular recursive descent parser, but it never backtracks. It always knows which production to use by looking at the current input token (lookahead).

This is possible when the grammar is:

Free of left recursion
Left-factored (no two productions for the same non-terminal share a prefix)

Example — Predictive Recursive Descent

Grammar (already left-factored, no left recursion):

Example

E → T E'

E' → + T E' | ε

T → F T'

T' → * F T' | ε

F → ( E ) | id

Parsing functions:

Example

function parseE():

parseT()

parseE_prime()

function parseE_prime():

if current_token == '+':

match('+')

parseT()

parseE_prime()

// else: ε production — do nothing

function parseT():

parseF()

parseT_prime()

function parseT_prime():

if current_token == '*':

match('*')

parseF()

parseT_prime()

// else: ε production — do nothing

function parseF():

if current_token == '(':

match('(')

parseE()

match(')')

else if current_token == 'id':

match('id')

else:

error("Expected '(' or identifier")

Tracing the Parser on "id + id * id"

Example

parseE()

parseT()

parseF() → match 'id' ✓

parseT_prime() → current = '+', not '*' → do nothing (ε)

parseE_prime()

current = '+' → match '+' ✓

parseT()

parseF() → match 'id' ✓

parseT_prime() → current = '*' → match '*' ✓

parseF() → match 'id' ✓

parseT_prime() → current = '$', not '*' → do nothing (ε)

parseE_prime() → current = '$', not '+' → do nothing (ε)

Done. ✓

No backtracking. Every function call makes exactly the right choice on the first try.

Building an AST During Parsing

A recursive descent parser can be easily extended to build an AST (Abstract Syntax Tree) while it parses. Each parsing function returns a tree node.

Example — Returning AST Nodes

Example

function parseE():

left = parseT()

return parseE_prime(left)

function parseE_prime(left):

if current_token == '+':

match('+')

right = parseT()

node = makeNode('+', left, right)

return parseE_prime(node) // left-associative chaining

else:

return left // ε case — pass through

function parseT():

left = parseF()

return parseT_prime(left)

function parseT_prime(left):

if current_token == '*':

match('*')

right = parseF()

node = makeNode('*', left, right)

return parseT_prime(node)

else:

return left

function parseF():

if current_token == '(':

match('(')

node = parseE()

match(')')

return node

else:

node = makeLeaf('id', current_token.value)

match('id')

return node

AST for "a + b * c":

The AST correctly groups multiplication before addition because the grammar enforces it through the T and F levels.

Predictive vs. Recursive Descent — Key Differences

Both are top-down parsing strategies. Here is what sets them apart:

Feature	Recursive Descent (with backtracking)	Predictive Recursive Descent
Grammar class	Any CFG (if written carefully)	LL(1) grammars only
Backtracking	Yes — may try multiple alternatives	No — always picks the right alternative
Lookahead	May need arbitrary lookahead	Exactly one token
Speed	Potentially exponential	Linear O(n)
Implementation	Simple to write	Requires left recursion elimination + left factoring
Error recovery	Easy to customise	Slightly harder

When to Use Each

Recursive descent with backtracking: For quick parser prototypes, small languages, or when the grammar is awkward to transform. Not suitable for performance-critical parsers.
Predictive recursive descent: For production parsers written by hand. Most compiler front-ends (like GCC, Clang, and Go's parser) use this approach. Fast, readable, and easy to extend with good error messages.

Summary

Example

Grammar (any CFG)

↓ Eliminate left recursion

↓ Left-factor common prefixes

↓ Compute FIRST and FOLLOW sets

↓ Build LL(1) parsing table (or write predictive functions by hand)

↓

Predictive Parser — O(n), no backtracking ✓

Recursive Descent Parsing

Recursive descent is the most intuitive way to write a top-down parser. The idea is simple:

Write one parsing function for each non-terminal in the grammar.

From Grammar to Functions

Grammar:

Example

S → if ( E ) S | id := E

E → E + id | id

Corresponding parsing functions:

Example

function parseS():

if current_token == 'if':

match('if'); match('('); parseE(); match(')'); parseS()

else if current_token == 'id':

match('id'); match(':='); parseE()

else:

error("Expected 'if' or identifier")

function parseE():

match('id')

while current_token == '+':

match('+')

match('id')

The function match(t) checks that the current input token is t, then advances to the next token. If the token does not match, it reports an error.

Why "Recursive"?

Example

parseS()

└── calls parseE()

└── may loop for E + id + id + ...

└── may call parseS() again (for the nested statement)

Recursive Descent with Backtracking

When a grammar has multiple productions for the same non-terminal that could all match, a recursive descent parser must try each one in order and backtrack if one fails.

Example — Backtracking Recursive Descent

Grammar:

Example

S → c A d

A → ab | a

Input: c a d

Example

parseS():

match('c') → success, consume 'c'

parseA() → try to parse A

parseA() — attempt 1: A → ab

match('a') → success, consume 'a'

match('b') → FAIL: current token is 'd', not 'b'

→ backtrack: restore input to before 'a' was consumed

parseA() — attempt 2: A → a

match('a') → success, consume 'a'

→ return success

match('d') → success, consume 'd'

→ Overall: success ✓

Backtracking requires the parser to remember where it was so it can restore the input position on failure.

The Problem with Backtracking

Backtracking works but is slow. For grammars with many alternatives and deep nesting, the parser may try exponentially many combinations before finding the right one (or giving up with an error).

This is why predictive parsers — which never backtrack — are preferred.

Predictive Recursive Descent (No Backtracking)

This is possible when the grammar is:

Free of left recursion
Left-factored (no two productions for the same non-terminal share a prefix)

Example — Predictive Recursive Descent

Grammar (already left-factored, no left recursion):

Example

E → T E'

E' → + T E' | ε

T → F T'

T' → * F T' | ε

F → ( E ) | id

Parsing functions:

Example

function parseE():

parseT()

parseE_prime()

function parseE_prime():

if current_token == '+':

match('+')

parseT()

parseE_prime()

// else: ε production — do nothing

function parseT():

parseF()

parseT_prime()

function parseT_prime():

if current_token == '*':

match('*')

parseF()

parseT_prime()

// else: ε production — do nothing

function parseF():

if current_token == '(':

match('(')

parseE()

match(')')

else if current_token == 'id':

match('id')

else:

error("Expected '(' or identifier")

Tracing the Parser on "id + id * id"

Example

parseE()

parseT()

parseF() → match 'id' ✓

parseT_prime() → current = '+', not '*' → do nothing (ε)

parseE_prime()

current = '+' → match '+' ✓

parseT()

parseF() → match 'id' ✓

parseT_prime() → current = '*' → match '*' ✓

parseF() → match 'id' ✓

parseT_prime() → current = '$', not '*' → do nothing (ε)

parseE_prime() → current = '$', not '+' → do nothing (ε)

Done. ✓

No backtracking. Every function call makes exactly the right choice on the first try.

Building an AST During Parsing

A recursive descent parser can be easily extended to build an AST (Abstract Syntax Tree) while it parses. Each parsing function returns a tree node.

Example — Returning AST Nodes

Example

function parseE():

left = parseT()

return parseE_prime(left)

function parseE_prime(left):

if current_token == '+':

match('+')

right = parseT()

node = makeNode('+', left, right)

return parseE_prime(node) // left-associative chaining

else:

return left // ε case — pass through

function parseT():

left = parseF()

return parseT_prime(left)

function parseT_prime(left):

if current_token == '*':

match('*')

right = parseF()

node = makeNode('*', left, right)

return parseT_prime(node)

else:

return left

function parseF():

if current_token == '(':

match('(')

node = parseE()

match(')')

return node

else:

node = makeLeaf('id', current_token.value)

match('id')

return node

AST for "a + b * c":

The AST correctly groups multiplication before addition because the grammar enforces it through the T and F levels.

Predictive vs. Recursive Descent — Key Differences

Both are top-down parsing strategies. Here is what sets them apart:

Feature	Recursive Descent (with backtracking)	Predictive Recursive Descent
Grammar class	Any CFG (if written carefully)	LL(1) grammars only
Backtracking	Yes — may try multiple alternatives	No — always picks the right alternative
Lookahead	May need arbitrary lookahead	Exactly one token
Speed	Potentially exponential	Linear O(n)
Implementation	Simple to write	Requires left recursion elimination + left factoring
Error recovery	Easy to customise	Slightly harder

When to Use Each

Recursive descent with backtracking: For quick parser prototypes, small languages, or when the grammar is awkward to transform. Not suitable for performance-critical parsers.
Predictive recursive descent: For production parsers written by hand. Most compiler front-ends (like GCC, Clang, and Go's parser) use this approach. Fast, readable, and easy to extend with good error messages.

Summary

Example

Grammar (any CFG)

↓ Eliminate left recursion

↓ Left-factor common prefixes

↓ Compute FIRST and FOLLOW sets

↓ Build LL(1) parsing table (or write predictive functions by hand)

↓

Predictive Parser — O(n), no backtracking ✓