FIRST, FOLLOW, and LL1 Parsing Table for the Given Expression Grammar | AI Research

FIRST, FOLLOW, and LL(1) Parsing Table for the Given Expression Grammar

Verified Sources

Sep 13, 2026

We are given the grammar (with terminals $\\{+,*,(,),id\\}$ and start symbol $E$ ):

\\begin{aligned} E &\\rightarrow TE' \\\\ E' &\\rightarrow +TE' \\mid \\epsilon \\\\ T &\\rightarrow FT' \\\\ T' &\\rightarrow *FT' \\mid \\epsilon \\\\ F &\\rightarrow (E) \\mid id \\end{aligned}

We will compute:

[keyword]{def="FIRST(A) is the set of terminals that can begin strings derived from A, possibly including $\\epsilon$ "}
keyword
the keyword

Finally, we derive the LL(1) parsing table.

LL(1) Parsing Table (FIRST & FOLLOW) - Simple Explanation

Key definitions used

keyword
[keyword]{def="If $\\epsilon \\in FIRST(α)$ , then $\\epsilon$ can be derived from α"}
keyword
[keyword]{def="LL(1) table entry uses FIRST(α); if $\\epsilon \\in FIRST(α)$ then use FOLLOW(A)"}

Step 1 — Compute FIRST sets

