《编译原理实验报告first集和follow集》由会员分享，可在线阅读，更多相关《编译原理实验报告first集和follow集（10页珍藏版）》请在金锄头文库上搜索。
1、编译原理实验报告编译原理实验报告 实验名称实验名称 计算计算 first 集合和集合和 follow 集合集合 实验时间实验时间 院系院系 计算机科学与技术计算机科学与技术 班级班级 软件工程软件工程 1 班班 学号学号 姓名姓名 1. 实验目的实验目的 输入：任意的上下文无关文法。 输出：所输入的上下文无关文法一切非终结符的 first 集合和 follow 集合。 2. 实验原理实验原理 设文法 GS（VN，VT，P，S） ，则首字符集为： FIRST（）a | a，aVT，,V *。 * 若 ，FIRST（） 。 * 由定义可以看出，FIRST（）是指符号串 能够推导出的所有符号串中 处
2、于串首的终结符号组成的集合。所以 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
3、 产生式。这些合法地 出现在非终结符 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）若文法
4、GS中有形如 BxA 的规则，或形如 BxAy 的规则且 FIRST（y） ，其中 x，yV *，则 FOLLOW（B）FOLLOW（A） ； 3.实验内容实验内容 计算 first 集合和 follow 集合 4.实验心得实验心得 通过上机实验我对文法符号的 FIRST 集和 FOLLOW 集有了更深刻的理解， 已经熟练的掌握了求解的思想和方法，同时也锻炼了自己的动手解决问题的能 力，对编程能力也有所提高。 5.实验代码与结果实验代码与结果 #include #include #include using namespace std; #define MAXS 50 int NONEMAXS
5、=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 和 VT void VNVT(STR *p) int i,j; for(i=0;i=A else if(Vt.find(pi.left
6、j)100) Vt +=pi.leftj; for(j=0;j=A 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)=
7、“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
8、); for(int i_i=0;i_i100) FirstVn.find(ch)+=ffi_i; else for(int j=0;j100) 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); fo
9、r(int i=0;i100) FollowVn.find(ch)+=ggk; else string FF; for(int jj=j+1;jj100) 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) string dd; dd=Letter_Follow(p,pi.left0); NONEVn.find(pi.left0)=0; for(k=0;k100) FollowVn.find(ch)+=ddk; return F
10、ollowVn.find(ch); void result() coutN; coutstrings; getlr(p,i); VNVT(p); coutendl; cout“n=“endl; cout“非终结符“t“FIRST“tt“FOLLOW“endl; for(i=0;iVn.length();i+) cout“ “Vni“tt“; 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()-1“endl; result(); cout“n=“endl; return 0;
