I know that, removing left factoring is a simple task.
And i understand following procedure:

$S→aA | aB$

Yet I'm running into problems with this particular grammar:

$S→AD|bbS|bScS|BS $
$A→aAbb | abb$

How to remove left factoring from it, I'm trying to convert it into LL(1) grammar

  • 1
    $\begingroup$ What do you mean by "removing left factoring"? Left factoring is a technique that removes left recursion: stackoverflow.com/questions/15194142/… $\endgroup$ Commented Jul 19, 2020 at 15:40
  • $\begingroup$ @BearAqua The post you link to establishes a difference between left factoring and left recursion, not a connection. $\endgroup$ Commented Jul 20, 2020 at 3:05

1 Answer 1


Your grammar can be abbreviated as follows:

$S \rightarrow a^{m}b^{2m}c^{n+2}d^{n}\;|\;(a^{*}(ba|b)|bb)S\;|\;bScS; \; m,n \ge 1$

You can't factor out, for instance, the subexpressions generating the sequences of $a$'s that appear on the left. The language is not even LL($k$), let alone LL($1$).

Consider the following analogous, and simpler, example:

$S \rightarrow aS\;|\;T\; \\ T \rightarrow aTb\;|\;\varepsilon$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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