FOLLOW · Definition and derivation

🎓 This is the advanced track · theory.
Now that you've finished the FIRST track, here comes its partner, FOLLOW.
If FIRST was about "what does it start with," FOLLOW is about "what comes after it."
On this page we'll look at the definition and at deriving it directly from the definition. Then on → Computation rules → Implementation.

📍 Where it lives · engine FirstFollowAnalyzer · module Janglim.FrontEnd — Layer 2 (the tier below the parse table)

Here's the example grammar we keep using.
This time the start symbol matters, so let me mark it — the Expr at the very top is the start symbol.

Expr   : Expr '+' Term | Term ;      ← start symbol
Term   : Term '*' Factor | Factor ;
Factor : '(' Expr ')' | id ;

The answer we worked out by hand in the basic track was this.

   FOLLOW(Expr)   = { $, '+', ')' }
   FOLLOW(Term)   = { $, '+', ')', '*' }
   FOLLOW(Factor) = { $, '+', ')', '*' }

Let's go through this again, carefully, starting from the definition.

Definition — what FOLLOW is

Let me pin it down in one line first.

FOLLOW(B) = the set of terminals that can appear immediately after the nonterminal B somewhere in a valid sentence.
(And if B can come at the very end of a sentence, we also include $, which stands for the end of input.)

Lining it up with FIRST as a pair: FIRST is the terminal that can come first when you derive that symbol, and FOLLOW is the terminal that can come right after it.

Seeing "right behind" through derivation

Back in the FIRST definition we defined derivation (⇒) — swapping a nonterminal for the right-hand side of a production.
FOLLOW is about deriving outward from the start symbol Expr and watching which terminal ends up attached right behind B.

   Expr  ⇒*  …  B  a  …       →  a came right after B   ⇒   a ∈ FOLLOW(B)

Written tightly in symbols (S = start symbol, T = the set of terminals):

   FOLLOW(B) = { a ∈ T | S ⇒* … B a … }   ∪   ( { $ }  if  S ⇒* … B )

📎 One thing that's crucially different from FIRST.
With FIRST you only had to look at that one symbol, but for FOLLOW you have to scan everywhere B is used across the whole grammar. What comes after B differs at every spot where B appears.

By the definition — deriving it directly

Let's apply the definition directly and work out "gather the terminals that come right after B" by hand.

FOLLOW(Expr) — it comes out cleanly

Expr is the start symbol — that is, the entire input is one big Expr.
So once you've read that Expr all the way to the end, what comes right after?
The end of input, with nothing left to read.
And the imaginary token that marks the end of input was $.
So in effect $ comes right after Expr — $ ∈ FOLLOW(Expr).

Now let's hunt across the whole grammar for what comes right after Expr.

   Expr → Expr '+' Term      right after the leading Expr :  '+'
   Factor → '(' Expr ')'     right after Expr :       ')'

What can come after Expr is '+' and ')', plus $ at the very end. Gathering them all:

   FOLLOW(Expr) = { $, '+', ')' }

FOLLOW(Term) — when it sits at the end, it inherits

Let's hunt the grammar for what's right after Term.

   Term → Term '*' Factor    right after the leading Term :  '*'           →  add '*'
   Expr → Expr '+' Term      Term is at the end of the production …          →  nothing after it?
   Expr → Term               Term is at the end of the production …          →  again, nothing after

'*' goes straight in.
But the last two lines are curious — Term sits at the very end of the production, so there's no terminal right behind it.

So then what comes after Term?
Look at Expr → Term: Term is all of Expr — that is, Expr and Term end at the exact same spot.

Words are abstract, so let's see it as one scene.
Picture the fragment ( Expr ) (Factor → '(' Expr ')'). Here ) comes right after Expr.
But if that Expr is just a single Term (Expr → Term), then the same spot becomes ( Term ).

   ( Expr )        →   ) after Expr
   ( Term )        →   now ) after Term   (same spot!)

Look — the ) that used to be after Expr is now sitting right after Term.
Because Term inherited the end-spot of Expr as is.

💡 This is the core rule of FOLLOW.
When a nonterminal comes at the very end of a production, it inherits the entire FOLLOW of that production's LHS (the left-hand nonterminal).
Here it's Expr → Term, so — FOLLOW(Expr) flows straight into FOLLOW(Term).

   FOLLOW(Term) = { '*' }  ∪  FOLLOW(Expr)
                = { '*' }  ∪  { $, '+', ')' }   =   { $, '+', ')', '*' }

When ε is involved — with a small grammar

Up to now, the β after B has always been a terminal ('+', ')', '*'), so it was simple. But if β is a nonterminal that can disappear, one more layer appears. Our expr grammar has no such nonterminal, so here's the grammar we'll use for this section:

S → A B
A → a | ε
B → b | ε

A and B can each disappear into ε. Look at FOLLOW(A) by the definition: in S → A B, right after A comes B.

if B doesn't disappear: the first terminal after A is B's first terminal b. → b ∈ FOLLOW(A). (The ε in FIRST(B) isn't a terminal, so we drop it and add only FIRST(B) − ε.)
if B does disappear: S ⇒ A B ⇒ A (B is ε), so A becomes the very end of S, and what's after A is then what's after S — it inherits FOLLOW(S). Since FOLLOW(S) = { $ } (start symbol), $ ∈ FOLLOW(A).

   FOLLOW(A) = ( FIRST(B) − ε )  ∪  FOLLOW(S)  =  { b } ∪ { $ } = { b, $ }

β (here B) can disappear, which is why $ flowed in too. These two things we just saw — taking FIRST(β) with only ε removed and inheriting the LHS's FOLLOW when β disappears — are exactly rules 2 and 3 of the summary below.

Why it doesn't finish in one pass — the FOLLOW you'd inherit may not be settled yet

As we just saw, when B comes at the very end of a production, you need the FOLLOW of that production's left-hand nonterminal (LHS).
But that LHS's FOLLOW may itself still be filling in. (Exactly the same situation as when recursion blocked us with FIRST.)
So just following the definition step by step won't finish in a single pass.

That's why on the next page we'll — tidy this process into a handful of rules and solve it, like with FIRST, by iterating until nothing changes.

Summary

Following the definition, FOLLOW ended up being filled in three ways.

The start symbol's FOLLOW gets $. (Because it can come at the very end of a sentence.)
$ ∈ FOLLOW(start symbol)
If something comes right after B, the first terminal of that something goes into FOLLOW(B).
For A → α B β, add FIRST(β) − ε to FOLLOW(B)
If B comes at the very end of a production, it inherits the FOLLOW of that production's LHS.
For A → α B, inherit FOLLOW(A) into FOLLOW(B)

Next — turning this process into rules

Next up is tidying these three into computation rules that work for any grammar, and solving them by iteration.

👉 FOLLOW · Computation rules

👈 Back to the basic concepts: FIRST / FOLLOW

Table of Contents