Course contentsShow
← Computer Science
Lesson 1957 of 2,87244. Lexical Analysis and ParsingFree lesson

FOLLOW Sets

Computing FOLLOW sets to handle epsilon productions and decide when to pop non-terminals from the stack.

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:

  1. Start symbol: Add $ (end-of-input) to FOLLOW(S)
  2. Right-hand side inspection: If you have A → αBβ, add FIRST(β) - {ε} to FOLLOW(B)
  3. Inheritance: If A → αB or A → α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.