Top-Down Parsing: Recursive Descent and LL(1)

Parsing from the top: grow the tree downward

In guide 1 the scanner already did its job: it chewed the raw characters into a clean stream of tokens (an identifier, a `+`, a number, an open paren). The parser's task now is to decide whether that token stream fits the grammar, and if so, to build the parse tree that shows how. Top-down parsing does this in the most optimistic way imaginable: it starts at the root labelled with the start symbol and grows the tree DOWNWARD toward the tokens, expanding one variable at a time, always betting on a rule before it has seen the whole input.

Connect this straight back to the previous rung. Growing the tree from the top, always attacking the leftmost unfinished variable and matching tokens left to right, is exactly building a leftmost derivation of the input. So top-down parsing is not a new mathematical object — it is the leftmost derivation you already know, run as an algorithm with the input pinned down in advance. The whole game is: at each variable, guess which rule's right-hand side will eventually spell out the tokens lying ahead.

Recursive descent: one function per rule

The most direct way to write a top-down parser is recursive descent, and the trick is delightfully literal: turn each nonterminal of the grammar into one function. To parse a variable A, you call the function `parseA`. Inside it, you walk along the right-hand side of A's rule from left to right; for a terminal you check that the current token matches and then consume it (advance the input), and for a nonterminal B you simply call `parseB`. The grammar's recursion becomes the program's recursion — a rule that mentions itself becomes a function that calls itself.

Grammar (tokens: id  +  (  ) ):
  E  ->  T E'
  E' ->  + T E'  |  epsilon
  T  ->  id  |  ( E )

parseE():            parseEprime():           parseT():
   parseT()             if peek == '+':           if peek == 'id':
   parseEprime()           match('+')                match('id')
                           parseT()              elif peek == '(':
                           parseEprime()            match('(')
                        # else epsilon: return       parseE()
                                                      match(')')
                                                   else: ERROR

Notice what `parseEprime` had to do: facing the rule `E' -> + T E' | epsilon`, it had two choices and chose by PEEKING at the next token. If it saw a `+`, it took the first alternative; otherwise it took the empty (epsilon) alternative and returned without consuming anything. That single peek-then-decide is the heart of efficient top-down parsing. When a parser can always pick the right rule by looking at just the next token — never guessing, never backing up — we call it predictive parsing. The reward is huge: each token is consumed once, so the parser runs in O(n) linear time on input of length n.

LL(1): predicting with one token of lookahead

The class of grammars a predictive parser can handle with a single peek has a precise name: LL(1). Read the label literally. The first L means we scan the input Left to right; the second L means we produce a Leftmost derivation; and the (1) means we look ahead exactly 1 token to decide each step. (LL(k) allows k tokens of lookahead, but LL(1) is the workhorse.) An LL(1) grammar is one where, at every variable, that single lookahead token is always enough to pick the correct rule with no ambiguity and no backtracking.

Instead of hand-writing functions, we can capture all the decisions in a single PARSE TABLE: rows are nonterminals, columns are lookahead tokens, and each cell names the one rule to use. A tiny stack-driven loop then drives the whole parse — push the start symbol, and repeatedly look at the top of the stack and the next token to decide whether to match a terminal or expand a nonterminal via the table. This is, in spirit, a deterministic pushdown automaton: the stack holds the part of the sentential form still to be matched, exactly the stack-as-memory idea from the PDA rung made concrete.

Be honest about the ceiling here. LL(1) is genuinely useful and gives clean, readable, fast parsers — but it is strictly weaker than the LR family you will meet next. Some perfectly reasonable context-free languages have no LL(1) grammar at all, because one token of lookahead simply is not enough to commit. When an LL(1) parser must decide between two rules and that single token cannot tell them apart, the parse table has a cell with two entries — a conflict — and the grammar is rejected as not LL(1). Two grammar habits cause almost all such conflicts, and the rest of this guide is about spotting and fixing them.

FIRST and FOLLOW: the maps that make prediction safe

