Follow Calculation in Compiler Design

What is FOLLOW in Compiler Design?

The FOLLOW set of a non-terminal symbol A in a context-free grammar is the set of terminals that can appear immediately to the right of A in any sentential form derived from the start symbol. Unlike FIRST sets, which look at what can come immediately after a symbol, FOLLOW sets consider what can come after a symbol in any context.

FOLLOW sets are essential for:

• Constructing LL(1) parsing tables
• Determining when to use a production rule
• Resolving conflicts in grammar design

How to Calculate FOLLOW Sets

The FOLLOW set can be calculated using the following rules:

1. Place $ in FOLLOW(S), where S is the start symbol
2. If there is a production A → αBβ, then:
• FIRST(β) is added to FOLLOW(B)
• If β can derive ε (the empty string), then FOLLOW(A) is added to FOLLOW(B)

These rules are applied repeatedly until no more elements can be added to any FOLLOW set.

Worked Example

Consider the following grammar:

S → aBd | bAe
A → cA | ε
B → bB | ε

Calculating FOLLOW sets for this grammar:

1. Initialize FOLLOW(S) = {$}
2. From S → aBd: FOLLOW(B) = {d}
3. From S → bAe: FOLLOW(A) = {e}
4. From A → cA: FOLLOW(A) = FOLLOW(A) ∪ FIRST(cA) = {e, c}
5. From B → bB: FOLLOW(B) = FOLLOW(B) ∪ FIRST(bB) = {d, b}

The final FOLLOW sets are:

• FOLLOW(S) = {$}
• FOLLOW(A) = {e, c}
• FOLLOW(B) = {d, b}