FIRST and FOLLOW sets

Why it exists

A top-down parser standing at a nonterminal $A$ with several productions must pick one by looking at the next input token. A bottom-up parser must decide when to reduce. Both need to know which tokens can start what is derived from a symbol, and which tokens can come right after a symbol. Those two questions are answered by FIRST and FOLLOW.

Prerequisites

You need a grammar in a form suitable for parsing (ambiguity, left recursion and left factoring); the examples use the expression grammar after left recursion has been removed. Terminals are the tokens, nonterminals are the grammar variables, $\varepsilon$ is the empty string and $\mathdollar$ is the end-of-input marker.

Precise definitions

Nullable. A nonterminal $A$ is nullable if $A \Rightarrow^{*} \varepsilon$. A terminal is never nullable. A string of symbols is nullable if every symbol in it is.

FIRST($\alpha$) for a string $\alpha$ of grammar symbols: the set of terminals that can begin some string derived from $\alpha$; if $\alpha \Rightarrow^{*} \varepsilon$, then $\varepsilon \in \text{FIRST}(\alpha)$ as well.

Rules:

1. If $X$ is a terminal, $\text{FIRST}(X) = \{X\}$.
2. If $X \to \varepsilon$ is a production, add $\varepsilon$ to $\text{FIRST}(X)$.
3. If $X \to Y_1 Y_2 \cdots Y_k$: add $\text{FIRST}(Y_1) \setminus \{\varepsilon\}$ to $\text{FIRST}(X)$; if $Y_1$ is nullable also add $\text{FIRST}(Y_2) \setminus \{\varepsilon\}$; continue while the symbols so far are nullable; if all of $Y_1, \dots, Y_k$ are nullable, add $\varepsilon$.
4. For a string, $\text{FIRST}(X_1 X_2 \cdots X_n)$ is built the same way (stop at the first symbol that is not nullable).

FOLLOW($A$) for a nonterminal $A$: the set of terminals $a$ that can appear immediately to the right of $A$ in some sentential form (that is, $S \Rightarrow^{*} \alpha A a \beta$), plus $\mathdollar$ if $A$ can be the last symbol of a sentential form. FOLLOW is defined only for nonterminals and never contains $\varepsilon$.

Rules:

1. Put $\mathdollar$ in $\text{FOLLOW}(S)$ for the start symbol $S$.
2. For a production $A \to \alpha B \beta$: add $\text{FIRST}(\beta) \setminus \{\varepsilon\}$ to $\text{FOLLOW}(B)$.
3. For a production $A \to \alpha B$, or $A \to \alpha B \beta$ with $\varepsilon \in \text{FIRST}(\beta)$: add $\text{FOLLOW}(A)$ to $\text{FOLLOW}(B)$.

Algorithm. The sets depend on each other (rule 3 of FOLLOW copies a whole set), so apply the rules repeatedly, pass after pass over all productions, until a complete pass changes nothing. This is a fixed-point computation; it terminates because the sets only grow and are bounded by the number of terminals.

Use in LL(1) parsing. For a production $A \to \alpha$ define the set of lookahead tokens for which it is chosen:

$\text{SELECT}(A \to \alpha) = \begin{cases} \text{FIRST}(\alpha) & \text{if } \varepsilon \notin \text{FIRST}(\alpha)\\ (\text{FIRST}(\alpha) \setminus \{\varepsilon\}) \cup \text{FOLLOW}(A) & \text{if } \varepsilon \in \text{FIRST}(\alpha) \end{cases}$

A grammar is LL(1) exactly when, for every nonterminal $A$, the SELECT sets of its productions are pairwise disjoint. For $A \to \alpha \mid \beta$ this is the condition: $\text{FIRST}(\alpha) \cap \text{FIRST}(\beta) = \emptyset$; at most one of $\alpha, \beta$ derives $\varepsilon$; and if $\beta \Rightarrow^{*} \varepsilon$ then $\text{FIRST}(\alpha) \cap \text{FOLLOW}(A) = \emptyset$. The table construction is on the LL(1) page; SLR parsing uses FOLLOW as well (SLR).

How it works

Each animation runs the passes. A step happens only when a production adds something; the highlighted production is the one applied and the changed cell is shaded. First the FIRST sets of the expression grammar. Notice that $E$, $T$ and $F$ all end up with the same FIRST set, since each of them begins with a factor.

Now FOLLOW of the same grammar. FIRST is shown for reference. The first step puts $\mathdollar$ in $\text{FOLLOW}(E)$ (rule 1); then, for example, $F \to ( E )$ puts ) in FOLLOW($E$), because ) comes right after $E$ there.

A grammar with nullable symbols is more interesting, because FIRST must look past a nullable symbol and FOLLOW must pass sets along. The nullable column is computed too.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The grammar must first be made suitable by removing left recursion and factoring. FIRST and FOLLOW feed the table of the LL(1) parser and the reduce entries of the SLR parser; LR(1) and LALR(1) use more precise lookahead sets instead (CLR and LALR).

PYQs

Which of the following statement(s) is/are TRUE
while computing First and Follow during top-down
parsing by a compiler?

Consider the following grammar G, with S as the
start symbol. The grammar G has three incomplete
productions denoted by (1), (2), and (3):
S → daT | (1)
 T → aS | bT | (2)
 R → (3) | ε

The set of terminals is {a, b, c, d, f}. The FIRST
and FOLLOW sets of the different non-terminals
are as follows:

FIRST(S) = {c, d, f}, FIRST(T) = {a, b, ε},
FIRST(R) = {c, ε}

FOLLOW(S) = FOLLOW(T) = {c, f, $},
FOLLOW(R) = {f}

Consider the following context-free grammar where
the set of terminals is {a,b,c,d,f}.
S→daT|Rf
T→aS|baT|ε
R→caTR|ε

          The following is a partially-filled LL(1) parsing table.

a
b
c
d
f
$
S

(1)
S →da T
(2)

T
T →a S
 T →ba T
(3)

T →ε
(4)
R

R →caTR

R →ε

Which one of the following choices represents the
correct combination for the numbered cells in the
parsing table ("blank" denotes that the corresponding
cell is empty)?

COMPILER DESIGN

Consider the following grammar:

P→xQRS
Q→yz|z
R→w|ε
S→y

         What is FOLLOW(Q)?

For the grammar below, a partial LL(1) parsing table
is also presented along with the grammar. Entries that
need to be filled are indicated as E1, E2 and E3. ε is
the empty string, $ indicates end of input, and |
separates alternate right hand sides of productions.

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

A → S

B → S

      a
b
$
S
E 1
E 2
 S →ε
A
 A → S
 A → S
error
B
B →S
B →S
E3

The FIRST and FOLLOW sets for the non-terminals
A and B are:-

FIRST(A) = {a, b, ε} = FIRST(B)

Self-check

Revision card

References