Lesson 2.2 — nullable, FIRST and FOLLOW as least fixed points¶

Techniques: round-robin iteration, worklist propagation, relational closure (DeRemer–Pennello digraph) · Pebble implements: round-robin (lab exercises E1–E3) · Lab: labs/ch02-ll1-toolkit (SPEC, contract analyze) · Prerequisites: Lesson 2.1 (grammars, derivations) · Time: 4 hours

A predictive parser looks at one token and must know which production to use. For $S' \to e\, S \mid \varepsilon$ and the lookahead e, it needs two facts: e can begin $e\, S$, and e can follow $S'$ (after the $\varepsilon$-alternative). Three sets answer every such question: nullable (which nonterminals can vanish), FIRST (which tokens can begin a string) and FOLLOW (which tokens can come right after a nonterminal). This lesson defines them, proves that they are the least fixed points of monotone equations, and compares three algorithms that compute them.

1. Problem and motivation¶

Every LL and SLR parser generator computes these sets before it builds a table (Lesson 2.3 and Ch 3), and every hand-written parser encodes them in its if (Tok.is(...)) tests. The sets are defined by recursive equations, because nonterminals refer to each other, so the question is how to solve such equations. The answer is the one you will meet again in Ch 14 (dataflow analysis): start from the empty sets and apply the equations until nothing changes. The result is the least solution (Theorem 2.2.4), and it is exactly the set of facts that some derivation proves (Theorem 2.2.5).

FIRST and FOLLOW come from Lewis and Stearns's LL(k) work [LS68] and were made the standard presentation by Knuth's Top-down syntax analysis [Knu71], which characterizes LL(1) through them. The same equations are solved in three ways in practice:

Round-robin iteration¶

Apply every equation once per pass, in a fixed order, until a pass changes nothing: Kleene iteration. It is the textbook algorithm [ALSU07 §4.4.2] and what the reference solution of the lab implements (solutions/labs/ch02-ll1-toolkit/src/Analysis.cpp), because each pass is easy to trace and the drills print exactly these passes.

Worklist propagation¶

Round-robin re-examines every production even when nothing it depends on changed. A worklist algorithm only revisits the equations whose inputs grew. For nullable, the counting variant (one counter per production) is the linear-time Horn-clause algorithm of Dowling and Gallier [DG84]; Bison uses it in nullable_compute [BISON-src]. For FIRST and FOLLOW, the worklist pushes a changed set along the edges of an inclusion graph ("FIRST(T) ⊆ FIRST(E)").

Relational closure (digraph)¶

The inclusion graph can also be solved in one depth-first traversal: every strongly connected component (SCC) of the graph must end up with one shared set, and Tarjan's SCC algorithm [Tar72] visits each component once. DeRemer and Pennello introduced this Digraph algorithm to compute LALR(1) lookaheads [DP82]; it is the fastest method on large grammars and is what LALR generators use (Ch 3).

2. Definitions and algorithms¶

Grammars are as in Lesson 2.1 (Definition 2.1.1). The end-of-input marker $\$$ is a fresh symbol: $\$ \notin N \cup T$, and it appears in no production.

Definition 2.2.1 (nullable, FIRST, FOLLOW)

For $A \in N$ and $\alpha \in (N \cup T)^{*}$:

\[ \begin{aligned} \mathrm{Nullable} &\triangleq \{\, A \in N \mid A \Rightarrow^{*} \varepsilon \,\}, \qquad \alpha \text{ is nullable} \iff \alpha \Rightarrow^{*} \varepsilon,\\ \mathrm{FIRST}(\alpha) &\triangleq \{\, t \in T \mid \exists \beta.\ \alpha \Rightarrow^{*} t\,\beta \,\},\\ \mathrm{FOLLOW}(A) &\triangleq \{\, t \in T \cup \{\$\} \mid \exists \alpha, \beta.\ S\,\$ \Rightarrow^{*} \alpha\, A\, t\, \beta \,\}. \end{aligned} \]

Textbooks often put $\varepsilon$ into $\mathrm{FIRST}(\alpha)$ when $\alpha$ is nullable; this course keeps the two facts apart (the lab stores the flag separately) and prints $\varepsilon$ inside FIRST in tables and drills. $\$$ is never in a FIRST set and $\varepsilon$ is never in a FOLLOW set.

The sets on a two-line grammar

For $S \to A\, a$, $A \to a \mid \varepsilon$: $\mathrm{Nullable} = \{A\}$, $\mathrm{FIRST}(A) = \{a\}$, $\mathrm{FIRST}(S) = \{a\}$ (from $A \to a$ and, since $A$ is nullable, from the second symbol $a$), $\mathrm{FOLLOW}(S) = \{\$\}$, $\mathrm{FOLLOW}(A) = \{a\}$.

Definition 2.2.2 (The rule operators)

Let $\nu \subseteq N$, $\phi : N \to \mathcal{P}(T)$ and $\psi : N \to \mathcal{P}(T \cup \{\$\})$ be candidate solutions; extend $\phi$ to terminals by $\phi(t) = \{t\}$ and to strings by

\[ \mathrm{FirstOf}_{\nu,\phi}(X_1 \cdots X_k) \triangleq \bigcup \{\, \phi(X_i) \mid 1 \le i \le k,\ X_1, \dots, X_{i-1} \in \nu \,\}. \]

The three rule operators are

\[ \begin{aligned} F_{\mathrm{N}}(\nu) &\triangleq \{\, A \mid A \to X_1 \cdots X_k \in P,\ X_1, \dots, X_k \in \nu \,\} &&\text{(N)}\\ F_{\mathrm{F}}^{\nu}(\phi)(A) &\triangleq \textstyle\bigcup_{A \to \alpha \in P} \mathrm{FirstOf}_{\nu,\phi}(\alpha) &&\text{(F)}\\ F_{\mathrm{W}}^{\nu,\phi}(\psi)(B) &\triangleq [B = S]\{\$\} \;\cup \textstyle\bigcup_{A \to \alpha B \beta \in P} \Big( \mathrm{FirstOf}_{\nu,\phi}(\beta) \cup [\beta \in \nu^{*}]\, \psi(A) \Big) &&\text{(W1–W3)} \end{aligned} \]

