Parsingtypical

LL Parsing, FIRST and FOLLOW

Left-to-right scan, leftmost derivation, k tokens of lookahead. The FIRST and FOLLOW sets are the mechanical answer to "which production do I pick", and the reason some grammars simply cannot be parsed top-down.

The question

What does the "LL" in LL(1) actually mean, and how does a parser decide which production to use?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

The parser holds a stack of grammar symbols — what it still expects to see — and a position in the token stream. The stack starts as just the start symbol. At every step the top of the stack is either a terminal, which must match the next token, or a nonterminal, which is replaced by the right-hand side of exactly one production. That stack is a partially-expanded leftmost derivation: read it together with the tokens already consumed and you have the current sentential form.

What this phase may assume or do

A grammar is LL(k) exactly when, for every nonterminal, the next k tokens uniquely determine which of its productions to apply. Formally, for LL(1): for any two alternatives A -> α and A -> β, FIRST(α) and FIRST(β) must be disjoint, and if one of them can derive the empty string, the other's FIRST set must be disjoint from FOLLOW(A). Fail either condition and the parse table has a cell with two entries, which is a conflict — the parser cannot decide, and no amount of implementation cleverness fixes it, because the information it would need is not in the next k tokens.

Key points

LL = left-to-right scan, leftmost derivation. The second L is the substantive one: it means top-down, choosing a production before seeing what it matches.
The parser's state is a stack of expected grammar symbols; that stack is a partially-expanded leftmost derivation.
FIRST(α) answers "if I pick this production, what token comes next"; FOLLOW(A) answers "when may I pick a production that derives nothing".
The parse table has a row per nonterminal and a column per terminal; LL(1) means no cell holds two productions.
Left recursion and common prefixes both break LL(1); the first is fixed by rewriting to iteration, the second by left factoring.
Some grammars are LL(k) for no k at all, because the deciding evidence lies an unbounded distance ahead.
A recursive-descent parser computes this table implicitly: its lookahead conditions are FIRST sets and its stopping conditions are FOLLOW sets.

Reading the name

The two letters are two separate facts, and both are worth unpacking because the second one is what people usually miss.

The first L is *left-to-right*: the input is scanned once, forward, with no backtracking and no rescanning. Every mainstream parsing family shares this.

The second L is *leftmost derivation*: at each step the parser expands the leftmost nonterminal in the sentential form. That is what makes it top-down — it starts at the start symbol and works outward toward the tokens, choosing a production before it has seen what that production will match. [[lr-parsing]] differs in exactly this letter: R for rightmost derivation, discovered in reverse, which is bottom-up.

The number in parentheses is how many tokens of lookahead the decision is allowed to consult. LL(1) means one. LL(k) means a fixed k. The important consequence is that the parser must commit before it has evidence: at the moment it chooses a production for a nonterminal, the tokens that would confirm the choice have not been read yet. Everything difficult about top-down parsing follows from that sentence.

The grammar has to be prepared

The stratified grammar from [[what-parsing-does]] cannot be used directly: expr -> expr '+' term expands the leftmost nonterminal to itself, so a leftmost derivation never makes progress — the same non-termination that kills a hand-written parser in [[recursive-descent]], seen from the derivation side rather than the call-stack side.

Eliminating left recursion produces the grammar below, with tail nonterminals E' and T' that may derive nothing. This is the canonical LL(1) expression grammar, and the epsilon productions in it are what make FOLLOW sets necessary — without them, FIRST alone would decide everything.

The canonical LL(1) expression grammar, and a leftmost derivation of 1 + 2 * 3

E	::=	T E'	Every expression is a term followed by an optional tail.
E'	::=	'+' T E' \| ε	The tail. ε is what allows the expression to simply end.
T	::=	F T'
T'	::=	'*' F T' \| ε
F	::=	NUMBER \| '(' E ')'

Deriving 1 + 2 * 3