1
Step 1
Use each nonterminal’s productions: $E\to TE'$ , $E'\to +TE'\mid\epsilon$ , $T\to FT'$ , $T'\to *FT'\mid\epsilon$ , $F\to (E)\mid id$ .
2
Step 2
Since $F\to (E)$ starts with $($ and $F\to id$ starts with $id$ , we get $FIRST(F)=\{(,\,id\}$ .
3
Step 3
$T'\to *FT'$ starts with $*$ , and $T'\to \epsilon$ contributes $\epsilon$ , so $FIRST(T')=\{*,\,\epsilon\}$ .
4
Step 4
$T\to FT'$ . Because $FIRST(F)=\{(,id\}$ and neither production of $F$ derives $\epsilon$ , we have $FIRST(T)=FIRST(F)=\{(,\,id\}$ .
5
Step 5
$E'\to +TE'$ starts with $+$ , and $E'\to \epsilon$ contributes $\epsilon$ , so $FIRST(E')=\{+,\,\epsilon\}$ .
6
Step 6
$E\to TE'$ . Since $FIRST(T)=\{(,id\}$ and $T$ cannot derive $\epsilon$ (because $T\to FT'$ and $F$ cannot derive $\epsilon$ ), we get $FIRST(E)=FIRST(T)=\{(,\,id\}$ .

FIRST summary

$FIRST(E)=\\{(,\\,id\\}$
$FIRST(E')=\\{+,\\,\\epsilon\\}$
$FIRST(T)=\\{(,\\,id\\}$
$FIRST(T')=\\{*,\\,\\epsilon\\}$
$FIRST(F)=\\{(,\\,id\\}$

Step 2 — Compute FOLLOW sets

1
Step 1
Take $\$ as the end-marker (common LL(1) convention): since $E$ is the start symbol, $\$ is in $FOLLOW(E)$ .
2
Step 2
Scan each production for every appearance of a nonterminal and apply FOLLOW rules based on what can come after it.
3
Step 3
In $TE'$ , $T$ is followed by $E'$ so $FIRST(E')\setminus\{\epsilon\}=\{+\}$ is added to $FOLLOW(T)$ . Because $\epsilon\in FIRST(E')$ , add $FOLLOW(E)$ to $FOLLOW(T)$ .
4
Step 4
In $+TE'$ , $T$ is followed by $E'$ . Again add $FIRST(E')\setminus\{\epsilon\}=\{+\}$ to $FOLLOW(T)$ . Since $\epsilon\in FIRST(E')$ , add $FOLLOW(E')$ to $FOLLOW(T)$ (we will compute $FOLLOW(E')$ from other placements).
5
Step 5
This production has no symbols after $E'$ , so its effect is already captured via positions where $E'$ appears (not by the empty rule itself).
6
Step 6
In $FT'$ , $F$ is followed by $T'$ . Add $FIRST(T')\setminus\{\epsilon\}=\{*\}$ to $FOLLOW(F)$ . Since $\epsilon\in FIRST(T')$ , add $FOLLOW(T)$ to $FOLLOW(F)$ .
7
Step 7
In $*FT'$ , $F$ is followed by $T'$ . Add $FIRST(T')\setminus\{\epsilon\}=\{*\}$ to $FOLLOW(F)$ . Since $\epsilon\in FIRST(T')$ , add $FOLLOW(T')$ to $FOLLOW(F)$ .
8
Step 8
$E'$ appears at the end of $E\to TE'$ , so $FOLLOW(E')\supseteq FOLLOW(E)$ . Also $E'$ appears at the end of $E'\to +TE'$ , so $FOLLOW(E')\supseteq FOLLOW(E')$ (self-consistent).
9
Step 9
$T'$ appears at the end of $T\to FT'$ , so $FOLLOW(T')\supseteq FOLLOW(T)$ , and also at the end of $T'\to *FT'$ , giving self-consistency.

Solving the FOLLOW equations

Let’s denote:

$FOLLOW(E)=\\{\\$ \}\, $(we'll confirm no other terminal is forced to follow$ E $outside of the$ \ $case;$ E $also appears inside$ F\to (E)$, which changes this.)
From $F\\to (E)$ : the symbol after $E$ is $)$ , so add $\\{)\\}$ to $FOLLOW(E)$ .

So:

FOLLOW(E)=\\{\\$,\\,)\\}.

Now use $E\\to TE'$ :

$T$ is followed by $E'$ , so add $FIRST(E')\\setminus\\{\\epsilon\\}=\\{+\\}$ to $FOLLOW(T)$ .
Because $\\epsilon\\in FIRST(E')$ , add $FOLLOW(E)$ to $FOLLOW(T)$ .

Thus:

FOLLOW(T)=\\{+,\\$,\\,)\\}.

Now $T\\to FT'$ :

$F$ is followed by $T'$ , so add $FIRST(T')\\setminus\\{\\epsilon\\}=\\{*\\}$ to $FOLLOW(F)$ .
Because $\\epsilon\\in FIRST(T')$ , add $FOLLOW(T)$ to $FOLLOW(F)$ .

So:

FOLLOW(F)=\\{*,\\, +,\\$,\\,)\\}.

Now derive $FOLLOW(E')$ :

$E'$ appears at end of $E\\to TE'$ , hence $FOLLOW(E')\\supseteq FOLLOW(E)=\\{\\$ ,\,)\}$.
No other terminal is added to $FOLLOW(E')$ from other contexts (it is not followed by a terminal in any production where it occurs before the end).

So:

FOLLOW(E')=\\{\\$,\\,)\\}.

Finally $FOLLOW(T')$ :

$T'$ appears at end of $T\\to FT'$ , so $FOLLOW(T')\\supseteq FOLLOW(T)=\\{+,\\$ ,\,)\}$. Thus:

FOLLOW(T')=\\{+,\\$,\\,)\\}.

FOLLOW summary

$FOLLOW(E)=\\{\\$ ,\,)\}$
$FOLLOW(E')=\\{\\$ ,\,)\}$
$FOLLOW(T)=\\{+,\\$ ,\,)\}$
$FOLLOW(T')=\\{+,\\$ ,\,)\}$
$FOLLOW(F)=\\{*,\\,+,\\$ ,\,)\}$

Quick visual: how $\\epsilon$ affects FOLLOW

Because $E'\\Rightarrow \\epsilon$ , symbols that can follow $E$ also become possible followers of $T$ in $E\\to TE'$ . Similarly, because $T'\\Rightarrow \\epsilon$ , followers of $T$ can follow $F$ in $T\\to FT'$ .

Pro Tip

When a nonterminal is followed by a suffix that can derive $\epsilon$ , you must union $FOLLOW$ of the left-hand side into the $FOLLOW$ of the nonterminal (not just $FIRST$ ).

Common Pitfall

Do not add $\epsilon$ to FOLLOW sets. FOLLOW contains terminals only (and $\$ ). $\epsilon$ is used only to decide whether to propagate FOLLOW across nullable suffixes.

Step 3 — Derive the LL(1) parsing table

1
Step 1
For each production $A\to \alpha$ : for each $a\in FIRST(\alpha)\setminus\{\epsilon\}$ , set $M[A,a]=A\to\alpha$ . If $\epsilon\in FIRST(\alpha)$ , then for each $b\in FOLLOW(A)$ set $M[A,b]=A\to\alpha$ .
2
Step 2
Production: $E\to TE'$ . $FIRST(TE')=FIRST(E)=\{(,id\}$ . So $M[E,(]=E\to TE'$ and $M[E,id]=E\to TE'$ .
3
Step 3
Productions: $E'\to +TE'$ and $E'\to \epsilon$ . $FIRST(+TE')=\{+\}$ so $M[E',+]=E'\to +TE'$ . For $E'\to \epsilon$ : since $\epsilon\in FIRST(E')$ , add it over $FOLLOW(E')=\{\$ ,,)} $, so$ M[E',$$]=E'\to\epsilon $and$ M[E',)]=E'\to\epsilon$.
4
Step 4
Production: $T\to FT'$ . $FIRST(FT')=\{(,id\}$ . So $M[T,(]=T\to FT'$ and $M[T,id]=T\to FT'$ .
5
Step 5
Productions: $T'\to *FT'$ and $T'\to \epsilon$ . $FIRST(*FT')=\{*\}$ so $M[T',*]=T'\to *FT'$ . For $T'\to \epsilon$ , use $FOLLOW(T')=\{+,\$ ,,)} $: so$ M[T',+]=T'\to\epsilon $,$ M[T',$$]=T'\to\epsilon $,$ M[T',)]=T'\to\epsilon$.
6
Step 6
Productions: $F\to (E)$ and $F\to id$ . So $M[F,(]=F\to (E)$ and $M[F,id]=F\to id$ .

LL(1) Parsing Table (M)

Rows are nonterminals, columns are lookahead terminals.

Parsing table as production listings

Let terminals be columns: $(, id, +, *, ), \\$ .

Nonterminal $E$ :

$M[E,(] = E\\to TE'$
$M[E,id] = E\\to TE'$

Nonterminal $E'$ :

$M[E',+] = E'\\to +TE'$
$M[E',)] = E'\\to \\epsilon$
$M[E',$ \ $] = E'\\to \\epsilon$

Nonterminal $T$ :

$M[T,(] = T\\to FT'$
$M[T,id] = T\\to FT'$

Nonterminal $T'$ :

$M[T',*] = T'\\to *FT'$
$M[T',+] = T'\\to \\epsilon$
$M[T',)] = T'\\to \\epsilon$
$M[T',$ \ $] = T'\\to \\epsilon$

Nonterminal $F$ :

$M[F,(] = F\\to (E)$
$M[F,id] = F\\to id$

All other cells are error/undefined.

Workflow to Build LL(1) Table

FIRST sets

Determine which terminals can begin each nonterminal’s derivations."

FOLLOW sets

Propagate terminal followers using $\epsilon$ -nullable suffix logic."

LL(1) table

Use $FIRST$ for normal entries; use $FOLLOW$ when $\epsilon$ is possible."

Why this grammar is LL(1) (intuition)

FIRST/FOLLOW/LL(1) Self-Check Deck

1 / 5

Question · Term

What is FIRST(E')?

Click to reveal

Answer · Definition

$FIRST(E')=\{+,\,\epsilon\}$ .

Knowledge Check

Question 1 of 4

Q1Single choice

For the grammar, what is $FIRST(T')$ ?

$\{*,\,\epsilon\}$

$\{+,\,\epsilon\}$

$\{(,\,id\}$

$\{(,\,id,\,+\}$

Explore Related Topics

Top-Down Parsing: Choosing the Correct Answer

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