《计算first集合和follow集合--编译原理.doc》由会员分享，可在线阅读，更多相关《计算first集合和follow集合--编译原理.doc（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精品文档，仅供学习与交流，如有侵权请联系网站删除计算first集合和follow集合姓名：彦清 学号：E10914127一、实验目的输入：任意的上下文无关文法。输出：所输入的上下文无关文法一切非终结符的first集合和follow集合。二、实验原理设文法GS（VN，VT，P，S），则首字符集为： FIRST（）a | a，aVT，,V *。若，FIRST（）。由定义可以看出，FIRST（）是指符号串能够推导出的所有符号串中处于串首的终结符号组成的集合。所以FIRST集也称为首符号集。设x1x2xn，FIRST（）可按下列方法求得：令FIRST（），i1；（1） 若xiVT，则xiFIRST（）
2、；（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）。由定义可
3、以看出，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）；三、源程序#include#include/产生式struct csschar left;char zhuan;/用“-”表示箭头char right20;/空标志struct kon
4、gint kongzuo;int kongyou;struct biaoji/第三步扫描式子的右部标记号int r100;struct first/初步求first集合时用char fjihe200;struct first2/保存最终的first集合char fjihe2200;struct follow/初步求follow集合时用char fow200;struct follow2/保存最终的follow集合char fow2200;void main()int i,n,k;/产生式条数css shizi100;kong kongshi100;cout请输入产生式的条数n(n100)：n;
5、cout请从开始符输入产生式(空用“#”表示，产生式由字母组成)：endl;for(i=0;ishizii.leftshizii.zhuanshizii.right;int l,m,j,h,g,f;for(l=0;ln;l+)for(m=0;m=a & shizil.rightm=z )kongshil.kongyou=0; break;for(j=0;j=n;j+)for(h=0;hn;h+) if(j=h)break;if(shizij.left=shizih.left)if(kongshij.kongyou=0 & kongshih.kongyou=0)kongshij.kongzuo=
6、kongshih.kongzuo=0;break;int d,s,a,q,w,e;char linshi;biaoji biaoyou100;for(d=0;dn;d+)if(!(kongshid.kongzuo=1|kongshid.kongyou=0)for(s=0;shizid.rights!=0;s+)for(a=0;a=n;a+)linshi=shizid.rights;if(linshi=shizia.left & kongshia.kongzuo=1)biaoyoud.rs=1;else kongshid.kongyou=0;int sum,t,y;/第三部-1sum=0;for
7、(e=0;en;e+)for(q=0;shizie.rightq!=0;q+)t=biaoyoue.rq;if(t=1)for(sum;shizie.rightq!=0;)sum+;y=sum-1;if(q=y)kongshie.kongzuo=1;break;else break;int a1,a2;/*第二次扫描判断转为否的式子*/for(a1=0;a1=n;a1+)for(a2=0;a2n;a2+) if(a1=a2)break;if(shizia1.left=shizia2.left&kongshia1.kongzuo!=1&kongshia2.kongzuo!=1)if(kongsh
8、ia1.kongyou=0 & kongshia2.kongyou=0)kongshia1.kongzuo=kongshia2.kongzuo=0;break;/计算first集合first fji100;int u,a3,a5,a6,a7,a8;/char linshi22=-;/for(u=0;un;u+)fjiu.fjihe0=0;for(a3=0;a3=a & shizia3.right0=z)linshi20=shizia3.right0;strcat(fjia3.fjihe,linshi2);elseif(kongshia3.kongzuo=1)strcat(fjia3.fjihe
9、,#);for(a5=0;a5=A & shizia5.righta6=a & shizia5.right0=z)break;for(a7=0;a7n;a7+)if(a5!=a7 & shizia5.righta6=shizia7.left)if(kongshia7.kongzuo!=1)strcat(fjia5.fjihe,fjia7.fjihe);if(a6=(strlen(shizia5.right)-1)for(a8=0;a8n;a8+)if(a5!=a8 & shizia5.righta6=shizia8.left)if(kongshia5.kongzuo!=1)strcat(fji
10、a5.fjihe,fjia8.fjihe);elsestrcat(fjia5.fjihe,fjia8.fjihe);strcat(fjia5.fjihe,#);/求follow集合follow fw100;int b1,b2,b3,b4,b5,b6,b7,b8,b9,b10;char linshi52;for(b1=0;b1n;b1+)fwb1.fow0=0;fw0.fow0=#;fw0.fow1=0;for(b8=0;b8n;b8+)if(shizib8.left=shizi0.left)fwb8.fow0=#;fwb8.fow1=0;int e1;for(e1=0;e12;e1+)for(
11、b2=0;b2n;b2+)for(b3=0;b3=A&shizib2.rightb3=a&shizib2.rightb3+1=z)linshi50=shizib2.rightb3+1;linshi51=0;for(b9=0;b9=A&shizib2.rightb3+1=Z)for(b4=0;b4n;b4+)if(shizib2.rightb3+1=shizib4.left)if(kongshib4.kongzuo!=1)for(b10=0;b10n;b10+)if(shizib2.rightb3=shizib10.left)strcat(fwb10.fow,fjib4.fjihe);else
12、for(b5=0;b5n;b5+)if(shizib2.rightb3=shizib5.left)strcat(fwb5.fow,fwb2.fow);if(b3+1)=strlen(shizib2.right)for(b7=0;b7n;b7+)if(shizib2.rightb3=shizib7.left)strcat(fwb7.fow,fwb2.fow);first2 fji2100;int a11,a12,a13;for(a11=0;a11n;a11+)fji2a11.fjihe20=0;for(a12=0;a12=n;a12+)for(a13=0;a13n;a13+)if(a12!=a1
13、3 & shizia12.left=shizia13.left)strcat(fjia12.fjihe,fjia13.fjihe);char linshi3100;char linshi42;int a15,a16,a17=0,a19=0,a21,a18;/for(a15=0;a15n;a15+)for(a21=0;a2199;a21+)linshi3a21=0;for(a16=0;a16strlen(fjia15.fjihe);a16+)if(a16=0)linshi40=fjia15.fjihea16;linshi41=0;strcat(linshi3,linshi4);a16+;for(
14、a17=0;a17=strlen(linshi3);a17+)if(linshi3a17=fjia15.fjihea16)break;/if(linshi3a17=0)linshi40=fjia15.fjihea16;linshi41=0; strcat(linshi3,linshi4);strcat(fji2a15.fjihe2,linshi3);follow2 fw2100;int b11,b12,b13;for(b11=0;b11n;b11+)fw2b11.fow20=0;for(b12=0;b12=n;b12+)for(b13=0;b13n;b13+)if(b12!=b13 & shi
15、zib12.left=shizib13.left)strcat(fwb12.fow,fwb13.fow);char linshi6100;char linshi72;int b15,b16,b17,b19=0,b21,b18;/for(b15=0;b15n;b15+)for(b21=0;b2199;b21+)linshi6b21=0;for(b16=0;b16strlen(fwb15.fow);b16+)if(b16=0)linshi70=fwb15.fowb16;linshi71=0;strcat(linshi6,linshi7);b16+;for(b17=0;b17=strlen(lins
16、hi6);b17+)if(linshi6b17=fwb15.fowb16)break;/if(linshi6b17=0)linshi70=fwb15.fowb16;linshi71=0; strcat(linshi6,linshi7);strcat(fw2b15.fow2,linshi6);int c1,c2;cout非终结符 first集合endl;cout shizi0.left fji20.fjihe2endl;for(c1=1;c1n;c1+)for(c2=0;c2c1;c2+)if(shizic1.left!=shizic2.left&c2=(c1-1)cout shizic1.left fji2c1.fjihe2endl;int d1,d2;cout非终结符 follow集合endl;cout shizi0.left fw20.fow2endl;for(d1=1;d1n;d1+)for(d2=0;d2d1;d2+)if(shizid1.left!=shizid2.left&d2=(d1-1)cout shizid1.left fw2d1.fow2endl;四、运行截图【精品文档】第 6 页