1.Eapplying start
2.T E'applying E -> T E'
3.F T' E'applying T -> F T'
4.1 T' E'applying F -> NUMBER, lookahead was NUMBER
5.1 E'applying T' -> ε, lookahead was '+' which is in FOLLOW(T')
6.1 '+' T E'applying E' -> '+' T E', lookahead was '+'
7.1 '+' F T' E'applying T -> F T'
8.1 '+' 2 T' E'applying F -> NUMBER
9.1 '+' 2 '*' F T' E'applying T' -> '*' F T', lookahead was '*'
10.1 '+' 2 '*' 3 T' E'applying F -> NUMBER
11.1 '+' 2 '*' 3 E'applying T' -> ε, lookahead is $
12.1 '+' 2 '*' 3applying E' -> ε, lookahead is $

FIRST and FOLLOW

Two sets per symbol, and they exist to answer one question each.

FIRST(α) is the set of terminals that can begin a string derived from α, plus ε if α can derive the empty string. It answers: *if I choose this production, what is the first token I will see?* When a nonterminal has several alternatives with disjoint FIRST sets, the lookahead picks one, and the decision is made.

FOLLOW(A) is the set of terminals that can appear immediately after A in some sentential form, plus the end marker $ if A can end the input. It answers a question FIRST cannot: *this production derives nothing at all, so when am I allowed to use it?* An epsilon production is chosen precisely when the lookahead is something that could legally follow the nonterminal — because if the nonterminal produces nothing, the next token must belong to whatever comes after it.

They are computed by fixed-point iteration: start with empty sets, apply the rules repeatedly until nothing changes. That is the same shape as every analysis in [[data-flow-framework]], and it is worth noticing that the compiler is already doing fixed-point reasoning before it has built a single tree.

FIRST and FOLLOW for the grammar above

Symbol	FIRST	FOLLOW	What the set is deciding
E	{ NUMBER, ( }	{ ), $ }	An expression starts with a number or a parenthesis, and can only be followed by `)` or end of input.
E'	{ +, ε }	{ ), $ }	Choose the `+` alternative on `+`; choose ε on `)` or `$` — which is exactly FOLLOW(E').
T	{ NUMBER, ( }	{ +, ), $ }	A term ends when the next token is `+`, `)` or end.
T'	{ *, ε }	{ +, ), $ }	Choose `` on ``; choose ε on anything in FOLLOW — this is why `1 + 2` does not try to multiply.
F	{ NUMBER, ( }	{ *, +, ), $ }	Two alternatives with disjoint FIRST sets: NUMBER picks one, `(` picks the other.

The parse table, and what a conflict looks like

simplifiedThis table is built by hand for five nonterminals and six terminals. A real language has hundreds of each, and the table is generated — by ANTLR, by a hand-rolled tool, or not at all if the parser is recursive descent, in which case the table exists only implicitly as the branch conditions in each function. The conditions are identical either way: a recursive-descent parser that branches on lookahead is computing this table's row at runtime, and a grammar that is not LL(1) shows up there as an if that cannot be written.

Put the two sets together and the table writes itself. For each production A -> α, put that production in row A under every terminal in FIRST(α); if α can derive ε, put it under every terminal in FOLLOW(A) as well. Every empty cell is a syntax error, and — usefully — the set of non-empty cells in a row is exactly the set of tokens that would have been legal there, which is where a table-driven parser gets its "expected one of..." message.

The LL(1) condition is now visible as a property of the table: no cell may contain two productions. If it does, the lookahead does not determine the choice, and the grammar is not LL(1). The classic case is a common prefix — stmt -> 'if' expr 'then' stmt | 'if' expr 'then' stmt 'else' stmt puts both productions in the if cell — which left factoring fixes by pulling the shared prefix out into stmt -> 'if' expr 'then' stmt tail with tail -> 'else' stmt | ε. The other classic case is left recursion, which puts a production in a cell it can never usefully occupy.

What left factoring cannot fix is a grammar that genuinely needs to see arbitrarily far ahead. A -> x* 'a' | x* 'b' is not LL(k) for any k, because deciding requires reading past an unbounded run of x. Bottom-up parsing handles it without difficulty, because it never has to choose in advance — see [[ll-vs-lr]].

The LL(1) parse table. Row = nonterminal on the stack, column = lookahead token

	NUMBER	+	*	(	)	$
E	E -> T E'	—	—	E -> T E'	—	—
E'	—	E' -> '+' T E'	—	—	E' -> ε	E' -> ε
T	T -> F T'	—	—	T -> F T'	—	—
T'	—	T' -> ε	T' -> '*' F T'	—	T' -> ε	T' -> ε
F	F -> NUMBER	—	—	F -> '(' E ')'	—	—

