FIRST and FOLLOW sets in Compiler Design - Step-by-Step Execution

Concept Flow - FIRST and FOLLOW sets

Start with Grammar

↓

Compute FIRST sets

↓

Use FIRST sets to find FOLLOW sets

↓

Apply FIRST and FOLLOW in parsing

↓

Build Parsing Table or Detect Conflicts

The flow starts from a grammar, then computes FIRST sets for symbols, uses them to find FOLLOW sets, and finally applies both in parsing decisions.

Execution Sample

Compiler Design

Grammar:
S -> A B
A -> a | ε
B -> b

Compute FIRST and FOLLOW sets

This example shows how to find FIRST and FOLLOW sets for a simple grammar with epsilon.

Analysis Table

Step	Action	Symbol	FIRST Set	FOLLOW Set	Reason/Note
1	Initialize FIRST	a	{a}	{}	Terminal symbol's FIRST is itself
2	Initialize FIRST	b	{b}	{}	Terminal symbol's FIRST is itself
3	Initialize FIRST	ε	{ε}	{}	Epsilon symbol's FIRST is epsilon
4	Compute FIRST	A	{a, ε}	{}	A -> a | ε, so FIRST(A) = {a, ε}
5	Compute FIRST	B	{b}	{}	B -> b, so FIRST(B) = {b}
6	Compute FIRST	S	{a, b}	{}	S -> A B, FIRST(S) includes FIRST(A) without ε plus FIRST(B) because A can be ε
7	Initialize FOLLOW	S	N/A	{$}	Start symbol S's FOLLOW includes end marker $
8	Compute FOLLOW	A	N/A	{b}	Since A is before B in S->A B, FOLLOW(A) includes FIRST(B) without ε
9	Compute FOLLOW	B	N/A	{$}	B is last in production, so FOLLOW(B) includes FOLLOW(S)
10	Final Sets	All	FIRST(S)={a,b}, FIRST(A)={a,ε}, FIRST(B)={b}	FOLLOW(S)={$}, FOLLOW(A)={b}, FOLLOW(B)={$}	Sets ready for parsing table construction

💡 All FIRST and FOLLOW sets computed for grammar symbols

State Tracker

Symbol	Initial FIRST	After Step 4	After Step 5	After Step 6	Initial FOLLOW	After Step 7	After Step 8	After Step 9	Final FOLLOW
A	{}	{a, ε}	{a, ε}	{a, ε}	{}	{}	{b}	{b}	{b}
B	{}	{}	{b}	{b}	{}	{}	{}	{$}	{$}
S	{}	{}	{}	{a, b}	{}	{$}	{$}	{$}	{$}
a	{}	{a}	{a}	{a}	{}	{}	{}	{}	{}
b	{}	{b}	{b}	{b}	{}	{}	{}	{}	{}
ε	{}	{ε}	{ε}	{ε}	{}	{}	{}	{}	{}

Key Insights - 3 Insights

Why does FIRST(A) include ε in step 4?

Because A has a production A -> ε, so ε is part of FIRST(A) as shown in execution_table row 4.

How do we know FOLLOW(A) includes 'b' in step 8?

Since A is followed by B in S -> A B, FOLLOW(A) includes FIRST(B) without ε, which is {b}, as explained in execution_table row 8.

Why does FOLLOW(B) include the end marker $ in step 9?

Because B is at the end of the production S -> A B, FOLLOW(B) includes FOLLOW(S), which contains $, as shown in execution_table row 9.

Visual Quiz - 3 Questions

Look at the execution_table at step 6. What is included in FIRST(S)?

A {a, ε}

B {a, b}

C {b}

D {$}

💡 Hint

Refer to execution_table row 6 under FIRST Set column.

At which step does FOLLOW(A) get the symbol 'b'?

A Step 8

B Step 9

C Step 7

D Step 10

💡 Hint

Check execution_table row 8 under FOLLOW Set and Reason columns.

If A did not have the ε production, how would FIRST(S) change at step 6?

A It would be {a, b}

B It would be {b}

C It would be {a}

D It would be empty

💡 Hint

Look at how ε in FIRST(A) affects inclusion of FIRST(B) in FIRST(S) in execution_table row 6.

Concept Snapshot

FIRST and FOLLOW sets help parsers decide which rules to apply.
FIRST(X) is the set of terminals that begin strings derived from X.
FOLLOW(X) is the set of terminals that can appear immediately after X.
Include ε in FIRST if X can produce empty string.
Use FIRST and FOLLOW to build parsing tables and detect conflicts.

Full Transcript

This visual execution trace shows how to compute FIRST and FOLLOW sets for a simple grammar. We start by initializing FIRST sets for terminals and epsilon. Then, for non-terminals like A and B, we compute FIRST sets based on their productions. For example, A has FIRST(A) = {a, ε} because it can produce 'a' or empty string. Next, we compute FIRST(S) by combining FIRST(A) and FIRST(B), considering epsilon in A. FOLLOW sets start with FOLLOW(S) containing the end marker $. Then, FOLLOW(A) includes 'b' because A is followed by B, and FOLLOW(B) includes $ because B is at the end of the production. These sets are essential for building parsing tables in compiler design.

