First and Follow Sets Explained: Rules, Worked Example and LL(1) Checks

You may remember the definitions but lose track when two nullable nonterminals occur together. Then an answer option with one extra symbol looks believable. A repeatable fixed-point procedure carries the grammar from productions to complete sets and an LL(1) table check.

First and Follow sets: what each set actually answers

FIRST(X) contains the terminals that can begin a string derived from X, plus epsilon only if X can derive the empty string. FOLLOW(A) contains the terminals that can appear immediately after nonterminal A in a sentential form. It includes the end marker $ for the start symbol.

The invariant is simple: epsilon can occur in FIRST, but never in FOLLOW.

In a predictive parser, FIRST selects a production using the next input symbol. FOLLOW tells the parser when an epsilon production may be used.

FIRST(A) asks what A can start with. FOLLOW(A) asks what may come after A.

If you are placing this topic inside a wider study plan, the GATE course category connects it to the rest of the syllabus.

The complete computation rules and fixed-point method

Apply the FIRST rules in this order:

1. For a terminal t, FIRST(t) = {t}.

2. For A -> epsilon, put epsilon in FIRST(A).

3. For A -> X1 X2 ... Xk, scan from left to right. Add FIRST(Xi) - {epsilon} and continue only if Xi is nullable. Add epsilon only when every symbol on the right-hand side is nullable.

Then apply the FOLLOW rules:

1. Put $ in FOLLOW of the start symbol.

2. For A -> alpha B beta, add FIRST(beta) - {epsilon} to FOLLOW(B).

3. If beta is empty or nullable, also add FOLLOW(A) to FOLLOW(B).

Scan the grammar repeatedly and stop only when a full pass changes no set. Sets have no duplicates, and discovery order has no meaning. Never stop after an assumed number of passes.

Worked grammar, part one: compute every FIRST set

Consider the grammar:

S -> A B C
A -> a A | epsilon
B -> b B | epsilon
C -> c C | epsilon

S is the start symbol, a, b, and c are terminals, and A, B, and C are nullable.

The direct productions give FIRST(A) = {a, epsilon}, FIRST(B) = {b, epsilon}, and FIRST(C) = {c, epsilon}.

Now scan A B C. Add a. Since A is nullable, continue and add b. Since B is nullable, continue and add c. C is also nullable, so add epsilon.

Stopping at {a} ignores the nullable chain. Omitting epsilon ignores that the whole right-hand side is nullable.

Worked grammar, part two: propagate every FOLLOW set

Seed FOLLOW(S) = {$}. In S -> A B C, A has suffix B C. Add FIRST(B C) - {epsilon} = {b, c}. Since both B and C are nullable, also transfer FOLLOW(S) = {$}. Therefore FOLLOW(A) = {b, c, $}.

After B, suffix C adds {c} and, because C is nullable, $ from FOLLOW(S). Thus FOLLOW(B) = {c, $}. C is at the end, so FOLLOW(C) = FOLLOW(S) = {$}.

Rescanning A -> a A, B -> b B, and C -> c C adds nothing. A nullable suffix transfers the left-hand side's FOLLOW, never epsilon.

Turn the sets into an LL(1) decision and parsing-table entries

For alternatives X -> alpha | beta, their FIRST sets must be disjoint. If one derives epsilon, FIRST of the other must also be disjoint from FOLLOW(X).

Here, {a} does not intersect FOLLOW(A) {b, c, $}; {b} does not intersect FOLLOW(B) {c, $}; and {c} does not intersect FOLLOW(C) {$}. The grammar has no LL(1) conflict.

The non-error parsing-table entries are:

Every other cell is an error, and no cell contains two productions. First and Follow in Compiler Design: Solved Examples uses the classic expression grammar to show pass-by-pass FOLLOW propagation. This fully nullable chain tests a different failure mode: carrying epsilon through three symbols and placing the resulting productions without a conflict.

Traps that create plausible but wrong answers

For this grammar, FOLLOW(A) = {b, c, epsilon} is invalid because FOLLOW never contains epsilon. FOLLOW(A) = {b, c} is incomplete because the nullable suffix B C transfers $ from FOLLOW(S).

As a mechanical check, explain every FOLLOW terminal using either a position in a production or a FOLLOW transfer. Remove every epsilon before adding anything to FOLLOW.

How questions test First and Follow sets

Common formats ask you to choose a set, find a member missed after a nullable suffix, test whether a grammar is LL(1), or locate a multiple-entry table cell.

KnowledgeGate has over 10 questions available for practice in the First and Follow Sets subtopic. For timed mixed practice, use the GATE Test Series. For an immediate related drill, work through these solved parsing MCQs.

A 30-second answer routine is: mark nullable nonterminals, compute every FIRST set, seed $, propagate FOLLOW to a fixed point, then run the LL(1) overlap checks. Changing that order makes missed transfers more likely.

The short version and next step

• FIRST looks forward from a symbol.

• FOLLOW looks rightward around a nonterminal.

• Epsilon belongs only in FIRST.

• A nullable suffix transfers FOLLOW.

• Iteration stops only at a fixed point.

For the worked grammar, the headline results are FIRST(S) = {a, b, c, epsilon} and FOLLOW(A) = {b, c, $}.

Now recompute all four FIRST sets and all four FOLLOW sets on paper without looking. Rebuild the table and confirm that no filled cell contains two productions. For a structured route through the surrounding syllabus, continue with GATE Guidance by Sanchit Sir.