The table and the recursion are the same parser

A table-driven LL(1) parser and a recursive-descent parser for the same grammar make identical decisions. The difference is where the stack lives: explicit and on the heap in the table-driven version, implicit in the call stack in the recursive one. That has consequences worth knowing — the table-driven parser cannot overflow the runtime stack on deeply nested input, and its table can be regenerated when the grammar changes — and one large drawback: it has nowhere to hang a good error message, because there is no per-construct code to put one in.

The practical upshot for a hand-written parser is that FIRST and FOLLOW are not academic. When you write if (peek() is NUMBER or LPAREN) parseFactor(), that condition *is* FIRST(F). When you write "the operand list ends when the lookahead is ) or ,", that set is FOLLOW. Getting them wrong is what produces a parser that mysteriously stops early on some inputs, and the sets are the tool for reasoning about it — including during error recovery, where FOLLOW sets are exactly the tokens a construct is allowed to resume at, which is the subject of [[parser-synchronization]].

The table-driven loop: nine lines, and the same decisions the recursive parser makes

1stack = [ '$', START ]
2lookahead = tokens.next()
3 
4while stack is not empty:
5    top = stack.pop()
6 
7    if top is a terminal:
8        if top == lookahead.kind:
9            lookahead = tokens.next()          # match and advance
10        else:
11            error("Expected " + top + ", found " + lookahead.text)
12 
13    else:                                       # top is a nonterminal
14        production = TABLE[top][lookahead.kind]
15        if production is empty:
16            # The non-empty cells in TABLE[top] are exactly the legal tokens here.
17            error("Expected one of " + keys(TABLE[top]) + ", found " + lookahead.text)
18        else:
19            push production.rhs onto stack in REVERSE order   # leftmost symbol on top

The reverse push is the only fiddly part, and it is what makes the stack a leftmost derivation: the leftmost symbol of the production ends up on top, so it is the next thing expanded. Note also what the parser does *not* have: any place to build a tree. Table-driven LL parsers attach semantic actions to productions to do that, and those actions are where the readability goes.

How it works

The steps, in the order the compiler takes them.

Compute FIRST for every symbol by fixed-point iteration: FIRST of a terminal is itself; FIRST of A -> X₁…Xₙ includes FIRST(X₁), and continues into X₂ only if X₁ can derive ε.
Compute FOLLOW similarly: FOLLOW(start) contains $; for A -> αBβ add FIRST(β) minus ε to FOLLOW(B), and if β can derive ε add FOLLOW(A) to FOLLOW(B).
Build the table: production A -> α goes under every terminal in FIRST(α), and additionally under every terminal in FOLLOW(A) if α can derive ε.
Report a conflict if any cell receives two productions — that is the grammar failing the LL(1) condition, not the tool failing.
At parse time, push the start symbol and the end marker; repeatedly pop the top symbol.
A terminal on top must equal the lookahead: match it and advance, or report an error naming the expected terminal.
A nonterminal on top is replaced by the right-hand side selected from the table, pushed in reverse so the leftmost symbol is on top.
The parse succeeds when the stack holds only the end marker and the lookahead is end of input.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

The generator reports a conflict in a cell and the grammar author "fixes" it by deleting one of the two productions, silently removing a construct from the language.
A FOLLOW set is computed too small by hand, so an epsilon production is not chosen where it should be, and a construct fails to terminate — the parser reports an error at the token after a perfectly valid statement.
A FOLLOW set is computed too large, and the parser accepts input the grammar does not describe; the error surfaces much later as a malformed tree rather than a syntax error.
The grammar is left-factored to satisfy LL(1) and the resulting tree shape changes, so associativity or the attachment of an optional clause silently inverts.
A table-driven parser reports "expected one of NUMBER, IDENT, (, [, {, -, !, ++, --, new, this, ..." — a machine-derived list of thirty tokens that tells the user nothing about what they actually did wrong.
A hand-written parser's lookahead condition and the language grammar's FIRST set disagree for one rarely used construct, so that construct is rejected only when it appears in a particular position.

