# Is C → A B C | A left-factorizable?

$$C \to A B C \mid A$$

Obviously has the same FIRST(C) for the both productions.

But how can this be left-factorised?

Tried:

$$C \to A B C'$$ $$C' \to A C \mid \varepsilon$$

The FIRST sets are disjoint, but is this correct?

Should $B \to \varepsilon$ (or $C \to \varepsilon$) be added as well, so that it handles $A B A$?

Your proposed factoring won't work correctly because both productions start with the same nonterminal. Remember that for an LL(1) parser you cannot have two productions that start with the same nonterminal (usually) because if you see anything in the FIRST set for that nonterminal, you wouldn't know which production to pick.

To left-factor the grammar, try something like this:

C → AX

X → BC | ε

Notice that this gives you the same strings as before, but (assuming that at least one of B and C doesn't produce ε) is LL(1).

• It's probably also easy to see things like this if you interpret productions as polynomials where multiplication is noncommutative. $ABX + A = A (BX+ \epsilon)$, now substitute $X := (BX + \epsilon)$ and add that production. – G. Bach Jan 5 '16 at 14:36
• That should've read "now substitute $Y := (BX + \epsilon)$" – G. Bach Jan 12 '16 at 11:40

IIRC, the left factorization take the common part out of the rules and add a non-term with the non common part, thus:

$$\newcommand{\ang}{\langle#1\rangle} \begin{array}{rl} \ang{C} \to & \ang{A} \ang{C'}\\ \ang{C'} \to & \ang{B} \ang{C} \; | \; \epsilon\\ \end{array}$$