编译原理实验报告记录FIRST集和FOLLOW集————————————————————————————————作者：————————————————————————————————日期：编译原理实验报告实验名称计算first集合和follow集合实验时间院系计算机科学与技术班级软件工程1班学号姓名输入：任意的上下文无关文法。

输出：所输入的上下文无关文法一切非终结符的first 集合和follow 集合。

2. 实验原理设文法G[S]＝（V N ，V T ，P ，S ），则首字符集为： FIRST （α）＝{a | α⇒*a β，a ∈V T ，α,β∈V *}。

若α⇒*ε，ε∈FIRST （α）。

由定义可以看出，FIRST （α）是指符号串α能够推导出的所有符号串中处于串首的终结符号组成的集合。

所以FIRST 集也称为首符号集。

设α＝x 1x 2…x n ，FIRST （α）可按下列方法求得：令FIRST （α）＝Φ，i ＝1；（1） 若x i ∈V T ，则x i ∈FIRST （α）；（2） 若x i ∈V N ；① 若ε∉FIRST （x i ），则FIRST （x i ）∈FIRST （α）；② 若ε∈FIRST （x i ），则FIRST （x i ）－{ε}∈FIRST （α）；（3） i ＝i+1，重复（1）、（2），直到x i ∈V T ，（i ＝2，3，…，n ）或x i∈V N 且若ε∉FIRST （x i ）或i>n 为止。

当一个文法中存在ε产生式时，例如，存在A →ε，只有知道哪些符号可以合法地出现在非终结符A 之后，才能知道是否选择A →ε产生式。

这些合法地出现在非终结符A 之后的符号组成的集合被称为FOLLOW 集合。

下面我们给出文法的FOLLOW 集的定义。

设文法G[S]＝（V N ，V T ，P ，S ），则FOLLOW （A ）＝{a | S ⇒… Aa …，a ∈V T }。

若S ⇒*…A ，#∈FOLLOW （A ）。

由定义可以看出，FOLLOW （A ）是指在文法G[S]的所有句型中，紧跟在非终结符A 后的终结符号的集合。

FOLLOW 集可按下列方法求得：（1） 对于文法G[S]的开始符号S ，有#∈FOLLOW （S ）；（2） 若文法G[S]中有形如B →xAy 的规则，其中x ，y ∈V *，则FIRST（y ）－{ε}∈FOLLOW （A ）；（3） 若文法G[S]中有形如B →xA 的规则，或形如B →xAy 的规则且ε∈FIRST （y ），其中x ，y ∈V *，则FOLLOW （B ）∈FOLLOW （A ）；计算first集合和follow集合4.实验心得通过上机实验我对文法符号的FIRST集和FOLLOW集有了更深刻的理解，已经熟练的掌握了求解的思想和方法，同时也锻炼了自己的动手解决问题的能力，对编程能力也有所提高。