where $[c]X$ is $X$ if $c$ holds and $\emptyset$ otherwise. They act on the finite lattices $\mathcal{L}_{\mathrm{N}} = (\mathcal{P}(N), \subseteq)$, $\mathcal{L}_{\mathrm{F}} = (\mathcal{P}(T)^{N}, \subseteq)$ and $\mathcal{L}_{\mathrm{W}} = (\mathcal{P}(T \cup \{\$\})^{N}, \subseteq)$, ordered pointwise, with bottoms $\emptyset$, $\lambda A.\emptyset$, $\lambda A.\emptyset$ and heights $h_{\mathrm{N}} = \lvert N \rvert$, $h_{\mathrm{F}} = \lvert N \rvert \lvert T \rvert$, $h_{\mathrm{W}} = \lvert N \rvert (\lvert T \rvert + 1)$.

The operators as rules

Read as inference rules they are the classical list: (N) $A$ is nullable if some $A \to X_1 \cdots X_k$ has every $X_i$ nullable ($k = 0$ allowed); (F) $\mathrm{FIRST}(X_i) \subseteq \mathrm{FIRST}(A)$ if $A \to X_1 \cdots X_k$ and $X_1 \cdots X_{i-1}$ are nullable; (W1) $\$ \in \mathrm{FOLLOW}(S)$; (W2) $\mathrm{FIRST}(\beta) \subseteq \mathrm{FOLLOW}(B)$ for every $A \to \alpha B \beta$; (W3) $\mathrm{FOLLOW}(A) \subseteq \mathrm{FOLLOW}(B)$ for every $A \to \alpha B \beta$ with $\beta$ nullable ($\beta = \varepsilon$ included).

Lemma 2.2.3 (The operators are monotone)

$\nu \subseteq \nu' \Rightarrow F_{\mathrm{N}}(\nu) \subseteq F_{\mathrm{N}}(\nu')$; for fixed $\nu$, $\phi \sqsubseteq \phi' \Rightarrow F_{\mathrm{F}}^{\nu}(\phi) \sqsubseteq F_{\mathrm{F}}^{\nu}(\phi')$; for fixed $\nu, \phi$, $\psi \sqsubseteq \psi' \Rightarrow F_{\mathrm{W}}^{\nu,\phi}(\psi) \sqsubseteq F_{\mathrm{W}}^{\nu,\phi}(\psi')$. Moreover $\mathrm{FirstOf}_{\nu,\phi}$ is monotone in both $\nu$ and $\phi$.

Proof

Each operator is built from unions and from conditions of the form "$X \in \nu$", which can only become true when $\nu$ grows. Enlarging $\nu$ lengthens the prefix $X_1, \dots, X_{i-1} \in \nu$ admitted in $\mathrm{FirstOf}$, so it adds terms to the union; enlarging $\phi$ enlarges each term. The condition $[\beta \in \nu^{*}]$ and the term $\psi(A)$ only grow. A union of larger sets is larger, so each operator is monotone.

Theorem 2.2.4 (Least fixed points by Kleene iteration)

Let $(\mathcal{L}, \sqsubseteq)$ be a finite lattice with bottom $\bot$ and height $h$ (the length of its longest strict chain), and $F : \mathcal{L} \to \mathcal{L}$ monotone. Then $\bot \sqsubseteq F(\bot) \sqsubseteq F^{2}(\bot) \sqsubseteq \cdots$, the chain is constant from some $j \le h$ on, and $F^{j}(\bot) = \mathrm{lfp}(F)$ is the least fixed point of $F$; indeed $\mathrm{lfp}(F) \sqsubseteq x$ for every $x$ with $F(x) \sqsubseteq x$.

Proof

The chain increases. By induction on $i$: $\bot \sqsubseteq F(\bot)$ since $\bot$ is least; if $F^{i}(\bot) \sqsubseteq F^{i+1}(\bot)$, monotonicity gives $F^{i+1}(\bot) \sqsubseteq F^{i+2}(\bot)$.

It stabilizes within $h$ steps. If $F^{i}(\bot) = F^{i+1}(\bot)$ then $F^{i+1}(\bot) = F(F^{i}(\bot)) = F(F^{i+1}(\bot)) = F^{i+2}(\bot)$, so once two consecutive elements are equal all later ones are. Before that, the elements form a strict chain $F^{0}(\bot) \sqsubset \cdots \sqsubset F^{j}(\bot)$, whose length $j$ is at most $h$.

Fixed point. $F(F^{j}(\bot)) = F^{j+1}(\bot) = F^{j}(\bot)$.

Least, even among pre-fixed points. Let $F(x) \sqsubseteq x$. By induction $F^{i}(\bot) \sqsubseteq x$: true for $i = 0$; if $F^{i}(\bot) \sqsubseteq x$ then $F^{i+1}(\bot) \sqsubseteq F(x) \sqsubseteq x$ by monotonicity. In particular every fixed point $x$ lies above $F^{j}(\bot)$.

(For infinite complete lattices the existence of a least fixed point of a monotone map is the Knaster–Tarski theorem [Tar55]; the finite case needs only the argument above.)

Theorem 2.2.5 (The three sets are least fixed points)

Let $\nu^{*} = \mathrm{lfp}(F_{\mathrm{N}})$, $\phi^{*} = \mathrm{lfp}(F_{\mathrm{F}}^{\nu^{*}})$ and $\psi^{*} = \mathrm{lfp}(F_{\mathrm{W}}^{\nu^{*},\phi^{*}})$. They exist, are computed by Kleene iteration in at most $h_{\mathrm{N}}$, $h_{\mathrm{F}}$ and $h_{\mathrm{W}}$ strict steps, and

\[ \nu^{*} = \mathrm{Nullable}, \qquad \phi^{*}(A) = \mathrm{FIRST}(A), \qquad \psi^{*}(A) = \mathrm{FOLLOW}(A) \qquad \text{for all } A \in N, \]

and $\mathrm{FirstOf}_{\nu^{*},\phi^{*}}(\alpha) = \mathrm{FIRST}(\alpha)$ for every string $\alpha$.

Proof

Existence and the step bounds are Theorem 2.2.4 with Lemma 2.2.3. Write $D_{\mathrm{N}}, D_{\mathrm{F}}, D_{\mathrm{W}}$ for the derivational sets of Definition 2.2.1.