How does the parser actually know, from one peeked token, which rule to fire? It precomputes two small maps from the grammar — the FIRST and FOLLOW sets. FIRST(α), for a string of symbols α, is the set of terminals that can appear as the very first token of some string derived from α. (If α can derive the empty string, we record that α is 'nullable' and add epsilon to FIRST(α).) Intuitively, FIRST answers: 'if I commit to this rule, what could the next visible token possibly be?'

FIRST alone is not enough, because of the epsilon (empty) rules. When the parser sits at a nullable variable A and the next token is NOT in FIRST(A), it may still be right to apply A -> epsilon and quietly move on — but only if that token is something that can legitimately come AFTER A. That is what FOLLOW(A) records: the set of terminals that can appear immediately to the right of A in some sentential form. FOLLOW is how the parser decides it is safe to 'erase' a variable and let the surrounding context continue.

1. For each rule A -> α, compute FIRST(α): the tokens that could start whatever α produces (peek through nullable pieces, adding the next piece's FIRST until you hit a non-nullable one).
2. Put the rule A -> α into the parse table cell [A, t] for every terminal t in FIRST(α). On the lookahead t, that rule is the prediction.
3. If α is nullable (it can derive epsilon), ALSO place A -> α in cell [A, t] for every t in FOLLOW(A) — the tokens that may legally appear after A, signalling 'take the empty branch here'.
4. If this procedure ever tries to write TWO different rules into the same cell, that is a conflict: the single lookahead token is ambiguous, and the grammar is not LL(1).

Two things LL(1) cannot stomach (and how to fix them)

The first poison is left recursion: a rule like E -> E + T, where the variable calls itself as its OWN leftmost symbol. A recursive-descent `parseE` would immediately call `parseE` with no token consumed, looping forever — and the parse table gets a conflict because FIRST of the recursive alternative overlaps everything. The cure is left recursion removal: rewrite the rule to recurse on the right instead. The classic transform turns A -> A α | β into A -> β A' with A' -> α A' | epsilon. Same language, but now the recursion grows rightward and is safe to descend.

The second poison is two alternatives that share a common prefix, like S -> if E then S | if E then S else S. One peeked token `if` cannot tell the two apart — they look identical until much later — so the table cell for `if` holds both rules: a conflict. The cure is left factoring: pull the shared prefix out front and defer the decision. Rewrite S -> if E then S S' with S' -> else S | epsilon. Now after parsing the common part, a single lookahead (`else` or not) cleanly chooses the tail, and the grammar becomes LL(1)-friendly.

Two honest cautions. First, these transforms preserve the LANGUAGE (the set of accepted strings) but they reshape the grammar and the parse tree, so a tool that builds an abstract syntax tree usually does extra work to recover the natural structure afterwards. Second, fixing left recursion and shared prefixes makes a grammar predictive-FRIENDLY, but it does not guarantee LL(1): a genuinely ambiguous grammar (the dangling-else above is the famous case) can still leave conflicts that no amount of factoring removes, because the ambiguity is real, not cosmetic. There you must change the language's intended meaning, add a disambiguating rule, or reach for a stronger bottom-up parser.

What you now hold, and where guide 3 goes

Step back and see the whole picture. Top-down parsing grows the parse tree from the start symbol downward, which is just building a leftmost derivation against a fixed input. Recursive descent codes that as one function per nonterminal; predictive parsing makes it backtrack-free by peeking one token; and LL(1) is the precise grammar class where that single peek always suffices, with FIRST and FOLLOW sets filling the parse table and flagging conflicts. It is linear-time, readable, and the method behind many real hand-written front ends.

But we keep bumping into the ceiling: left recursion is awkward, shared prefixes need factoring, and some context-free languages have no LL(1) grammar however hard we try. Guide 3 lifts that ceiling by flipping the whole direction. Instead of predicting a rule before seeing its contents, a bottom-up parser SHIFTS tokens onto a stack and REDUCES a completed right-hand side only once it is fully in view — recognising the handle after the fact. That patience is exactly why the LR family is strictly more powerful than LL, and why it underlies the parser generators (yacc, bison) you will meet at the end of this rung.