Algorithm to compute FIRST and FOLLOW

Notation: $X$ = nonterminal/terminal; $\alpha,\beta$ = strings of grammar symbols; $\epsilon$ = empty string; $ = end marker.

FIRST

Compute $FIRST(X_1\dots X_n))$ = set of terminals that can start any string derivable from $X_1X_2\dots X_n$ (plus $\epsilon$ if the whole can derive $\epsilon$).

Rules (for individual symbol):

1. If $X$ is a terminal, then $\mathrm{FIRST}(X) = \{X\}$.
2. If $X$ is $\epsilon$ production i.e. $X\to\epsilon$, add $\epsilon$ to $\mathrm{FIRST}(X)$.
3. If $X$ is a nonterminal and $X\to Y_1Y_2\dots Y_k$, then:
   • Put $\mathrm{FIRST}(Y_1)$ \textbackslash}{\epsilon} into $\mathrm{FIRST}(X)$.
   • If $Y_1$ derives $\epsilon$, also put $\mathrm{FIRST}(Y_2)\setminus\{\epsilon\}$, and so on.
   • If $Y_1..Y_k$ all can derive $\epsilon$, then put $\epsilon$ into $\mathrm{FIRST}(X)$.
   • Order: For each production, apply until no more additions; repeat the whole loop until no change.

For a string $\alpha = X_1X_2\dots X_n$ :
$\mathrm{FIRST}(\alpha) = \mathrm{FIRST}(X_1) \setminus \{\epsilon\}$; if $\epsilon\in \mathrm{FIRST}(X_1)$, add $\mathrm{FIRST}(X_2)\setminus\{\epsilon\}$, etc.; if all $X_i$ derive $\epsilon$, add $\epsilon$ to $\mathrm{FIRST}(\alpha)$.

2. Compute FOLLOW(X) for every nonterminal X

Rule to find the set of terminals that can appear immediately to the right of $X$ in some sentential form.

1. If $X$ is the start symbol, place `$` in$\mathrm{FOLLOW}(X)$.
2. For a production $A\to\alpha B\beta$: everything in $\mathrm{FIRST}(\beta)$ except $\epsilon$ goes into $\mathrm{FOLLOW}(B)$.
3. If there is a production $A\to\alpha B$ or $A\to\alpha B\beta$ where $\beta \rightsquigarrow \epsilon$ (i.e. $\beta$ is nullable), then everything in $\mathrm{FOLLOW}(A)$ gets added to $\mathrm{FOLLOW}(B)$.
4. Repeat these steps until no further additions occur.

(Terminals/symbol ) that are not nonterminals have no FOLLOW.)

These First/Follow results are then used to build the predictive (LL(1)) parsing table: for $A\to\alpha$, put the production into M[A][a] for each a in $\mathrm{FIRST}(\alpha)$; if $\alpha$ nullable, put it into M[A][b] for each b in $\mathrm{FOLLOW}(A)$.