Lecture No. 18

Dated: 08-04-2025

Here is the algorithm for computing the FIRST sets.¹

For all terminal symbols $b$.

\[\text{FIRST}(b) = \{b\}\]

For all productions $X \to A_1 \ldots A_n$ or in general, $X \to A_i$.

\[\text{Add FIRST}(A_i) - \{\epsilon\} \text{ to FIRST} (X) \text{, stop if } \epsilon \notin \text{FIRST}(A_i)\]

This strategy is encoded in the following procedure

for each $a \in (T \cup \epsilon)$ $\text{FIRST}(a) \to \{a\}$
for each $A \in NT$ $\text{FIRST}(A) \to \emptyset$
while (FIRST sets¹ are still changing)
for each $A \to \beta_1 \beta_2 \ldots \beta_k \in P$
$\text{FIRST}(A) \to \text{FIRST}(A) \cup (\text{FIRST}(\beta_1) - \epsilon)$
$i \to 1$
while ($\epsilon \in \text{FIRST}(\beta_i)$ and $i = k - 1$)
$\text{FIRST}(A) \to \text{FIRST}(A) \cup (\text{FIRST}(\beta_{i + 1}) - \{\epsilon\})$
$i \to i + 1$
if (i == k and $\epsilon \in \text{FIRST}(\beta_k)$)
$\text{FIRST}(A) \to \text{FIRST}(A) \cup \{\epsilon\}$

Example

Expression Grammar

1. E  ->   T E'
2. E' -> + T E'
3.    |    e
4. T  ->   F T'
5. T' -> * F T'
6.    |    e
7. F  ->  (E)
8.    |    ID

\[\text{FIRST}(id) = \{ id \}\]

\[\text{FIRST}('(') = \{ ( \}\]

\[\text{FIRST}('+') = \{ + \}\]

\[\text{FIRST}(E) = \text{FIRST}(T) - \{ \varepsilon \}\]

\[\text{FIRST}(T) = \text{FIRST}(F) - \{ \varepsilon \}\]

\[\text{FIRST}(F) = \text{FIRST}('(') - \{ \varepsilon \} = \{ ( \}\]

\[\text{FIRST}(F) = \{ '(' \} + \text{FIRST}(id) - \{ \varepsilon \} = \{ (, id \}\]

\[\text{FIRST}(E') = \{ +, \varepsilon \}\]

\[\text{FIRST}(T') = \{ *, \varepsilon \}\]

Then

\[\text{FIRST}(E) = \text{FIRST}(T) = \text{FIRST}(F) = \{ (, id \}\]

\[\text{FIRST}(E') = \{ +, \varepsilon \}\]

\[\text{FIRST}(T') = \{ *, \varepsilon \}\]

`Follow Sets`²

Definition

\[\text{FOLLOW}(X) = \{b | S \to *\beta X b \omega\}\]

Strategy

Add $ to $\text{FOLLOW}(S)$ where $S$ is the start non terminal.
If $A \to \alpha B \beta$ exists then everything in $\text{FIRST}(\beta) - \{\epsilon\}$ is in $\text{FOLLOW}(B)$.
If $A \to \alpha B$ or $A \to \alpha B \beta$ exists where $\epsilon \in \text{FIRST}(\beta)$ then everything in $\text{FOLLOW}(A)$ is in $\text{FOLLOW}(B)$.

Procedure

for each $A \in NT$ $\text{FOLLOW}(A) \to \emptyset$
$\text{FOLLOW}(S) \to \{\$\}$
while (FOLLOW sets² are still changing) {
for each $A \to \beta_1 \beta_2 \ldots \beta_k \in P$ {
$\text{FOLLOW}(\beta_k) \to \text{FOLLOW}(\beta_k) \cup \text{FOLLOW}(A)$
$T \to \text{FOLLOW}(A)$
for $i \to k$ down to $2$ {
if ($\epsilon \in \text{FIRST}(\beta_i)$)
$\text{FOLLOW}(\beta_{i - 1}) \to \text{FOLLOW}(\beta_{i - 1}) \cup (\text{FIRST}(\beta_i) - \{\epsilon\}) \cup T$
else {
$\text{FOLLOW}(\beta_{i - 1}) \to \text{FOLLOW}(\beta_{i - 1}) \cup \text{FIRST}(\beta_i)$
$T \to \emptyset$
}
}
}
}

Apply to Expression Grammar

Put $ in $\text{FOLLOW}(E)$.
By rule (2) applied to production ? ( E ), ‘)’ is also in $\text{FOLLOW}(E)$.
Thus, $\text{FOLLOW}(E) = \{ ), \$\}$.
By rule (3) applied to production $E \to T E'$ , $ and ‘)’ are in $\text{FOLLOW}(E')$.
Thus, $\text{FOLLOW}(E) = \text{FOLLOW}(E') = \{ ), \$ \}$.
Similarly, $\text{FOLLOW}(T) = \text{FOLLOW}(T') = \{ +, ), \$ \}$ and $\text{FOLLOW}(F) = \{ +, \cdot , ), \$ \}$.

References

Read more about FIRST sets. ↩↩
Read more about FOLLOW sets. ↩↩