LL(1) Predictive Parsing Tables

Everything so far has been preparation. We took a grammar, stripped its left recursion and common prefixes, and computed its FIRST and FOLLOW sets. Now we cash it all in. An LL(1) parser is a beautifully simple machine: an explicit stack, a pointer into the input, and a two-dimensional lookup table that tells it, deterministically, exactly what to do next. No backtracking, no guessing, linear time. The table is the compiler's crystallised knowledge of the grammar.

The name decodes as: L — scan the input Left to right; L — produce a Leftmost derivation; (1) — using one token of lookahead. That single lookahead token, matched against the top-of-stack nonterminal, indexes the table and picks the production. If one token always suffices to choose, the grammar is LL(1).

Building the table M[A, a]

The table has a row per nonterminal A and a column per terminal a (including the end-marker \$). Each cell M[A, a] holds the production to expand A by when the next input token is a — or is blank, meaning "error". The construction rule is two lines, and it is entirely driven by FIRST and FOLLOW:

For each production A \to \alpha and each terminal a \in \mathrm{FIRST}(\alpha), put A \to \alpha in M[A, a].
If \varepsilon \in \mathrm{FIRST}(\alpha), then for each terminal b \in \mathrm{FOLLOW}(A) put A \to \alpha in M[A, b] (and in M[A, \$] if \$ \in \mathrm{FOLLOW}(A)).
Every cell left undefined is an error entry.

The intuition is exactly the two questions FIRST and FOLLOW answer. FIRST tells you "this production can start with token a, so use it on a". FOLLOW handles the vanishing case: if \alpha can derive \varepsilon, then choosing A \to \alpha makes A disappear, which is the right move precisely when the next token is one that can legally follow A.

Here is the finished table for the expression grammar. Blank cells are errors:

M[A,a]	\mathbf{id}	+	*	(	)	\$
E	E \to T E'			E \to T E'
E'		E' \to + T E'			E' \to \varepsilon	E' \to \varepsilon
T	T \to F T'			T \to F T'
T'		T' \to \varepsilon	T' \to * F T'		T' \to \varepsilon	T' \to \varepsilon
F	F \to \mathbf{id}			F \to (\,E\,)

Every cell holds at most one production. That is the signature of an LL(1) grammar — and the whole point.

The table-driven predictive parser

The engine that drives the table never changes — only the table does. Push the start symbol and \$ onto a stack, append \$ to the input, then loop on the top-of-stack symbol X against the current input token a:

If X is a terminal: it must equal a — pop and advance (a match). Otherwise, error.
If X is a nonterminal: consult M[X, a]. If it holds X \to Y_1 Y_2 \dots Y_k, pop X and push Y_k \dots Y_2 Y_1 (reversed, so Y_1 ends up on top). If the cell is blank, error.
Accept when X = \$ and a = \$.

The picture to keep in your head — stack on one side, input buffer on the other, the table as an oracle in the middle emitting productions:

Watch it parse \mathbf{id} + \mathbf{id} * \mathbf{id}. The stack is shown with its top on the left; each row is one loop iteration:

Stack (top left)	Input	Action
E\,\$	\mathbf{id}+\mathbf{id}*\mathbf{id}\,\$	output E \to T E'
T\,E'\,\$	\mathbf{id}+\mathbf{id}*\mathbf{id}\,\$	output T \to F T'
F\,T'\,E'\,\$	\mathbf{id}+\dots	output F \to \mathbf{id}
\mathbf{id}\,T'\,E'\,\$	\mathbf{id}+\dots	match \mathbf{id}
T'\,E'\,\$	+\,\mathbf{id}*\mathbf{id}\,\$	output T' \to \varepsilon
E'\,\$	+\,\mathbf{id}*\mathbf{id}\,\$	output E' \to + T E'
+\,T\,E'\,\$	+\,\mathbf{id}*\mathbf{id}\,\$	match +
… (parse the \mathbf{id}*\mathbf{id} term) …
E'\,\$	\$	output E' \to \varepsilon
\$	\$	accept

Read the sequence of "output" lines top to bottom and you have reconstructed the leftmost derivation — which is exactly what the two Ls in "LL" promised.

The parser, in code

The whole engine is about twenty lines. The table below is the one we built above; the driver is grammar- independent.