Practice

1. What does the FIRST set of a non-terminal in a grammar represent?

easy

A. The set of all non-terminals reachable from that non-terminal

B. The set of terminals that can appear immediately after that non-terminal

C. The set of all terminals in the grammar

D. The set of terminals that can appear at the start of strings derived from that non-terminal

Solution

1. Step 1: Understand the definition of FIRST set

   The FIRST set of a non-terminal includes all terminals that can appear at the beginning of any string derived from that non-terminal.

2. Step 2: Differentiate from FOLLOW set

   FOLLOW sets represent terminals that can appear immediately after the non-terminal, not at the start.

3. Final Answer:

   The set of terminals that can appear at the start of strings derived from that non-terminal -> Option D

4. Quick Check:

   FIRST set = starting terminals [OK]

Hint: FIRST = start terminals of derivations [OK]

Common Mistakes:

• Confusing FIRST with FOLLOW sets
• Thinking FIRST includes all terminals in grammar
• Mixing terminals and non-terminals in FIRST

2. Which of the following is the correct way to compute the FOLLOW set of a non-terminal A in a grammar?

easy

A. Include all terminals that can start strings derived from A

B. Include all non-terminals reachable from A

C. Include terminals that can appear immediately after A in any production, plus FOLLOW of the start symbol if A can be at the end

D. Include only the terminals that appear before A in productions

Solution

1. Step 1: Understand FOLLOW set definition

   FOLLOW(A) contains terminals that can appear immediately after A in some sentential form.

2. Step 2: Consider special case for end of productions

   If A appears at the end of a production, FOLLOW of the production's left side non-terminal is included in FOLLOW(A).

3. Final Answer:

   Include terminals that can appear immediately after A in any production, plus FOLLOW of the start symbol if A can be at the end -> Option C

4. Quick Check:

   FOLLOW set = terminals after A [OK]

Hint: FOLLOW = terminals after non-terminal in productions [OK]

Common Mistakes:

• Confusing FOLLOW with FIRST sets
• Ignoring FOLLOW of start symbol when non-terminal is at production end
• Including terminals before the non-terminal

3. Given the grammar:

S -> A B
A -> a | ε
B -> b

What is the FIRST set of B?

medium

A. {b}

B. {a, b}

C. {ε}

D. {a}

Solution

1. Step 1: Analyze productions of B

   B produces only terminal 'b', so FIRST(B) includes 'b'.

2. Step 2: Check for epsilon in B

   There is no epsilon (empty string) production for B, so ε is not included.

3. Final Answer:

   {b} -> Option A

4. Quick Check:

   FIRST(B) = {b} [OK]

Hint: FIRST of terminal-only production is that terminal [OK]

Common Mistakes:

• Including ε when no epsilon production exists
• Mixing FIRST sets of A and B
• Adding terminals from other productions incorrectly

4. Consider the grammar:

E -> T E'
E' -> + T E' | ε
T -> int

Which mistake is present if FOLLOW(E') is computed as {+} only?

medium

A. Ignoring that E' can be at the end of production, so FOLLOW(E) should be included

B. Including terminals from FIRST sets instead of FOLLOW sets

C. Adding terminals that never appear after E'

D. Confusing E' with T in FOLLOW computation

Solution

1. Step 1: Identify where E' appears

   E' appears at the end of production E -> T E'.

2. Step 2: Apply FOLLOW rule for end non-terminal

   Since E' is at the end, FOLLOW(E) must be included in FOLLOW(E'). Ignoring this causes incomplete FOLLOW set.

3. Final Answer:

   Ignoring that E' can be at the end of production, so FOLLOW(E) should be included -> Option A

4. Quick Check:

   FOLLOW of end non-terminal includes FOLLOW of left side [OK]

Hint: Add FOLLOW of left side if non-terminal is at production end [OK]

Common Mistakes:

• Forgetting to add FOLLOW of left side non-terminal
• Mixing FIRST and FOLLOW sets
• Assuming FOLLOW only includes terminals directly after

5. Given the grammar:

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

What is the FIRST set of S?

hard

A. {a, b, c, ε}

B. {a, b, c}

C. {a, b, ε}

D. {a, b}

Solution

1. Step 1: Compute FIRST sets of A, B, and C

   FIRST(A) = {a, ε}, FIRST(B) = {b, ε}, FIRST(C) = {c}.

2. Step 2: Calculate FIRST(S) considering ε in A and B

   Since A and B can be ε, FIRST(S) includes FIRST(A) without ε, FIRST(B) without ε, and FIRST(C). So FIRST(S) = {a, b, c}.

3. Final Answer:

   {a, b, c} -> Option B

4. Quick Check:

   FIRST(S) = {a, b, c} considering ε in A and B [OK]

Hint: Include FIRST of next symbol if previous can be ε [OK]

Common Mistakes:

• Including ε in FIRST(S) incorrectly
• Ignoring ε in A or B when computing FIRST(S)
• Only taking FIRST(A) and ignoring B and C