0
$\begingroup$

There is sample question to calculate equivalent LL(1) grammar for below grammar:

$S \rightarrow S b$

$S \rightarrow S d$

$S \rightarrow c S$

$S \rightarrow c c a$

At first step, it has left recursion so I remove it and convert it to bellow grammar:

$S \rightarrow F M$

$F \rightarrow c S$ (same as $F \rightarrow c F M$)

$F \rightarrow c c a$

$M \rightarrow \epsilon$

$M \rightarrow b M$

$M \rightarrow d M$

We can remove first collision of second and third part too:

$S \rightarrow F M$

$F \rightarrow c D$

$D \rightarrow F M$ (same as $D \rightarrow c D M$)

$D \rightarrow c a$

$M \rightarrow \epsilon$

$M \rightarrow b M$

$M \rightarrow d M$

One more time remove first collision:

$S \rightarrow F M$ (predict: c)

$F \rightarrow c D$ (predict: c)

$D \rightarrow c G$ (predict: c)

$G \rightarrow D M$ (predict: c)

$G \rightarrow a$ (predict: a)

$M \rightarrow \epsilon$ (predict: b, d, \$)

$M \rightarrow b M$ (predict: b)

$M \rightarrow d M$ (predict: d)

Everything is solved except last part of grammar. I tried to solve it but I think there is no LL(1) grammar for this. Is it true? If not, Is it possible to help me? Thanks.

$\endgroup$

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.