5.实验代码与结果#include<iostream>#include<string>#include<algorithm>using namespace std;#define MAXS 50int NONE[MAXS]={0};string strings;//产生式string Vn;//非终结符string Vt;//终结符string first[MAXS];// 用于存放每个终结符的first集string First[MAXS];// 用于存放每个非终结符的first集string Follow[MAXS]; // 用于存放每个非终结符的follow集int N;//产生式个数struct STR{string left;string right;};//求VN和VTvoid VNVT(STR *p){int i,j;for(i=0;i<N;i++){for(j=0;j<(int)p[i].left.length();j++){if((p[i].left[j]>='A'&&p[i].left[j]<='Z')){if(Vn.find(p[i].left[j])>100)Vn+=p[i].left[j];}else{if(Vt.find(p[i].left[j])>100)Vt +=p[i].left[j];}}for(j=0;j<(int)p[i].right.length();j++){if(!(p[i].right[j]>='A'&&p[i].right[j]<='Z')){if(Vt.find(p[i].right[j])>100)Vt +=p[i].right[j];}else{if(Vn.find(p[i].right[j])>100)Vn+=p[i].right[j];}}}}void getlr(STR *p,int i){int j;for(j=0;j<strings.length();j++){if(strings[j]=='-'&&strings[j+1]=='>'){p[i].left=strings.substr(0,j);p[i].right=strings.substr(j+2,strings.length()-j);}}}//对每个文法符号求first集string Letter_First(STR *p,char ch){int t;if(!(Vt.find(ch)>100)){first[Vt.find(ch)]="ch";return first[Vt.find(ch)-1];}if(!(Vn.find(ch)>100)){for(int i=0;i<N;i++){if(p[i].left[0]==ch){if(!(Vt.find(p[i].right[0])>100)){if(First[Vn.find(ch)].find(p[i].right[0])>100){First[Vn.find(ch)]+=p[i].right[0];}}if(p[i].right[0]=='*'){if(First[Vn.find(ch)].find('*')>100){First[Vn.find(ch)]+='*';}}if(!(Vn.find(p[i].right[0])>100)){if(p[i].right.length()==1){string ff;ff=Letter_First(p,p[i].right[0]);for(int i_i=0;i_i<ff.length();i_i++){if( First[Vn.find(ch)].find(ff[i_i])>100){First[Vn.find(ch)]+=ff[i_i];}}}else{for(int j=0;j<p[i].right.length();j++){string TT;TT=Letter_First(p,p[i].right[j]);if(!(TT.find('*')>100)&&(j+1)<p[i].right.length()){sort(TT.begin(),TT.end());string tt;for(int t=1;t<TT.length();t++){tt+=TT[t];}TT=tt;tt="";for(t=0;t<TT.length();t++){if( First[Vn.find(ch)].find(TT[t])>100){First[Vn.find(ch)]+=TT[t];}}}else{for(t=0;t<TT.length();t++){if( First[Vn.find(ch)].find(TT[t])>100){First[Vn.find(ch)]+=TT[t];}}break;}}}}}}return First[Vn.find(ch)];}}// 求每个非终结符的Follow集string Letter_Follow(STR *p,char ch){int t,k;NONE[Vn.find(ch)]++;if(NONE[Vn.find(ch)]==2){NONE[Vn.find(ch)]=0;return Follow[Vn.find(ch)];}for(int i=0;i<N;i++){for(int j=0;j<p[i].right.length();j++){if(p[i].right[j]==ch){if(j+1==p[i].right.length()){string gg;gg=Letter_Follow(p,p[i].left[0]);NONE[Vn.find(p[i].left[0])]=0;for(int k=0;k<gg.length();k++){if(Follow[Vn.find(ch)].find(gg[k])>100){Follow[Vn.find(ch)]+=gg[k];}}}else{string FF;for(int jj=j+1;jj<p[i].right.length();jj++){string TT;TT=Letter_First(p,p[i].right[jj]);if(!(TT.find('*')>100)&&(jj+1)<p[i].right.length()){sort(TT.begin(),TT.end());string tt;for(int t=1;t<TT.length();t++){tt+=TT[t];}TT=tt;tt="";for(t=0;t<TT.length();t++){if( FF.find(TT[t])>100&&TT[t]!='*'){FF+=TT[t];}}}else{for(t=0;t<TT.length();t++){if( FF.find(TT[t])>100){FF+=TT[t];}}break;}}if(FF.find('*')>100){for(k=0;k<FF.length();k++){if(Follow[Vn.find(ch)].find(FF[k])>100){Follow[Vn.find(ch)]+=FF[k];}}}else{for(k=0;k<FF.length();k++){if((Follow[Vn.find(ch)].find(FF[k])>100)&&FF[k]!='*'){Follow[Vn.find(ch)]+=FF[k];}}string dd;dd=Letter_Follow(p,p[i].left[0]);NONE[Vn.find(p[i].left[0])]=0;for(k=0;k<dd.length();k++){if(Follow[Vn.find(ch)].find(dd[k])>100){Follow[Vn.find(ch)]+=dd[k];}}}}}}}return Follow[Vn.find(ch)];}void result(){cout<<"\n该文法不是LL(1)型文法"<<endl;}//主函数int main(){int i,j,k;cout<<"请输入产生式总数:";cin>>N;cout<<"\n请输入各产生式（*代表空）:"<<endl;STR *p=new STR[MAXS];for(i=0;i<N;i++){cin>>strings;getlr(p,i);}VNVT(p);cout<<endl;cout<<"\n========================================="<<endl;cout<<"非终结符"<<"\t"<<"FIRST"<<"\t\t"<<"FOLLOW"<<endl;for(i=0;i<Vn.length();i++){cout<<" "<<Vn[i]<<"\t\t{";string pp;pp=Letter_First(p,Vn[i]);for(j=0;j+1<pp.length();j++){cout<<pp[j]<<",";}cout<<pp[pp.length()-1]<<"} ";Follow[0]+='#';cout<<" {";string ppp;ppp=Letter_Follow(p,Vn[i]);for(k=0;k+1<ppp.length();k++){cout<<ppp[k]<<",";}cout<<ppp[ppp.length()-1]<<"}"<<endl;}result();cout<<"\n========================================="<<endl;return 0;}。