Problem 5 - Compilation

Answer the following questions about the context-free grammar below.

$$\begin{tabular}{l} $S\rightarrow E$ \\ $E\rightarrow E(S)$ \\ $S\rightarrow S+E$ \\ $E\rightarrow i$ \\ \end{tabular}$$

$\Sigma =\{i,+,(,)\}$ is the set of terminal symbols and $S$ is the starts symbol.

1.

Remove left recursion from this grammar.

2.

Show that the result of 1. is LL(1).

3.

Consider the set

$$\begin{tabular}{rcl} $L = \{ \alpha A a$ & $\vert$ & $S \Rightarr... ...*,$ \\ & & $A \in \{S,E\}, a \in \Sigma, w \in \Sigma^*\}$ \\ \end{tabular}$$

as a language over $\Sigma\cup\{S,E\}$. Construct a deterministic finite automata $M$ that accepts $L$.

4.

Prove that $L$ is equal to the language accepted by $M$ using the following inductions:

• induction on the length of right-most derivations,
• induction on the number of transitions of $M$.

1.

We just have to deal with trivial left-recusions:

• $E\rightarrow E(S) \; \vert \; i$ can be replaced by $E\rightarrow iE'$ and $E'\rightarrow (S)E' \; \vert \; \epsilon$.
• $S\rightarrow S+E \; \vert \; E$ can be replaced by $S\rightarrow ES'$ and $S'\rightarrow +ES' \; \vert \; \epsilon$.

2.