Elimination of Left Recursion
Left Recursion:
The generation is left-recursive if the leftmost symbol on the right side is equivalent to the nonterminal on the left side. For Ex: exp → exp + term.
A grammar that contains a production having left recursion is called as a Left-Recursive Grammar. Similarly, if the rightmost symbol on the right side is equal to
left side is called Right-Recursion.
Why to Eliminate Left Recursion?
Consider an example: E->E+T/T,
The above example will go in an infinite loop because the function E keeps calling itself which causes a problem for a parser to go in an infinite loop which is never ending process.
so to avoid this infinite loop problem we do Elimination of left recursion.
Rules to follow to eliminate left recursion
A-->bA'
A'-->eps/aA' //eps stands for epsilon
Therefore solution for above left recursion problem,
E --> TE'
E'-->eps/+TE'
C++ Program - Elimination Of Left Recursion in compiler design
#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 + "\'->";
ip += "->";
op2+=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;
for(int i=0,k=3;i<n;i++)
{
if(ip[0] == ip[k])
{
cout<<"Production "<<i+1<<" has left recursion."<<endl;
if(ip[k] != '#')
{
for(l=k+1;l<k+sizes[i];l++)
op1.push_back(ip[l]);
k=l+1;
op1.push_back(ip[0]);
op1 += "\'|";
}
}
else
{
cout<<"Production "<<i+1<<" does not have left recursion."<<endl;
if(ip[k] != '#')
{
for(j=k;j<k+sizes[i];j++)
op2.push_back(ip[j]);
k=j+1;
op2.push_back(ip[0]);
op2 += "\'|";
}
else
{
op2.push_back(ip[0]);
op2 += "\'";
}}}
op1 += "#";
cout<<op2<<endl;
cout<<op1<<endl;
return 0;}
OUTPUT:
Enter the Parent Non-Terminal: E
Enter the number of productions : 3
Enter Production 1: E+T
Enter Production 2: T
Enter Production 3: #
Production Rule : E->E+T|T|#
Production 1 has left recursion.
Production 2 does not have left recursion.
Production 3 does not have left recursion.
E->TE'|E'
E'->+TE'|#
You must be also searching for these programming languages :
Tags: Elimination of Left Recursion, Left Recursion Elimination, Program to eliminate Left Recursion, Elimination of Left Recursion, learn C++ Programs, code hour, C++ programming tutorials, Left Recursion in C.
hlw
ReplyDelete