消除文法的左递归

编译原理实验

实验名称：消除文法左递归 姓名：

学号：

教师签字：

成绩：

消除文法的左递归

实验目的：

实现消除左递归

实验要求：

输入任意的上下文无关文法, 输出消除了左递归的等价文法。

实验原理：

1. 非终结符的排列为A1，A2……An

2. For(i=1;i

For(j=1;j

If(Ai→Aj&& A →B1|B2|…|Bn) 替换为Ai=B1r|B2r|…|Bnr；

3. 消除Ai 的左递归

4. 消除无用产生式

消除直接左递归的方法是：将左递归改为右递归。

消除简介左递归的方法是：先通过产生式非终结符置换，将间接左递归变为直接左

递归，然后消除直接左递归。

实验代码:

#include

#include

using namespace std;

//*******************************

structwenfa //结构体定义

{

string left; //产生式左部

string right; //产生式右部

};

//************************************

void change(wenfa *p,char *q,intn,int count) //消除左递归

{

int count1=n;

int flag=0;

for(int i=0;i

if(p[i].left[0]==q[0])

if(p[i].left[0]==p[i].right[0])

flag++;

if(flag!=0)

{

for(int i=0;i

if(p[i].left[0]==q[0])

if(p[i].left[0]==p[i].right[0])

{

stringstr;

str=p[i].right.substr(1,int (p[i].right.length()));

string temp=p[i].left;

string temp1="'";

p[i].left=temp+temp1;

p[i].right=str+p[i].left;

}

else

{

string temp=p[i].left;

string temp1="'";

temp=temp+temp1;

p[i].right=p[i].right+temp;

}

string str="'";

p[count1].left=p[0].left[0]+str;

p[count1].right="#";

}

for( i=0;i

{

for(int j=0;j

{

for(int g=0;g

if(q[i]==p[g].left[0])

if(p[g].right[0]==q[j])

{

for(int h=0;h

if(p[h].left[0]==q[j]&&int (p[h].left.length())==1)

{

stringstr;

str=p[g].right.substr(1,int (p[g].right.length()));

p[++count1].left=p[g].left;

p[count1].right=p[h].right+str;

}

p[g].left="";

p[g].right="";

}

}

}

for( i=0;i

{

flag=0;

for(int j=0;j

if(p[j].left[0]==q[i])

if(p[j].left[0]==p[j].right[0])

flag++;

if(flag!=0)

{

for(int j=0;j

if(p[j].left[0]==q[i])

if(p[j].left[0]==p[j].right[0])

{

stringstr;

str=p[j].right.substr(1,int (p[j].right.length()));

string temp=p[j].left;

string temp1="'";

p[j].left=temp+temp1;

p[j].right=str+p[j].left;

}

else

{

string temp=p[j].left;

string temp1="'";

temp=temp+temp1;

p[j].right=p[j].right+temp;

}

string str="'";

p[++count1].left=q[i]+str;

p[count1].right="#";

}

}

}

//******************************************************

int Delete(wenfa *p,int n)

{

return 0;

}

//*********************************************************************** int main()

{

cout

*********************"

inti,j,flag=0,count=1,n;

cout

wenfa *p=new wenfa[60];

cout

for(i=0;i

cin>>p[i].left;

cout";

cin>>p[i].right;

cout

}

cout

cout

for(i=0;i

cout

cout"

}

cout

char q[20];

q[0]=p[0].left[0];

for(i=1;i

{

flag=0;

for(j=0;j

if(p[i].left==p[j].left)

flag++;

if(flag==0)

q[count++]=p[i].left[0];

}

count--;

change(p,q,n,count);

Delete(p,n);

cout

for(i=0;i

{

for(int j=0;j

if( (p[j].left[0]==q[i]) &&int (p[j].left.length())==1 ) cout"

else continue;

for( j=0;j

if( (p[j].left[0]==q[i]) &&int (p[j].left.length())==2 ) cout"

else continue;

return 0; }

实验截图：