Constructing an LL(1) grammar

Let's have a look at the grammar $G$ for arithmetical expressions again. $G=(\{E,T,F\},\{(,),a,+,*\},E,P)$ where

$$P = \{ E \to T \mid E + T$$

$$ T \to F \mid T * F$$

$$ F \to a \mid ( E )$$

We don't need the $\textrm {Follow}$-sets in the moment because the empty word doesn't occur in the grammar. For the nonterminal symbols we have

$$\textrm{First}(F) = \{ \texttt{a},\texttt{(} \}$$

$$\textrm{First}(T) = \{ \texttt{a},\texttt{(} \}$$

$$\textrm{First}(E) = \{ \texttt{a},\texttt{(} \}$$

and now it is easy to see that most of the $\textrm{Lookahead}$-sets agree, e.g.

$$\textrm{Lookahead}(E \to T) = \{ \texttt{a},\texttt{(} \}$$

$$\textrm{Lookahead}(E \to E+T) = \{ \texttt{a},\texttt{(} \}$$

$$\textrm{Lookahead}(T \to F) = \{ \texttt{a},\texttt{(} \}$$

$$\textrm{Lookahead}(T \to T*F) = \{ \texttt{a},\texttt{(} \}$$

$$\textrm{Lookahead}(F \to a) = \{ \texttt{a}\}$$

$$\textrm{Lookahead}(F \to (E) ) = \{ \texttt{(} \}$$

Hence the grammar $G$ is not LL(1).

However, luckily there is an alternative grammar $G'$ which defines the same language: $G'=(\{E,E',T,T',F\},\{(,),a,+,*\},E,P')$ where

$$P' = \{ E \to T E'$$

$$E' \to \texttt{+} T E' \mid \epsilon$$

$$T \to F T'$$

$$T' \to \texttt{*} F T' \mid \epsilon$$

$$F \to a \mid \texttt{(} E \texttt{)}$$

Since we have $\epsilon$-productions we do need the $\textrm {Follow}$-sets.

$$\textrm{First}(E) = \textrm{First}(T) = \textrm{First}(F) = \{ \texttt{a},\texttt{(} \}$$

$$\textrm{First}(E') = \{\texttt{+}\}$$

$$\textrm{First}(T') = \{\texttt{*}\}$$

$$\textrm{Follow}(E) = \textrm{Follow}(E') = \{ \texttt{)},\texttt{\$} \}$$

$$\textrm{Follow}(T) = \textrm{Follow}(T') = \{ \texttt{+},\texttt{)},\texttt{\$} \}$$

$$\textrm{Follow}(F) = \{ \texttt{+},\texttt{*},\texttt{)},\texttt{\$} \}$$

Now we calculate the $\textrm{Lookahead}$-sets:

$$\textrm{Lookahead}(E \to T E') = \{ \texttt{a},\texttt{(} \}$$

$$\textrm{Lookahead}(E' \to \texttt{+} T E') =\{ \texttt{+}\}$$

$$\textrm{Lookahead}(E' \to \epsilon) = \textrm{Follow}(E') = \{ \texttt{)},\texttt{\$}\}$$

$$\textrm{Lookahead}(T \to \texttt{+} F T') = \{ \texttt{a},\texttt{(} \}$$

$$\textrm{Lookahead}(T' \to \texttt{*} F T') = \{ \texttt{*} \}$$

$$\textrm{Lookahead}(T' \to \epsilon) =\textrm{Follow}(T') = \{ \texttt{+},\texttt{)},\texttt{\$}\}$$

$$\textrm{Lookahead}(F \to a) = \{ \texttt{a}\}$$

$$\textrm{Lookahead}(F \to (E) ) = \{ \texttt{(} \}$$

Hence the grammar $G'$ is LL(1).