编译原理实验报告1

1、编译原理实验报告书姓 名班 级计102学 号109074指导教师王森玉安徽工业大学计算机学院2013年5月编译原理实验报告一、 实验内容求解一个文法的first、follow、select集合并判断是不是LL(1)文法。二、 实验目的通过实验熟练掌握first、follow、select集合的求解算法，加深对理论知识的理解。三、 实验环境VC+6.0、C语言。四、 实验原理1.first集的求解：(1)若XVt,则FIRST(X)=X; (2)若XVn,且有产生式X->a,aVt，则aFIRST(X); (3)若XVn,X->,则FIRST(X) (4)若X,Y1,Y2,Y3,Y4

2、Yn都Vn,而产生式X->Y1,Y2Yn.当Y1,Y2,Y3,Y4Yn都能=>那么FIRST(X)=并集的FIRST(Yi)- (0<=i<=n) (5)若Yi=>(i=1,2,3)，则FIRST(X)=并集的FIRST(Yi)- 并上2.follow集的求解:(1)若为文法开始符号S，则FOLLOW(S)=# (2)若为文法A->aBb是一个产生式，则把FIRST（b）的非空元素加入FOLLOW(B)中。如果b->则把FOLLOW(A)也加入FOLLOW(B)中。3.select=(A->a)=(first(a)- )并上follow(A)。五

3、、 设计实现数据结构定义:typedef struct Nodechar nonTerminal;char str10; /用来存放各个产生式右边的字符串int tag; /用来标记是否能推出空char first10; /用来存放非终结符的first集合char firsts10; /用来存放字符串的first集合char follow10; /用来存放各个非终结符的follow集char formFollow10;/用来存放各个非终结符的follow集合的组成部分int fol; /用来标记非终结符是否已经计算过follow集char sellect10;/用来存放sellect集合int

4、 fir; /用来标志非终结符的first集合是否计算过，0表示没有，1表示计算过nonTer,*nonTerminal;typedef struct char Ldata;/int tag1; /用来标记是否能推出空int tag2;/用来标记该产生式是否被删除LeftData;typedef struct nodeLeftData lData;char mData2;char rData10;/产生式右边字符串最大值为10Pro;typedef structPro proNum50; /输入产生式的最大数量 Production;static int num=0; /统计实际输入产生式的数

5、量int sum=1; /统计非终结符的数量函数功能说明：Production init() /初始化产生式Production input() /输入产生式Production copyProduction(Production p) /int isJudLegal(Production p) /判断产生式是否合法int leftRecursive(Production p,nonTer nT20) /判断是否有左递归，有则返回1，否则返回0Production delProduction1(Production p) /删除右部含有小写字母所有产生式Production delProduc

6、tion(Production p,char ch)/删除以ch开头所有产生式Production delProduction2(Production p,char ch)/删除以ch开头一条产生式Production delNonTer(Production p,int position,int n) /删除非终结符int isExist(nonTer nT20)/判断是否有未处理的产生式有则返回1否则返回0void isInferNull(Production p,nonTer nT20) /判断非终结符能否推出空int judgeGrammar(Production p,nonTer n

7、T20) /判断文法是否能计算first集合int isEnd(nonTer nT20) /用来判定每个非终结符的first集是否还可能在增大void initStrings(Production p,nonTer nT20) /将每个产生式右边的字符串存放到str数组中int First(Production p,nonTer nT20) /计算first集void initFollow(nonTer nT20) /初始化follow集合int judgeGrammar1(Production p,nonTer nT20) /判断文法是否能计算follow集合void Follow(Prod

8、uction p,nonTer nT20,char non,int s) /计算某一非终结符的follow集void calFollow(Production p,nonTer nT20) /计算Follow集void showFollow(nonTer nT20) /显示follow集void initSellect(nonTer nT20) /初始化sellect集合void sellect(Production p,nonTer nT20) /计算sellect集部分函数源代码(由于代码比较多，只给出部分)：int isJudLegal(Production p) /判断产生式是否合法i

