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

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);
}

Sample Input and Output

Left Factoring Example

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.

You Might Like: