Predictive Parsing

Predictive parsing is a deterministic top-down parsing strategy in which the parser selects the correct grammar production by examining a bounded number of input tokens — typically one — without backtracking. A parser is predictive when, for every non-terminal and every lookahead token, at most one production can lead to a valid parse. This property makes predictive parsers linear-time and linear-space, but it imposes strong constraints on the grammar: no left recursion, no common prefixes, no ambiguity.

The canonical predictive parser is the LL(1) parser, whether implemented as recursive descent or table-driven. The prediction is encoded in FIRST and FOLLOW sets — computed properties of the grammar that determine which terminals can begin or follow each non-terminal's productions.

Predictive parsing is the formalization of optimism: the assumption that a glance at the next token is enough to know the entire grammatical future. It works beautifully when grammars are designed to make this true, and fails catastrophically when they are not.