When it helps

Designing a language: checking that the grammar is LL(1) is a cheap, mechanical test that it can be parsed by hand-written recursive descent, which is the frontend most implementations will want.
Debugging a hand-written parser that stops early or too late — the FOLLOW set of the construct in question is usually the thing that is wrong.
Writing error recovery, where FOLLOW sets are the natural synchronization sets.
Reading a generator's conflict report: knowing that a conflict is a property of the grammar and not of the tool is what stops you looking for a flag to silence it.

When it hurts

Grammars you do not control that were written for LR tools. Making them LL requires eliminating left recursion and left factoring, both of which change the tree shape and neither of which is always mechanical.
Languages with genuinely unbounded lookahead requirements — C++ type-versus-expression ambiguity, some template syntaxes — where no k suffices and the real implementations use speculative parsing with backtracking instead.
Deriving user-facing messages from the table. The "expected one of" list is complete and correct and reads as noise; good diagnostics need construct-level knowledge the table does not have.

What it costs

Every one of these is paid by something.

A one-token lookahead decision buys a parser that runs in linear time with no backtracking and a table that is small enough to verify, and pays with a grammar that must be rewritten — left recursion out, common prefixes factored — so that the grammar in the implementation is no longer the grammar in the specification.
The explicit symbol stack buys immunity to runtime stack overflow on deep nesting and a table that can be regenerated when the grammar changes, and costs every diagnostic: there is no per-construct code, so there is nowhere to write a message better than "expected one of".
Computing FIRST and FOLLOW mechanically buys a decidable answer to "is this grammar parseable this way" before a line of parser is written, and pays a real learning cost — these are the sets every practitioner half-remembers, and getting FOLLOW subtly wrong by hand is common.
Left factoring buys LL(1) conformance and costs tree shape: the factored grammar produces a different derivation, so any semantic action or AST construction attached to the original productions has to be rewritten, and the correspondence to the language reference is weakened.

What else you could do

What a different compiler or language does instead, and when that is better.

[[recursive-descent]] implements the same decisions in code rather than a table, trading regenerability for arbitrary diagnostics and per-construct recovery. It is what almost every production compiler actually ships.
ANTLR's ALL(*) keeps the top-down shape but decides productions by simulating an automaton over the remaining input at parse time, giving effectively unbounded lookahead and accepting many non-LL(k) grammars, at the cost of a decision procedure whose worst-case time is not linear.
[[lr-parsing]] postpones every decision until the entire right-hand side has been seen, which handles left recursion natively and accepts a strictly larger class of grammars — see [[ll-vs-lr]] for why most compilers still do not use it.
PEG replaces the "choose one production" problem with ordered choice: try alternatives in order and take the first that succeeds. Conflicts become impossible by construction, which is exactly the criticism — an ambiguity that LL would have reported as a conflict is silently resolved by rule order instead.

See it for yourself

The flag, dump or tool that shows you this directly.

ANTLR: antlr4 -Xlog Grammar.g4 reports the decisions it could not make with fixed lookahead, and grun Grammar rule -gui renders the parse tree it produced.
Compute the sets on a small grammar by hand once, then check yourself against any of the online FIRST/FOLLOW calculators — the value is in seeing which entry you got wrong, and it is almost always a FOLLOW involving an epsilon production.
In a hand-written parser, grep for the lookahead conditions: every if (peek() == ...) selecting an alternative is a FIRST set, and every loop-exit condition is a FOLLOW set. Writing them down is often the fastest way to find why a construct terminates in the wrong place.
Bison will happily report that an LL-shaped grammar is fine, because it is LR; to test LL-ness specifically you need an LL tool such as ANTLR or a FIRST/FOLLOW calculator.
Our deriver at /compilers/grammar steps a leftmost derivation one production at a time and shows the lookahead that selected each.

Plausible wrong readings

Stated the way a confident engineer states them.

