Recursive Descent Parsing — Compiler Construction

Section 1

What Is Recursive Descent?

A top-down parser that matches input by calling mutually recursive functions.

🔄

One Function Per Non-Terminal

Every non-terminal in the grammar gets its own parsing function. E, T, F each become E(), T(), F().

👁️

Lookahead to Choose

Each function peeks at the next input token (lookahead) to decide which production rule to apply — no backtracking needed.

📞

Calls = Derivation

The call sequence mirrors the leftmost derivation: calling E()→T()→F() corresponds to E → T → F.

Key Insight: The call stack is the parse tree! Each function call represents expanding a node in the derivation tree. When the function returns, the subtree rooted at that non-terminal is complete.

How It Works: Three Primitives

peek()

Look at the current input token without consuming it. Returns the terminal at the current position.

            char peek() { return input[pos]; }
          

match(c)

Consume the current token if it matches c. Otherwise, report a syntax error and stop.

            match('+') → advance pos
          

NT_func()

Call the parsing function for a non-terminal. It recursively parses the input until that NT is fully matched.

            T() → F() T_prime()
          

Section 2

The Problem: Left Recursion

Why a naive grammar causes infinite recursion — and stack overflow.

⚠️ Left Recursion: A grammar has left recursion when a non-terminal directly or indirectly derives a string starting with itself: A → Aα. Recursive descent parsers cannot handle this — they loop forever.

❌ Left-Recursive Grammar

E → E + T ← left recursive!

E → T

T → T * F ← left recursive!

T → F

F → (E)

F → id

What happens when we call E():

E() { // Try E → E + T E() ← calls E() again! match('+') T() } // E() → E() → E() → E() → ... // INFINITE LOOP → STACK OVERFLOW!

Animated: Stack Overflow Visualization

💥 STACK OVERFLOW!

Section 3

Removing Left Recursion

Transform the grammar systematically so recursive descent parsing works.

📐 The Left Recursion Removal Rule

A → Aα | β

becomes

A → β A'

A' → α A' | ε

The right-recursive A' handles the repeating suffix, while A starts fresh with the base case β.

Step-by-Step Transformation

Step 1 / 3

Step 1 — Non-Terminal: E

E → E + T | T has direct left recursion. Applying the rule with α = + T and β = T…

Before (left-recursive)

E → E + T

E → T

→

After (right-recursive)

E → T E'

E' → + T E'

E' → ε

α = + T (the left-recursive suffix), β = T (the base case). The new rule E' loops right-recursively or terminates with ε.

Step 2 — Non-Terminal: T

T → T * F | F has the same pattern. Applying with α = * F and β = F…

Before (left-recursive)

T → T * F

T → F

→

After (right-recursive)

T → F T'

T' → * F T'

T' → ε

Same pattern: α = * F, β = F. Now T() won't call itself first — it calls F() then delegates repetition to T'.

Step 3 — Non-Terminal: F

F → (E) | id has no left recursion. It stays unchanged.

Before

F → (E)

F → id

✓

After (unchanged)

F → (E)

F → id

F has no production starting with itself, so no transformation is needed!

Step 1 / 3

✅ Final Grammar (Left Recursion Removed)

E → T E'

E' → + T E' | ε

T → F T'

T' → * F T' | ε

F → (E) | id

Section 4

Parser Functions

Each non-terminal becomes a function in the recursive descent parser.

Pseudocode First

function E(): // E → T E' T() E_prime() function E_prime(): // E' → + T E' | ε if peek() == '+': match('+') T() E_prime() // else: ε (do nothing)

function T(): // T → F T' F() T_prime() function T_prime(): // T' → * F T' | ε if peek() == '*': match('*') F() T_prime() // else: ε function F(): // F → (E) | id if peek() == '(': match('('); E(); match(')') else: match('id')

Complete C++ Implementation

#include <iostream>
#include <string>
using namespace std;

string input;
int pos = 0;

char peek() { return pos < input.size() ? input[pos] : '$'; }

void match(char c) {
    if (peek() == c) pos++;
    else { cout << "Error: expected '" << c << "'\n"; exit(1); }
}

void E_prime();
void T();
void T_prime();
void F();

// ── E → T E' ──────────────────────────────
void E() {
    cout << "E()\n";
    T(); E_prime();
}

// ── E' → + T E' | ε ───────────────────────
void E_prime() {
    cout << "E_prime()\n";
    if (peek() == '+') {
        match('+'); T(); E_prime();
    }
    // else epsilon — do nothing
}

// ── T → F T' ──────────────────────────────
void T() {
    cout << "T()\n";
    F(); T_prime();
}

// ── T' → * F T' | ε ───────────────────────
void T_prime() {
    cout << "T_prime()\n";
    if (peek() == '*') {
        match('*'); F(); T_prime();
    }
    // else epsilon — do nothing
}

// ── F → (E) | id ──────────────────────────
void F() {
    cout << "F()\n";
    if (peek() == '(') {
        match('('); E(); match(')');
    } else if (peek() == 'i') {   // 'id' represented as 'i','d'
        match('i'); match('d');
    } else {
        cout << "Error: unexpected '" << peek() << "'\n";
        exit(1);
    }
}

int main() {
    input = "id+id*id";
    E();
    if (peek() == '$' || pos >= (int)input.size())
        cout << "Accept!\n";
    return 0;
}

Section 5

Visual Call Stack Simulation

Step through parsing id + id * id and watch the call stack evolve.

Call Stack (top = active)

Input Tape

Current Action

Ready

Press Next to start the simulation.

Parse Tree (growing)

Step Log