Designing the FIRST and FOLLOW Sets for a Grammar

Verified Sources

Nov 4, 2026

To design LL(1) parsing logic, you must compute two lookahead sets for each nonterminal in a context-free grammar: FIRST and [FOLLOW]{def="Set of terminals (and possibly $) that can appear immediately to the right of a nonterminal in some sentential form"}. These sets are constructed using production rules and (for many grammars) an iterative "fixed-point" procedure until they stop changing. Standard definitions treat ε as a special case in FIRST, and the end-marker [$ ]{def="Input end marker used in parsing tables and FOLLOW sets"} as a special case in FOLLOW (added for the start symbol).2

Key idea:

FIRST focuses on “what tokens can start what this nonterminal can generate.”
FOLLOW focuses on “what tokens can legally follow this nonterminal in some derivation,” which is essential for resolving parsing decisions.

Learning targets (what you should be able to do)

Compute FIRST(X) for every nonterminal $X$ .
Compute [FOLLOW]{def="Set of terminals (and possibly $) that can appear immediately to the right of a nonterminal in some sentential form"}(A) for every nonterminal$ A$.
Correctly handle ε propagation and when to stop scanning symbols in a production body.

"FIRST set (context-free grammar) — Wikipedia" https://en.wikipedia.org/wiki/LL_parser - Defines FIRST concept and ε handling in LL parsing. ↩
"FOLLOW set (context-free grammar) — Wikipedia" https://en.wikipedia.org/wiki/LL_parser - Defines FOLLOW computation, including $ and propagation rules. ↩ ↩²

FIRST and FOLLOW Sets (LL(1) Parsing) — Core Examples

Core definitions you will use

Let $G=(V,T,P,S)$ where $V$ are nonterminals, $T$ terminals, $P$ productions, and $S$ start symbol.

FIRST of a string of grammar symbols

To compute FIRST for a production body like $X_1X_2\cdots X_k$ , you need a helper notion: FIRST of a sequence. A standard rule is:

Add $\;t\in T$ to $\text{FIRST}(X_1X_2\cdots X_k)$ if $t\in \text{FIRST}(X_i)$ for the first position $i$ where $X_i$ can derive something starting with $t$ .
If $X_1$ can derive ε, then FIRST can include what starts from $X_2$ as well; similarly continue.
If every symbol $X_i$ in the sequence can derive ε, then ε is included in FIRST of the sequence.

This “scan left-to-right until a symbol can’t derive ε” behavior is crucial to avoid over-approximations and to make your algorithm converge correctly.

FOLLOW of a nonterminal

$\text{FOLLOW}(A)$ collects terminals that can appear immediately after $A$ in some sentential form $\,\alpha A \beta\Rightarrow^* \alpha a \gamma\,$ where $a$ is a terminal and $\gamma$ is any string of symbols.

Operationally, in LL(1) computation:

Add $\,\$ , $to$ \text{FOLLOW}(S)$.
For each production $A\to \alpha B \beta$ , everything in $\text{FIRST}(\beta)$ (except ε) goes into $\text{FOLLOW}(B)$ .
If $\beta$ can derive ε (or if $\beta$ is empty), then $\text{FOLLOW}(A)$ goes into $\text{FOLLOW}(B)$ .

"FIRST set (context-free grammar) — Wikipedia" https://en.wikipedia.org/wiki/LL_parser - Defines FIRST concept and ε handling in LL parsing. ↩ ↩²
"FOLLOW set (context-free grammar) — Wikipedia" https://en.wikipedia.org/wiki/LL_parser - Defines FOLLOW computation, including $ and propagation rules. ↩ ↩²

Pro Tip: Treat ε as a “permission to continue”

When scanning a production body for FIRST/FOLLOW propagation, ε doesn’t add a terminal token. Instead, ε tells you that you should keep looking at later symbols. This prevents the common mistake of stopping too early.

