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

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

But how can this be left-factorised?


$$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).

  • $\begingroup$ 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. $\endgroup$ – G. Bach Jan 5 '16 at 14:36
  • $\begingroup$ That should've read "now substitute $Y := (BX + \epsilon)$" $\endgroup$ – 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}[1]{\langle#1\rangle} \begin{array}{rl} \ang{C} \to & \ang{A} \ang{C'}\\ \ang{C'} \to & \ang{B} \ang{C} \; | \; \epsilon\\ \end{array}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.