Left Factoring in Compiler Design: Program in C with Explanation

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 → αβ₁ | αβ₂

Rewrite the given expression without changing the meaning,

A → αX

X → β₁ | β₂

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

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

    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.