9、nt mid1,mid2,right=0;int i; int flag=0;mid1=0;mid2=1;right=0;if(num=0)printf("产生式个数为零n");return 0;for(i=0;i<num;i+)if(Numi.lData.Ldata>'Z'|Numi.lData.Ldata<'A')printf("产生式左部应该为非终结符（大写字母）n");return 0;if(Numi.mDatamid1!='-'|Numi.

10、mDatamid2!='>')printf("产生式中间->有误n");return 0;while(Numi.rDataright!='0')if(Numi.rDataright='*')|(Numi.rDataright>='a'&&Numi.rDataright<='z')|(Numi.rDataright>='A'&&(Numi.rDataright&

11、lt;='Z')flag=1;if(flag!=1)printf("产生式右部输入不符合要求！n");return 0;right+;flag=0;right=0;return 1;int leftRecursive(Production p,nonTer nT20) /判断是否有左递归，有则返回1，否则返回0int i,j;char ch1,ch2;for(i=0;i<num;i+)if(Numi.lData.Ldata=Numi.rData0)printf("文法含有直接左递归!n");return 1;fo

12、r(i=0;i<num;i+)ch1=Numi.lData.Ldata;ch2=Numi.rData0;for(j=0;j<num;j+)if(Numj.lData.Ldata=ch2&&Numj.rData0=ch1)printf("文法中含有间接左递归!n");return 1;return 0;int First(Production p,nonTer nT20) /计算first集int i,j=0,right=0,k=1,t,m=0,low,n,a=0,b,f,k1,flag,f1,f2;char

13、 ch; /中间变量，对first集合排序时使用char r10; /临时存放产生式右边非终结符memset(r,'0',sizeof(r);t=0; /用来记录某个产生式右边非终结符的个数low=0; /用来标记某一产生式右边是否是非终结符和终结符的组合for(i=0;i<sum;i+) /初始化FIRST集for(j=0;j<10;j+)nTi.firstj='0'nTi.fir=0;for(i=0;i<sum;i+)k=0;k1=0;right=0;t=0;/memset(r,'0',sizeof(r);for(j=0;j

14、<num;j+)if(nTi.nonTerminal=Numj.lData.Ldata) /步骤二if(Numj.rData0>='a'&&Numj.rData0<='z')nTi.firstk=Numj.rData0;k+;Numj.lData.tag2=0; /表示该产生式被处理过if(Numj.rData0='*') /步骤三nTi.firstk='*'k+;Numj.lData.tag2=0;if(Numj.r

15、Data0>='A'&&Numj.rData0<='Z') /步骤四，五Numj.lData.tag2=2;for(i=0;i<sum;i+) /将计算过first集合的非终结符对应的标志位置1for(j=0;j<num;j+)if(Numj.lData.Ldata=nTi.nonTerminal&&Numj.lData.tag2=2)break;if(j=num)nTi.fir=1;/开始处理右边以大写字母开头的产生式while(isEnd(nT)for(i=0;i

16、<num;i+) f2=1;t=0;right=0;memset(r,'0',sizeof(r);k=0;b=0;low=0;if(Numi.lData.tag2=2)for(j=0;j<sum&&f2;j+)if(Numi.lData.Ldata=nTj.nonTerminal)f2=0;right=0;while(Numi.rDataright!='0')rt=Numi.rDataright; /printf("r%d=%cn",t,rt);t+; right+;f=1;

17、 /用来标记右边字符串能否推出空 for(m=0;m<t;m+)while(nTj.firstk!='0')k+;if(rm>='a'&&rm<='z')/nTj.firstk=rm;/k+;f=0;continue;for(n=0;n<sum;n+)if(rm=nTn.nonTerminal&&nTn.tag=1)b=0; while(nTn.firstb!='0')if(nTn.firstb!='*')nTj.firstk=nTn.firstb;k+;b+

18、;if(nTn.fir=0)low=1;if(rm=nTn.nonTerminal&&nTn.tag=0)a=0;while(nTn.firsta!='0')nTj.firstk=nTn.firsta;k+;a+;f=0;b=0;if(f) nTj.firstk='*'k+;if(!low)nTj.fir=1;for(i=0;i<sum;i+) /对非终结符的first集合从小到大排序j=0;while(nTi.firstj!='0')k=j;a=j;while(nTi.firsta!='0')if(nTi.

19、firsta<nTi.firstk)k=a;a+;if(k!=j)ch=nTi.firstk;nTi.firstk=nTi.firstj; nTi.firstj=ch;j+;/memset(r,'0',sizeof(r);for(i=0;i<sum;i+) /删除first集中重复的元素memset(r,'0',sizeof(r); j=1;b=1;k=0;r0=nTi.first0;while(nTi.firstj!='0')if(rk!=nTi.firstj)k+;rk=nTi.firstj;b+;j+;for(a=0;a<

20、b;a+)nTi.firsta=ra;nTi.firsta='0'for(i=0;i<num;i+) /计算字符串的first集合f1=0;k=0;j=0;f=0;flag=0;if(Numi.rData0>='a'&&Numi.rData0<='z')nTi.firsts0=Numi.rData0;continue;if(Numi.rData0>='A'&&Numi.rData0<='Z')for(k=

21、0;k<sum;k+)if(Numi.rData0=nTk.nonTerminal)if(nTk.tag=0)f=1;a=0;while(nTk.firsta!='0')nTi.firstsa=nTk.firsta;a+;break;if(nTk.tag=1)a=0;while(nTk.firsta!='0')if(nTk.firsta!='*')nTi.firstsj=nTk.firsta;j+;a+;b=1;if(f)continue;while(Numi.rDatab!='0')if(Nu

22、mi.rDatab>='a'&&Numi.rDatab<='z')nTi.firstsj=Numi.rDatab;j+;f1=1;elsefor(k=0;k<sum;k+)a=0;if(nTk.nonTerminal=Numi.rDatab)if(nTk.tag=1)while(nTk.firsta!='0')if(nTk.firsta!='*')nTi.firstsj=nTk.firsta;j+;a+;if(nTk.tag=0)while(nTk.firsta!=&

23、#39;0')nTi.firstsj=nTk.firsta;j+;a+;flag=1;b+;if(!flag&&!f1)nTi.firstsj='*'j+;for(i=0;i<num;i+) /对字符串的first集合从小到大排序j=0;while(nTi.firstsj!='0')k=j;a=j;while(nTi.firstsa!='0')if(nTi.firstsa<nTi.firstsk)k=a;a+;if(k!=j)ch=nTi.firstsk;nTi.firstsk=nTi.firstsj; nTi

24、.firstsj=ch;j+;for(i=0;i<num;i+) /删除firsts集中重复的元素memset(r,'0',sizeof(r); j=1;b=1;k=0;r0=nTi.firsts0;while(nTi.firstsj!='0')if(rk!=nTi.firstsj)k+;rk=nTi.firstsj;b+;j+;for(a=0;a<b;a+)nTi.firstsa=ra;nTi.firstsa='0'for(i=0;i<sum;i+)j=0;printf("非终结符%c的first集为:",

25、nTi.nonTerminal);while(nTi.firstj!='0')printf("%c ",nTi.firstj);j+;printf("n");printf("n");for(i=0;i<num;i+)j=0;printf("字符串%s的first集为:",nTi.str);while(nTi.firstsj!='0')printf("%c ",nTi.firstsj);j+;printf("n");printf("n");return 1;void initFollow(nonTer nT20) /初始化follow集合int i,j;for(i=0;i<sum;i+)for(j=0;j<10;j+)nTi.followj='0'nTi.formFollowj='0&#