【8A版】编译原理实验报告FIRST集和FOLLOW集
编译原理实验报告
实验名称计算first集合和follow集合实验时间
院系计算机科学与技术
班级软件工程1班
学号
姓名
输入：任意的上下文无关文法。
输出：所输入的上下文无关文法一切非终结符的first 集合和follow 集合。
2. 实验原理
设文法G[S]＝（V N ，V T ，P ，S ），则首字符集为： FIRST （α）＝{a|α?*
a β，a ∈V T ，α,β∈V G }。
若α?*
ε，ε∈FIRST （α）。
由定义可以看出，FIRST （α）是指符号串α能够推导出的所有符号串中处于串首的终结符号组成的集合。所以FIRST 集也称为首符号集。
设α＝G 1G 2…G n ，FIRST （α）可按下列方法求得：
令FIRST （α）＝Φ，i ＝1；
（1） 若G i ∈V T ，则G i ∈FIRST （α）；
（2） 若G i ∈V N ；
①若ε?FIRST （G i ），则FIRST （G i ）∈FIRST （α）；
②若ε∈FIRST （G i ），则FIRST （G i ）－{ε}∈FIRST （α）；
（3） i ＝i+1，重复（1）、（2），直到G i ∈V T ，（i ＝2，3，…，n ）或G i
∈V N 且若ε?FIRST （G 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 →GAy 的规则，其中G ，y ∈V G ，则FIRST
（y ）－{ε}∈FOLLOW （A ）；
（3） 若文法G[S]中有形如B →GA 的规则，或形如B →GAy 的规则且ε
∈FIRST （y ），其中G ，y ∈V G ，则FOLLOW （B ）∈FOLLOW （A ）；
计算first集合和follow集合
4.实验心得
通过上机实验我对文法符号的FIRST集和FOLLOW集有了更深刻的理解，已经熟练的掌握了求解的思想和方法，同时也锻炼了自己的动手解决问题的能力，对编程能力也有所提高。
5.实验代码与结果
#include
#include
#include
usingnamespacestd;
#defineMAGS50
intNONE[MAGS]={0};
stringstrings;//产生式
stringVn;//非终结符
stringVt;//终结符
stringfirst[MAGS];//用于存放每个终结符的first集
stringFirst[MAGS];//用于存放每个非终结符的first集
stringFollow[MAGS];//用于存放每个非终结符的follow集
intN;//产生式个数
structSTR
{
stringleft;
stringright;
};
//求VN和VT
voidVNVT(STRGp)
{
inti,j;
for(i=0;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]; } } } } voidgetlr(STRGp,inti) { intj; for(j=0;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集 stringLetter_First(STRGp,charch) { intt; if(!(Vt.find(ch)>100)) { first[Vt.find(ch)]="ch"; returnfirst[Vt.find(ch)-1]; } if(!(Vn.find(ch)>100)) { for(inti=0;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]=='G') { if(First[Vn.find(ch)].find('G')>100) { First[Vn.find(ch)]+='G'; } } if(!(Vn.find(p[i].right[0])>100)) { if(p[i].right.length()==1) { stringff; ff=Letter_First(p,p[i].right[0]); for(inti_i=0;i_i { if(First[Vn.find(ch)].find(ff[i_i])>100) { First[Vn.find(ch)]+=ff[i_i]; } } } else { for(intj=0;j { stringTT; TT=Letter_First(p,p[i].right[j]); if(!(TT.find('G')>100)&&(j+1) sort(TT.begin(),TT.end()); stringtt; for(intt=1;t { tt+=TT[t]; } TT=tt; tt=""; for(t=0;t { if(First[Vn.find(ch)].find(TT[t])>100) { First[Vn.find(ch)]+=TT[t]; } } } else { for(t=0;t { if(First[Vn.find(ch)].find(TT[t])>100) { First[Vn.find(ch)]+=TT[t]; } } break; } } } } } } returnFirst[Vn.find(ch)]; } } //求每个非终结符的Follow集 stringLetter_Follow(STRGp,charch) { intt,k; NONE[Vn.find(ch)]++; if(NONE[Vn.find(ch)]==2) { NONE[Vn.find(ch)]=0; returnFollow[Vn.find(ch)]; } for(inti=0;i { for(intj=0;j { if(p[i].right[j]==ch) { if(j+1==p[i].right.length()) { stringgg; gg=Letter_Follow(p,p[i].left[0]); NONE[Vn.find(p[i].left[0])]=0; for(intk=0;k { if(Follow[Vn.find(ch)].find(gg[k])>100) { Follow[Vn.find(ch)]+=gg[k]; } } } else { stringFF; for(intjj=j+1;jj { stringTT; TT=Letter_First(p,p[i].right[jj]); if(!(TT.find('G')>100)&&(jj+1) sort(TT.begin(),TT.end()); stringtt; for(intt=1;t { tt+=TT[t]; } TT=tt; tt=""; for(t=0;t { if(FF.find(TT[t])>100&&TT[t]!='G') { FF+=TT[t]; } } } else { for(t=0;t { if(FF.find(TT[t])>100) { FF+=TT[t]; } } break; } } if(FF.find('G')>100) { for(k=0;k { if(Follow[Vn.find(ch)].find(FF[k])>100) { Follow[Vn.find(ch)]+=FF[k]; } } } else { for(k=0;k { if((Follow[Vn.find(ch)].find(FF[k])>100)&&FF[k]!='G') { Follow[Vn.find(ch)]+=FF[k]; } } stringdd; dd=Letter_Follow(p,p[i].left[0]); NONE[Vn.find(p[i].left[0])]=0; for(k=0;k { if(Follow[Vn.find(ch)].find(dd[k])>100) { Follow[Vn.find(ch)]+=dd[k]; } } } } } } } returnFollow[Vn.find(ch)]; } voidresult() { cout<<"\n该文法不是LL(1)型文法"< } //主函数 intmain() { inti,j,k; cout<<"请输入产生式总数:"; cin>>N; cout<<"\n请输入各产生式（G代表空）:"< STRGp=newSTR[MAGS]; for(i=0;i { cin>>strings; getlr(p,i); } VNVT(p); cout< cout<<"\n========================================="< cout<<"非终结符"<<"\t"<<"FIRST"<<"\t\t"<<"FOLLOW"< for(i=0;i { cout<<""< stringpp; pp=Letter_First(p,Vn[i]); for(j=0;j+1 { cout< } cout< Follow[0]+='#'; cout<<" {"; stringppp; ppp=Letter_Follow(p,Vn[i]); for(k=0;k+1 { cout< } cout< } result(); cout<<"\n========================================="< return0; }