Top-Down Parsing

A grammar defines a language by derivation: starting from a start symbol `S`, repeatedly replace a nonterminal by the right-hand side of one of its productions, until only terminals remain. A top-down parse of a string `w` reconstructs a specific derivation of `w` from `S` by simulating this replacement process directly, always expanding the leftmost nonterminal in the current sentential form. Because expansion proceeds leftmost-first, a top-down parser produces what is called a leftmost derivation, and the parse tree grows from the root (the start symbol) down toward the leaves (the terminals of the input), which is the origin of the name. The central difficulty is choice. At any point the parser holds a nonterminal `A` and must decide which of `A`'s productions, say `A → α₁ | α₂ | … | αₖ`, actually matches the remaining input. A naive top-down parser handles this by trying each alternative in turn and backtracking on failure — this always terminates for simple cases but can require exponential time on pathological grammars, and it interacts badly with side effects (you cannot easily backtrack after printing an error message or emitting code). A predictive top-down parser instead commits to exactly one alternative based on a fixed, small amount of lookahead — classically just the next unconsumed input token — and never backtracks. This is only possible when the grammar has the property that, for every nonterminal, the alternatives can be distinguished by their possible starting tokens; grammars with this property are called `LL(1)` (Left-to-right scan, Leftmost derivation, 1 token of lookahead), a concept fully developed in LL Parsing and Parse Tables. Two structural obstacles block predictiveness and must be removed before a grammar can be parsed top-down without backtracking. Left recursion, where a nonterminal can derive a string beginning with itself (`A → A α`), sends a naive top-down parser into infinite descent, since expanding `A` immediately re-poses the problem of expanding `A`. Left-factoring ambiguity arises when two productions of the same nonterminal share a common prefix (`A → α β₁ | α β₂`), so that seeing the start of `α` does not yet reveal which alternative applies. Both problems are grammar transformations, not parsing tricks: left recursion is eliminated by rewriting the grammar to use right recursion plus an auxiliary nonterminal, and common prefixes are factored out into a shared production followed by a choice point.

Conceptually, a top-down parser maintains a frontier of grammar symbols still to be matched against the remaining input — think of it as a stack, initialized with the start symbol. At each step it looks at the symbol on top of the stack and the next input token, and does one of three things: if the top is a terminal, it must equal the current input token (consume both, or fail); if the top is the end-marker and input is exhausted, parsing succeeds; if the top is a nonterminal, the parser uses the current input token as lookahead to select one production for that nonterminal, then replaces the nonterminal on the stack with the right-hand side of the chosen production, symbols in left-to-right order so the leftmost symbol ends up on top. The prediction step is the heart of the method. For each nonterminal `A` and each production `A → α`, the grammar's `FIRST(α)` set tells us which terminals can appear as the first symbol of some string derived from `α`. If `α` can derive the empty string, we also consult `FOLLOW(A)`, the set of terminals that can legally follow `A` in some derivation, because in that case `A` might need to vanish entirely and let whatever comes next decide. This information is precomputed once from the grammar and packaged into a parsing table `M[A, a]`, indexed by nonterminal and lookahead terminal, giving the production to use (or an error). Building the table is exactly the concern of LL Parsing and Parse Tables; here we treat the table lookup as a black box `select(A, a)`. ``` // Generic predictive (LL) top-down parsing algorithm. // Grammar G with start symbol S, end-of-input marker $. // select(A, a) returns a production A -> X1 X2 ... Xn // chosen by lookahead terminal a, or FAIL if none applies. function PARSE(input_tokens): stack ← new Stack() stack.push($) // bottom-of-stack marker stack.push(S) // start symbol tokens ← input_tokens + [$] // append end marker i ← 0 // index of current lookahead token a ← tokens[i] while stack is not empty: X ← stack.top() if X is a terminal or X =$: if X = a: stack.pop() i ← i + 1 a ← tokens[i] else: report_error("expected " + X + " found " + a) return FAIL else: // X is a nonterminal production ← select(X, a) // table lookup M[X, a] if production = FAIL: report_error("no rule for " + X + " on lookahead " + a) return FAIL stack.pop() for symbol in reverse(production.rhs): if symbol ≠ ε: // skip epsilon productions stack.push(symbol) record_expansion(X, production) // grows the parse tree if a = $: return SUCCESS(parse_tree) else: report_error("extra input after end of parse") return FAIL ``` Two implementation styles realize this same abstract algorithm. In recursive descent, the explicit stack is replaced by the call stack: each nonterminal `A` becomes a function that inspects the lookahead token, decides which production applies (often via an `if`/`switch` on `FIRST` sets), and recursively calls functions for the nonterminals in the chosen production's right-hand side, in order. In table-driven predictive parsing, the algorithm above is run literally, with an explicit stack and an explicit two-dimensional table `M`, making the parser data-driven and easy to regenerate automatically when the grammar changes. Both are explored as dedicated techniques; the algorithm above is their shared skeleton.

