LL parser

LL parsing combines a left-to-right scan of the input with construction of a leftmost derivation.¹ A parser begins with the grammar's start symbol and repeatedly expands the leftmost nonterminal until the sentential form matches the input. Its decision procedure chooses a production by examining the current nonterminal and the next token, rather than by first building a complete parse tree and then reducing it.

In the common LL(1) form, a parsing table maps each pair of nonterminal and lookahead token to one production. The parser maintains a stack containing grammar symbols; matching terminals are consumed, while nonterminals are replaced by the right-hand side selected from the table. A successful parse ends when both the stack and input reach the end marker.

An LL grammar must make each top-down choice determinable from the permitted lookahead.¹ For LL(1), table construction usually relies on FIRST and FOLLOW sets. FIRST identifies tokens that can begin strings derived from a grammar symbol; FOLLOW identifies tokens that may occur immediately after a nonterminal. If a production can derive the empty string, FOLLOW information helps decide when that production should be selected.

Two alternatives for the same nonterminal must not compete for the same table entry. A conflict indicates that the grammar is not LL(1), although it may still be LL(k) for a larger fixed lookahead or suitable for another parsing strategy. Grammar transformation, especially left factoring, can expose a common prefix and postpone the decision until enough input has been read.

LL parsers are attractive because their control flow is explicit, their error locations are often close to the point of failure, and hand-written recursive-descent implementations can closely mirror a grammar. They are also useful when a language needs customized diagnostics, semantic actions, or selective recovery. Predictive parsing can run in linear time for a grammar whose choices are resolved with bounded lookahead.

The principal limitation is that many natural grammars are not directly LL(1). Immediate left recursion, such as Expr ::= Expr '+' Term | Term, causes a top-down parser to recurse indefinitely; it is commonly rewritten into a non-left-recursive form. Ambiguous alternatives and long shared prefixes may require left factoring, more lookahead, explicit predicates, or a different parser family such as LR. These rewrites can make the grammar less faithful to the language's conceptual structure.

LL parsing is a family of techniques rather than a single algorithm. LL(k) parsers use up to k tokens of lookahead, while generalized forms such as LL(*) allow the parser generator to inspect an unbounded sequence when deciding among alternatives, subject to restrictions imposed by the tool and grammar.²

Predictive parsing also has an important relationship with scanner design: token boundaries and keyword treatment can determine whether grammar alternatives are distinguishable. Some practical systems combine LL-style prediction with syntactic predicates, memoization, or adaptive decision procedures instead of exposing a literal fixed-size table. Error recovery is another separate design problem; a grammar can be LL(1) while its implementation still gives poor messages unless it records expected tokens, synchronizing sets, and the context of the failed prediction.³

leftmost derivation

A derivation that always expands the leftmost nonterminal first.

lookahead

Input tokens examined before a parser chooses a production.

FIRST set

The set of terminals that can begin strings derived from a grammar symbol or sequence.

FOLLOW set

The set of terminals that can appear immediately after a nonterminal in some sentential form.

left factoring

A grammar transformation that removes a shared prefix from competing alternatives.

left recursion

A grammar pattern in which a nonterminal can derive a sentential form beginning with itself.