Problem 5 - Compilation

Consider a context-free grammar with the following production rules, where $\epsilon$ denotes an empty string. Terminals symbols are $\Rightarrow$, $\times$, $v$ and parentheses.

$$\begin{tabular}{l} $E\rightarrow TE'$ \\ $E'\rightarrow \epsilo... ...row T\times F$ \\ $F\rightarrow v$ \\ $F\rightarrow (E)$ \\ \end{tabular}$$

1.

In order to remove left-recursion from the above grammar, we change the rules whose left-hand size is $T$ to the following one:

$$T\rightarrow FT'.$$

Obtain the production rules whose left-hand size is $T'$.

2.

Let $M[A,a]$ be the LL(1) parsing table for the grammar after left-recursion is removed, where $A$ denotes a non-terminal symbol and $a$ denotes a terminal symbol. Obtain production rules for the following entries of $M[A,a]$:

$$\begin{tabular}{l} $M[E',)]$ \\ $M[E',\Rightarrow]$ \\ $M[E',... ... \\ $M[T',)]$ \\ $M[T',\Rightarrow]$ \\ $M[T',\times]$ \\ \end{tabular}$$

1.

$$T\rightarrow FT'$$

$$T'\rightarrow \times FT' \; \vert \; \epsilon$$

2.

First, we build function FIRST:
For all the terminals, we have:
FIRST $(\Rightarrow)=\{\Rightarrow\}$
FIRST $(\times)=\{\times\}$
FIRST$(v)=\{v\}$
FIRST$(()=\{(\}$
FIRST$())=\{)\}$
If $X\rightarrow \epsilon$ is a production, we add $\epsilon$ to FIRST$(X)$.
FIRST $(E') = \{\epsilon, \dots\}$
FIRST $(T') = \{\epsilon, \dots\}$
If $X\rightarrow Y_1Y_2\cdots Y_k$ is a production and if, for some $i$, $Y_1Y_2\cdots Y_{i-1}\Rightarrow^*\epsilon$, then add FIRST$(Y_i)$ to FIRST$(X)$.
Since $F\rightarrow v \; \vert \; (E)$, FIRST $(F)=\{v,(\}$.
Since $T\rightarrow FT'$, $T'\rightarrow\epsilon$ and $F$ cannot derive to $\epsilon$, FIRST$(T)=$FIRST $(F)=\{v,(\}$.
Since $E\rightarrow TE'$, $E'\rightarrow\epsilon$ and $T$ cannot derive to $\epsilon$, FIRST$(E)=$FIRST $(T)=\{v,(\}$.
Since $E'\rightarrow \Rightarrow E$, FIRST $(E')=\{\epsilon, \Rightarrow\}$.
Since $T'\rightarrow \times FT'$, FIRST $(T')=\{\epsilon, \times\}$.

Then, we build fonction FOLLOW for every non-terminal.
First, since $E$ is the axiom, we had $ to FOLLOW $(E) = \{\$, \dots\}$.
Then, we look at all the production $A\rightarrow \alpha B \beta$, and we add the contents of FIRST$(\beta)$ (except $\epsilon$) to FOLLOW$(B)$.
Since $E\rightarrow TE'$, FOLLOW $(T)=\{\Rightarrow, \dots\}$.
Since $T\rightarrow FT'$, FOLLOW $(F)=\{\times, \dots\}$.
Since $F\rightarrow (E)$, FOLLOW $(E)=\{\$, ), \dots\}$.
Finally, we look at all the productions $A\rightarrow \alpha B$ (or $A\rightarrow \alpha B \beta$ with $\beta \Rightarrow^* \epsilon$) and we add FOLLOW$(A)$ to FOLLOW$(B)$.
Since $E\rightarrow TE'$, FOLLOW $(E')=\{\$, ), \dots\}$ and FOLLOW $(T)=\{\Rightarrow, \$, ), \dots\}$.
Since $E'\rightarrow \Rightarrow E$, FOLLOW $(E)=\{\$, ), \dots\}$.
Since $T\rightarrow FT'$, FOLLOW $(T')=\{\Rightarrow, \$, ), \dots\}$ and FOLLOW $(F)=\{\times, \Rightarrow, \$, ), \dots\}$.
As these sets are closed, we conclude:
FOLLOW $(E)=\{\$,)\}$
FOLLOW $(E')=\{\$,)\}$
FOLLOW $(T)=\{\Rightarrow, \$, )\}$
FOLLOW $(T')=\{\Rightarrow, \$, )\}$
FOLLOW $(F)=\{\times, \Rightarrow, \$, )\}$

Now, we build the predictive parse table. For each production $A\rightarrow \alpha$, we do the following. For each terminal $a$ in FIRST$(\alpha)$, we add $A\rightarrow \alpha$ to $M[A,a]$. If $\epsilon$ is in FIRST$(\alpha)$, we add $A\rightarrow \alpha$ to $M[A,b]$ for all the terminals in FOLLOW$(A)$. If $\epsilon$ is in FIRST$(\alpha)$ and $ is in FOLLOW(A), we had $A\rightarrow \alpha$ to $M[A,\$]$.
We add $E'\rightarrow \Rightarrow E$ to $M[E',\Rightarrow]$.
We add $T'\rightarrow \times FT'$ to $M[T',\times]$.
We add $E'\rightarrow\epsilon$ to $M[E',)]$ and $M[E',\$]$.
We add $T'\rightarrow\epsilon$ to $M[T',\Rightarrow]$, $M[T',)]$ and $M[T',\$]$.
No productions involving $E'$ as a left-hand yields an entry to $M[E',\times]=\emptyset$.

$M[E',)] = \{E'\rightarrow \epsilon\}$
$M[E',\Rightarrow] = \{E'\rightarrow \Rightarrow E\}$
$M[E',\times]=\emptyset$
$M[T',)] = \{T'\rightarrow \epsilon\}$
$M[T',\Rightarrow] = \{T'\rightarrow \epsilon\}$
$M[T',\times] = \{T'\rightarrow \times F T'\}$

The $\emptyset$ locates errors in the parse table.