Soundness ($\subseteq$): the derivational sets are pre-fixed points. If $A \to X_1 \cdots X_k$ and each $X_i \Rightarrow^{*} \varepsilon$, then $A \Rightarrow^{*} \varepsilon$: so $F_{\mathrm{N}}(D_{\mathrm{N}}) \subseteq D_{\mathrm{N}}$ and $\nu^{*} \subseteq D_{\mathrm{N}}$ by Theorem 2.2.4. Similarly, if $A \to X_1 \cdots X_k$, $X_1 \cdots X_{i-1} \Rightarrow^{*} \varepsilon$ and $X_i \Rightarrow^{*} t \beta$, then $A \Rightarrow^{*} t\, \beta\, X_{i+1} \cdots X_k$, so $D_{\mathrm{F}}$ is closed under (F) given $\nu^{*} \subseteq D_{\mathrm{N}}$; and (W1)–(W3) are sound: (W1) because $S\,\$ \Rightarrow^{0} S\,\$$; (W2) because a form containing $A$ can rewrite $A$ to $\alpha B \beta$ and $\beta$ to $t \cdots$; (W3) because it can rewrite $A$ to $\alpha B \beta$ and $\beta$ to $\varepsilon$, leaving whatever followed $A$ right after $B$.

Completeness ($\supseteq$), by induction on the length $\ell$ of the derivation that witnesses a fact. Nullable: if $A \Rightarrow^{\ell} \varepsilon$, the first step uses some $A \to X_1 \cdots X_k$ and each $X_i \Rightarrow^{< \ell} \varepsilon$; by induction every $X_i \in \nu^{*}$, so $A \in F_{\mathrm{N}}(\nu^{*}) = \nu^{*}$. FIRST: if $A \Rightarrow^{\ell} t \beta$ with first step $A \to X_1 \cdots X_k$, let $X_i$ be the symbol whose descendant contains the first $t$; then $X_1 \cdots X_{i-1} \Rightarrow^{*} \varepsilon$ (so each is in $\nu^{*}$ by the nullable case) and $X_i \Rightarrow^{< \ell} t \cdots$ (so $t \in \phi^{*}(X_i)$ by induction, or $X_i = t$); hence $t \in F_{\mathrm{F}}^{\nu^{*}}(\phi^{*})(A) = \phi^{*}(A)$. FOLLOW: let $S\,\$ \Rightarrow^{\ell} \alpha A t \beta$. If $\ell = 0$, then $A = S$ and $t = \$$, covered by (W1). Otherwise trace the displayed occurrence of $A$ back to the step that created it, $\alpha' B \beta' \Rightarrow \alpha' \gamma A \delta \beta'$ with $B \to \gamma A \delta$. In the final form, $t$ descends either from $\delta$, in which case $\delta \Rightarrow^{*} t \cdots$ and $t \in \mathrm{FirstOf}(\delta)$ (W2); or $\delta \Rightarrow^{*} \varepsilon$ and $t$ descends from $\beta'$. In the second case, perform only the steps inside $\beta'$ without ever expanding that occurrence of $B$: this gives $S\,\$ \Rightarrow^{< \ell} \alpha' B t \cdots$, so $t \in \psi^{*}(B)$ by induction, and (W3) puts $t$ into $\psi^{*}(A)$. The claim for strings follows from the FIRST case applied symbol by symbol.

Round-robin iteration¶

Algorithm 2.2.6 (Round-robin nullable, FIRST, FOLLOW)

Input: $G = (N, T, P, S)$.
Output: $\nu$, $\phi$, $\psi$.
Precondition: none: left recursion, $\varepsilon$-productions, cycles and useless symbols are all allowed.
Postcondition: $\nu = \mathrm{Nullable}$, $\phi = \mathrm{FIRST}$, $\psi = \mathrm{FOLLOW}$ (Theorem 2.2.11).
Invariant: after pass $p$ of each loop, $F^{p}(\bot) \sqsubseteq$ (current sets) $\sqsubseteq \mathrm{lfp}(F)$ for the loop's operator $F$ (Lemma 2.2.10).

Reference solution: solutions/labs/ch02-ll1-toolkit/src/Analysis.cpp; contract ll1::analyze in labs/ch02-ll1-toolkit/include/ll1/LL1.h.

function FirstOf(X1 … Xk, nullable, FIRST):          # FIRST of a string, and whether it is nullable
    out ← {}
    for i ← 1 to k:
        out ← out ∪ FIRST(Xi)                        # FIRST(t) = {t} for a terminal t
        if Xi is a terminal or Xi ∉ nullable:
            return (out, false)
    return (out, true)                               # every Xi (or none) was nullable

function Nullable(G):
    nullable ← {}
    repeat
        changed ← false
        for each production A → X1 … Xk in order:
            if A ∉ nullable and every Xi ∈ nullable:
                nullable ← nullable ∪ {A};  changed ← true
    until not changed
    return nullable

function First(G, nullable):
    FIRST(A) ← {} for every A ∈ N
    repeat
        changed ← false
        for each production A → α in order:
            (f, _) ← FirstOf(α, nullable, FIRST)
            if f ⊄ FIRST(A):
                FIRST(A) ← FIRST(A) ∪ f;  changed ← true
    until not changed
    return FIRST

function Follow(G, nullable, FIRST):
    FOLLOW(A) ← {} for every A ∈ N;  FOLLOW(S) ← {$}
    repeat
        changed ← false
        for each production A → X1 … Xk in order:
            for i ← 1 to k with Xi ∈ N:
                (f, rest_nullable) ← FirstOf(Xi+1 … Xk, nullable, FIRST)
                add f to FOLLOW(Xi)                               # rule W2
                if rest_nullable: add FOLLOW(A) to FOLLOW(Xi)      # rule W3
                if FOLLOW(Xi) grew: changed ← true
    until not changed
    return FOLLOW

CPython's pegen computes FIRST sets without iterating, and misses some

Reproduce (CPython source at tag v3.13.0, run with Python 3.11.15; needs network for the clone):

git -c advice.detachedHead=false clone -q --depth 1 --filter=blob:none --sparse -b v3.13.0 https://github.com/python/cpython
cd cpython && git sparse-checkout set Tools/peg_generator && cd Tools/peg_generator
cat > running.gram <<'EOF'
start: s ENDMARKER
s: 'i' e 't' s s1 | 'a'
s1: ['e' s]
e: t e1
e1: ['+' t e1]
t: '(' e ')' | 'x'
EOF
cat > cycle.gram <<'EOF'
start: a ENDMARKER
a: b | ['x']
b: a
EOF
PYTHONHASHSEED=0 python3 -m pegen.first_sets running.gram
PYTHONHASHSEED=0 python3 -m pegen.first_sets cycle.gram

Output (complete):

