安徽工业大学编译原理实验报告.doc

编译原理实验报告

姓名：叶玉虎
班级：计122班
指导老师：王森玉
实验日期：2015/5/11

实验内容：
1.求出每个非终结符的FIRST集合
2.求出每个产生式右部的FIRST集合
3.求出每个非终结符的Follow集合
实验环境：
Visual Studio2010
实验目的:
让同学们掌握FIRST集合和FOLLOW集合的求法
实验代码：
#include<stdio.h>
#include<string.h>
#define MAX 50
char css[MAX][MAX];//保存所有的产生式
int count=0;
int cnt=0;
struct L{//保存所有的终结符
char ch;
int flag;//1:能推出ε,0:不能,初值:-1
int num;
char first[MAX];
int s;//first的长度
char follow[MAX];
int l;//follow的长度
}l[MAX];
//对输入的格式进行控制,并校验输入是否符合格式
int handle(char a[])
{
int len,i=0,j,k;

len=strlen(a);

while(a[i]!=10)
{
if(a[i]=='$')
return 2;
if((' '==a[i])||(9==a[i]))
{
i++;
continue;
}
if((a[i]>='A')&&(a[i]<='Z'))
{
if((a[i+1]!='-')||(a[i+2]!='>'))
{
printf("产生式格式错误\n");
return -1;
}
else
{
j=i;
k=0;
while((a[j]!=' ')&&(a[j]!=9)&&(a[j]!='$')&&(a[j]!=10))
{
if(a[j]=='|')
{
css[count][k]='\0';
count++;
if((a[j+1]==' ')||(a[j]==9)||(a[j]=='$')||(a[j]==10))
{
printf("产生式格式错误\n");
return 0;
}
css[count][0]=a[i];
css[count][1]=a[i+1];
css[count][2]=a[i+2];
k=3;
j++;
continue;
}
css[count][k]=a[j];
k++;
j++;
}
css[count][k]='\0';
i=j;
count++;
}
}
else
{
printf("产生式格式错误\n");
return -1;
}
}
return 0;
}
//从键盘获得输入
int input()
{
char a[MAX*MAX];
int v;
printf("输入产生式,产生式之间以空格回车或Tab键分隔,并以$键结束.\n");
printf("用@表示虚拟符号ε,终结符用大写字母表示,其他字符表示非终结符\n");
while(1)
{
fgets(a,MAX*MAX,stdin);
v=handle(a);
if(v==-1)
return -1;
if(v==2)
return 0;
}
}
//求出能推出ε的非终结符
void seekEmpty()
{
int i,j,k,t;
int flag=0,flag2=0;
int len,c;
char a[MAX][MAX],ch;
for(i=0;i<count;i++)
{
strcpy(a[i],css[i]);
}
//求出含有的非终结符的个数,并把各终结符保存起来
for(i=0;i<count;i++)
{
for(j=0;j<cnt;j++)
{
if(l[j].ch==a[i][0])
{
l[j].num++;
flag=1;
break;
}
else
flag=0;
}
if((!cnt)||(!flag))
{
l[cnt].ch=a[i][0];
l[cnt].flag=-1;
l[cnt].num=1;
l[cnt].s=0;
l[cnt].l=0;
cnt++;
flag=1;
continue;
}
}
c=count;
while(c)
{
for(i=0;i<c;i++)
{
//如果该终结符推出ε，从a[]中删除所有带有该终结符的产生式
if(a[i][3]=='@')
{
ch=a[i][0];
for(j=0;j<c;j++)
{
if(ch==a[j][0])
{
if(j!=c-1)
{
for(k=j;k<c-1;k++)
strcpy(a[k],a[k+1]);
c--;
j--;
}
else
{
c--;
j--;
}
}
}
for(j=0;j<cnt;j++)
{
if(ch==l[j].ch)
{
l[j].flag=1;
break;
}
}
i--;
continue;
}
len=strlen(a[i]);
for(j=3;j<len;j++)
{
//当该产生式右边含有非终结符时从a[]中删除该条记录
if((a[i][j]<'A')||(a[i][j]>'Z'))
{
flag2=1;
break;
}
}
if(flag2)
{
for(k=0;k<cnt;k++)
{
if(a[i][0]==l[k].ch)
{
l[k].num--;
if(l[k].num==0)
l[k].flag=0;
break;
}
}
if(i!=c-1)
for(k=i;k<c-1;k++)
{
strcpy(a[k],a[k+1]);
}
c--;
i--;
flag2=0;
continue;
}

//如果产生式右边为非终结符看看该终结符能不能推出ε
for(j=3;j<len;j++)
{
if((a[i][j]>='A')&&(a[i][j]<='Z'))
{
for(k=0;k<cnt;k++)
{
if(a[i][j]==l[k].ch)
{
if(l[k].flag==0)
{
flag2=1;
break;
}
else if(l[k].flag==1)
{
for(t=j;t<len-1;t++)
a[i][t]=a[i][t+1];
a[i][len-1]='\0';
j--;
len--;
break;
}
break;
}
}
if(flag2)
break;
}
}
if(a[i][3]=='\0')
{
ch=a[i][0];
for(j=0;j<c;j++)
{
if(ch==a[j][0])
{
if(j!=c-1)
{
for(k=j;k<c-1;k++)
strcpy(a[k],a[k+1]);
c--;
j--;
}
else
{
c--;
j--;
}
}
}
i--;
for(k=0;k<cnt;k++)
{
if(ch==l[k].ch)
{
l[k].flag=1;
break;
}
}
}
if(flag2)
{
for(k=0;k<cnt;k++)
{
if(a[i][0]==l[k].ch)
{
l[k].num--;
if(l[k].num==0)
l[k].flag=0;
}
}
if(i!=c-1)
for(k=i;k<c-1;k++)
{
strcpy(a[k],a[k+1]);
}
c--;
i--;
flag2=0;
continue;
}
}
}
}
//求每个非终结符的First集合
void seekFirstVn()
{
int i,j,k,t,t1,t2,c,item;
int len,s,flag=0,flag2=0,fchange;
char a[MAX][MAX],ch[MAX];
for(i=0;i<count;i++)
{
strcpy(a[i],css[i]);
}
c=count;
while(1)
{
fchange=0;
for(i=0;i<c;i++)
{
//右部为ε,将ε并入到左部的First中
if(a[i][3]=='@')
{
/*for(j=0;j<cnt;j++)
{
if(l[j].ch==a[i][0])
{
for(k=0;k<l[j].s;k++)
if(l[j].first[k]==a[i][3])
{
flag=1;
break;
}
if(!flag)
{
l[j].first[l[j].s]=a[i][3];
l[j].s++;
l[j].first[l[j].s]='\0';
fchange=1;
break;
}
flag=0;
}
}*/
//从当前列表a[]中删除
if(i!=c-1)
for(j=i;j<c-1;j++)
strcpy(a[j],a[j+1]);

c--;
i--;
continue;
}
len=strlen(a[i]);
//产生式右边符号为终结符时,将该终结符并入到左部的First集合中
for(j=3;j<len;j++)
{
if((a[i][j]<'A')||(a[i][j]>'Z'))
{
for(k=0;k<cnt;k++)
{
if(a[i][0]==l[k].ch)
{
for(t=0;t<l[k].s;t++)
{
if(a[i][j]==l[k].first[t])
{
flag=1;
break;
}
}
if(!flag)
{
l[k].first[l[k].s]=a[i][j];
l[k].s++;
l[k].first[l[k].s]='\0';
fchange=1;
}
flag=0;
break;
}
}
//从a[][]中删除该条产生式
if(i!=c-1)
for(k=i;k<c-1;k++)
strcpy(a[k],a[k+1]);
c--;
i--;
break;
}
//产生式右边符号为非终结符时
else if((a[i][j]>='A')&&(a[i][j]<='Z'))
{
/*将该非终结符的FIRST集合除去ε并入到当前
非终结符的FIRST集合中*/
for(k=0;k<cnt;k++)
{
if(a[i][j]==l[k].ch)
{
for(t=0;t<cnt;t++)
{
if(a[i][0]==l[t].ch)
{
for(t1=0;t1<l[k].s;t1++)
{
for(t2=0;t2<l[t].s;t2++)
{
if(l[k].first[t1]==l[t].first[t2])
{
break;
}
}
if((t2==l[t].s)&&(l[k].first[t1])!='@')
{
fchange=1;
l[t].first[l[t].s]=l[k].first[t1];
l[t].s++;
l[t].first[l[t].s]='\0';
}
}
break;
}
}
break;
}
}
if(l[k].flag)
continue;
else
break;
}
}
}
if(!fchange)
{
for(i=0;i<cnt;i++)
{
if(l[i].flag)
{
l[i].first[l[i].s]='@';
l[i].s++;
l[i].first[l[i].s]='\0';
}
printf("FIRST(%c): %s\n",l[i].ch,l[i].first);
}
printf("\n");
break;
}
}
}
//求产生式右部的First集合
void seekFirstRight()
{
struct Right{
char a[MAX];
char first[MAX];
int s;
}r[MAX];
int i,j,k,t;
int cnt=0,len,len1,flag=0;
for(i=0;i<count;i++)
{
for(j=0;j<cnt;j++)
{
if(!strcmp(css[i]+3,r[j].a))
{
flag=1;
break;
}
}
if(flag)
{
flag=0;
continue;
}
strcpy(r[j].a,css[i]+3);
r[j].s=0;
cnt++;
}
for(i=0;i<cnt;i++)
{
len=strlen(r[i].a);
for(j=0;j<len;j++)
{
//遇到终结符
if(r[i].a[j]=='@')
{
r[i].first[r[i].s]='@';
r[i].s++;
r[i].first[r[i].s]='\0';
break;
}
else if((r[i].a[j]<'A')||(r[i].a[j]>'Z'))
{
r[i].first[r[i].s]=r[i].a[j];
r[i].s++;
r[i].first[r[i].s]='\0';
break;
}
else
{
for(k=0;k<cnt;k++)
{
if(r[i].a[j]==l[k].ch)
{
len1=strlen(l[k].first);
for(t=0;t<len1;t++)
{
if(l[k].first[t]!='@')
{
r[i].first[r[i].s]=l[k].first[t];
r[i].s++;
r[i].first[r[i].s]='\0';
}
}
break;
}
}
if(l[k].flag)
{
if(j==len-1)
{
r[i].first[r[i].s]='@';
r[i].s++;
r[i].first[r[i].s]='\0';
}
continue;
}
else
break;
}
}
}
for(i=0;i<cnt;i++)
{
printf("FIRST(%s): %s\n",r[i].a,r[i].first);
}
printf("\n");
}
//求每个非终极符的Follow集合
void seekFollow()
{
int i,j,k,t,t1,t2,t3,c=0;
int flag=0,len;
int fchange;//判断一次循环是否有改动的地方
char a[MAX][MAX],ch[MAX];

for(i=0;i<count;i++)
{
len=strlen(css[i]);
for(j=3;j<len;j++)
{
if((css[i][j]>='A')&&(css[i][j]<='Z'))
{
break;
}
}
if(j!=len)
{
strcpy(a[c],css[i]);
c++;
}
}
l[0].follow[l[0].l]='#';
l[0].l++;
l[0].follow[l[0].l]='\0';

while(1)
{
fchange=0;
for(i=0;i<c;i++)
{
len=strlen(a[i]);
for(j=3;j<len;j++)
{
if((a[i][j]>='A')&&(a[i][j]<='Z'))
{
//判断该非终结符的前一位是否为非终结符,是的话,
//将其First集合去ε后并到其前一位非终结符的Follow集合中
if((a[i][j-1]>='A')&&(a[i][j-1]<='Z'))
{
for(k=0;k<cnt;k++)
{
if(a[i][j-1]==l[k].ch)
{
for(t=0;t<cnt;t++)
{
if(a[i][j]==l[t].ch)
{
for(t1=0;t1<l[t].s;t1++)
{
if(l[t].first[t1]=='@')
continue;
for(t2=0;t2<l[k].l;t2++)
if(l[t].first[t1]==l[k].follow[t2])
break;
if(t2==l[k].l)
{
fchange=1;
l[k].follow[l[k].l]=l[t].first[t1];
l[k].l++;
l[k].follow[l[k].l]='\0';
}
}
break;
}
}
break;
}
}
}
//如果该非终结符是最后一位,
//将该产生式左部非终结符的Follow集合
//加入到当前非终结符的Follow集合中.
//然后从当前终结符开始向右判断是否为非终结符，是的话,进行相应处理
//循环直到当前非终结符推不出ε或当前为终结符时退出
if(j==len-1)
{
t3=j;
strcpy(ch,a[i]);
while(!flag)
{
if((ch[t3]>='A')&&(ch[t3]<='Z'))
{
for(k=0;k<cnt;k++)
{
if(ch[0]==l[k].ch)
{
for(t=0;t<cnt;t++)
{
if(ch[t3]==l[t].ch)
{
for(t1=0;t1<l[k].l;t1++)
{
for(t2=0;t2<l[t].l;t2++)
if(l[k].follow[t1]==l[t].follow[t2])
break;
if(t2!=l[t].l)
continue;
else
{
fchange=1;
l[t].follow[l[t].l]=l[k].follow[t1];
l[t].l++;
l[t].follow[l[t].l]='\0';
}
}
if(l[t].flag)
ch[t3--]='\0';
else
{
flag=1;
t3--;
}
break;
}
}
break;
}
}
}
else
break;
}
flag=0;
}
}
//如果当前位为终结符，判断其前一位是否为非终结符
//是的话,将该终结符并到该非终结符的Follow集合中
else
{
if((a[i][j-1]>='A')&&(a[i][j-1]<='Z'))
{
for(k=0;k<cnt;k++)
{
if(a[i][j-1]==l[k].ch)
{
for(t=0;t<l[k].l;t++)
if(a[i][j]==l[k].follow[t])
break;
if(t==l[k].l)
{
fchange=1;
l[k].follow[l[k].l]=a[i][j];
l[k].l++;
l[k].follow[l[k].l]='\0';
}
}
}
}
}
}
}
if(!fchange)
{
for(i=0;i<cnt;i++)
printf("FOLLOW(%c): %s\n",l[i].ch,l[i].follow);
break;
}
}
}
int main()
{
int i;
if(input()==-1)
return -1;
seekEmpty();
seekFirstVn();
seekFirstRight();
seekFollow();
return 0;
}
实验演示：
因为不知道怎么用电脑输出’ε’符号，我在代码里用’@’来表示 ‘ε’.以‘$’来结束输入
测试数据1：
S->MH|a
H->LSo|@
K->dML|@
L->eHf
M->K|bLM

测试数据2：
S->aH
H->aMd|d
M->Ab|@
A->aM|e

实验感想：
经过这几次的实验，不仅让我们更加深刻的知道了first集合和follow集合的计算步骤和方法，还很好的培养了我们动手能力。虽然这两个集合用笔算的方法很简单，但是要让计算机来演算就不是那么容易了，这需要设计合理的数据结构和算法才能正确地求出结果。当然在设计算法的时候难免会出现错误，这就需要我们这些程序员们仔细的去调试，发现错误并改正。本以为这次的实验代码不会很长，但是实际写好了却有好几百行，可能是我的算法不够好吧。总的来讲这次的实验没有遇到太大的问题，因为课上老师很认真的给我们讲解了它们的求法，笔推也做了好几次练习，让我们理清了思路。