Computing the FOLLOW() set of a grammar

Question

I'm reading Compilers: Principles, Techniques, and Tools (2nd Edition) and I'm trying to compute the FOLLOW() sets of the following grammar:

S  →  iEtSS' | a
S' →  eS | ε
E  →  b

where S, S', E are non-terminal symbols, S is the start symbol, i, t, a, e, b are terminal symbols, and ε is the empty string.

What I've done so far

FOLLOW(S) = {$} ∪ FOLLOW(S')
FOLLOW(S') = FOLLOW(S)
FOLLOW(E) = FIRST(tSS') - {ε} = FIRST(t) - {ε} = {t} - {ε} = {t}

where $ is the input right endmaker.

Explanation

$ ∈ FOLLOW(S), since S is the start symbol. We also know that S' → eS, so everything in FOLLOW(S') is in FOLLOW(S). Therefore, FOLLOW(S) = {$} ∪ FOLLOW(S').

We also know that S → iEtSS', so everything in FOLLOW(S) is in FOLLOW(S'). Therefore, FOLLOW(S') = FOLLOW(S).

The problem is that I can't compute FOLLOW(S), since I don't know FOLLOW(S'). Any ideas?

Answer 1

The simple algorithm, described in the text, is a least fixed-point computation. You basically cycle through the nonterminals, putting terminals into the follow sets, until you get through an entire cycle without changes.

Since nothing is ever removed from any follow set, and the number of terminals is finite, the algorithm must terminate. It usually only takes a few cycles.