{'e': {"'('", "'x'"},
 'e1': {'', "'+'"},
 's': {"'i'", "'a'"},
 's1': {'', "'e'"},
 'start': {"'i'", "'a'"},
 't': {"'('", "'x'"}}
{'a': {'', "'x'"}, 'b': set(), 'start': {'ENDMARKER', "'x'"}}

What to notice: on the running example (written in PEG syntax, […] = optional, '' = $\varepsilon$), FirstSetCalculator in Tools/peg_generator/pegen/first_sets.py [CPY-pegen] prints the FIRST sets of §3. But it is a single memoized depth-first visit that returns $\emptyset$ for a rule already in process, not an iteration to a fixed point. On cycle.gram, $b \to a$ makes $\mathrm{FIRST}(b) \supseteq \mathrm{FIRST}(a) = \{x\}$ and $b$ nullable, yet the tool reports set(): it visited $b$ while $a$ was still in process and never came back. Round-robin iteration cannot make this mistake (Theorem 2.2.11); nothing else in pegen imports this module (it is a standalone debugging aid run with python -m), so the under-approximation is harmless there.

Worklist propagation¶

Definition 2.2.7 (Inclusion graphs)

The FIRST inclusion graph has vertex set $N$, direct sets $\mathrm{direct}_{\mathrm{F}}(A) = \{\, t \mid A \to \alpha\, t\, \beta \in P,\ \alpha \in \mathrm{Nullable}^{*} \,\}$, and an edge $B \to A$ whenever $A \to \alpha B \beta \in P$ with $\alpha$ nullable. The FOLLOW inclusion graph has $\mathrm{direct}_{\mathrm{W}}(B) = [B = S]\{\$\} \cup \bigcup_{A \to \alpha B \beta} \mathrm{FIRST}(\beta)$ and an edge $A \to B$ whenever $A \to \alpha B \beta$ with $\beta$ nullable. In both, the sought sets are the least solution of

\[ \mathcal{S}(x) = \mathrm{direct}(x) \cup \textstyle\bigcup_{y \to x} \mathcal{S}(y), \]

i.e. $\mathcal{S}(x) = \bigcup \{\, \mathrm{direct}(y) \mid y \to^{*} x \,\}$.

Algorithm 2.2.8 (Propagate and NullableCounting)

Input: an inclusion graph $(V, E)$ with direct sets; for NullableCounting, $G$.
Output: $\mathcal{S} : V \to$ sets; the nullable set.
Precondition: for FOLLOW, the final nullable and FIRST sets are known (Definition 2.2.7 uses them).
Postcondition: $\mathcal{S}(x) = \bigcup \{\, \mathrm{direct}(y) \mid y \to^{*} x \,\}$ for all $x$; NullableCounting returns $\mathrm{Nullable}$ (Theorem 2.2.13).
Invariant: (I1) every $\mathcal{S}(x)$ is a subset of its final value; (I2) for every edge $x \to y$ with $\mathcal{S}(x) \not\subseteq \mathcal{S}(y)$, $x$ is in the queue. For counting: count(p) = number of occurrences on the right of $p$ that are not yet known nullable.

function Propagate(nodes, direct, edges):            # used for FIRST and for FOLLOW
    S(x) ← direct(x) for every x
    queue ← all nodes in order;  queued ← all nodes
    while queue is not empty:
        x ← pop the front of queue;  queued ← queued − {x}
        for each edge x → y:
            if S(x) ⊄ S(y):
                S(y) ← S(y) ∪ S(x)
                if y ∉ queued: push y at the back;  queued ← queued ∪ {y}
    return S

function NullableCounting(G):                        # Dowling–Gallier / Bison nullable_compute
    for each production p: count(p) ← |rhs(p)|;  mark p dead if rhs(p) contains a terminal
    for each nonterminal B: occurs(B) ← the productions in which B occurs (once per occurrence)
    nullable ← { A : A → ε };  queue ← those A in order
    while queue is not empty:
        B ← pop the front of queue
        for each live p ∈ occurs(B):
            count(p) ← count(p) − 1
            if count(p) = 0 and lhs(p) ∉ nullable:
                nullable ← nullable ∪ {lhs(p)};  push lhs(p)
    return nullable

Bison's counting nullable computation

Reproduce (bison 3.8.2; any OS):

cat > running.y <<'EOF'
%token i t a e x
%%
S  : i E t S S1 | a ;
S1 : e S | %empty ;
E  : T E1 ;
E1 : '+' T E1 | %empty ;
T  : '(' E ')' | x ;
EOF
bison --trace=sets -o /dev/null running.y 2>&1 | sed -n '/^NULLABLE/,/^$/p'

Output (the NULLABLE section of the trace, complete):

NULLABLE
  $accept: no
  S: no
  S1: yes
  E: no
  E1: yes
  T: no

What to notice: this is the running example of §3 in Bison syntax (plus Bison's own start rule $accept: S $end). The table is printed by nullable_compute in src/nullable.c [BISON-src], which is Algorithm 2.2.8's counting loop (rcount per rule, a queue squeue of newly nullable symbols) and agrees with the least fixed point $\{S', E'\}$ of Theorem 2.2.5.

Relational closure (digraph)¶

Algorithm 2.2.9 (Digraph [DP82])

Input: an inclusion graph $(V, E)$ with direct sets.
Output: $F(x) = \bigcup \{\, \mathrm{direct}(y) \mid y \to^{*} x \,\}$ for every $x$.
Precondition: the same graph as Algorithm 2.2.8.
Postcondition: as the output; all members of one SCC get the same set (Theorem 2.2.14).
Invariant: when Traverse(x) returns and $N(x) = \infty$, $F(x)$ is final; when an SCC root $x$ finishes, every $y$ with an edge into the SCC from outside is already final.

function Digraph(nodes, direct, edges):
    stack ← empty;  N(x) ← 0 for every x;  F(x) ← direct(x)
    for each x in nodes with N(x) = 0: Traverse(x)
    return F

function Traverse(x):
    push x on stack;  d ← |stack|;  N(x) ← d
    for each y with an edge y → x:                   # every set that flows into x
        if N(y) = 0: Traverse(y)
        N(x) ← min(N(x), N(y))
        F(x) ← F(x) ∪ F(y)
    if N(x) = d:                                     # x is the root of an SCC
        repeat
            top ← pop stack;  N(top) ← ∞;  F(top) ← F(x)
        until top = x

Bison's Digraph computes FOLLOW-like sets per transition

Reproduce (bison 3.8.2; running.y from the previous box):

bison --trace=sets -o /dev/null running.y 2>&1 | sed -n '/^follows after includes/,/^$/p'

Output (that section of the trace, complete):

follows after includes:
    FOLLOWS[goto[0] = (0, S, 3)] = $end
    FOLLOWS[goto[1] = (10, S, 14)] = $end e
    FOLLOWS[goto[2] = (16, S, 19)] = $end e
    FOLLOWS[goto[3] = (14, S1, 17)] = $end e
    FOLLOWS[goto[4] = (1, E, 6)] = t
    FOLLOWS[goto[5] = (5, E, 9)] = ')'
    FOLLOWS[goto[6] = (7, E1, 12)] = t ')'
    FOLLOWS[goto[7] = (15, E1, 18)] = t ')'
    FOLLOWS[goto[8] = (1, T, 7)] = t '+'
    FOLLOWS[goto[9] = (5, T, 7)] = '+' ')'
    FOLLOWS[goto[10] = (11, T, 15)] = t '+' ')'

What to notice: Bison prints this right after compute_follows in src/lalr.c calls relation_digraph (src/relation.c, Algorithm 2.2.9) on the includes relation, the LR analogue of the W3 edges [DP82, BISON-src]. Each line is one occurrence of a nonterminal in an LR state rather than the nonterminal as a whole, so the sets are finer; their union per nonterminal is exactly FOLLOW from §3: $S, S' \mapsto \{e, \$\}$ ($end is Bison's $\$$; goto 0 belongs to Bison's added start rule), $E, E' \mapsto \{), t\}$, $T \mapsto \{), +, t\}$. Ch 3 explains the states.

