FOLLOW Sets
What You'll Learn
You'll learn how to compute FOLLOW sets to determine what tokens can legally appear after a non-terminal, enabling your parser to handle epsilon productions correctly.
The Core Idea
When building a predictive parser, FIRST sets tell you what tokens can start a production. But what happens when a non-terminal can derive epsilon (the empty string)? You need to know what can come after that non-terminal to decide whether to use the epsilon production.
FOLLOW(A) is the set of all terminals that can legally appear immediately after non-terminal A in any valid derivation.
Why FOLLOW Sets Matter
Imagine parsing with this grammar:
S → A b
A → a | ε
When you see token b and need to expand A, should you use A → a or A → ε? FIRST(A) = {a, ε} doesn't help directly. But FOLLOW(A) = {b} tells you: "If you see b, and A can go to epsilon, use the epsilon production because b is allowed to follow A."
Computing FOLLOW Sets
Three rules:
- Start symbol: Add
$(end-of-input) to FOLLOW(S) - Right-hand side inspection: If you have
A → αBβ, add FIRST(β) - {ε} to FOLLOW(B) - Inheritance: If
A → αBorA → αBβwhere β derives ε, add FOLLOW(A) to FOLLOW(B)
Apply these rules repeatedly until nothing changes.
Example
S → A B
A → a | ε
B → b | ε
- FOLLOW(S) = {$}
- FOLLOW(A) = FIRST(B) = {b, ε}, so {b} ∪ FOLLOW(S) = {b, $}
- FOLLOW(B) = FOLLOW(S) = {$}
Key Takeaway: FOLLOW sets identify which tokens can appear after a non-terminal, enabling your parser to correctly choose epsilon productions during predictive parsing.