Question $3$

Left$-$factorization is a grammar transformation technique that can help better prepare a grammar

for recognition by a predictive parser. When faced with a choice between two different

A$-$productions, it may not be possible to determine which production to utilize.

If $A{}_1|{}_2$ are two A $-$productions, and the input begins with a nonempty string derived

from $,$ we may not know which production to utilize. By introducing a new nonterminal into the

grammar, we may delay the decision until more of the input has been seen, allowing us to make

the correct choice.

Here, we introduce A$\text{'}$ and reformulate the productions to become

$A{A}^{\text{'}}$

$A^{\text{'}}{}_1|{}_2$

In general, the procedure for doing this is as follows:

For each nonterminal A$,$ find the longest prefix $$ common to two or

more of its alternatives. If $,$ replace all A$-$productions of the form

$A{}_1|{}_2|dots|!$

where $$ represents all alternatives that do not begin with $,$ with

$A{A}^{\text{'}}|$

$A^{\text{'}}{}_1|{}_2|dots|$

Apply this transformation until no two alternatives for a nonterminal have

a common prefix.

Utilizing the grammar from the end of Question $2,$ please left$-$factor it$.$