How to Calculate Follow Set in Compiler Design

To calculate the FOLLOW set of a grammar symbol, start by adding $ (end marker) to the start symbol's FOLLOW set. Then, for each production, add FIRST sets of symbols following the target symbol, and if those can be empty, add FOLLOW of the production's left side. Repeat until no changes occur.

Syntax

The FOLLOW set of a non-terminal symbol in a grammar is the set of terminals that can appear immediately to the right of that symbol in some "sentential" form.

Steps to calculate FOLLOW(A) for a non-terminal A:

• Add $ (end of input marker) to FOLLOW(S) where S is the start symbol.
• For each production B → α A β, add FIRST(β) \ {ε} to FOLLOW(A).
• If β can derive ε (empty string), add FOLLOW(B) to FOLLOW(A).
• Repeat until no FOLLOW set changes.

text

FOLLOW(S) = { $ }  // S is start symbol
For each production B → α A β:
  FOLLOW(A) += FIRST(β) - {ε}
  If ε in FIRST(β):
    FOLLOW(A) += FOLLOW(B)
Repeat until no changes

Example

This example shows how to calculate FOLLOW sets for a simple grammar:

1. S → A B
2. A → a | ε
3. B → b

We calculate FOLLOW sets step-by-step.

python

productions = {
  'S': ['A B'],
  'A': ['a', 'ε'],
  'B': ['b']
}

# FIRST sets (given or calculated separately)
FIRST = {
  'a': {'a'},
  'b': {'b'},
  'A': {'a', 'ε'},
  'B': {'b'},
  'S': {'a', 'b'}
}

# Initialize FOLLOW sets
FOLLOW = { 'S': {'$'}, 'A': set(), 'B': set() }

changed = True
while changed:
    changed = False
    # For production S -> A B
    # FOLLOW(A) += FIRST(B) - {ε} = {'b'}
    if 'b' not in FOLLOW['A']:
        FOLLOW['A'].add('b')
        changed = True
    # Since B does not produce ε, no FOLLOW(S) added to FOLLOW(B)

print('FOLLOW sets:')
for nt in FOLLOW:
    print(f'{nt}:', FOLLOW[nt])

Output

FOLLOW sets:
S: {'$'}
A: {'b'}
B: set()

Common Pitfalls

Common mistakes when calculating FOLLOW sets include:

• Not adding $ to the start symbol's FOLLOW set.
• Forgetting to add FOLLOW of the left side non-terminal when the following symbol can produce ε.
• Confusing FIRST and FOLLOW sets.
• Not repeating the process until no changes occur, leading to incomplete sets.

text

## Wrong approach (missing FOLLOW addition when ε in FIRST):
# For B → A β, if β can be ε, missing FOLLOW(B) in FOLLOW(A)

## Correct approach:
# If β can be ε, FOLLOW(A) += FOLLOW(B)

Quick Reference

Step	Action
1	Add $ to FOLLOW of start symbol.
2	For each production B → α A β, add FIRST(β) \ {ε} to FOLLOW(A).
3	If β can be ε, add FOLLOW(B) to FOLLOW(A).
4	Repeat until no FOLLOW set changes.

Key Takeaways

Start by adding $ to the FOLLOW set of the start symbol.

Add FIRST of the following symbols (excluding ε) to the FOLLOW set of the target symbol.

If the following symbols can be empty, add FOLLOW of the production's left side to the target's FOLLOW set.

Repeat the process until no FOLLOW sets change to ensure completeness.

Distinguish clearly between FIRST and FOLLOW sets to avoid confusion.