FIRST and FOLLOW Sets

• Grammar Transformations for Parsing: the notation for grammars, and the left-recursion-free expression grammar used below.

Nullable symbols first

NULLABLE(G)
    N <- {A : A -> eps is a production}
    repeat
        for each production A -> Y1 ... Yk with every Yi in N (no terminal in the body)
            add A to N
    until N does not change

FIRST of a single symbol

FIRST-SETS(G)
    for each terminal a: FIRST(a) <- {a}
    for each nonterminal A: FIRST(A) <- {}
    repeat
        for each production A -> Y1 Y2 ... Yk
            add FIRST-OF-STRING(Y1 Y2 ... Yk) to FIRST(A)
    until no set changes
    return FIRST

FIRST-OF-STRING(Y1 Y2 ... Yk)
    result <- {}
    for i <- 1 to k
        add FIRST(Yi) - {eps} to result
        if eps not in FIRST(Yi) then return result
    add eps to result          (every Yi is nullable, or k = 0)
    return result

FOLLOW

FOLLOW-SETS(G, S)
    FOLLOW(S) <- {$}; every other FOLLOW(A) <- {}
    repeat
        for each production A -> alpha B beta, for each nonterminal occurrence B
            add FIRST-OF-STRING(beta) - {eps} to FOLLOW(B)
            if eps in FIRST-OF-STRING(beta)     (beta nullable or empty)
                add FOLLOW(A) to FOLLOW(B)
    until no set changes

The expression grammar

E  -> T E'
E' -> + T E' | eps
T  -> F T'
T' -> * F T' | eps
F  -> ( E ) | id

Nullable chains

S -> A B c | B d
A -> a A | eps
B -> b | eps

• $\text{FIRST}(A) = \{a, \varepsilon\}$, $\text{FIRST}(B) = \{b, \varepsilon\}$.
• $\text{FIRST}(A B c)$: $a$ from $A$; $A$ nullable, so $b$ from $B$; $B$ nullable, so $c$. Result $\{a, b, c\}$, and no $\varepsilon$ because $c$ is not nullable.
• $\text{FIRST}(B d) = \{b, d\}$, so $\text{FIRST}(S) = \{a, b, c, d\}$.
• $\text{FOLLOW}(S) = \{\text{\textdollar}\}$. $\text{FOLLOW}(A) = \text{FIRST}(B c) = \{b, c\}$ (and $A \to a A$ adds FOLLOW(A) to itself, nothing new). $\text{FOLLOW}(B) = \{c\} \cup \{d\} = \{c, d\}$.

A conflict that appears only through FOLLOW

S -> X Y Z
X -> x | eps
Y -> y X | eps
Z -> z | X

• Directly from $S \to X Y Z$. What follows $X$ there is $Y Z$. $Y$ is nullable, so $\text{FIRST}(Y Z) - \{\varepsilon\} = \{y\} \cup \text{FIRST}(Z) - \{\varepsilon\} = \{x, y, z\}$ goes into FOLLOW(X). x is in FIRST(Z) because of $Z \to X$.
• Through $Y \to y X$. $X$ ends this body, so FOLLOW(Y) flows into FOLLOW(X), and FOLLOW(Y) contains FIRST(Z) minus epsilon, which contains x.

FOLLOW sets that feed each other

P -> S d S
S -> a B | eps
B -> b S | c

• $\text{FIRST}(P)$ contains d because the first $S$ is nullable; it does not contain $\varepsilon$ because d is a terminal.
• In $P \to S d S$ the first $S$ gets d and the last $S$ gets $\text{FOLLOW}(P) = \{\text{\textdollar}\}$.
• $S \to a B$ sends FOLLOW(S) into FOLLOW(B), and $B \to b S$ sends FOLLOW(B) back into FOLLOW(S). Mutual inclusion forces $\text{FOLLOW}(S) = \text{FOLLOW}(B)$; the iteration still stops, because sets only grow.
• The number of passes depends on the order of productions. Processing $P, S, B$ gives the final sets in one pass and a second pass confirms. Processing $B, S, P$ needs three passes: FOLLOW(S) is filled in pass 1 (from $P$), FOLLOW(B) only in pass 2 (from $S \to a B$), and pass 3 confirms. The result is the same.
• The grammar is LL(1): $S$'s alternatives are chosen by a versus $\text{FOLLOW}(S) = \{d, \text{\textdollar}\}$, and $B$'s by b versus c.

FIRST and FOLLOW of a left-recursive grammar

E -> E + T | T
T -> T * F | F
F -> ( E ) | id