3. Worked example¶

Running example (tests/ch02/Inputs/running.grammar; also the running example of Lesson 2.3): statements with an optional else and parenthesized sums.

(1) S  → i E t S S'        (4) S' → ε           (7) E' → ε
(2) S  → a                 (5) E  → T E'        (8) T  → ( E )
(3) S' → e S               (6) E' → + T E'      (9) T  → x

Its inclusion graphs (solid: FIRST(B) ⊆ FIRST(A); dashed: FOLLOW(A) ⊆ FOLLOW(B)). The FOLLOW graph has a cycle S ⇄ S', so S and S' must end with the same FOLLOW set (Theorem 2.2.14).

flowchart LR
  T[T] -->|FIRST| E[E]
  S[S] -.->|FOLLOW| S2["S'"]
  S2 -.->|FOLLOW| S
  E -.->|FOLLOW| E2["E'"]
  E -.->|FOLLOW| T
  E2 -.->|FOLLOW| T

Round-robin iteration on the running example¶

Nullable (rule N): pass 1 adds $S'$ by (4) and $E'$ by (7); pass 2 adds nothing, so $\mathrm{Nullable} = \{S', E'\}$.

FIRST, productions visited in the order (1)…(9):

nonterminal	init	after pass 1	after pass 2	after pass 3
S	{}	{a,i}	{a,i}	{a,i}
S'	{ε}	{e,ε}	{e,ε}	{e,ε}
E	{}	{}	{(,x}	{(,x}
E'	{ε}	{+,ε}	{+,ε}	{+,ε}
T	{}	{(,x}	{(,x}	{(,x}

pass 1: (1) adds {i} to FIRST(S); (2) adds {a}; (3) adds {e} to FIRST(S'); (5) E → T E' adds nothing yet, because FIRST(T) is still empty; (6) adds {+} to FIRST(E'); (8) and (9) add {(} and {x} to FIRST(T).
pass 2: (5) E → T E' now copies {(,x} from FIRST(T). T comes after E in the production order, which is why a second pass is needed.
pass 3: no change: this confirming pass proves the fixed point (Theorem 2.2.4).

FOLLOW, same order:

nonterminal	init	after pass 1	after pass 2	after pass 3
S	{$}	{e,$}	{e,$}	{e,$}
S'	{}	{e,$}	{e,$}	{e,$}
E	{}	{),t}	{),t}	{),t}
E'	{}	{t}	{),t}	{),t}
T	{}	{+,t}	{),+,t}	{),+,t}

pass 1: (1) S → i E t S S' gives {t} to FOLLOW(E) (W2, t follows E), {e} to FOLLOW(S) (W2: FIRST(S') = {e}), and FOLLOW(S) = {e,$} to FOLLOW(S') (W3, S' ends the production); (5) E → T E' gives {+} to FOLLOW(T) (W2), then {t} from FOLLOW(E) to both T (E' is nullable) and E' (W3); (8) T → ( E ) gives {)} to FOLLOW(E), after (5) already ran.
pass 2: (5) propagates the late ) from FOLLOW(E) to FOLLOW(T) and FOLLOW(E').
pass 3: no change.

Result: FIRST = {S: a i, S': e ε, E: ( x, E': + ε, T: ( x}; FOLLOW = {S: e $, S': e $, E: ) t, E': ) t, T: ) + t}. The golden file tests/ch02/Inputs/running.expected holds the same sets; both the Python oracle and the C++ reference solution reproduce it, and CPython's pegen and Bison print the same sets in the real-world boxes of §2.

Worklist propagation on the running example¶

Counting nullable: productions (1), (2), (3), (8), (9) contain terminals and are dead. Initially nullable = {S', E'} from (4) and (7), queue = S' E'.

step	pop	counters decremented	newly nullable	queue
init	—	—	S', E'	S' E'
1	S'	none (S' occurs only in dead (1))	—	E'
2	E'	(5) E → T E': 2 → 1	—	(empty)

