编译原理实验报告FIRST集和FOLLOW集

编译原理实验报告实验名称计算first集合和follow集合实验时间院系计算机科学与技术班级软件工程1班学号姓名1.实验目的输入：任意的上下文无关文法。输出：所输入的上下文无关文法一切非终结符的first集合和follow集合。2.实验原理设文法G[S]＝（VN，VT，P，S），则首字符集为：FIRST（α）＝{a|α*aβ，a∈VT，α,β∈V*}。若α*ε，ε∈FIRST（α）。由定义可以看出，FIRST（α）是指符号串α能够推导出的所有符号串中处于串首的终结符号组成的集合。所以FIRST集也称为首符号集。设α＝x1x2…xn，FIRST（α）可按下列方法求得：令FIRST（α）＝Φ，i＝1；（1）若xi∈VT，则xi∈FIRST（α）；（2）若xi∈VN；①若εFIRST（xi），则FIRST（xi）∈FIRST（α）；②若ε∈FIRST（xi），则FIRST（xi）－{ε}∈FIRST（α）；（3）i＝i+1，重复（1）、（2），直到xi∈VT，（i＝2，3，…，n）或xi∈VN且若εFIRST（xi）或in为止。当一个文法中存在ε产生式时，例如，存在A→ε，只有知道哪些符号可以合法地出现在非终结符A之后，才能知道是否选择A→ε产生式。这些合法地出现在非终结符A之后的符号组成的集合被称为FOLLOW集合。下面我们给出文法的FOLLOW集的定义。设文法G[S]＝（VN，VT，P，S），则FOLLOW（A）＝{a|S…Aa…，a∈VT}。若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）；3.实验内容计算first集合和follow集合4.实验心得通过上机实验我对文法符号的FIRST集和FOLLOW集有了更深刻的理解，已经熟练的掌握了求解的思想和方法，同时也锻炼了自己的动手解决问题的能力，对编程能力也有所提高。5.实验代码与结果#includeiostream#includestring#includealgorithmusingnamespacestd;#defineMAXS50intNONE[MAXS]={0};stringstrings;//产生式stringVn;//非终结符stringVt;//终结符stringfirst[MAXS];//用于存放每个终结符的first集stringFirst[MAXS];//用于存放每个非终结符的first集stringFollow[MAXS];//用于存放每个非终结符的follow集intN;//产生式个数structSTR{stringleft;stringright;};//求VN和VTvoidVNVT(STR*p){inti,j;for(i=0;iN;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(STR*p,inti){intj;for(j=0;jstrings.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集stringLetter_First(STR*p,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;iN;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){stringff;ff=Letter_First(p,p[i].right[0]);for(inti_i=0;i_iff.length();i_i++){if(First[Vn.find(ch)].find(ff[i_i])100){First[Vn.find(ch)]+=ff[i_i];}}}else{for(intj=0;jp[i].right.length();j++){stringTT;TT=Letter_First(p,p[i].right[j]);if(!(TT.find('*')100)&&(j+1)p[i].right.length()){sort(TT.begin(),TT.end());stringtt;for(intt=1;tTT.length();t++){tt+=TT[t];}TT=tt;tt=;for(t=0;tTT.length();t++){if(First[Vn.find(ch)].find(TT[t])100){First[Vn.find(ch)]+=TT[t];}}}else{for(t=0;tTT.length();t++){if(First[Vn.find(ch)].find(TT[t])100){First[Vn.find(ch)]+=TT[t];}}break;}}}}}}returnFirst[Vn.find(ch)];}}//求每个非终结符的Follow集stringLetter_Follow(STR*p,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;iN;i++){for(intj=0;jp[i].right.length();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;kgg.length();k++){if(Follow[Vn.find(ch)].find(gg[k])100){Follow[Vn.find(ch)]+=gg[k];}}}else{stringFF;for(intjj=j+1;jjp[i].right.length();jj++){stringTT;TT=Letter_First(p,p[i].right[jj]);if(!(TT.find('*')100)&&(jj+1)p[i].right.length()){sort(TT.begin(),TT.end());stringtt;for(intt=1;tTT.length();t++){tt+=TT[t];}TT=tt;tt=;for(t=0;tTT.length();t++){if(FF.find(TT[t])100&&TT[t]!='*'){FF+=TT[t];}}}else{for(t=0;tTT.length();t++){if(FF.find(TT[t])100){FF+=TT[t];}}break;}}if(FF.find('*')100){for(k=0;kFF.length();k++){if(Follow[Vn.find(ch)].find(FF[k])100){Follow[Vn.find(ch)]+=FF[k];}}}else{for(k=0;kFF.length();k++){if((Follow[Vn.find(ch)].find(FF[k])100)&&FF[k]!='*'){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;kdd.length();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)型文法endl;}//主函数intmain(){inti,j,k;cout请输入产生式总数:;cinN;cout\n请输入各产生式（*代表空）:endl;STR*p=newSTR[MAXS];for(i=0;iN;i++){cinstrings;getlr(p,i);}VNVT(p);coutendl;cout\n=========================================endl;cout非终结符\tFIRST\t\tFOLLOWendl;for(i=0;iVn.length();i++){coutVn[i]\t\t{;stringpp;pp=Letter_First(p,Vn[i]);for(j=0;j+1pp.length();j++){coutpp[j],;}coutpp[pp.length()-1]};Follow[0]+='#';cout{;stringppp;ppp=Letter_Follow(p,Vn[i]);for(k=0;k+1ppp.length();k++){coutppp[k],;}coutppp[ppp.length()-1]}endl;}result();cout\n=========================================endl;return0;}