FIRST, FOLLOW, and LL1 Parsing Table for a Grammar with ε-Productions | AI Research

FIRST, FOLLOW, and LL(1) Parsing Table for a Grammar with ε-Productions

Verified Sources

Nov 4, 2026

We have the grammar:
$S \to ABC$
$A \to aA \mid \varepsilon$
$B \to bB \mid \varepsilon$
$C \to cC \mid d$

Let $FIRST(X)$ be the set of terminals that can appear first in strings derived from $X$ , and $FOLLOW(X)$ be the set of terminals that can appear immediately to the right of $X$ in some sentential form. These sets are used to build the LL(1) parsing table $M[X, a]$ with the rule: for a production $X \to \alpha$ ,

if $a \in FIRST(\alpha)$ then $M[X,a] = X \to \alpha$ ,
if $\varepsilon \in FIRST(\alpha)$ then for every $b \in FOLLOW(X)$ , set $M[X,b] = X \to \alpha$ .

Key keywords: LL(1) , FIRST , FOLLOW , ε-production , Parsing table.

LL(1) FIRST/FOLLOW and Parsing Table (construction walkthrough)

Compute FIRST sets

1
Step 1
A → aA | ε, so FIRST(A) = {a, ε}.
2
Step 2
B → bB | ε, so FIRST(B) = {b, ε}.
3
Step 3
C → cC | d, so FIRST(C) = {c, d} (no ε).
4
Step 4
FIRST(ABC) depends on leading symbols: A can start with a or ε. If A ⇒ ε, then B can start with b or ε. If both A ⇒ ε and B ⇒ ε, then C starts with c or d. Therefore FIRST(S)=FIRST(ABC) = {a, b, c, d}.

Compute FOLLOW sets

1
Step 1
By convention for LL parsing, $\$ $(end marker) is in FOLLOW(S). So FOLLOW(S) = {$ $ }.
2
Step 2
From S → A B C: after A comes B C. So add FIRST(BC) \u2212 {ε} to FOLLOW(A), and if ε ∈ FIRST(BC) then also add FOLLOW(S) to FOLLOW(A).
3
Step 3
B can be ε, so FIRST(BC) = FIRST(B) if B doesn't vanish; since B → bB | ε, we get FIRST(BC) = {b} ∪ FIRST(C) when B ⇒ ε = {b, c, d}. Also ε ∉ FIRST(BC) because C has no ε-production.
4
Step 4
So FOLLOW(A) gets FIRST(BC) \u2212 {ε} = {b, c, d}. Since ε \u2208 FIRST(BC) is false, FOLLOW(S) is NOT added.
5
Step 5
After B in S → A B C comes C, so add FIRST(C) to FOLLOW(B). Since ε ∉ FIRST(C), FOLLOW(S) is not added via this path.
6
Step 6
FOLLOW(B) = FIRST(C) = {c, d}. For C: C is at the end of S → ABC, so FOLLOW(C) includes FOLLOW(S) = { $\$ }.

FIRST sets (final)

$FIRST(A) = \\{a, \\varepsilon\\}$
$FIRST(B) = \\{b, \\varepsilon\\}$
$FIRST(C) = \\{c, d\\}$
$FIRST(S) = \\{a, b, c, d\\}$

FOLLOW sets (final)

$FOLLOW(S) = \\{\\$ \}$
$FOLLOW(A) = \\{b, c, d\\}$
$FOLLOW(B) = \\{c, d\\}$
$FOLLOW(C) = \\{\\$ \}$

ε-handling rule

When building FIRST for a sequence like ABC: if A ⇒ ε, then continue to B; if B ⇒ ε, then continue to C. This is exactly why FIRST(S) includes a, b, c, d.

FOLLOW propagation via 'last symbol' only

FOLLOW(X) only receives FOLLOW(Left-Hand Side) when X can appear at the end of some derivation from that production. Here, in S → ABC, C is last, so FOLLOW(C) gets FOLLOW(S).

LL(1) parsing table construction

Terminals: $\{a,b,c,d,\\$ \}$.

We list each production and the lookahead symbols that trigger it:

Productions

$S \to ABC$
$A \to aA$
$A \to \\varepsilon$
$B \to bB$
$B \to \\varepsilon$
$C \to cC$
$C \to d$

Use rules

For $X \to \alpha$ with $\\varepsilon \\notin FIRST(\\alpha)$ : fill $M[X,t]$ for $t \\in FIRST(\\alpha)$ .
For $X \to \\alpha$ with $\\varepsilon \\in FIRST(\\alpha)$ : fill $M[X,t]$ for all $t \\in FOLLOW(X)$ .

LL(1) Parsing Table M (entries shown compactly)

Columns are lookahead tokens; rows are nonterminals. Empty cells mean error.

The compact chart above encodes whether a production exists; here is the explicit table.

Nonterminal	lookahead a	lookahead b	lookahead c	lookahead d	lookahead $
$S$	$S \to ABC$	—	$S \to ABC$	$S \to ABC$	—
$A$	$A \to aA$	—	$A \to \varepsilon$	$A \to \varepsilon$	—
$B$	—	$B \to bB$	$B \to \varepsilon$	$B \to \varepsilon$	—
$C$	—	—	$C \to cC$	$C \to d$	—

