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

编译原理实验报告实验名称 计算first集合和follow集合 实验时间 院系 计算机科学与技术 班级 软件工程1班 学号 姓名 1. 实验目的输入：任意的上下文无关文法。输出：所输入的上下文无关文法一切非终结符的first集合和follow集合。2. 实验原理设文法GS（VN，VT，P，S），则首字符集为： FIRST（）a | a，aVT，,V *。若，FIRST（）。由定义可以看出，FIRST（）是指符号串能够推导出的所有符号串中处于串首的终结符号组成的集合。所以FIRST集也称为首符号集。设x1x2xn，FIRST（）可按下列方法求得：令FIRST（），i1；（1） 若xiVT，则xiFIRST（）；（2） 若xiVN； 若FIRST（xi），则FIRST（xi）FIRST（）； 若FIRST（xi），则FIRST（xi）FIRST（）；（3） ii+1，重复（1）、（2），直到xiVT，（i2，3，n）或xiVN且若FIRST（xi）或in为止。当一个文法中存在产生式时，例如，存在A，只有知道哪些符号可以合法地出现在非终结符A之后，才能知道是否选择A产生式。这些合法地出现在非终结符A之后的符号组成的集合被称为FOLLOW集合。下面我们给出文法的FOLLOW集的定义。设文法GS（VN，VT，P，S），则 FOLLOW（A）a | S Aa ，aVT。若SA，#FOLLOW（A）。由定义可以看出，FOLLOW（A）是指在文法GS的所有句型中，紧跟在非终结符A后的终结符号的集合。FOLLOW集可按下列方法求得：（1） 对于文法GS的开始符号S，有#FOLLOW（S）；（2） 若文法GS中有形如BxAy的规则，其中x，yV *，则FIRST（y）FOLLOW（A）；（3） 若文法GS中有形如BxA的规则，或形如BxAy的规则且FIRST（y），其中x，yV *，则FOLLOW（B）FOLLOW（A）；3.实验内容计算first集合和follow集合4.实验心得通过上机实验我对文法符号的FIRST集和FOLLOW集有了更深刻的理解，已经熟练的掌握了求解的思想和方法，同时也锻炼了自己的动手解决问题的能力，对编程能力也有所提高。5.实验代码与结果#include#include#includeusing namespace std;#define MAXS 50int NONEMAXS=0;string strings;/产生式string Vn;/非终结符string Vt;/终结符string firstMAXS;/ 用于存放每个终结符的first集string FirstMAXS;/ 用于存放每个非终结符的first集string FollowMAXS; / 用于存放每个非终结符的follow集int N;/产生式个数struct STR string left; string right; ; /求VN和VTvoid VNVT(STR *p) int i,j; for(i=0;iN;i+) for(j=0;j=A&pi.leftj100) Vn+=pi.leftj; else if(Vt.find(pi.leftj)100) Vt +=pi.leftj; for(j=0;j=A&pi.rightj100) Vt +=pi.rightj; else if(Vn.find(pi.rightj)100) Vn+=pi.rightj; void getlr(STR *p,int i) int j; for(j=0;j) pi.left=strings.substr(0,j); pi.right=strings.substr(j+2,strings.length()-j); /对每个文法符号求first集string Letter_First(STR *p,char ch)int t;if(!(Vt.find(ch)100)firstVt.find(ch)=ch;return firstVt.find(ch)-1;if(!(Vn.find(ch)100)for(int i=0;i100) if(FirstVn.find(ch).find(pi.right0)100) FirstVn.find(ch)+=pi.right0; if(pi.right0=*) if(FirstVn.find(ch).find(*)100) FirstVn.find(ch)+=*; if(!(Vn.find(pi.right0)100) if(pi.right.length()=1) string ff; ff=Letter_First(p,pi.right0); for(int i_i=0;i_i100) FirstVn.find(ch)+=ffi_i; else for(int j=0;j100)&(j+1)pi.right.length() sort(TT.begin(),TT.end(); string tt; for(int t=1;tTT.length();t+) tt+=TTt; TT=tt; tt=; for(t=0;t100) FirstVn.find(ch)+=TTt; else for(t=0;t100) FirstVn.find(ch)+=TTt; break; return FirstVn.find(ch);/ 求每个非终结符的Follow集string Letter_Follow(STR *p,char ch)int t,k;NONEVn.find(ch)+;if(NONEVn.find(ch)=2)NONEVn.find(ch)=0;return FollowVn.find(ch);for(int i=0;iN;i+)for(int j=0;jpi.right.length();j+)if(pi.rightj=ch)if(j+1=pi.right.length()string gg;gg=Letter_Follow(p,pi.left0);NONEVn.find(pi.left0)=0;for(int k=0;k100)FollowVn.find(ch)+=ggk;else string FF; for(int jj=j+1;jj100)&(jj+1)pi.right.length() sort(TT.begin(),TT.end(); string tt; for(int t=1;tTT.length();t+) tt+=TTt; TT=tt; tt=; for(t=0;t100&TTt!=*) FF+=TTt; else for(t=0;t100) FF+=TTt; break; if(FF.find(*)100) for(k=0;k100) FollowVn.find(ch)+=FFk; else for(k=0;k100)&FFk!=*) FollowVn.find(ch)+=FFk; string dd; dd=Letter_Follow(p,pi.left0); NONEVn.find(pi.left0)=0; for(k=0;k100) FollowVn.find(ch)+=ddk; return FollowVn.find(ch);void result()coutn该文法不是LL(1)型文法endl;/主函数int main()int i,j,k; coutN;coutn请输入各产生式（*代表空）:endl; STR *p=new STRMAXS; for(i=0;istrings; getlr(p,i); VNVT(p);coutendl;coutn=endl;cout非终结符tFIRSTttFOLLOWendl;for(i=0;iVn.length();i+)cout Vnitt;string pp;pp=Letter_First(p,Vni);for(j=0;j+1pp.length();j+)coutppj,;coutpppp.length()-1;Follow0+=#;cout;string ppp;ppp=Letter_Follow(p,Vni);for(k=0;k+1ppp.length();k+)coutpppk,;coutpppppp.length()-1endl;result();coutn=endl;return 0;