top-down parsing

Suppose you are told the answer is a sentence and must figure out how it was built, but you start from the big idea and work down to the words. You begin by assuming 'this is a Sentence', then guess 'a Sentence is a Subject followed by a Predicate', then expand the Subject, and so on, until your guesses reach the actual words on the page. Top-down parsing is exactly this: it starts at the grammar's start symbol and tries to grow a derivation downward toward the input.

Mechanically, a top-down parser builds the parse tree from the root and predicts, at each nonterminal, which production rule to apply next, then checks whether that prediction can match the upcoming tokens. It produces a leftmost derivation: always expand the leftmost remaining nonterminal first. The central difficulty is choosing the right rule. If a nonterminal A has rules A -> b... and A -> c..., the parser peeks at the next token and picks the rule whose expansion can start with that token. When one token of look-ahead is always enough to decide, the grammar is LL(1) and parsing is clean and fast. Two things break this prediction and must be fixed first: left recursion (a rule like A -> A x makes the parser loop forever guessing A) and common prefixes among rules (which blur the choice and need left factoring).

Top-down parsing is the basis of recursive-descent and LL parsers, the kind you can readily write by hand and the kind ANTLR-style tools generate. Its great virtue is that the code mirrors the grammar, one function per nonterminal, so it is easy to read, easy to add custom error messages to, and easy to debug. Its limit is power: top-down parsers handle a smaller class of grammars than bottom-up LR parsers, so some natural grammars must be rewritten before a top-down parser can cope.