计算first集合和follow集合--编译原理

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） 若xiVN； 若FIRST（xi），则

2、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的所有句

3、型中，紧跟在非终结符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 kongint kongzuo;int kongyou

4、;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;cout请从开始符输入产生式(空用“#”表示，产

5、生式由字母组成)：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=kongshih.kongzuo=0;brea

6、k;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(e=0;en;e+)for(q=0;shiz

7、ie.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(kongshia1.kongyou=0 & kongshi

8、a2.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,#);for(a5=0;a5=A & shi

9、zia5.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(fjia5.fjihe,fjia8.fjihe);e

10、lsestrcat(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(b2=0;b2n;b2+)for(b3=0;b

11、3=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 for(b5=0;b5n;b5+)if(shi

12、zib2.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!=a13 & shizia12.left=shizi

13、a13.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(a17=0;a17=strlen(linshi

14、3);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 & shizib12.left=shizib13.lef

15、t)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(linshi6);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(