Time complexity. Each iteration of the main loop either pops a terminal and consumes exactly one input token, or expands one nonterminal into a fixed (grammar-dependent) number of stack symbols and consumes no input. The number of terminal-consuming steps is bounded by `n`, the input length, since each consumes a distinct token. The number of expansion steps is bounded because each expansion strictly decreases the "distance to termination" measured by summing, over the stack, the length of the shortest terminal string each symbol can still derive — and because the grammar is finite, only finitely many nonterminal expansions can occur before some terminal is consumed. Concretely, for a fixed grammar with maximum production length `k` and no infinite chains of epsilon-only expansions, the total number of stack operations is `O(n)`, and each operation (table lookup, push, pop) is `O(1)` with a properly indexed table. Hence the whole parse runs in `O(n)` time and `O(n)` space in the worst case (for the stack and the resulting parse tree, which has `O(n)` nodes for grammars without vacuous unbounded epsilon expansion chains). This linear bound is precisely what predictiveness buys you. A backtracking top-down parser without lookahead-based selection can, on adversarial grammars, explore an exponential number of candidate derivations before finding (or ruling out) a match, since each nonterminal with `k` alternatives multiplies the branching factor by `k` at every recursive call with no way to prune wrong guesses early.

Correctness. The algorithm is correct if it accepts exactly the strings derivable from `S`, and when it accepts, the tree it records is a valid parse tree for the input. Invariant. At every point in the loop, define the sentential form represented by the stack as the sequence of symbols currently on the stack (bottom to top) followed by nothing — call it `β`. The invariant maintained is:

that is, the start symbol has a leftmost derivation to (the already-consumed input) concatenated with the current stack contents. Initially `β = S` and no input is consumed, so the invariant holds trivially (`S ⇒ S`). Each step preserves it: matching a terminal moves one symbol from `β`'s front into the consumed prefix without changing the derivability claim; expanding a nonterminal `A` at the front of `β` using production `A → α` extends the leftmost derivation by exactly one step, `A ⇒ α`, replacing `A` with `α` in `β`. When the stack becomes just `$` and input is exhausted, `β` is empty and the consumed input equals `w`, giving `S ⇒lm w`, i.e., a full leftmost derivation — exactly the definition of "w is generated by G," witnessed constructively by the sequence of `record_expansion` calls, which is precisely a parse tree. Soundness of production selection. The invariant's correctness depends on `select(A, a)` never choosing a production that cannot lead to a successful match. This is guaranteed exactly when the grammar is `LL(1)`: for every nonterminal `A` with productions `A → α₁ | … | αₖ`, the sets `FIRST(αᵢ)` (extended to include `FOLLOW(A)` when `αᵢ ⇒* ε`) are pairwise disjoint. Disjointness means the current lookahead token uniquely identifies the correct alternative — there is no ambiguity to backtrack over, so a single deterministic table lookup suffices and is provably safe. When the grammar fails this condition (has left recursion, requires left-factoring, or is inherently ambiguous), the table has a cell with two entries or none applicable, and top-down parsing without backtracking is not sound for that grammar; this is the boundary the grammar transformations in Recursive Descent Parsing and LL Parsing and Parse Tables exist to fix.

Honest tradeoffs. Top-down predictive parsing trades grammar generality for speed and simplicity: it handles only `LL(1)` (or, with `k`-token lookahead, `LL(k)`) grammars, which excludes many natural, unambiguous grammars — most notably any grammar with left recursion (the natural way to express left-associative operators) and grammars needing unbounded lookahead to disambiguate. Bottom-up methods such as `LR` parsing accept a strictly larger class of grammars at the cost of a less intuitive table-construction process and less direct correspondence between code structure and grammar structure.

Consider the classic expression grammar, already left-factored and free of left recursion, used above: ``` E → T E′ E′ → + T E′ | ε T → F T′ T′ → * F T′ | ε F → id | ( E ) ``` The FIRST/FOLLOW sets needed to build the prediction table are:

From these, the parsing table `M[A, a]` is fully determined (only nonterminal rows shown; blanks are errors):

Running `PARSE` on the token stream `id + id * id $` (traced fully in the diagram above) makes concrete why the table works: at step 5, the stack top is `T′` and the lookahead is `+`; since `+` is not in `FIRST(* F T′)` but *is* in `FOLLOW(T′)`, the table correctly predicts `T′ \to ε`, letting the `+` be handled by `E′` instead. This is exactly the FOLLOW-based fallback the correctness argument relies on. The parser accepts after 15 steps having consumed all 5 input tokens plus `$`, doing `O(1)` work per step — confirming the `O(n)` bound with `n = 5`.

Top-down parsing is the strategy of choice whenever a grammar is small, hand-tunable, or needs a parser that is easy to read and modify — which describes an enormous share of real software. Compilers for languages engineered with `LL(1)`-friendly grammars (Pascal historically, many configuration and markup languages, JSON parsers, and most hand-written expression evaluators) use recursive descent or table-driven prediction directly. Parser-generator ecosystems such as ANTLR, and the hand-written front ends inside tools like `clang`'s early parsing stages and many scripting-language interpreters, rely on the same predictive core described here. Interactive tools — IDEs offering syntax highlighting and incremental reparsing, linters, and configuration validators — favor top-down parsers because the direct correspondence between grammar rule and parsing function makes them easy to instrument with error recovery and precise diagnostics. Understanding the top-down strategy is also the necessary foundation for its two concrete children: Recursive Descent Parsing, where nonterminals become functions, and LL Parsing and Parse Tables, where the whole prediction process is compiled into a lookup table, both of which depend on the derivation and ambiguity concepts from Derivations, Parse Trees, and Ambiguity to even define what "correct" means.

Ask the tutor: How do I compute FIRST and FOLLOW sets systematically for an arbitrary context-free grammar?