TransWikia.com

Removing left factoring from Context-Free Grammar

Computer Science Asked by mmbs on October 21, 2021

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

One Answer

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$

Answered by André Souza Lemos on October 21, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP