How to calculate $\textrm {First}$ and $\textrm {Follow}$

We have to determine whether $A\Rightarrow ^* \epsilon$. If there are no $\epsilon$-production we now that the answer is always negative, otherwise

• If $A\to\epsilon\in P$ we know that $A\Rightarrow ^* \epsilon$.

• If $A\to B_1B_2\dots B_n$ where all $B_i$ are nonterminal symbols and for all $1\leq i\leq n$: $B_i\Rightarrow ^*\epsilon$ then we also know $A\Rightarrow ^* \epsilon$.

We calculate $\textrm {First}$ and $\textrm {Follow}$ in a similar fashion:

• $\textrm{First}(a)=\{a\}$ if $a\in\Sigma$.

• If $A\to B_1B_2\dots B_n$ and there is an $i\leq n$ s.t. $\forall 1\leq k < i.B_k\Rightarrow ^* \empty$ then we add $\textrm{First}(B_i)$ to $\textrm{First}(A)$.

And for $\textrm {Follow}$:

• $\$\in \textrm{Follow}(S)$ where $S$ is the original start symbol.

• If there is a production $A\to \alpha B \beta$ then everything in $\textrm{First}(\beta)$ is in $\textrm{Follow}(B)$.

• If there is a production $A\to \alpha B \beta$ with $\beta\Rightarrow ^*\epsilon$ then everything in $\textrm{Follow}(A)$ is also in $\textrm{Follow}(B)$.