FIRST and FOLLOW Sets for the Grammar E \rightarrow E+T/T, T \rightarrow TF/F, F \rightarrow E/id | AI Research

FIRST and FOLLOW Sets for the Grammar $E \rightarrow E+T/T$ , $T \rightarrow T*F/F$ , $F \rightarrow (E)/id$

Verified Sources

Nov 4, 2026

We consider the grammar (with explicit alternatives):

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

This is a standard expression grammar with operator precedence ( $*$ binds tighter than $+$ ). To compute FIRST and FOLLOW we apply the FIRST/FOLLOW rules for LL parsing, taking care of left recursion (which is handled naturally by the fixed-point computation of these sets).

We will compute:

FIRST $(E),$ FIRST $(T),$ FIRST $(F)$
FOLLOW $(E),$ FOLLOW $(T),$ FOLLOW $(F)$

Note: The input grammar uses “/” for alternatives; we interpret it as “ $\mid$ ”.

How to think about FIRST/FOLLOW here

Because $E$ and $T$ have base productions via $E\to T$ and $T\to F$ , the sets stabilize quickly: FIRST is driven by what can start from $F$ , and FOLLOW is driven by where $E$ and $T$ appear inside $(E)$ and in the $+$ / $*$ operator contexts.

Key parsing sets we will use

Terminals: $\{id, +, *, (, ), \$ }$
Start symbol: $E$
[End marker]{def="Special terminal $\\$ indicating end of input"}: $$$

By LL convention:

$\$ \in $[F O L L O W] d e f = " S e t o f t e r m i n a l s t h a t c a n a p p e a r i m m e d i a t e l y t o t h e r i g h t o f a n o n t e r m i n a l i n s o m e s e n t e n t i a l f o r m "$ (E)$

Step 1 — Compute FIRST sets

1
Step 1
From $F \to (E) \mid id$ , the strings derived from $F$ begin with either '(' or 'id'.
2
Step 2
Therefore $\text{FIRST}(F) = \{(, id\}$ .
3
Step 3
Since $T \to F$ exists, $\text{FIRST}(T)$ must include $\text{FIRST}(F)$ . Also $T \to T*F$ does not introduce new starting terminals beyond those already possible for the leading $T$ .
4
Step 4
So $\text{FIRST}(T) = \{(, id\}$ .
5
Step 5
Because $E \to T$ exists, $\text{FIRST}(E)$ includes $\text{FIRST}(T)$ . Again, $E \to E+T$ is left-recursive and does not change the possible leading terminals.
6
Step 6
So $\text{FIRST}(E) = \{(, id\}$ .

FIRST sets (final)

\begin{aligned} \text{FIRST}(E) &= \{(, id\} \\ \text{FIRST}(T) &= \{(, id\} \\ \text{FIRST}(F) &= \{(, id\} \end{aligned}

No production derives the empty string $\\varepsilon$ , so none of these FIRST sets contains $\\varepsilon$ .

Do not forget FOLLOW(E) contains end marker

Since $E$ is the start symbol, $\$ must be included in FOLLOW $(E)$ . This is the most common omission in manual computations.

Step 2 — Compute FOLLOW sets

1
Step 1
Add $\$ to FOLLOW(E). Initialize others as empty: FOLLOW(T)=\emptyset, FOLLOW(F)=\emptyset.
2
Step 2
In $E \to E + T$ , the symbol $E$ is followed by '+' in that sentential form, so $+$ is in FOLLOW(E). Also $T$ appears at the end of the right side, so FOLLOW(T) must include FOLLOW(E).
3
Step 3
In $E \to T$ , $T$ is at the end, so FOLLOW(T) includes FOLLOW(E). (This confirms the propagation from the previous step.)
4
Step 4
In $T \to T * F$ , $T$ is followed by '', so '' is in FOLLOW(T). Also $F$ is at the end of the right side, so FOLLOW(F) must include FOLLOW(T).
5
Step 5
In $T \to F$ , $F$ is at the end, so FOLLOW(F) includes FOLLOW(T).
6
Step 6
In $F \to (E)$ , the nonterminal $E$ is followed immediately by ')', so ')' is in FOLLOW(E).
7
Step 7
Combine all derived terminals into each FOLLOW set; since there is no $\varepsilon$ , we do not need FIRST-of-suffix propagation beyond end-of-production cases.

FOLLOW sets (final)

From the rules:

FOLLOW(E) gets $\\$ (start symbol), '+' (from $E \\to E+T$ ), and ')' (from $F \\to (E)$ ).
FOLLOW(T) gets FOLLOW(E) (because $T$ appears at the end in $E \\to T$ ) and also '+' (already in FOLLOW(E)), plus '*' (from $T \\to T*F$ ).
FOLLOW(F) gets FOLLOW(T) (because $F$ appears at the end in $T \\to F$ and $T \\to T*F$ ).

Concretely:

\begin{aligned} \text{FOLLOW}(E) &= \\{\\$, +, )\\} \\ \text{FOLLOW}(T) &= \\{\\$, +, *, )\\} \\ \text{FOLLOW}(F) &= \\{\\$, +, *, )\\} \end{aligned}

Fixed-Point Computation View (Conceptual)

Set starts

Initialization

Start with FOLLOW(E)={$}, others empty; compute FIRST from base F productions."

Apply local FOLLOW rules

Propagation via productions

From $E\to E+T$ add '+' to FOLLOW(E) and FOLLOW(E) to FOLLOW(T); from $F\to (E)$ add ')' to FOLLOW(E)."

Add '*' and shift FOLLOW(T) to FOLLOW(F)

Operator contexts

From $T\to T*F$ add '*' to FOLLOW(T) and FOLLOW(T) to FOLLOW(F)."

No epsilon, sets stop changing

Stabilization

Because no $\varepsilon$ is derived, FIRST-of-suffix terms don’t extend via nullable chains; sets stabilize."

Common Pitfalls and Edge Cases

Knowledge Check

Question 1 of 4

Q1Single choice

Which terminal set is FIRST(F) for the grammar?

{(, id}

{+, *, )}

{id}

{(}

Explore Related Topics

SLR(1) Parsing for the Grammar $E \to E+T \mid T,\; T \to T*F \mid F,\; F \to t\,d$

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

FIRST and FOLLOW Sets for a Given CFG

Browse all research articles

FIRST and FOLLOW Sets for the Grammar E→E+T/TE \rightarrow E+T/TE→E+T/T, T→T∗F/FT \rightarrow T*F/FT→T∗F/F, F→(E)/idF \rightarrow (E)/idF→(E)/id