C++ Program to Eliminate Left Factoring

Elimination of Left Factoring in Compiler Design

What is Left Factoring?

Left factoring is taking out the regular left factor that shows up in two productions of the equivalent non-terminal. It is done to keep away from back-tracking by the parser.

Consider an example below

A -> αP/αQ

where A, P, Q are non-terminals and α is a common factor

after left factoring the grammar will be:

A -> αS'

S' -> P/Q

Left Factoring is basically a grammar transformation technique. It has "factoring out" prefixes which are common to two or more productions or in other words Left factoring is a process of transformation, in which the grammar turns from a left-recursive form to an equivalent non-left-recursive form.

The C++ Code to remove left factoring is written below where the user is asked to enter the Parent non-terminal and production rules and based on that, the output is generated which you can see below.

C++ Program To Remove Left Factoring

#include<iostream>

#include<string>

using namespace std;

int main()

{ string ip,op1,op2,temp;

   int sizes[10] = {};

   char c;

   int n,j,l;

   cout<<"Enter the Parent Non-Terminal : ";

   cin>>c;

   ip.push_back(c);

   op1 += ip + "\'->";

   op2 += ip + "\'\'->";;

   ip += "->";

   cout<<"Enter the number of productions : ";

   cin>>n;

   for(int i=0;i<n;i++)

   {

       cout<<"Enter Production "<<i+1<<" : ";

       cin>>temp;

       sizes[i] = temp.size();

       ip+=temp;

       if(i!=n-1)

           ip += "|";

   }

   cout<<"Production Rule : "<<ip<<endl;

   char x = ip[3];

   for(int i=0,k=3;i<n;i++)

   {

       if(x == ip[k])

       {

               if(ip[k+1] == '|')

               {

                   op1 += "#";

                   ip.insert(k+1,1,ip[0]);

                   ip.insert(k+2,1,'\'');

                   k+=4;

               }

               else

               {

                   op1 += "|" + ip.substr(k+1,sizes[i]-1);

                   ip.erase(k-1,sizes[i]+1);

               }

       }

       else

       {

           while(ip[k++]!='|');

       }

   }

   char y = op1[6];

   for(int i=0,k=6;i<n-1;i++)

   {

       if(y == op1[k])

       {

               if(op1[k+1] == '|')

               {

                   op2 += "#";

                   op1.insert(k+1,1,op1[0]);

                   op1.insert(k+2,2,'\'');

                   k+=5;

               }

               else

               {

                   temp.clear();

                   for(int s=k+1;s<op1.length();s++)

                       temp.push_back(op1[s]);

                   op2 += "|" + temp;

                   op1.erase(k-1,temp.length()+2);

               } }}

   op2.erase(op2.size()-1);

   cout<<"After Left Factoring : "<<endl;

   cout<<ip<<endl;

   cout<<op1<<endl;

   cout<<op2<<endl;

   return 0;

}

OUTPUT

Enter the Parent Non-Terminal : L

Enter the number of productions : 4

Enter Production 1 : i

Enter Production 2 : iL

Enter Production 3 : (L)

Enter Production 4 : iL+L

Production Rule : L->i|iL|(L)|iL+L

After Left Factoring :

L->iL'|(L)

L'->#|LL''

L''->#|+L

You must be also searching for these programming languages :

• C++ Program to Implement Left Recursion in Compiler Designer
• C++ Program to Implement String Tokenization for a given program

Tags: Left factoring, Left Recursion, Left Recursion Elimination, Program to eliminate Left Factoring, learn C++ Programs, code hour, C++ programming tutorials