FIRST FOLLOW (Top-Down) Parsing

For FIRST and FOLLOW, we keep applying rules until nothing else can be added to the FIRST and FOLLOW sets.

$FIRST(\alpha)$

The set of terminals that BEGIN strings derived from $\alpha$. If $\alpha$ is $\epsilon$ or generates $\epsilon$, then $\epsilon$ is also in $FIRST(\alpha)$.$f(x) = x * e^{2 pi i \xi x}$

1. If X is a terminal, the FIRST(X) = {X}

2. If X $\rightarrow a\alpha, add ~a ~~to ~FIRST(X)$

3. If X $\rightarrow \epsilon, add ~ \epsilon ~to ~ FIRST(X)$

4. If a production has multiple Symbols like X $\rightarrow Y_1, Y_2, ..., Y_k$

   1. Add every $non-\epsilon ~~in ~~ FIRST(Y_i) ~~to ~~FIRST(X)$

   2. If $Y_1 \Rightarrow^* \epsilon, add ~~\epsilon ~~FIRST(Y_2) ~to ~FIRST(X)$

   3. Continue for each subsequent $Y_i$, if $Y_i \Rightarrow^*\epsilon ~add ~FIRST(Y_{i+1}) ~to ~FIRST(X)$

   to FIRST(X).

5. If all symbols $Y_1, Y_2, ..., Y_k$ can derive $\epsilon$, then add $\epsilon$

$FOLLOW(\alpha)$

The set of terminals that can immediately follow A in sentential form (i.e. ).

1. If S is the start symbol, add $ to FOLLOW(S)

2. If $A \rightarrow \alpha B \beta, add ~FIRST(\beta) - {\epsilon} ~to ~FOLLOW(B)$

3. Search for A in a production body and apply rules to that production:

   1. Add FOLLOW(A) to FOLLOW(B) if:

      1. $A \rightarrow \alpha B$

      2. $A \rightarrow \alpha B \beta ~and ~\beta \Rightarrow^*\epsilon$