"FIRST set (context-free grammar) — Wikipedia" https://en.wikipedia.org/wiki/LL_parser - Defines FIRST concept and ε handling in LL parsing. ↩

Common Pitfall: Adding ε into FOLLOW sets

In standard LL(1) construction rules, FOLLOW sets contain terminals and $ only; ε is handled indirectly via “if the remainder can derive ε” rules. Don’t place ε directly into FOLLOW(A) when adding FIRST(β).

"FOLLOW set (context-free grammar) — Wikipedia" https://en.wikipedia.org/wiki/LL_parser - Defines FOLLOW computation, including $ and propagation rules. ↩

Step-by-step algorithm to compute FIRST sets

1
Step 1
For every terminal $a\in T$ , set $\text{FIRST}(a)=\{a\}$ . For every nonterminal $A\in V$ , initialize $\text{FIRST}(A)=\emptyset$ . If the grammar contains an explicit production $A\to \epsilon$ , then include ε in $\text{FIRST}(A)$ (usually as part of your iterative update logic).

Footnotes

"FIRST set (context-free grammar) — Wikipedia" https://en.wikipedia.org/wiki/LL_parser - Defines FIRST concept and ε handling in LL parsing. ↩
2
Step 2
For each production $A\to X_1X_2\cdots X_k$ , compute what can start strings derived from the RHS: add $\text{FIRST}(X_1)$ excluding ε to $\text{FIRST}(A)$ . If $\epsilon\in \text{FIRST}(X_1)$ , also add $\text{FIRST}(X_2)$ excluding ε, and so on. Keep going while the prefix symbols can derive ε.

Footnotes

"FIRST set (context-free grammar) — Wikipedia" https://en.wikipedia.org/wiki/LL_parser - Defines FIRST concept and ε handling in LL parsing. ↩
3
Step 3
If ε is in FIRST of every symbol $X_i$ in the RHS (equivalently, the whole RHS can derive ε), then add ε to $\text{FIRST}(A)$ .

Footnotes

"FIRST set (context-free grammar) — Wikipedia" https://en.wikipedia.org/wiki/LL_parser - Defines FIRST concept and ε handling in LL parsing. ↩
4
Step 4
Because FIRST sets only grow (monotonic growth) and are finite over $T\cup\{\epsilon\}$ , you can keep looping through productions until a full pass adds nothing new (fixed point).
5
Step 5
Pick a few nonterminals and manually derive short strings to verify that all terminals you found in FIRST(X) can actually appear as initial tokens, and that you didn’t miss derivable terminals (a quick sanity check before using them in FOLLOW).

Step-by-step algorithm to compute FOLLOW sets

1
Step 1
Set $\text{FOLLOW}(S)=\{\$ } $for the start symbol$ S $. Initialize$ \text{FOLLOW}(A)=\emptyset $for all other nonterminals$ A
e S$.

Footnotes

"FOLLOW set (context-free grammar) — Wikipedia" https://en.wikipedia.org/wiki/LL_parser - Defines FOLLOW computation, including $ and propagation rules. ↩
2
Step 2
For every production $A\to \alpha B \beta$ , consider each occurrence of a nonterminal $B$ on the RHS and treat the symbols after it as $\beta$ .

Footnotes

"FOLLOW set (context-free grammar) — Wikipedia" https://en.wikipedia.org/wiki/LL_parser - Defines FOLLOW computation, including $ and propagation rules. ↩
3
Step 3
If $\beta$ starts with some sequence of symbols, add every terminal in $\text{FIRST}(\beta)$ except ε to $\text{FOLLOW}(B)$ .

Footnotes

"FOLLOW set (context-free grammar) — Wikipedia" https://en.wikipedia.org/wiki/LL_parser - Defines FOLLOW computation, including $ and propagation rules. ↩
4
Step 4
If $\epsilon\in \text{FIRST}(\beta)$ (or if $\beta$ is empty), then add everything in $\text{FOLLOW}(A)$ into $\text{FOLLOW}(B)$ .