"LL(1) means the parser looks at one token." It means the *decision* about which production to apply consults one token. The parser reads the whole input; it just never needs more than one token in hand to choose.
"FOLLOW sets tell you what token comes next." They tell you what token *could* come after a nonterminal in some sentential form, across the whole grammar. That is a static over-approximation, not a prediction about this input, and it is why FOLLOW-based decisions can accept slightly more than the grammar describes.
"If my grammar is not LL(1) I need a more powerful parser." Usually you need to rewrite the grammar — left recursion and common prefixes are both mechanically removable, and between them they account for most conflicts.
"LL(2) is twice as powerful as LL(1)." Increasing k does enlarge the class of grammars, but the classic hard cases — left recursion, unbounded common prefixes — are not fixed by any finite k.
"Recursive descent is not LL parsing." It is LL parsing with the stack in the call frames. Every branch it makes is a table lookup that was inlined.

Misconceptions

The claim, and what is actually true.

LL and recursive descent are different techniques.

Recursive descent is the standard implementation of LL. The FIRST sets become if conditions and the FOLLOW sets become loop-exit conditions.

A grammar conflict is a tool limitation you can configure away.

A conflict says the next k tokens do not determine the choice. That is a fact about the grammar. Suppressing the report picks one branch arbitrarily and changes the language the parser accepts.

FIRST and FOLLOW only matter if you use a generator.

They are what you are computing in your head every time you write a lookahead condition or decide when a loop stops. Doing it informally is exactly how a hand-written parser ends up rejecting a valid construct in one position only.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

An LL parser works from the start symbol downward, and at each point it has to guess which grammar rule applies using only the next token. FIRST tells it which tokens each rule can begin with, so the guess is usually forced. FOLLOW handles the awkward case where a rule can produce nothing at all: then the parser looks for a token that could legally come *after*, and concludes the rule matched nothing.

practical

You will meet these sets whether or not you use a generator. If your hand-written parser rejects a valid construct, write out the FIRST set of the alternative it should have chosen and compare it against the actual if condition. If it stops one construct too early or runs one too far, the FOLLOW set of that construct is wrong. And when you add a syntax to a language, check for a common prefix with an existing rule before writing any code — that is the conflict that costs the most to discover late, because fixing it by left factoring changes the tree shape and therefore every semantic action attached to it.

advanced

The real content of the LL condition is an information constraint: the parser must commit to a production before reading the evidence for it. That is why the fixes are all about moving the evidence earlier — left factoring delays the commitment until the prefix is consumed, and increasing k buys a bounded window. It is also why the whole family loses to LR on grammar power: an LR parser never commits until the entire right-hand side is on the stack, so it always has more evidence. The counter-argument, and it is the one that decides real implementations, is that committing early is what leaves you *inside a named construct* when something goes wrong — which is worth a great deal for error messages and for recovery, and is worth nothing at all to a grammar-power comparison.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

typicalThe claim that mainstream languages are "basically LL(1)" holds for the core of Java, Go, Pascal and Python but is not exact for any of them: Python needs the indentation-driven INDENT/DEDENT tokens the lexer synthesises, Java needs unbounded lookahead to distinguish a cast from a parenthesised expression, and Go's composite-literal-versus-block ambiguity is resolved by a parser flag rather than by the grammar. Every real implementation has at least one such exception.

implementationANTLR 4 is the mainstream LL-family generator, and its ALL(*) algorithm is materially more powerful than LL(k): it resolves ambiguity by simulating the grammar over the actual remaining input, so grammars that no fixed k accepts are parsed. Do not use ANTLR as evidence about what LL(k) can do; it can do more, and it pays with a decision procedure that is not linear-time in the worst case.

simplifiedThe FOLLOW-set rule shown ("add the production under FOLLOW(A) when α derives ε") is the standard construction and it is slightly permissive: it can admit some strings the grammar does not generate before an error is detected. Practical generators layer additional checks on top; the construction here is the textbook one and is what conflicts are reported against.

If you were asked this in an interview

What do the two Ls stand for, and which one actually constrains the grammar?
Why do we need FOLLOW sets at all if FIRST tells us which production to pick?
My grammar has a conflict in the cell for if. What is wrong with the grammar and what is the standard fix?

Connections

DSAstack hash-table dfs

Domains that do not exist yet

Programming Languages & Runtime Internals — An explicit stack machine as an execution strategy
The table-driven LL loop is a stack machine over grammar symbols rather than values. The general mechanics of stack machines and their dispatch loops are the runtime's subject; [[stack-based-vm]] is our compiler-side version.