《编译原理试验报告记录FIRST集和FOLLOW集.docx》由会员分享，可在线阅读，更多相关《编译原理试验报告记录FIRST集和FOLLOW集.docx（13页珍藏版）》请在三一文库上搜索。
1、编译原理实验报告记录FIRST集和 FOLLOW作者:日期:编译原理实验报告实验名称计算first集合和follow集合实验时间院系 计算机科学与技术班级 软件工程1班学号 姓名 131 .实验目的输入：任意的上下文无关文法。输出：所输入的上下文无关文法一切非终结符的first集合和follow集合2 .实验原理设文法GS= (Vn, Vt, P, S),*则首字符集为:FIRST ( a ) = a | a a B , a C Vt, a , B C V *。 *若 a £, FIRST ( a )。由定义可以看出，FIRST (a)是指符号用a能够推导出的所有符号用中处 于申首的
2、终结符号组成的集合。所以 FIRST集也称为首符号集。设a = X1X2Xn, FIRST (a)可按下列方法求得：令 FIRST ( a )=，i=1;(1) 若 XiC Vt,则 Xi e FIRST (a);(2) 若 Xi C Vn;若 £ FIRST (Xi),则 FIRST (xi) FIRST (a);若氏 FIRST (Xi),则 FIRST (xi) - FIRST ( a );(3) i = i+1 ,重复(1)、(2),直到 XiCVT, (i = 2, 3,，n)或 xi CVn 且若 & FIRST (xi)或 i>n 为止。当一个文法中存在e
3、产生式时，例如，存在 A- e,只有知道哪些符号可以 合法地出现在非终结符 A之后，才能知道是否选择A-e产生式。这些合法地出 现在非终结符A之后的符号组成的集合被称为 FOLLOW集合。下面我们给出文 法的FOLLOW集的定义。设文法 GS= (Vn, Vt, P, S),则FOLLOW (A) =a | S Aa ，a Vt 0若 S - A, #C FOLLOW (A)。由定义可以看出，FOLLOW (A)是指在文法GS的所有句型中，紧跟在非 终结符A后的终结符号的集合。FOLLOW集可按下列方法求得：(1) 对于文法GS的开始符号S,有# FOLLOW (S);(2) 若文法GS中有形
4、如B-xAy的规则，其中x, yC V ,则FIRST(y) e FOLLOW (A);(3) 若文法GS中有形如B-xA的规则，或形如B-xAy的规则且£ FIRST (y),其中 x, y V *,贝 U FOLLOW (B) FOLLOW (A);3 .实验内容计算first集合和follow集合4 .实验心得通过上机实验我对文法符号的FIRST集和FOLLOW集有了更深刻的理解,已经熟练的掌握了求解的思想和方法，同时也锻炼了自己的动手解决问题的能 力，对编程能力也有所提高。5 .实验代码与结果#include<iostream>#include<string
5、>#include<algorithm>using 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 STRstring left;string right;求VN和VTvoid VNVT(ST
6、R *p)int i,j;for(i=0;i<N;i+)for(j=0;j<(int)pi.left.length();j+)if(pi.leftj>='A'&&pi.leftj<='Z')if(Vn.find(pi.leftj)>100)Vn+=pi.leftj;elseif(Vt.find(pi.leftj)>100)Vt +=pi.leftj;for(j=0;卜(int)pi.right.length();j+)if(!(pi.rightj>='A'&&pi.righ
7、tj<=Z)if(Vt.find(pi.rightj)>100)Vt +=pi.rightj;elseif(Vn.find(pi.rightj)>100)Vn+=pi.rightj;void getlr(STR *p,int i)int j；for(j=0;j<strings.length();j+)if(stringsj='-'&&stringsj+1='>')pi.left=strings.substr(0,j);pi.right=strings.substr(j+2,strings.length()-j);/对
8、每个文法符号求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;i<N;i+)if(pi.left0=ch)if(!(Vt.find(pi.right0)>100)if(FirstVn.find(ch).find(pi.right0)>100)FirstVn.find(ch)+=pi.right0;
9、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_i<ff.length();i_i+)if( FirstVn.find(ch).find(ffi_i)>100)FirstVn.find(ch)+=ffi_i;elsefo
10、r(int j=0;j<pi.right.length();j+)string TT;TT=Letter_First(p,pi.rightj);if(!(TT.find('*')>100)&&O+1)<pi.right.length() sort(TT.begin(),TT.end(); string tt;for(int t=1;t<TT.length();t+) tt+=TTt; TT=tt; tt=""for(t=0;t<TT.length();t+) if( FirstVn.find(ch).find(T
11、Tt)>100) FirstVn.find(ch)+=TTt; else for(t=0;t<TT.length();t+) if( FirstVn.find(ch).find(TTt)>100) 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
12、(ch);for(int i=0;i<N;i+)for(int j=0;j<pi.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;k<gg.length();k+)if(FollowVn.find(ch).find(ggk)>100)FollowVn.find(ch)+=ggk;elsestring FF;for(int jj=j+1;jj<pi.r
13、ight.length();jj+) string TT;TT=Letter_First(p,pi.right皿);if(!(TT.find('*')>100)&&Oj+1)<pi.right.length() sort(TT.begin(),TT.end();string tt;for(int t=1;t<TT.length();t+)tt+=TTt;TT=tt;tt=""for(t=0;t<TT.length();t+)if( FF.find(TTt)>100&&TTt!='*'
14、;)FF+=TTt;elsefor(t=0;t<TT.length();t+)if( FF.find(TTt)>100)FF+=TTt;break;if(FF.find('*')>100)for(k=0;k<FF.length();k+)if(FollowVn.find(ch).find(FFk)>100)FollowVn.find(ch)+=FFk;elsefor(k=0;k<FF.length();k+)if(FollowVn.find(ch).find(FFk)>100)&&FFk!='*')Fol
15、lowVn.find(ch)+=FFk;string dd;dd=Letter_Follow(p,pi.left0);NONEVn.find(pi.left0)=0;for(k=0;k<dd.length();k+)if(FollowVn.find(ch).find(ddk)>100)FollowVn.find(ch)+=ddk;)return FollowVn.find(ch);)void result()(cout<<"n该文法不是LL(1)型文法"<<endl;) /主函数 int main()(int i,j,k;cout<
16、<"请输入产生式总数："；cin>>N;cout<<"n请输入各产生式(*代表空)："<<endl;STR *p=new STRMAXS;for(i=0;i<N;i+) (cin>>strings;getlr(p,i);)VNVT(p);cout<<endl;cout<<"n="<<endl; cout<<"非终结符"<<"t"<<"FIRST"
17、<<"tt"<<"FOLLOW"<<endl;for(i=0;i<Vn.length();i+) (cout<<" "<<Vni<<"t't”;string pp;pp=Letter_First(p,Vni);for(j=0;j+1<pp.length();j+) cout<<ppj<<",")cout<<pppp.length()-1<<""Fo
18、llow0+='#'cout<<" "string ppp;ppp=Letter_Follow(p,Vni);for(k=0;k+1<ppp.length();k+)cout<<pppk<<","cout<<pppppp.length()-1<<""<<endl;result();cout<<"n="<<endl;return 0;青输入各产生式（可弋表空）二:-ynB：->bC i->« I一!->b>->aS非终结符FIRSTFOLLOV8ABEQG£bnd心)D<#7该文法不是皿型文法