Small facts worth memorising

• $S \to a S b \mid \varepsilon$: $\text{FIRST}(S) = \{a, \varepsilon\}$, $\text{FOLLOW}(S) = \{b, \text{\textdollar}\}$.
• $S \to A a A b \mid B b B a$, $A \to \varepsilon$, $B \to \varepsilon$: $\text{FIRST}(S) = \{a, b\}$, $\text{FOLLOW}(A) = \text{FOLLOW}(B) = \{a, b\}$. Equal FOLLOW sets matter for SLR parsing; see the note LR(0) and SLR(1) Parsing.

• $\varepsilon \in \text{FIRST}(A)$ if and only if $A$ is nullable. $\varepsilon$ is never in a FOLLOW set; $\text{\textdollar}$ is never in a FIRST set of a grammar symbol.
• $\text{\textdollar} \in \text{FOLLOW}(S)$ always, and $\text{\textdollar} \in \text{FOLLOW}(A)$ whenever $A$ can end a sentential form (it appears last in a body whose head has $\text{\textdollar}$ in FOLLOW, possibly followed by nullable symbols).
• FOLLOW sets depend on the whole grammar, FIRST sets only on the productions reachable from the symbol. Adding a production anywhere can enlarge FOLLOW sets elsewhere.
• A nonterminal on the right of its own body. In $A \to \alpha A$, the rule "add FOLLOW(A) to FOLLOW(A)" is harmless. In $A \to \alpha A \beta$, FIRST($\beta$) minus epsilon goes into FOLLOW(A); when $\beta$ is nullable, the usual FOLLOW(head) contribution also applies.
• FIRST of a string stops at the first terminal. In $\text{FIRST}(A\, a\, B)$, nothing from $B$ can appear and $\varepsilon$ cannot appear.
• Mutual inclusion gives equal sets. If $\text{FOLLOW}(A) \subseteq \text{FOLLOW}(B)$ and $\text{FOLLOW}(B) \subseteq \text{FOLLOW}(A)$, the two sets are equal.
• Use of the sets. LL(1) table: FIRST of each body, and FOLLOW of the head for nullable bodies. SLR(1) table: FOLLOW of the head decides where to reduce. Operator-precedence and LR(1) parsing use other information.

• "FIRST($XY$) is FIRST($X$) $\cup$ FIRST($Y$)." Only when $X$ is nullable, and then without $X$'s $\varepsilon$.
• "FOLLOW($B$) in $A \to \alpha B \beta$ is FIRST($\beta$)." Without $\varepsilon$, and plus FOLLOW($A$) when $\beta$ is nullable.
• "If $A \to \varepsilon$ is a production, $\varepsilon$ goes into FOLLOW($A$)." Never; it goes into FIRST($A$).
• "A terminal enters FOLLOW($B$) only from the symbol right after $B$." It also comes from symbols further right when the ones in between are nullable, as x enters FOLLOW(X) from FIRST(Z) across the nullable $Y$.
• "FOLLOW sets that include each other make the algorithm loop forever." The sets are bounded by the terminals and only grow, so the passes stop.

• Compute FIRST and FOLLOW for a given grammar. Work in passes until nothing changes; most errors come from stopping after one pass when a FOLLOW set feeds another FOLLOW set.
• Option elimination. Any option with $\varepsilon$ in a FOLLOW set or $\text{\textdollar}$ in a FIRST set is wrong.
• Hidden flows through nullable symbols. As in the $S \to X Y Z$ example, a terminal can enter FOLLOW through two or three links of nullable symbols.
• LL(1) decision. Two alternatives with overlapping FIRST sets, or a nullable alternative whose head's FOLLOW overlaps another alternative's FIRST, make a conflict. See the note Top-Down Parsing and LL(1).
• SLR reductions. "On which lookaheads does state $I$ reduce by $A \to \alpha$?" The answer is $\text{FOLLOW}(A)$.
• Left-recursive grammars. FIRST and FOLLOW can be asked of $E \to E + T \mid T$ directly; compute them without removing the recursion.
• Every occurrence counts. A nonterminal that occurs twice in one body ($S$ in $P \to S d S$) collects from both occurrences.

• Grammar Transformations for Parsing: prerequisite. Grammars must usually be rewritten before their FIRST and FOLLOW sets give an LL(1) table.
• Top-Down Parsing and LL(1): dependent. The LL(1) table is filled from FIRST and FOLLOW.
• Bottom-Up Parsing and Shift-Reduce: dependent. SLR(1) reductions are placed on FOLLOW of the head.