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.


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.