Parsing: Top-Down

A context-free grammar (CFG) is a set of recursive rewriting rules that precisely defines the syntax of a language. Formally, a CFG is a 4-tuple G = (V, Σ, R, S) where:

• V is a finite set of nonterminal symbols (also called variables), written in uppercase, like Expr, Stmt, Term.
• Σ is a finite set of terminal symbols (the actual tokens), like +, *, int, id, (.
• R is a finite set of production rules, each of the form A → α where A ∈ V and α ∈ (V ∪ Σ)*.
• S ∈ V is the start symbol.

A rule A → α says: "A nonterminal A can be rewritten as the string α." A string of tokens is in the language if it can be derived from S by a sequence of rule applications.

Why "context-free"? In a context-sensitive grammar, you can only rewrite A when it appears in a specific context (e.g., between particular symbols). Context-free means the rewriting rule for A applies regardless of where A appears. This restriction is exactly what makes parsing tractable.

Example — a tiny expression grammar:

E → E + T  |  T
T → T * F  |  F
F → ( E )  |  id  |  num

This grammar captures arithmetic precedence structurally: multiplication is deeper in the tree (in T) than addition (in E), so it binds tighter. The string id + id * id has exactly one valid parse tree under this grammar, and the tree correctly shows * applied first.

Derivations and parse trees: A leftmost derivation always expands the leftmost nonterminal first. A parse tree makes the derivation visual — the root is S, internal nodes are nonterminals, leaves are terminals, and each internal node's children correspond to exactly one applied production. The parse tree is the syntactic structure of the program. Top-down parsing constructs this tree from root to leaves.

# CFG for arithmetic expressions (Python-style illustration)
# G = ({E, T, F}, {'+','*','(',')', 'id','num'}, R, E)
# Productions R:
#   E -> E + T | T
#   T -> T * F | F
#   F -> ( E ) | id | num

# Leftmost derivation of  id + id * id :
# E
# => E + T          (E -> E + T)
# => T + T          (E -> T)
# => F + T          (T -> F)
# => id + T         (F -> id)
# => id + T * F     (T -> T * F)
# => id + F * F     (T -> F)
# => id + id * F    (F -> id)
# => id + id * id   (F -> id)

A grammar is ambiguous if there exists a string in the language that has more than one distinct parse tree. Ambiguity is a property of the grammar, not the language — most ambiguous grammars can be rewritten as unambiguous ones.

Ambiguity is catastrophic for compilers: if 2 - 1 - 1 can be parsed as (2 - 1) - 1 = 0 or 2 - (1 - 1) = 2, the compiler has no idea which semantics to use.

Classic ambiguous grammar (dangling-else problem):

Stmt → if Expr then Stmt
     | if Expr then Stmt else Stmt
     | other

The string if E1 then if E2 then S1 else S2 can pair the else with either if. This is why C, Java, and Python use syntactic conventions (braces, indentation) to resolve it, or grammar transformations.

How to remove ambiguity (for expressions): Factor out the associativity and precedence into the grammar structure itself, as the standard expression grammar does (E → E+T | T, etc.). Recursive rules on the left encode left-associativity; recursive rules on the right encode right-associativity.

Why this matters for top-down parsing: Top-down parsing requires an unambiguous grammar (or at least a grammar with no ambiguity reachable from the start symbol). Moreover, the standard unambiguous expression grammar is left-recursive, which causes top-down parsers to loop forever — which leads us to the next concept: eliminating left recursion.

# Ambiguous grammar for expressions:
# E -> E + E | E * E | ( E ) | id
# 'id + id * id' has TWO parse trees:
#   Tree 1: (id + id) * id  [addition first]
#   Tree 2:  id + (id * id)  [multiplication first]
#
# Unambiguous equivalent (precedence encoded structurally):
# E -> E + T | T    (E is sum-level)
# T -> T * F | F    (T is product-level)
# F -> ( E ) | id
# Now 'id + id * id' has EXACTLY ONE parse tree.
# The grammar IS the precedence table.

A grammar has left recursion when a nonterminal A derives a string beginning with A itself, either directly (A → A α) or indirectly (A → B γ, B → A δ). Left recursion is lethal for top-down parsers: when you try to expand A by applying A → A α, you immediately need to expand A again, forever.

Immediate left recursion removal: Replace every production of the form:

A → A α₁ | A α₂ | ... | β₁ | β₂ | ...

(where βᵢ do not start with A) with:

A  → β₁ A' | β₂ A' | ...
A' → α₁ A' | α₂ A' | ε

This converts left-recursive iteration into right-recursive iteration with a new "tail" nonterminal A'. The resulting grammar is right-recursive and generates the same language.

Example: The classic expression grammar E → E + T | T becomes:

E  → T E'
E' → + T E' | ε

Now parsing id + id + id proceeds: parse one T (the id), then repeatedly parse + T chunks via E'. This is left-associative! Even though the grammar is right-recursive syntactically, the semantic actions (attach-left) preserve left-associativity.

Indirect left recursion (A → Bγ, B → Aδ) requires a more involved algorithm: topologically sort the nonterminals and apply substitution. The Dragon Book gives the canonical algorithm.

Intuition: Left recursion says "I start with myself." Recursive descent says "I call myself immediately." Infinite loop. Right recursion says "I end with myself" — you first consume some input, then recurse. Progress guaranteed.

# Before: left-recursive expression grammar
# E -> E + T | T
# T -> T * F | F
# F -> ( E ) | id

# After: left-recursion removed
# E  -> T E'
# E' -> + T E' | epsilon
# T  -> F T'
# T' -> * F T' | epsilon
# F  -> ( E ) | id

# Trace of  id + id * id  with new grammar:
# E => T E'
#   => F T' E'
#   => id T' E'
#   => id E'          (T' -> epsilon)
#   => id + T E'
#   => id + F T' E'
#   => id + id T' E'
#   => id + id * F T' E'
#   => id + id * id T' E'
#   => id + id * id E'  (T' -> epsilon)
#   => id + id * id     (E' -> epsilon)

Even without left recursion, a grammar can be troublesome for top-down parsing if two productions for the same nonterminal share a common prefix. The parser cannot decide which rule to use until it has consumed the shared prefix — but it must commit to a rule before consuming anything.

Example:

Stmt → if Expr then Stmt else Stmt
     | if Expr then Stmt

Both alternatives start with if Expr then Stmt. A single token lookahead (seeing if) cannot distinguish them.

Left factoring extracts the common prefix:

Stmt  → if Expr then Stmt Stmt'
Stmt' → else Stmt | ε

Now, after parsing if Expr then Stmt, we look at the next token: if it is else, expand Stmt' → else Stmt; otherwise, expand Stmt' → ε. The decision is made with one lookahead token.

General algorithm: For a nonterminal A with productions sharing a prefix α:

A → α β₁ | α β₂ | ... | γ₁ | γ₂

Replace with:

A  → α A' | γ₁ | γ₂
A' → β₁ | β₂ | ...

Repeat until no two productions for the same nonterminal share a common prefix.

Left factoring does not always terminate: Some grammars have infinite common prefixes (e.g., involving recursion). In such cases, the grammar may not be LL(1)-able no matter what. This is an inherent limitation of the LL(1) class.

# Before left factoring
# A -> a b c
# A -> a b d
# A -> e

# After left factoring
# A  -> a b A' | e
# A' -> c | d

# Another example: dangling else
# Stmt -> if E then Stmt else Stmt
#       | if E then Stmt
# After:
# Stmt  -> if E then Stmt Stmt'
# Stmt' -> else Stmt | epsilon

# The choice for Stmt' is now unambiguous:
# lookahead = 'else'  => use  Stmt' -> else Stmt
# lookahead = anything else => use  Stmt' -> epsilon

The FIRST set of a grammar symbol or string is the set of terminal tokens that can appear as the first token in any string derivable from it. FIRST is the mathematical foundation of predictive parsing: when you are trying to expand nonterminal A and you see token t in the lookahead, you pick the production A → α such that t ∈ FIRST(α).

Formal definition:

• FIRST(a) = {a} for any terminal a.
• FIRST(ε) = {ε}.
• For a nonterminal A: FIRST(A) = ∪ { FIRST(α) | A → α ∈ R }, where:
  • FIRST(X₁ X₂ ... Xₙ) is computed as: include FIRST(X₁) \ {ε}; if ε ∈ FIRST(X₁), also include FIRST(X₂) \ {ε}; if ε ∈ FIRST(X₁) and ε ∈ FIRST(X₂), also include FIRST(X₃); and so on. Include ε itself only if all Xᵢ can derive ε.

Algorithm (iterative fixed-point): Initialize FIRST(A) = ∅ for all nonterminals. Repeatedly apply the rules above until no FIRST set changes. This terminates because sets only grow and are bounded.

Example (left-recursion-removed expression grammar):

E  → T E'
E' → + T E' | ε
T  → F T'
T' → * F T' | ε
F  → ( E ) | id

FIRST(F) = { (, id } FIRST(T') = { *, ε } FIRST(T) = FIRST(F) = { (, id } FIRST(E') = { +, ε } FIRST(E) = FIRST(T) = { (, id }

Intuition: FIRST answers "what tokens announce this construct?" Seeing ( or id announces an expression; seeing + announces the tail of an expression.

def compute_first(grammar, nonterminals, terminals):
    """
    grammar: dict mapping nonterminal -> list of productions
             each production is a list of symbols (strings)
             use 'EPS' to denote epsilon
    Returns dict: symbol -> set of terminals (including 'EPS')
    """
    first = {s: set() for s in nonterminals}
    for t in terminals:
        first[t] = {t}
    first['EPS'] = {'EPS'}

    changed = True
    while changed:
        changed = False
        for A, productions in grammar.items():
            for prod in productions:
                # FIRST of production: X1 X2 ... Xn
                before = len(first[A])
                for sym in prod:
                    first[A] |= (first[sym] - {'EPS'})
                    if 'EPS' not in first[sym]:
                        break
                else:
                    first[A].add('EPS')  # all symbols derive EPS
                if len(first[A]) != before:
                    changed = True
    return first

# Example grammar (left-recursion removed expression grammar):
grammar = {
    'E':  [['T', "E'"]],
    "E'": [['+', 'T', "E'"], ['EPS']],
    'T':  [['F', "T'"]],
    "T'": [['*', 'F', "T'"], ['EPS']],
    'F':  [['(', 'E', ')'], ['id']],
}
# FIRST('F') = {'(', 'id'}
# FIRST('E') = {'(', 'id'}

The FOLLOW set of a nonterminal A is the set of terminals that can appear immediately after A in some sentential form derived from the start symbol S. It also includes $ (end-of-input) if A can appear at the end.

FOLLOW is needed for ε-productions: when we want to expand A → ε, we must know it is safe to produce nothing — which means the lookahead token must be something that legitimately follows A. If the lookahead t ∈ FOLLOW(A), we may apply A → ε.

Rules for computing FOLLOW(A):

1. Place $ in FOLLOW(S) (S is the start symbol).
2. For each production B → α A β: add FIRST(β) \ {ε} to FOLLOW(A).
3. For each production B → α A β where ε ∈ FIRST(β), or B → α A: add all of FOLLOW(B) to FOLLOW(A).

Again, iterate to a fixed point.

Example (continuing the expression grammar):

FOLLOW(E)  = { ), $ }        (E appears in F→(E), end of input)
FOLLOW(E') = FOLLOW(E) = { ), $ }  (E' is last in E→T E')
FOLLOW(T)  = FIRST(E') \ {ε} ∪ FOLLOW(E) = { +, ), $ }
FOLLOW(T') = FOLLOW(T) = { +, ), $ }
FOLLOW(F)  = FIRST(T') \ {ε} ∪ FOLLOW(T) = { *, +, ), $ }

Common mistake: FOLLOW(A) is about the enclosing context, not about what A internally produces. It is a global property computed over the whole grammar. It answers: "if I decide to use A → ε, which tokens in the lookahead are consistent with having 'nothing' here?"

def compute_follow(grammar, first, start, nonterminals):
    """
    Requires first sets already computed.
    Returns dict: nonterminal -> set of terminals (including '$')
    """
    follow = {A: set() for A in nonterminals}
    follow[start].add('$')

    changed = True
    while changed:
        changed = False
        for B, productions in grammar.items():
            for prod in productions:
                # prod = [X1, X2, ..., Xn]
                for i, A in enumerate(prod):
                    if A not in nonterminals:
                        continue
                    beta = prod[i+1:]  # symbols after A
                    before = len(follow[A])
                    # Add FIRST(beta) - {eps} to FOLLOW(A)
                    eps_in_beta = True
                    for sym in beta:
                        follow[A] |= (first[sym] - {'EPS'})
                        if 'EPS' not in first[sym]:
                            eps_in_beta = False
                            break
                    # If eps derivable from beta (or beta empty), add FOLLOW(B)
                    if eps_in_beta:
                        follow[A] |= follow[B]
                    if len(follow[A]) != before:
                        changed = True
    return follow

With FIRST and FOLLOW in hand, we can build a predictive parsing table M[A, a] that maps (nonterminal A, lookahead terminal a) to the production to apply. This table encodes a deterministic parsing algorithm.

Construction algorithm: For each production A → α in the grammar:

1. For each terminal a ∈ FIRST(α) (excluding ε): add A → α to M[A, a].
2. If ε ∈ FIRST(α): for each terminal b ∈ FOLLOW(A) (including $): add A → α to M[A, b].

The LL(1) condition: A grammar is LL(1) if and only if no cell M[A, a] contains more than one production. Equivalently:

• For any two distinct productions A → α and A → β, FIRST(α) ∩ FIRST(β) = ∅.
• For any production A → α where ε ∈ FIRST(α): FIRST(β) ∩ FOLLOW(A) = ∅ for all other alternatives β.
• At most one alternative can derive ε.

The name LL(1) means: Left-to-right scan, Leftmost derivation, 1 token of lookahead.

Example table entry (expression grammar):

M[E,  id] = E  → T E'
M[E,  ( ] = E  → T E'
M[E', +]  = E' → + T E'
M[E', )]  = E' → ε
M[E', $]  = E' → ε
M[T,  id] = T  → F T'
M[T,  ( ] = T  → F T'
M[T', *]  = T' → * F T'
M[T', +]  = T' → ε
M[T', )]  = T' → ε
M[T', $]  = T' → ε
M[F,  id] = F  → id
M[F,  ( ] = F  → ( E )

Every cell has at most one entry — the grammar is LL(1).

def build_ll1_table(grammar, first, follow, nonterminals, terminals):
    """
    Returns M: dict of (nonterminal, terminal) -> production (list)
    Raises ValueError if grammar is not LL(1).
    """
    M = {}  # (A, a) -> production

    def first_of_seq(seq):
        """Compute FIRST of a sequence of symbols."""
        result = set()
        for sym in seq:
            result |= (first[sym] - {'EPS'})
            if 'EPS' not in first[sym]:
                return result
        result.add('EPS')
        return result

    for A, productions in grammar.items():
        for prod in productions:
            actual_prod = prod if prod != ['EPS'] else []
            f = first_of_seq(prod)
            for a in f - {'EPS'}:
                key = (A, a)
                if key in M:
                    raise ValueError(f"Not LL(1): conflict at M[{A},{a}]")
                M[key] = actual_prod
            if 'EPS' in f:
                for b in follow[A]:
                    key = (A, b)
                    if key in M:
                        raise ValueError(f"Not LL(1): conflict at M[{A},{b}]")
                    M[key] = actual_prod  # epsilon production
    return M

The table-driven LL(1) parser uses an explicit stack (rather than the implicit call stack of recursive descent). It simulates the leftmost derivation mechanically using the parsing table.

Algorithm:

Initialize: stack = [S, $], input pointer at first token
Repeat:
  Let X = top of stack, a = current input token
  If X == a == $: accept (success)
  If X == a (terminal): pop X, advance input
  If X is nonterminal:
    If M[X, a] = X → Y₁ Y₂ ... Yₖ:
      pop X, push Yₖ, ..., Y₂, Y₁ (reverse order)
    Else: error (no entry in table)

Trace for id + id * id (expression grammar):

Stack            Input           Action
[E, $]           id+id*id$    M[E,id] = E→T E'
[T, E', $]       id+id*id$    M[T,id] = T→F T'
[F, T', E', $]   id+id*id$    M[F,id] = F→id
[id, T', E', $]  id+id*id$    match id
[T', E', $]      +id*id$      M[T',+] = T'→ε
[E', $]          +id*id$      M[E',+] = E'→+T E'
[+, T, E', $]    +id*id$      match +
[T, E', $]       id*id$       M[T,id] = T→F T'
[F, T', E', $]   id*id$       M[F,id] = F→id
[id, T', E', $]  id*id$       match id
[T', E', $]      *id$         M[T',*] = T'→*F T'
[*, F, T', E',$] *id$         match *
[F, T', E', $]   id$          M[F,id] = F→id
[id, T', E',$]   id$          match id
[T', E', $]      $            M[T',$] = T'→ε
[E', $]          $            M[E',$] = E'→ε
[$]              $            ACCEPT

Invariant: At every step, the stack concatenated with the remaining input equals a right-sentential form of the grammar. This is the guarantee that keeps the algorithm correct.

def ll1_parse(tokens, table, start):
    """
    tokens: list of terminals ending with '$'
    table: dict (nonterminal, terminal) -> list of symbols
    start: start symbol string
    Returns True if accepted, raises on error.
    """
    stack = [start, '$']
    idx = 0  # index into tokens

    while stack:
        X = stack[0]
        a = tokens[idx]

        if X == '$' and a == '$':
            return True  # accept

        if X == a:  # terminal match
            stack.pop(0)
            idx += 1

        elif X.isupper() or X.endswith("'"):  # nonterminal
            key = (X, a)
            if key not in table:
                raise SyntaxError(
                    f"Unexpected token '{a}' when expanding {X}")
            production = table[key]
            stack.pop(0)
            # Push production in reverse so left is on top
            for sym in reversed(production):
                stack.insert(0, sym)
            # If production is epsilon, we just popped X, nothing pushed

        else:
            raise SyntaxError(f"Expected '{X}', got '{a}'")

    raise SyntaxError("Stack empty before input exhausted")

Recursive-descent parsing is the hand-coded equivalent of the table-driven LL(1) parser: each nonterminal A becomes a function parse_A(), and each production A → X₁ X₂ ... Xₙ becomes a sequence of calls to parse_X₁(), parse_X₂(), ..., parse_Xₙ(). The call stack is the explicit stack of the table-driven parser.

For an LL(1) grammar, each parse_A() function looks at the lookahead (the next token) and dispatches to the correct production. No backtracking. No speculation. Every decision is made in O(1) time with one token of lookahead.

Why is this the industry standard? Because:

1. The code is isomorphic to the grammar — easy to read, maintain, and extend.
2. Error messages can be made excellent (you know exactly where you are in the parse).
3. Semantic actions (building the AST, type-checking, emitting code) are easy to weave in.
4. No external tool needed — just write it.

Compilers that use hand-written recursive descent include: CPython, GCC (since 2006), Clang/LLVM, rustc, the Go compiler, Swift's compiler, and V8.

Pattern:

def parse_E():
    parse_T()
    parse_E_prime()

def parse_E_prime():
    if lookahead == '+':
        consume('+')
        parse_T()
        parse_E_prime()
    # else: epsilon production, return without consuming

One practical nuance — building ASTs: In a real parser, each parse_X() returns a node (or appends to a tree). The call structure naturally produces the right nesting. For left-associative operators, you accumulate results as you return from the tail-recursive E' calls (or use an iterative loop).

# Recursive-descent parser for arithmetic expressions
# Grammar (LL(1), left-recursion removed):
#   E  -> T E'
#   E' -> + T E' | epsilon
#   T  -> F T'
#   T' -> * F T' | epsilon
#   F  -> ( E ) | id | num

class Parser:
    def __init__(self, tokens):
        self.tokens = tokens  # e.g. ['id', '+', 'id', '*', 'id', '$']
        self.pos = 0

    @property
    def lookahead(self):
        return self.tokens[self.pos]

    def consume(self, expected):
        if self.lookahead != expected:
            raise SyntaxError(f"Expected {expected!r}, got {self.lookahead!r}")
        self.pos += 1

    def parse_E(self):
        left = self.parse_T()
        return self.parse_E_prime(left)

    def parse_E_prime(self, left):
        if self.lookahead == '+':
            self.consume('+')
            right = self.parse_T()
            node = ('+', left, right)
            return self.parse_E_prime(node)  # left-associative
        return left  # epsilon

    def parse_T(self):
        left = self.parse_F()
        return self.parse_T_prime(left)

    def parse_T_prime(self, left):
        if self.lookahead == '*':
            self.consume('*')
            right = self.parse_F()
            node = ('*', left, right)
            return self.parse_T_prime(node)
        return left

    def parse_F(self):
        if self.lookahead == '(':
            self.consume('(')
            node = self.parse_E()
            self.consume(')')
            return node
        elif self.lookahead in ('id', 'num'):
            tok = self.lookahead
            self.consume(tok)
            return tok
        else:
            raise SyntaxError(f"Unexpected token: {self.lookahead!r}")

# Usage:
# p = Parser(['id', '+', 'id', '*', 'id', '$'])
# tree = p.parse_E()
# tree == ('+', 'id', ('*', 'id', 'id'))  [left side is id, right is id*id]

LL(1) is powerful but not universal. Understanding its limits is as important as understanding its mechanics.

Inherently non-LL(1) constructs:

1. Left-recursive grammars (must be transformed first — but transformation can change the shape of the AST).

2. Grammars requiring more lookahead: The C declaration syntax T *p is ambiguous without knowing whether T is a type or a variable, requiring semantic context to parse. C++ is famously not LL(k) for any fixed k.

3. Common FIRST/FIRST conflicts: If two productions for A share a token in their FIRST sets and cannot be left-factored (because the shared prefix is infinite), the grammar is not LL(1)-able.

4. FIRST/FOLLOW conflicts: If ε ∈ FIRST(α) for A → α and some token a is in both FIRST of another alternative and FOLLOW(A), the table has a conflict.

Real-world consequence: No major programming language has a perfectly LL(1) grammar. Solutions include:

• LL(k): k tokens of lookahead (ANTLR supports this).
• Parsing with semantic predicates: Resolve ambiguities using symbol-table lookup (used in C parsers for the typedef problem).
• PEG parsers (Parsing Expression Grammars): Ordered choice instead of ambiguous choice; handles many non-LL(1) constructs with implicit backtracking.
• LR parsing (bottom-up): The next module — handles a strictly larger class of grammars (all LL(1) grammars are LR(1), but not vice versa).

The key insight: LL(1) is the sweet spot for hand-written parsers of well-designed languages. Programming languages designed with parsing in mind (Go, Pascal, JSON, LISP) tend to be LL(1) or close to it. Languages designed for human readability first (C++, Perl, Ruby) tend to require heavier machinery.

# Example of a FIRST/FIRST conflict (not LL(1)):
# A -> a b
# A -> a c
# FIRST(a b) = {a}, FIRST(a c) = {a} — conflict!
# Fix: left-factor
# A  -> a A'
# A' -> b | c

# Example of a FIRST/FOLLOW conflict (not LL(1)):
# S -> A B
# A -> a | epsilon
# B -> a b
# FIRST(A) = {a, eps}
# FOLLOW(A) = FIRST(B) = {a}
# Conflict: seeing 'a', should we use A->a or A->epsilon ?
# M[A, a] would have two entries.
# This grammar is NOT LL(1) — no transformation fixes it.
# (It IS LR(1) — bottom-up parsing handles it.)

# Classic non-LL grammar: most of C++ :-)
# 'T * x' : is T a type (pointer declaration) or a variable (multiplication)?
# Resolving requires the symbol table — a semantic, not syntactic, action.