FIRST: $\mathrm{direct}_{\mathrm{F}}$ = {S: a i, S': e, E: {}, E': +, T: ( x}; the only edge is T → E. Queue initially S S' E E' T:

step	pop	grew	queue afterwards
1	S	—	S' E E' T
2	S'	—	E E' T
3	E	—	E' T
4	E'	—	T
5	T	FIRST(E) +=	E
6	E	—	(empty)

FOLLOW: $\mathrm{direct}_{\mathrm{W}}$ = {S: e $, S': {}, E: ) t, E': {}, T: +}; edges S → S', S' → S, E → E', E → T, E' → T:

step	pop	grew	queue afterwards
1	S	FOLLOW(S') +=	S' E E' T
2	S'	—	E E' T
3	E	FOLLOW(E') += {), t}; FOLLOW(T) += {), t}	E' T
4	E'	—	T
5	T	—	(empty)

For FIRST, six pops replace the round-robin's 27 production visits (9 productions × 3 passes); for FOLLOW, five pops replace another 27.

Relational closure (digraph) on the running example¶

Traverse on the FOLLOW graph, visiting the nonterminals in order; "into it" lists the $y$ with $y \to x$.

event	node	into it	stack	F afterwards
visit	S	S'	S	F(S) =
visit	S'	S	S S'	F(S') = {}; then N(S') ← N(S) = 1 and F(S') ∪= F(S) =
back in S	S	—	S S'	F(S) ∪= F(S') = {e,$}; N(S) = 1 = its depth: S is an SCC root
scc	{S', S}	—	(empty)	both get
visit / scc	E	—	(empty)	{),t} (nothing flows into E)
visit / scc	E'	E	(empty)	{),t} (E already finished)
visit / scc	T	E, E'	(empty)	{+} ∪ {),t} ∪ {),t} = {),+,t}

The SCC {S, S'} is found and closed in one step, where round-robin needed a whole pass to carry $ around the cycle.

Try it

./course drill first-follow --seed 4 --difficulty medium, then --solution for the pass-by-pass tables. All three methods give the drill's answer; use whichever you like to check yourself.

4. Invariants and correctness¶

Round-robin iteration¶

Lemma 2.2.10 (Round-robin is sandwiched between Kleene iterates)

Let $F$ be the operator of one of the loops of Algorithm 2.2.6 and $x_p$ the sets after pass $p$ ($x_0 = \bot$, except that FOLLOW starts from $\{S \mapsto \{\$\}\}$, which is below $F(\bot)$). Then $F^{p}(\bot) \sqsubseteq x_p \sqsubseteq \mathrm{lfp}(F)$ for every $p$.

Proof

By induction on $p$. For $p = 0$ both inequalities are immediate. Upper bound: inside pass $p+1$, every update replaces the current $x$ by $x \sqcup (\text{one rule applied to } x)$; one rule applied to $x \sqsubseteq \mathrm{lfp}(F)$ is below $F(x) \sqsubseteq F(\mathrm{lfp}(F)) = \mathrm{lfp}(F)$ by monotonicity, so every intermediate value stays below $\mathrm{lfp}(F)$. Lower bound: during pass $p+1$ the sets only grow and start at $x_p \sqsupseteq F^{p}(\bot)$; every production is visited once, and its contribution computed from the current sets is at least its contribution computed from $x_p$ (monotonicity), so after the pass $x_{p+1} \sqsupseteq F(x_p) \sqsupseteq F(F^{p}(\bot)) = F^{p+1}(\bot)$.

Theorem 2.2.11 (Correctness and termination of round-robin)

Each loop of Algorithm 2.2.6 terminates after at most $h + 1$ passes ($h$ the height of its lattice) and returns the least fixed point; the three results are $\mathrm{Nullable}$, $\mathrm{FIRST}$ and $\mathrm{FOLLOW}$.

Proof

Termination: each pass that does not end the loop adds at least one element to some set, and the sets are bounded, so at most $h$ passes change something and pass $h + 1$ at the latest changes nothing. Result: a pass that changes nothing has applied every rule to $x$ without effect, so $F(x) \sqsubseteq x$, and $x \sqsubseteq \mathrm{lfp}(F)$ by Lemma 2.2.10; by Theorem 2.2.4, $\mathrm{lfp}(F) \sqsubseteq x$. So $x = \mathrm{lfp}(F)$, and Theorem 2.2.5 identifies the three least fixed points with the derivational sets. The loops run in dependency order (nullable, then FIRST, then FOLLOW), so each uses the final sets of the previous one, as Theorem 2.2.5 requires.

When it breaks: running Follow with partial FIRST or nullable sets gives a sound but incomplete answer (it computes the least fixed point of the wrong operator). The order of the productions only changes the number of passes, never the result. A single recursive pass that cuts cycles, as pegen's does (real-world box in §2), is not a fixed-point computation and can miss elements.

Worklist propagation¶

Lemma 2.2.12 (Worklist invariants)

Throughout Algorithm 2.2.8: (I1) $\mathrm{direct}(x) \subseteq \mathcal{S}(x) \subseteq \bigcup \{\, \mathrm{direct}(y) \mid y \to^{*} x \,\}$ for every $x$; (I2) for every edge $x \to y$, either $\mathcal{S}(x) \subseteq \mathcal{S}(y)$ or $x$ is queued. For NullableCounting: count(p) equals the number of right-hand-side occurrences of live $p$ that have not been popped from the queue, and every popped symbol is nullable.

Proof

(I1) holds initially and is preserved because an update adds $\mathcal{S}(x)$ to $\mathcal{S}(y)$ along an edge $x \to y$, and anything reachable into $x$ is reachable into $y$. (I2) holds initially (all nodes queued). When $x$ is popped, the loop restores $\mathcal{S}(x) \subseteq \mathcal{S}(y)$ for every out-edge; when $\mathcal{S}(y)$ grows, only edges out of $y$ can become violated, and $y$ is queued at that moment. For counting: each pop of $B$ decrements count(p) once per occurrence of $B$ in $p$ (the occurrence lists have one entry per occurrence), and a symbol is pushed only when some production of it has all occurrences popped, i.e. every symbol on its right is nullable, so it is nullable by rule (N).

Theorem 2.2.13 (Correctness of the worklist algorithms)

Propagate terminates with $\mathcal{S}(x) = \bigcup \{\, \mathrm{direct}(y) \mid y \to^{*} x \,\}$, after at most $\lvert V \rvert + \lvert V \rvert \cdot \sigma$ pops, where $\sigma$ bounds the size of a set. NullableCounting terminates with $\mathrm{Nullable}$.

Proof

Termination: a node is pushed only when its set grows, at most $\sigma$ times, plus once initially. Result: when the queue is empty, (I2) gives $\mathcal{S}(x) \subseteq \mathcal{S}(y)$ for every edge, and (I1) gives $\mathrm{direct}(x) \subseteq \mathcal{S}(x)$; by induction on path length, $\mathrm{direct}(y) \subseteq \mathcal{S}(x)$ whenever $y \to^{*} x$. With the upper bound of (I1), equality. Counting: soundness is Lemma 2.2.12. Completeness by induction on the length of $A \Rightarrow^{*} \varepsilon$: the first step uses $A \to X_1 \cdots X_k$ with every $X_i$ nullable by shorter derivations, so by induction every $X_i$ is eventually pushed and popped, each pop decrements count(p), and when the last one is popped count(p) = 0 and $A$ is added.

When it breaks: a production like $A \to B\, B$ must decrement its counter once per occurrence; counting $B$ only once would leave the counter at 1 forever.

Relational closure (digraph)¶

Theorem 2.2.14 (Correctness of Digraph)

Algorithm 2.2.9 visits every node once and returns $F(x) = \bigcup \{\, \mathrm{direct}(y) \mid y \to^{*} x \,\}$; all nodes of one strongly connected component receive the same set.

Proof sketch (full proof: [DP82, §4]; SCC properties: [Tar72])

Nodes of one SCC reach each other, so their target sets coincide. Traverse is Tarjan's SCC algorithm run on the reversed edges (it follows $y \to x$ backwards): $N(x)$ is the low-link, and the SCC of $x$ is popped exactly when $N(x)$ equals $x$'s stack depth. An SCC is popped only after every SCC with an edge into it has been completely traversed and popped (Tarjan's reverse topological order), and those nodes have final sets by induction on the order in which SCCs are popped. The root $x$ has collected, through the ∪= in the loop, the sets of all its members' in-neighbors (members propagate their collected sets to the root through the low-link chain), so $F(x)$ is final when it is copied to the whole SCC. Each node is traversed once because $N(x) \neq 0$ afterwards.

When it breaks: the edges must point the right way. Solving FOLLOW with the edges reversed silently computes a different relation.

5. Complexity¶

Variables: $\lvert G \rvert$ total size of the productions (Definition 2.1.1), $\lvert N \rvert$ nonterminals, $\lvert T \rvert$ terminals, $e$ = number of edges of an inclusion graph ($e \le \lvert G \rvert$), $p$ = number of passes, $w$ = machine word size.

Technique	Time (worst)	Time (typical)	Space	Variables
Round-robin	$O(p \cdot \lvert G \rvert \cdot \lvert T \rvert)$ with $p \le h + 1$, $h$ the lattice height of Definition 2.2.2; $\Theta(n^{2})$ production visits on the chain below	2–6 passes on every grammar in `tests/ch02/Inputs`	$O(\lvert N \rvert \cdot \lvert T \rvert)$	as above
Worklist	$O(\lvert G \rvert + e \cdot \lvert T \rvert)$ set work; nullable counting $O(\lvert G \rvert)$	a few pops per nonterminal	$O(\lvert N \rvert \cdot \lvert T \rvert + e)$	as above
Digraph	$O(\lvert N \rvert + e)$ visits, each union $O(\lvert T \rvert / w)$ with bit sets	one DFS	$O(\lvert N \rvert \cdot \lvert T \rvert + e)$	as above

Proposition 2.2.15 (Cost bounds)

(a) Round-robin FIRST or FOLLOW takes at most $h + 1$ passes (Theorem 2.2.11), each $O(\lvert G \rvert \cdot \lvert T \rvert)$ with set unions of cost $O(\lvert T \rvert)$. (b) Propagate does $O(\lvert V \rvert + e \cdot \sigma)$ edge relaxations. (c) NullableCounting runs in $O(\lvert G \rvert)$. (d) Digraph runs in $O(\lvert V \rvert + e)$ unions.

Proof

(a) One pass visits each production once and computes FirstOf over its right side, $O(\lvert G \rvert)$ symbol steps each costing one union. (b) Each node is popped at most $1 + \sigma$ times (Theorem 2.2.13), and a pop relaxes its out-edges, so the total is $\sum_x (1 + \sigma)\, \mathrm{outdeg}(x) = O(e \sigma)$ plus the pops. (c) Each occurrence of a symbol on a right side is decremented at most once (a symbol is pushed at most once), so the work is linear in the number of occurrences, i.e. $O(\lvert G \rvert)$. (d) Traverse is called once per node and examines each edge once, performing one union per edge and one copy per node.

Pathological input: the chain grammar $A_1 \to A_2\, a_1$, $A_2 \to A_3\, a_2$, …, $A_n \to b$, listed top-down. $\mathrm{FIRST}(A_1) = \{b\}$ arrives one link per pass: pass $j$ adds $b$ to $A_{n+1-j}$, so round-robin needs $n + 1$ passes ($n = 3, 5, 8 \mapsto 4, 6, 9$ passes, measured with first_sets in tools/course/lib/grammar.py), that is $\Theta(n^{2})$ production visits. Listed bottom-up it needs 2 passes. The worklist and the digraph algorithm need $O(n)$ work in either order. The chain $A_1 \to A_2$, …, $A_n \to \varepsilon$ does the same to nullable ($n + 1$ passes).

At scale: on the corpus the round-robin needs at most 6 FIRST passes (precedence.grammar, whose five levels form such a chain) and 3 FOLLOW passes (the per-grammar pass counts printed by the first_sets/follow_sets traces). DeRemer and Pennello designed the digraph method to make LALR lookahead computation linear in the size of the relations, replacing the repeated propagation passes of earlier generators [DP82].

Round-robin iteration¶

Order the productions bottom-up (reverse topological order of the dependency graph) [ALSU07 §4.4.2; Kil73 for the dataflow analogue]: fewer passes (2 on the chain) — trade-off: computing the order costs a graph traversal, and cycles still need extra passes.
Bit-vector sets [Knu71]: FIRST as a $\lvert T \rvert$-bit vector per nonterminal, union = word-wise OR — trade-off: fast and compact for $\lvert T \rvert \lesssim 1000$, wasteful for sparse sets.

Worklist propagation¶

LIFO vs FIFO queue: both correct (Theorem 2.2.13 does not depend on the order) — trade-off: a stack processes a changed node's dependents immediately, but has no better revisit bound and its traces are harder to read.
Counting (Horn-clause) nullable [DG84]: linear time; used by Bison — trade-off: needs the occurrence lists, more bookkeeping than round-robin.

Relational closure (digraph)¶

FIRST via reflexive–transitive closure of "begins-with" [ALSU07 §4.4.2 exercises; BISON-src closure.c, set_firsts]: compute the closure matrix with Warshall's algorithm, $O(\lvert N \rvert^{3} / w)$ — trade-off: simpler than Tarjan, cubic.
Digraph for LALR lookaheads [DP82]: the same Traverse over the reads and includes relations of an LR automaton (real-world box in §2; Ch 3) — trade-off: none for correctness; it is the standard LALR method.

7. In real compilers¶

Production compilers with hand-written parsers never compute FIRST sets: they encode them by hand. Parser generators compute them.

Round-robin iteration¶

CPython 3.8 pgen Parser/pgen/pgen.py — ParserGenerator.addfirstsets and calcfirst (v3.8.0) [CPY38-pgen]: computes the FIRST sets of the LL(1) Python grammar recursively over rule DFAs, and raises "rule … is ambiguous" when two arcs' FIRST sets overlap (real-world box in Lesson 2.3). Python replaced it with a PEG parser in 3.9 [PEP617]; Tools/peg_generator/pegen/first_sets.py — FirstSetCalculator (v3.13.0) still computes FIRST sets in a standalone debugging module, with a single cut-off recursion instead of an iteration (real-world box in §2) [CPY-pegen].
Clang (LLVM 23.1.2) has no generated FIRST sets: clang/include/clang/Parse/Parser.h declares hand-written FIRST tests such as Parser::isDeclarationSpecifier and Parser::isTypeSpecifierQualifier, which answer "can this token begin a declaration specifier / type?" [CLANG-Parser].

Find where LLVM does it. Open clang/include/clang/Parse/Parser.h (LLVM 23.1.2) and find isTypeSpecifierQualifier. Question: what does it take as its argument, and which grammar set does the function body (in clang/lib/Parse/ParseDecl.cpp) implement by hand? (quiz clang-first-set)

Worklist propagation¶

Bison src/nullable.c — nullable_compute (Bison 3.8.2): the counting algorithm of §2, with rcount per rule and a queue squeue of newly nullable symbols [BISON-src] (real-world box in §2).
ANTLR 4 runtime/Java/src/org/antlr/v4/runtime/atn/LL1Analyzer.java — LOOK (4.13.2): computes FIRST/FOLLOW-style lookahead sets on the ATN by a depth-first walk with a visited set rather than whole-grammar passes [ANTLR4-LL1Analyzer].

Relational closure (digraph)¶

Bison src/relation.c — relation_digraph and its traverse (Bison 3.8.2): DeRemer–Pennello's algorithm, called from src/lalr.c — initialize_goto_follows (reads) and compute_follows (includes) for LALR(1) lookaheads (real-world box in §2); src/closure.c — set_firsts computes the FIRST-like "firsts" relation by reflexive–transitive closure [BISON-src].
LL generators rarely need the digraph method (their grammars are small and round-robin converges in a few passes); it matters for LALR generators, where the relations are large (Ch 3).

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Round-robin iteration	Exact least fixed point for nullable, FIRST, FOLLOW	O(p·\|G\|·\|T\|), p ≤ \|N\|·\|T\|+1 · 2–6 passes on the corpus	Pass-by-pass tables make every step explainable	Lowest: three nested loops	Textbooks, small generators, this course's lab and oracles
Worklist propagation	Exact (same sets)	O(\|G\| + e·\|T\|); nullable in O(\|G\|) · touches only what changed	The trace names the dependency that fired	Medium: inclusion graph + queue (+ counters)	Bison's nullable, large or incrementally edited grammars
Relational closure (digraph)	Exact (same sets)	O(\|N\| + e) set unions · one DFS	Exposes the relations that also explain conflicts	Medium–high: Tarjan's SCC algorithm	LALR generators (Bison, Menhir), large grammars

Choose round-robin when the grammar is small or you need to explain the result: it is the easiest to get right, and its pass tables are what textbooks and drills show. Choose the worklist when the grammar is large or changes incrementally (an IDE editing a grammar): it only redoes work that an update invalidates. Choose the digraph algorithm when you already need the relations for an LR generator, or when the grammar is huge: one traversal and no repeated passes.

The lab's reference solution implements round-robin; the Python oracles implement all three, and tools/course/tests/test_drills_ch02.py checks that they agree on 300 random grammars (uv run python -m unittest tools.course.tests.test_drills_ch02).

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch02.yaml`)	Drill	Flashcard tag	Exercises
Round-robin iteration	`first-sets-running`, `follow-sets-running`, `clang-first-set`	`./course drill first-follow`	`round-robin`	E1–E3
Worklist propagation	`first-sets-running`, `follow-sets-running`	`./course drill first-follow` (same sets)	`worklist`	— (theory + oracle)
Relational closure (digraph)	`follow-sets-running` (the S ⇄ S′ SCC), `first-sets-running`	`./course drill first-follow` (same sets)	`digraph`	— (theory + oracle)

The forgotten W3 edge

$\varepsilon$ never goes into a FOLLOW set, and $\$$ never goes into a FIRST set. When $\beta$ is nullable, rule W3 copies $\mathrm{FOLLOW}(A)$ into $\mathrm{FOLLOW}(B)$: forgetting it is the most common FOLLOW bug, and it only shows up with $\varepsilon$-productions.

References¶

See the chapter references.

Technique	Time (worst)	Time (typical)	Space	Variables
Round-robin	\(O(p \cdot \lvert G \rvert \cdot \lvert T \rvert)\) with \(p \le h + 1\), \(h\) the lattice height of Definition 2.2.2; \(\Theta(n^{2})\) production visits on the chain below	2–6 passes on every grammar in `tests/ch02/Inputs`	\(O(\lvert N \rvert \cdot \lvert T \rvert)\)	as above
Worklist	\(O(\lvert G \rvert + e \cdot \lvert T \rvert)\) set work; nullable counting \(O(\lvert G \rvert)\)	a few pops per nonterminal	\(O(\lvert N \rvert \cdot \lvert T \rvert + e)\)	as above
Digraph	\(O(\lvert N \rvert + e)\) visits, each union \(O(\lvert T \rvert / w)\) with bit sets	one DFS	\(O(\lvert N \rvert \cdot \lvert T \rvert + e)\)	as above

Lesson 2.2 — nullable, FIRST and FOLLOW as least fixed points¶

1. Problem and motivation¶

Round-robin iteration¶

Worklist propagation¶

Relational closure (digraph)¶

2. Definitions and algorithms¶

Round-robin iteration¶

Worklist propagation¶

Relational closure (digraph)¶

3. Worked example¶

Round-robin iteration on the running example¶

Worklist propagation on the running example¶

Relational closure (digraph) on the running example¶

4. Invariants and correctness¶

Round-robin iteration¶

Worklist propagation¶

Relational closure (digraph)¶

5. Complexity¶

6. Variants and refinements¶

Round-robin iteration¶

Worklist propagation¶

Relational closure (digraph)¶

7. In real compilers¶

Round-robin iteration¶

Worklist propagation¶

Relational closure (digraph)¶

8. Comparison¶

9. Assessment¶

References¶