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

编译原理实验报告

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

实验内容：

1.求出每个非终结符的FIRST集合 2.求出每个产生式右部的FIRST集合 3.求出每个非终结符的Follow集合 实验环境：

Visual Studio2010 实验目的:

让同学们掌握FIRST集合和FOLLOW集合的求法

实验代码：

#include #include #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

//求出含有的非终结符的个数,并把各终结符保存起来 for(i=0;i

{ 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

} } } for(j=0;j

len=strlen(a[i]); for(j=3;j'Z')) { flag2=1; break; } }

if(flag2) { for(k=0;k

continue; }

//如果产生式右边为非终结符看看该终结符能不能推出ε for(j=3;j='A')&&(a[i][j]<='Z')) { for(k=0;k

if(a[i][3]=='\\0') { ch=a[i][0]; for(j=0;j

}

}

}

c--; j--; } else { c--; j--; } } } i--; for(k=0;k

if(flag2) { for(k=0;k

//求每个非终结符的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

c=count; while(1) { fchange=0; for(i=0;i

c--; i--; continue; }

len=strlen(a[i]);

//产生式右边符号为终结符时,将该终结符并入到左部的First集合中 for(j=3;j'Z')) { for(k=0;k='A')&&(a[i][j]<='Z'))

{ /*将该非终结符的FIRST集合除去ε并入到当前 非终结符的FIRST集合中*/ for(k=0;k

if(!fchange) { for(i=0;i

{ if(l[i].flag) { l[i].first[l[i].s]='@'; l[i].s++; l[i].first[l[i].s]='\\0'; } printf(\ %s\\n\ } printf(\ 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

for(i=0;i

{

len=strlen(r[i].a); for(j=0;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

r[i].first[r[i].s]='\\0'; } continue; } else break; } } }

for(i=0;i

printf(\}

//求每个非终极符的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='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='A')&&(a[i][j]<='Z')) { //判断该非终结符的前一位是否为非终结符,是的话, //将其First集合去ε后并到其前一位非终结符的Follow集合中 if((a[i][j-1]>='A')&&(a[i][j-1]<='Z')) { for(k=0;k

//将该产生式左部非终结符的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

break; } } break; } } } else break; } flag=0; } } //如果当前位为终结符，判断其前一位是否为非终结符 //是的话,将该终结符并到该非终结符的Follow集合中 else { if((a[i][j-1]>='A')&&(a[i][j-1]<='Z')) { for(k=0;k

if(!fchange) { for(i=0;i

} } }

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

本文来源：https://www.bwwdw.com/article/jvz6.html