33/136
\begin{frame}{$\first{A}$}
\begin{goal}{}
We consider the first terminal letters derivable from a word:
\begin{talign}
\first{w} =
\ &\{\, a \in T \mid w \Rightarrow^* a\ldots \,\} \; \cup \; \{\, \lambda \mid w \Rightarrow^* \lambda \,\}
\end{talign}
\end{goal}
\pause

\begin{block}{Algorithm}
Let $$\text{PreFirst}(w)$$ be the smallest set such that:
\begin{itemize}
\item $$w \in \text{PreFirst}(w)$$
\item $$a \in \text{PreFirst}(w)$$ if $$av \in \text{PreFirst}(w)$$
\item $$B \in \text{PreFirst}(w)$$ if $$Bv \in \text{PreFirst}(w)$$
\item $$v \in \text{PreFirst}(w)$$ if $$Bv \in \text{PreFirst}(w)$$ and $$B$$ erasable
\item $$v \in \text{PreFirst}(w)$$ for every $$A \in \text{PreFirst}(w)$$ and rule $$A \to v$$
\end{itemize}
Then $$\text{First}(w)$$ consists of
\begin{itemize}
\item all terminal letters $$a \in T$$ such that $$a \in \text{PreFirst}(w)$$, and
\item $$\lambda$$ if $$w = A_1 A_2 \ldots A_n$$ for erasable variables $$A_1,\ldots,A_n$$.
\end{itemize}
\end{block}
\end{frame}