Why these entries?

$FIRST(ABC)=\\{a,b,c,d\\}$ and no ε, so $M[S,a],M[S,b],M[S,c],M[S,d]$ all get $S \to ABC$ .
For $A \to aA$ : $a \\in FIRST(aA)$ so $M[A,a]$ gets it.
For $A \to \\varepsilon$ : ε ∈ FIRST(ε), so use FOLLOW(A)=\{b,c,d\}; thus $M[A,c]$ and $M[A,d]$ get $A \to \\varepsilon$ (and $M[A,b]$ too, but that table cell is in conflict with how $A$ could also derive aA? Actually $aA$ only applies at lookahead a, so $M[A,b]$ is safe; in our explicit table above we left $M[A,b]$ blank, so we correct it now: $M[A,b]=A \\to \\varepsilon$ .)
For $B \to bB$ : $M[B,b]=B\\to bB$ .
For $B \\to \\varepsilon$ : FOLLOW(B)=\{c,d\}; so $M[B,c]=B\\to \\varepsilon$ and $M[B,d]=B\\to \\varepsilon$ .

Corrected explicit table (with the missing ε entry fixed)

Nonterminal	lookahead a	lookahead b	lookahead c	lookahead d	lookahead $
$S$	$S \to ABC$	$S \to ABC$	$S \to ABC$	$S \to ABC$	—
$A$	$A \to aA$	$A \to \\varepsilon$	$A \to \\varepsilon$	$A \to \\varepsilon$	—
$B$	—	$B \to bB$	$B \to \\varepsilon$	$B \to \\varepsilon$	—
$C$	—	—	$C \to cC$	$C \to d$	—

LL(1) parsing steps for input aabd

1
Step 1
Put $\$ on stack bottom, then start symbol $S$ on top. Input is $a a b d \$ .
2
Step 2
Top is $S$ , lookahead is $a$ . Use $M[S,a]=S\to ABC$ . Replace $S$ by $A B C$ .
3
Step 3
Top is $A$ , lookahead is $a$ . Use $M[A,a]=A\to aA$ . Match terminal $a$ .
4
Step 4
Top is $A$ , lookahead is next $a$ . Again use $A\to aA$ and match $a$ .
5
Step 5
Now lookahead is $b$ and top is $B$ . Use $M[B,b]=B\to bB$ and match $b$ .
6
Step 6
Now lookahead is $d$ and top is $C$ . Use $M[C,d]=C\to d$ and match $d$ .
7
Step 7
Input is exhausted; stack top is $\$ and lookahead is $\$ ; accept.

Trace table (stack top on the left)

Let stack be written as: top ... bottom, and input as remaining unread symbols.

Step	Stack (top→bottom)	Input (current→end)	Action
0	$S$ $\\$	$aabd\\$	Start
1	$A\,B\,C$ $\\$	$aabd\\$	$S\\to ABC$ (on lookahead $a$ )
2	$a\,A\,B\,C$ $\\$	$aabd\\$	$A\\to aA$
3	$A\,B\,C$ $\\$	$abd\\$	match $a$
4	$a\,A\,B\,C$ $\\$	$abd\\$	$A\\to aA$ (lookahead $a$ )
5	$A\,B\,C$ $\\$	$bd\\$	match $a$
6	$b\,B\,C$ $\\$	$bd\\$	$B\\to bB$
7	$B\,C$ $\\$	$d\\$	match $b$
8	$d$ $\\$	$d\\$	$C\\to d$
9	$\\$	$\\$	match $d$
10	(empty)	(empty)	accept

Common edge cases with ε in LL(1)

Knowledge Check

Question 1 of 4

Q1Single choice

What is $FIRST(S)$ for the grammar $S\to ABC$ , $A\to aA\mid\varepsilon$ , $B\to bB\mid\varepsilon$ , $C\to cC\mid d$ ?

$\{a,b,c,d\}$

$\{a,b\}$

$\{c,d\}$

$\{a,b,\varepsilon\}$

Explore Related Topics

Semantic Actions in Context-Free Grammars: Deriving Output for Input `aadbd`

Ambiguity in the Grammar $S \rightarrow ABA,\; A \rightarrow aA \mid \epsilon,\; B \rightarrow bB \mid \epsilon$

The grammar (S\rightarrow ABA,;A\rightarrow aA\mid\epsilon,;B\rightarrow bB\mid\epsilon) is ambiguous because the two (A) nonterminals can distribute the same (a)-string in multiple ways, especially when (B) derives (\epsilon).

It generates the language (L(S)={a^i b^j a^k\mid i,j,k\ge0}=a^*b^a^).
The shortest string (a) has two distinct left‑most derivations (or parse trees), proving ambiguity.
Every string (a^n) with (n\ge1) can be split between the two (A) symbols in (n+1) ways, yielding multiple parse trees.
The ambiguity stems from both (A) producing (a^*) and (B) being able to vanish via (\epsilon).
An equivalent unambiguous grammar can be constructed, showing the ambiguity is a property of this grammar, not necessarily of the language.

Constructing an LALR(1) Parsing Table for a Given Grammar (and Proving It Is Not SLR(1))

Browse all research articles