0
$\begingroup$

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

$S→aA | aB$
Becomes:
$S→aS'$
$S'→A|B$

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

$S→AD|bbS|bScS|BS $
$A→aAbb | abb$
$B→aB|ba|b$
$D→cDd|cccd$

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

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

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$

Improve this answer
$\endgroup$

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.