The following grammar is given:

\begin{align*} M &\rightarrow d M d \\ M &\rightarrow e M e \\ M &\rightarrow f M f \\ M &\rightarrow \varepsilon \end{align*}

I've checked it with the LL(1) table and there are ambiguous cell entries.

Now, I've tried to convert it to LL(1), but without success. Is this not possible for this grammar? Why?

  • $\begingroup$ Have you tried removing left recursion and left-factoring the grammar? $\endgroup$ – Francesco Gramano Mar 16 '15 at 3:59
  • $\begingroup$ In my opinion, there is no left recursion. Left-factorizing the grammar will break up the grammar, because, as shown above, it always produces 2 non-terminals. $\endgroup$ – Anderson Mar 16 '15 at 19:01
  • $\begingroup$ Good, you're right about left-recursion. Sometimes you need to add/modify production rules of your grammar to convert to LL(1), and left-factoring is definitely required in your case to get closer to a more useful result. $\endgroup$ – Francesco Gramano Mar 17 '15 at 21:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.