# Conversion of ambiguous left recursive grammar to LL(1)

I have been strugling with this LL(1) transformation for far longer than expected and am getting quite desperate. We are given a grammar $G = \left\{V_N, V_T, S, \Phi \right\}$, with the non-terminal set $V_N = \left\{S\right\}$, terminal set $V_T = \left\{\underline{o}, \underline{l}, \underline{r}, \underline{i}\right\}$, start symbol $S$ and the production rules in $\Phi$:

$$\begin{equation}\begin{split} S \rightarrow & \ S \underline{o} S \\ S \rightarrow & \ S \underline{l} S \underline{r} \\ S \rightarrow & \ \underline{i}\end{split}\end{equation}$$

I have tried the standard tricks like left factoring, left recursion removing, which lead to an infinite transformation loop. Trying to fix first and follow set clashes also did not help. Here are some results after applying the transformations:

$$\begin{equation}\begin{split} S \rightarrow & \ \underline{i} A & \ \ \ \ \ \ \ \ \ \ \ S \rightarrow & \ S A \\ A \rightarrow & \ \underline{o} S A & \ \ \ \ \ \ \ \ \ \ \ S \rightarrow & \ \underline{i} \\ A \rightarrow & \ \underline{l} S \underline{r} A & \ \ \ \ \ \ \ \ \ \ \ A \rightarrow & \ \underline{o} S \\ A \rightarrow & \ \epsilon & \ \ \ \ \ \ \ \ \ \ \ A \rightarrow & \ \underline{l} S \underline{r} \end{split}\end{equation}$$

However I go about the problem, I cannot seem to get even close to eliminating the double entries in my LL(1) table.

I don't want to do your homework, but the two insights that appear to solve it for me are:

1. What the first rules

$S \rightarrow SoS$

$S \rightarrow SlSr$

say is that whatever else $S$ can be rewritten to (which, in this case, is just $i$) can be followed by any number of occurrences of $oS$ and $lSr$ arbitrarily often.

1. If we introduce a nonterminal for that (the part that follows the $i$), left-factorized rules for it follow immediately.
• Yes, I tried the removal of the left recursion in S already, see left side of the transformations I did above. The $A$ is used to indicate that there are arbitrarily many repetitions of the desired parts $oS$ and $lSr$. However, this grammar is still ambiguous, because of the $A \rightarrow \epsilon$ rule, which leads to ambiguities. – de_dux Mar 5 '18 at 19:50
• I don't understand. Why aren't the 4 rules on the left hand side enough? – reinierpost Mar 5 '18 at 22:24
• It is not sufficient because of the ambiguity you get through $\epsilon$. It is perhaps more obvious if we take a look at the following production: $S \rightarrow iA \rightarrow ioSA \rightarrow ioiAA$ At that point there are two ways of producing anything in $First(A)$, since $A \rightarrow \epsilon$. Epsilon is the empty string in that case. – de_dux Mar 6 '18 at 6:46
• I haven't really done the exercise, but Isn't $L(A) = L(AA)$ so you can just drop an $A$? Does the assignment allow that? – reinierpost Mar 12 '18 at 9:47