FIRST and FOLLOW sets are the first thing to compute in predictive (LL(1)) parsing, and a standard compiler-design exam question. This page works them out for the classic expression grammar from the Dragon Book, then uses them to build the LL(1) table and parse an input.
The grammar
The usual expression grammar is left-recursive, which an LL(1) parser can't handle:
E → E + T | T
T → T * F | F
F → ( E ) | id
Removing the left recursion (A → Aα | β becomes A → βA′, A′ → αA′ | ε) gives:
E → T E′
E′ → + T E′ | ε
T → F T′
T′ → * F T′ | ε
F → ( E ) | id
FIRST sets
FIRST(α) is the set of terminals that can begin a string derived from α, plus ε if α can derive the empty string. The rules:
- For a terminal a, FIRST(a) = {a}.
- For A → ε, add ε to FIRST(A).
- For A → Y₁Y₂…, add FIRST(Y₁) without ε; if Y₁ can be ε, add FIRST(Y₂) too, and so on. If every Yᵢ can be ε, add ε.
Working bottom-up:
- FIRST(F) = { (, id }: F starts with ( or id.
- FIRST(T) = FIRST(F) = { (, id }: T → F T′ and F can't be ε.
- FIRST(E) = FIRST(T) = { (, id }.
- FIRST(E′) = { +, ε }.
- FIRST(T′) = { *, ε }.
FOLLOW sets
FOLLOW(A) is the set of terminals that can appear immediately after A in some sentential form, with $ for the end of input. The rules:
- Put $ in FOLLOW(start symbol).
- For A → αBβ, add FIRST(β) without ε to FOLLOW(B).
- For A → αB, or A → αBβ where β can be ε, add FOLLOW(A) to FOLLOW(B).
Repeat until nothing changes:
- FOLLOW(E) = { ), $ }: $ because E is the start symbol, ) from F → ( E ).
- FOLLOW(E′) = FOLLOW(E) = { ), $ }: E′ is at the end of E → T E′ (and of its own rule).
- FOLLOW(T) = FIRST(E′) without ε, plus FOLLOW(E), because E′ can be ε = { +, ), $ }.
- FOLLOW(T′) = FOLLOW(T) = { +, ), $ }.
- FOLLOW(F) = FIRST(T′) without ε, plus FOLLOW(T), because T′ can be ε = { *, +, ), $ }.
| Non-terminal | FIRST | FOLLOW |
|---|---|---|
| E | ( id | ) $ |
| E′ | + ε | ) $ |
| T | ( id | + ) $ |
| T′ | * ε | + ) $ |
| F | ( id | * + ) $ |
The LL(1) parsing table
For each production A → α, put it in row A under every terminal in FIRST(α); if α can be ε, also under every terminal in FOLLOW(A). (The table writes E′ as E', T′ as T'.)
| id | + | * | ( | ) | $ | |
|---|---|---|---|---|---|---|
| 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 → id | F → ( E ) |
No cell holds two productions, so the grammar is LL(1). A cell with two entries would be a conflict: FIRST/FIRST when two alternatives start with the same terminal, FIRST/FOLLOW when an ε-alternative's FOLLOW overlaps another alternative's FIRST.
Parsing id + id * id
Start with $ E on the stack (top on the right) and the input followed by $. At each step, if the top is a terminal, match it; if it's a non-terminal, replace it with the production from the table.
| Stack | Input | Action |
|---|---|---|
| $ E | id + id * id $ | Output E → T E' |
| $ E' T | id + id * id $ | Output T → F T' |
| $ E' T' F | id + id * id $ | Output F → id |
| $ E' T' id | id + id * id $ | Match id |
| $ E' T' | + id * id $ | Output T' → ε |
| $ E' | + id * id $ | Output E' → + T E' |
| $ E' T + | + id * id $ | Match + |
| $ E' T | id * id $ | Output T → F T' |
| $ E' T' F | id * id $ | Output F → id |
| $ E' T' id | id * id $ | Match id |
| $ E' T' | * id $ | Output T' → * F T' |
| $ E' T' F * | * id $ | Match * |
| $ E' T' F | id $ | Output F → id |
| $ E' T' id | id $ | Match id |
| $ E' T' | $ | Output T' → ε |
| $ E' | $ | Output E' → ε |
| $ | $ | Accept |
The input is accepted in 17 steps. Notice T′ → ε fires when the next token is + or $: exactly the FOLLOW(T′) entries in the table.
Common mistakes
- Putting ε in a FOLLOW set. FOLLOW sets never contain ε; $ marks the end instead.
- Stopping rule 3 too early. If E′ can be ε, FOLLOW(E) flows into FOLLOW(T) as well; keep iterating until no set changes.
- Building the table from the left-recursive grammar. Remove left recursion (and left-factor) first.
- Forgetting $ in FOLLOW of the start symbol.
Check your own answers
The FIRST and FOLLOW calculator computes both sets for any grammar and explains each entry. The LL(1) parser builds the table, classifies any conflicts, removes left recursion, and traces a parse step by step; for bottom-up parsing, use the LR parser.
For a related walkthrough, read Three Address Code: Examples and Quadruples.