3
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.
Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – de_dux
    Mar 5, 2018 at 19:50
  • $\begingroup$ I don't understand. Why aren't the 4 rules on the left hand side enough? $\endgroup$
    – reinierpost
    Mar 5, 2018 at 22:24
  • $\begingroup$ 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. $\endgroup$
    – de_dux
    Mar 6, 2018 at 6:46
  • $\begingroup$ 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? $\endgroup$
    – reinierpost
    Mar 12, 2018 at 9:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.