1
$\begingroup$

So I am in the process of learning about LL(1) grammar and converting an ambiguous one into LL(1). I know how to figure out if a grammar (G) is ambiguous, however, I am having trouble converting it to a LL(1) using left factoring.

From my understanding, left factoring is basically factoring out prefixes which are common to two or more productions. So for example,

 A -> X | X Y Z

Becomes

A -> X B
B -> Y Z | ε 

However, if we take an example such as the following grammar G,

A -> acB | da
B -> abB | daA | Af

How would I go about applying the left factoring to convert G to LL(1) since there is no common prefix based on what I can see. I am assuming I would have to use substitution (right corner substitution), correct?

The following is my attempt at converting G to LL(1), did I do it correctly?

A -> acB | da
B -> abB | daA | Af

A -> acabB | daA | Af | da     //sub B into A

A -> E | Af | da               //left factor
E -> acabB | daA | 1
$\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.