Footnotes

"FOLLOW set (context-free grammar) — Wikipedia" https://en.wikipedia.org/wiki/LL_parser - Defines FOLLOW computation, including $ and propagation rules. ↩
5
Step 5
FOLLOW sets also grow monotonically and reach a fixed point after repeated passes over productions.

Footnotes

"FOLLOW set (context-free grammar) — Wikipedia" https://en.wikipedia.org/wiki/LL_parser - Defines FOLLOW computation, including $ and propagation rules. ↩
6
Step 6
FOLLOW computation depends on FIRST(β), so ensure FIRST sets are computed first and are stable before running FOLLOW iterations.

Visualizing the FIRST/FOLLOW propagation

Consider a production $A\\to \\alpha B\\beta$ . The update behavior is:

From FIRST side: terminals that can begin strings from $\\beta$ should be legal followers of $B$ .
From ε side: if $\\beta$ can disappear (derive ε), then whatever can follow $A$ should also follow $B$ .

Rule-to-effect mapping for LL(1) FIRST/FOLLOW design

How each grammar situation contributes to set updates.

Edge cases and correctness checks

Workflow to design FIRST/FOLLOW

Parse grammar rules

Identify terminals/nonterminals, ε productions, and the start symbol S."

Compute FIRST sets

Use left-to-right scanning of RHS with ε as a continuation rule; iterate to fixed point."

Compute FOLLOW sets

Initialize FOLLOW(S) with $; propagate FIRST(β){ε} and FOLLOW(A) when β⇒*ε; iterate to fixed point."

Use results for LL(1) table checks

FIRST/FOLLOW guide which production to place under each lookahead terminal."

FIRST & FOLLOW micro-deck

1 / 5

Question · Term

What does FIRST(A) contain for a nonterminal A?

Click to reveal

Answer · Definition

Terminals that can begin some string derived from A; includes ε if A can derive ε.

"FIRST set (context-free grammar) — Wikipedia" https://en.wikipedia.org/wiki/LL_parser - Defines FIRST concept and ε handling in LL parsing. ↩

Knowledge Check

Question 1 of 4

Q1Single choice

In the standard LL(1) FOLLOW update rule for a production A → α B β, what is added to FOLLOW(B) from FIRST(β)?

FIRST(β) including ε

FIRST(β) excluding ε

Only terminals in FIRST(β) that appear first in β

Only $ if β is non-empty

Explore Related Topics

Predictive Parsing Table Construction for a Classic Expression Grammar (LL(1))

Consider the following grammar: $S \to CC$ $C \to cC | d$ Find the LR(1) set of items.

FIRST/FOLLOW, LL(1) Parsing Table, and LL(1) Determination for a Given CFG

Browse all research articles

Designing the FIRST and FOLLOW Sets for a Grammar

Learning targets (what you should be able to do)

Footnotes

FIRST and FOLLOW Sets (LL(1) Parsing) — Core Examples

Core definitions you will use

FIRST of a string of grammar symbols

FOLLOW of a nonterminal

Footnotes

Pro Tip: Treat ε as a “permission to continue”

Footnotes

Common Pitfall: Adding ε into FOLLOW sets

Footnotes

Step-by-step algorithm to compute FIRST sets

Footnotes

Footnotes

Footnotes

Step-by-step algorithm to compute FOLLOW sets

Footnotes

Footnotes

Footnotes

Footnotes

Footnotes

Visualizing the FIRST/FOLLOW propagation

Rule-to-effect mapping for LL(1) FIRST/FOLLOW design

Edge cases and correctness checks

Workflow to design FIRST/FOLLOW

Parse grammar rules

Compute FIRST sets

Compute FOLLOW sets

Use results for LL(1) table checks

FIRST & FOLLOW micro-deck

What does FIRST(A) contain for a nonterminal A?

Footnotes

Knowledge Check

Explore Related Topics