First and Follow sets look like simple bookkeeping until a question hands you a grammar with nullable nonterminals and four answer options that all look plausible. The fix is to stop treating the sets as something you "spot" by staring at the grammar, and start treating them as the output of a fixed-point algorithm: apply the rules in passes, and stop only when a full pass changes nothing. This post builds that procedure from the rules up and runs it, pass by pass, on two grammars in exactly the shape GATE questions use.
First and Follow sets: what they compute and why parser questions depend on them
FIRST(X) is the set of terminals that can begin some string derived from X. If X can derive the empty string ε, then ε is also in FIRST(X), and we call X nullable.
FOLLOW(A) is the set of terminals that can appear immediately to the right of nonterminal A in some sentential form. The end-of-input marker $ goes into FOLLOW of the start symbol, and ε is never a member of any FOLLOW set.
Why parsers need them: a predictive LL(1) parser must pick a production using only the next input token. FIRST says which production can begin with that token, and FOLLOW says when applying an ε-production is safe. An SLR(1) parser reduces by A → α only when the lookahead is in FOLLOW(A), so almost every parsing question routes through these two sets.
Rules for computing First sets
For any grammar symbol or string, FIRST is built from three rules.
If a is a terminal, FIRST(a) = { a }.
If X → ε is a production, add ε to FIRST(X).
If X → Y1 Y2 ... Yk, add FIRST(Y1) minus ε to FIRST(X). If Y1 is nullable, also add FIRST(Y2) minus ε, and so on down the chain. If every Yi is nullable, add ε to FIRST(X).
The same sequence rule computes FIRST of any string β, which you will need for FOLLOW: scan left to right, adding each symbol's FIRST minus ε, and stop at the first symbol that is not nullable.
Rules for computing Follow sets
FOLLOW is built from three rules as well, and the third one is where every hard question hides.
Put $ into FOLLOW(S), where S is the start symbol.
For every production A → αBβ, add FIRST(β) minus ε to FOLLOW(B). Whatever can start β can directly follow B.
For every production A → αB, or A → αBβ where β is nullable, add all of FOLLOW(A) to FOLLOW(B). If B can sit at the very end of A's expansion, then anything that follows A also follows B.
Rule 3 creates dependencies between FOLLOW sets: FOLLOW(B) depends on FOLLOW(A), which may depend on FOLLOW of something else. That is exactly why a single left-to-right scan of the productions is not enough.
First and Follow as a fixed-point algorithm: iterate until nothing changes
Here is the frame most terse notes skip. The rules are constraints, not a one-shot recipe, and the sets only ever grow as you apply them. So the honest algorithm is:
Initialise every set as empty, except $ in FOLLOW of the start symbol.
Make a full pass over all productions, applying every rule.
If anything was added, make another full pass.
Stop when a complete pass adds nothing. The sets have reached their fixed point, and that is the answer.
Two things fall out of this framing. You always know when you are finished, because the stopping condition is a full pass with no change, not a feeling. And every element in your answer is justified by a rule and a production, which is how you verify an MCQ option instead of guessing.
Solved example 1: First and Follow for the classic expression grammar, pass by pass
This is the single most reused grammar in compiler design questions, the left-factored expression grammar.
E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → ( E ) | id
First sets. Work bottom-up from F. FIRST(F) = { (, id }. FIRST(T') = { *, ε } and FIRST(E') = { +, ε } directly from their productions. Since F is not nullable, FIRST(T) = FIRST(F) = { (, id }, and FIRST(E) = FIRST(T) the same way.
Follow sets, by iteration. Initialise FOLLOW(E) = { $ }, everything else empty, then run full passes over the five productions applying rules 2 and 3.
Set | After pass 1 | After pass 2 (final) |
|---|---|---|
FOLLOW(E) | $, ) | $, ) |
FOLLOW(E') | $ | $, ) |
FOLLOW(T) | +, $ | +, $, ) |
FOLLOW(T') | +, $ | +, $, ) |
FOLLOW(F) | *, +, $ | *, +, $, ) |
Where pass 1 comes from: in E → T E', FIRST(E') minus ε puts + into FOLLOW(T), and since E' is nullable, FOLLOW(E) flows into FOLLOW(T). E' at the right end receives FOLLOW(E), so it gets $. In T → F T', the same logic puts * and FOLLOW(T) into FOLLOW(F), and FOLLOW(T) into FOLLOW(T'). Finally F → ( E ) puts ) into FOLLOW(E).
Pass 2 exists because ) reached FOLLOW(E) only at the end of pass 1, after FOLLOW(E) had already been copied into other sets, so the second pass propagates ) down the chain. A third pass adds nothing, and the computation is done. If your FOLLOW answer has ever missed a ), a stopped-too-early iteration is almost always the reason.
Solved example 2: nullable nonterminals, where the marks are actually lost
GATE-style questions love grammars where a nullable symbol sits between a nonterminal and what truly follows it. Take start symbol S:
S → A B c
A → a | ε
B → b | ε
FIRST(A) = { a, ε } and FIRST(B) = { b, ε }. For FIRST(S), scan A B c left to right: take a from A, then b from B since A is nullable, then c since B is also nullable. So FIRST(S) = { a, b, c }, and S is not nullable because the scan hit the terminal c.
For FOLLOW(A), the string after A is B c, so compute FIRST(B c): that is b, plus c because B is nullable. FOLLOW(A) = { b, c }. FOLLOW(B) = { c } and FOLLOW(S) = { $ }.
The classic wrong answer here is FOLLOW(A) = { b }, produced by forgetting that B can vanish. When an option list contains both { b } and { b, c }, the examiner is testing exactly this skip, and rule 2 catches it by forcing you to compute FIRST of the entire remaining string, not just the next symbol.
How GATE tests First and Follow
The questions come in three recurring shapes. Direct computation, where you are given a grammar and asked for FIRST or FOLLOW of one nonterminal, usually with a nullable trap like example 2. LL(1) table construction, where production A → α is placed in cell M[A, a] for every a in FIRST(α), and additionally in M[A, b] for every b in FOLLOW(A) when α is nullable; a grammar is LL(1) exactly when no cell gets two productions. And SLR(1) reduce decisions, where FOLLOW sets decide which table cells carry a reduce action. For cycle-specific paper rules and scoring, use the official GATE portal.
Compiler Design is a compact subject dense with procedure-driven questions like these, so it pays back preparation time quickly. Where it sits relative to the heavier subjects is mapped in our GATE CS subject-wise weightage breakdown. For structured coverage, the Compiler Design learn module walks from lexical analysis through parsing to code optimization, and KnowledgeGate's published question bank carries hundreds of Compiler Design questions, with syntax analysis and LL(1) parsing among its densest slices.
For cycle-specific paper rules and scoring, use the official GATE portal.
The short version, and your next step
FIRST looks at what a symbol can start with, FOLLOW at what can appear immediately after it, and $ belongs to FOLLOW of the start symbol.
Both are computed by iterating the rules in full passes until a pass changes nothing. The fixed point is the answer, and stopping early is the top source of missed elements.
The two traps that decide marks: propagating FOLLOW through the dependency chain (example 1's second pass), and computing FIRST of the whole remaining string when symbols are nullable (example 2).
Hand-run both examples once without looking at the tables, then check yourself. After that, confirm the skill under time pressure: the GATE Test Series includes subject-wise Compiler Design tests along with full-length mocks. If you are still sequencing your subjects, the GATE category page lists every course and test series in one place.
Learn the rules once, trust the iteration, and First and Follow stops being a memory exercise and becomes the most reliable marks in your compiler design paper.