type Prod = string[]; // right-hand side; "eps" = ε type Table = Record<string, Record<string, Prod>>; // M[A][a] = production const M: Table = { E: { id: ["T", "E'"], "(": ["T", "E'"] }, "E'": { "+": ["+", "T", "E'"], ")": ["eps"], "$": ["eps"] }, T: { id: ["F", "T'"], "(": ["F", "T'"] }, "T'": { "+": ["eps"], "*": ["*", "F", "T'"], ")": ["eps"], "$": ["eps"] }, F: { id: ["id"], "(": ["(", "E", ")"] }, }; const isNT = (X: string) => X in M; function parse(input: string[]): boolean { const inp = [...input, "$"]; const stack: string[] = ["$", "E"]; // bottom $, top E let i = 0; while (stack.length) { const X = stack.pop()!; // top of stack const a = inp[i]; if (X === "$") { return a === "$"; } // accept iff input also exhausted if (!isNT(X)) { // terminal: must match if (X === a) { i++; continue; } console.log(`error: expected '${X}', saw '${a}'`); return false; } const prod = M[X]?.[a]; // nonterminal: consult the table if (!prod) { console.log(`error: no rule M[${X}, ${a}]`); return false; } console.log(`${X} -> ${prod.join(" ")}`); if (prod[0] !== "eps") { for (let k = prod.length - 1; k >= 0; k--) stack.push(prod[k]); // push reversed } } return false; } console.log("Parsing id + id * id"); console.log("accepted:", parse(["id", "+", "id", "*", "id"])); console.log("---"); console.log("Parsing id + (malformed)"); console.log("accepted:", parse(["id", "+"]));

The good input prints its leftmost derivation and accepts; the malformed input hits a blank cell / early \$ and is rejected with a precise message. That precision — knowing exactly which token was unexpected — is a real virtue of predictive parsing.

When a cell holds two productions: a conflict

The table construction says "put the production in the cell". What if two different productions both want the same cell M[A, a]? That is a conflict — a multiply-defined entry — and it means the grammar is not LL(1): one token of lookahead cannot decide between the two rules. It happens exactly when two productions for A have overlapping FIRST sets, or when a nullable production's FIRST overlaps A's FOLLOW.

A grammar is LL(1) iff its predictive table has no multiply-defined entry — every cell holds at most one production.
Equivalently: for every pair of productions A \to \alpha \mid \beta, FIRST(\alpha) and FIRST(\beta) are disjoint, and if one derives \varepsilon its counterpart's FIRST is disjoint from FOLLOW(A).
Every LL(1) grammar is unambiguous — but not every unambiguous grammar is LL(1).

The classic non-LL(1) offender is the dangling-\mathbf{else} grammar: even after left factoring, the helper S' \to \mathbf{else}\ S \mid \varepsilon puts both \mathbf{else} (from FIRST) and — because it is nullable — \mathbf{else} again (from FOLLOW) into the same cell. Real tools break that tie by preferring the non-\varepsilon rule ("shift the \mathbf{else}"), which is precisely the "nearest \mathbf{if}" convention.

One token is a sweet spot: the table is small (nonterminals × terminals) and each step is a single array lookup, so parsing is genuinely linear with a tiny constant. Peeking further ahead is possible — LL(k) indexes the table by the next k tokens, growing its power but blowing the table up combinatorially (columns become k-tuples of terminals). Modern recursive-descent tools like ANTLR go further with LL(*), using an on-the-fly sub-automaton to look ahead a variable, unbounded distance when one token is not enough, falling back to cheap LL(1) decisions when it is. But the humble LL(1) table remains the thing every compiler course builds by hand, because it exposes the entire mechanism — FIRST, FOLLOW, table, stack — with nothing hidden.

Do not expect to feed a raw grammar to the LL(1) construction. Two preconditions are mandatory: the grammar must have no left recursion (or the derivation loops forever) and must be left factored (or two productions share a FIRST prefix and collide in a cell). Those transformations are prerequisites, not optional polish. But here is the sting in the tail: even a grammar that is both non-left-recursive and left-factored can still fail to be LL(1). Left factoring only removes overlaps caused by identical prefixes; overlaps caused by two productions whose FIRST sets happen to share a token further in, or by the nullable-FIRST-meets-FOLLOW case, survive and produce conflicts anyway. LL(1) is a genuinely restricted class. When a grammar resists every rewrite, the honest move is to step up to a more powerful method — bottom-up LR / LALR parsing — rather than to keep torturing the grammar.