In this article, we will learn what left factoring in compiler design and the left factoring Program in C Language with an explanation.

You Will Learn

## What is Left Factoring

Left factoring is a grammar transformation that produces a grammar more suitable for predictive or top-down praising. If more than one grammar production rules has a standard prefix string, then the top-down parser cannot choose which of the productions it should take to parse the string in hand.

The process by which the grammar with a common prefix is transformed to make it worthwhile for top-down parsers is known as left factoring.

## How to do Left Factoring

Left Factoring transforms the grammar to make it useful for top-down parsers. In this technique, we make one production for each common prefix, and the rest of the derivation is added by new productions.

A → αβ1 | αβ2

Rewrite the given expression without changing the meaning,

A → αX

X → β1 | β2

You can Check Left Recursion.

## Left Factoring Program in C

```#include<stdio.h>
#include<string.h>
int main()
{
char gram[20],part1[20],part2[20],modifiedGram[20],newGram[20],tempGram[20];
int i,j=0,k=0,l=0,pos;
printf("Enter Production : A->");
gets(gram);
for(i=0;gram[i]!='|';i++,j++)
part1[j]=gram[i];
part1[j]='\0';
for(j=++i,i=0;gram[j]!='\0';j++,i++)
part2[i]=gram[j];
part2[i]='\0';
for(i=0;i<strlen(part1)||i<strlen(part2);i++){
if(part1[i]==part2[i]){
modifiedGram[k]=part1[i];
k++;
pos=i+1;
}
}
for(i=pos,j=0;part1[i]!='\0';i++,j++){
newGram[j]=part1[i];
}
newGram[j++]='|';
for(i=pos;part2[i]!='\0';i++,j++){
newGram[j]=part2[i];
}
modifiedGram[k]='X';
modifiedGram[++k]='\0';
newGram[j]='\0';
printf("\nGrammar Without Left Factoring : : \n");
printf(" A->%s",modifiedGram);
printf("\n X->%s\n",newGram);
}```

## Code Explanation

```    char gram[20],part1[20],part2[20],modifiedGram[20],newGram[20],tempGram[20];
int i,j=0,k=0,l=0,pos;
printf("Enter Production : A->");
gets(gram);```

First, we are taking some variables for further use. You’ll get them along the way. Then we are simply taking the production.

```    for(i=0;gram[i]!='|';i++,j++)
part1[j]=gram[i];
part1[j]='\0';
for(j=++i,i=0;gram[j]!='\0';j++,i++)
part2[i]=gram[j];
part2[i]='\0';```

Here, we are separating the production and saving them in another variable. And adding null characters at the end of each string. If we don’t add a null character at the ending of the string it will carry some garbage value which will generate fault output.

```    for(i=0;i<strlen(part1)||i<strlen(part2);i++){
if(part1[i]==part2[i]){
modifiedGram[k]=part1[i];
k++;
pos=i+1;
}
}```

Using for loop and if statement, we are taking the common prefix and storing them in `modifiedGram` variable. And we are also taking the latest position of common prefix and increment by one for the next character.

```    for(i=pos,j=0;part1[i]!='\0';i++,j++){
newGram[j]=part1[i];
}
newGram[j++]='|';
for(i=pos;part2[i]!='\0';i++,j++){
newGram[j]=part2[i];
}
modifiedGram[k]='X';
modifiedGram[++k]='\0';
newGram[j]='\0';
printf("\nGrammar Without Left Factoring : : \n");
printf(" A->%s",modifiedGram);
printf("\n X->%s\n",newGram);
}```

The position we take, using that along with for loop, we are taking the rest of the production.

And the rest of the things are quite simple.