Write a C program to remove left factoring from single production.
Answers
Explanation:
What is Left Factoring ?
Consider a part of regular grammar,
E->aE+bcD
E->aE+cBD
Here, grammar is non-left recursive, and unambiguous but there is left factoring.
How to resolve ?
E=aB | aC | aD | ............
then,
E=aX
X=B | C | D |...........
So, the above grammar will be as :
E=aE+X
X=bcD | cBD
Explanation:
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)