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）或i>n為止。當一個文法中存在產生式時，例如，存在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<iostream.h>#include<string.h>/產生式struct csschar left;char zhuan;/用“-”表示箭頭char right20;

4、/空標志struct kongint 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<&

5、lt;"請輸入產生式的條數n(n<100)："<<endl;cin>>n;cout<<"請從開始符輸入產生式(空用“#”表示，產生式由字母組成)："<<endl;for(i=0;i<n;i+)cin>>shizii.left>>shizii.zhuan>>shizii.right;int l,m,j,h,g,f;for(l=0;l<n;l+)for(m=0;m<sizeof(shizil.right);m+)if(shizil.rightm=

6、9;#')kongshil.kongzuo=1;break;else while(shizil.rightm>='a' && shizil.rightm<='z' ) kongshil.kongyou=0; break;for(j=0;j<=n;j+)for(h=0;h<n;h+) if(j=h)break;if(shizij.left=shizih.left)if(kongshij.kongyou=0 && kongshih.kongyou=0)kongshij.kongzuo=kongshih.

7、kongzuo=0;break;int d,s,a,q,w,e;char linshi;biaoji biaoyou100;for(d=0;d<n;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,

8、y;/第三部-1sum=0;for(e=0;e<n;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;a2<n;a2+) if(a1=a2)break;if(shizia1.left=shizia2.left&

9、&kongshia1.kongzuo!=1&&kongshia2.kongzuo!=1)if(kongshia1.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;u<n;u+)fjiu.fjihe0='0'for(a3=0;a3<=n;a3+)if(shizia3

10、.right0>='a' && shizia3.right0<='z')linshi20=shizia3.right0;strcat(fjia3.fjihe,linshi2);elseif(kongshia3.kongzuo=1)strcat(fjia3.fjihe,"#");for(a5=0;a5<=n;a5+)for(a6=0;shizia5.righta6!='0'a6+)if(shizia5.righta6>='A' && shizia5.righ

11、ta6<='Z')if(shizia5.right0>='a' && shizia5.right0<='z')break;for(a7=0;a7<n;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;a8<n;a8+)if(a5!=a8 &&

12、; shizia5.righta6=shizia8.left)if(kongshia5.kongzuo!=1)strcat(fjia5.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;b1<n;b1+)fwb1.fow0='0'fw0.fow0='#'fw0.fow1=

13、'0'for(b8=0;b8<n;b8+)if(shizib8.left=shizi0.left)fwb8.fow0='#'fwb8.fow1='0'int e1;for(e1=0;e1<2;e1+)for(b2=0;b2<n;b2+)for(b3=0;b3<n;b3+)if(shizib2.rightb3>='A'&&shizib2.rightb3<='Z')if(shizib2.rightb3+1>='a'&&shizib

14、2.rightb3+1<='z')linshi50=shizib2.rightb3+1;linshi51='0'for(b9=0;b9<n;b9+)if(shizib2.rightb3=shizib9.left)strcat(fwb9.fow,linshi5);if(shizib2.rightb3+1>='A'&&shizib2.rightb3+1<='Z')for(b4=0;b4<n;b4+)if(shizib2.rightb3+1=shizib4.left)if(kongshib4

15、.kongzuo!=1)for(b10=0;b10<n;b10+)if(shizib2.rightb3=shizib10.left)strcat(fwb10.fow,fjib4.fjihe);else for(b5=0;b5<n;b5+)if(shizib2.rightb3=shizib5.left)strcat(fwb5.fow,fwb2.fow);if(b3+1)=strlen(shizib2.right)for(b7=0;b7<n;b7+)if(shizib2.rightb3=shizib7.left)strcat(fwb7.fow,fwb2.fow);first2 f

16、ji2100;int a11,a12,a13;for(a11=0;a11<n;a11+)fji2a11.fjihe20='0'for(a12=0;a12<=n;a12+)for(a13=0;a13<n;a13+)if(a12!=a13 && 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;a15<n;a15+)for(a

17、21=0;a21<99;a21+)linshi3a21='0'for(a16=0;a16<strlen(fjia15.fjihe);a16+)if(a16=0)linshi40=fjia15.fjihea16;linshi41='0'strcat(linshi3,linshi4);a16+;for(a17=0;a17<=strlen(linshi3);a17+)if(linshi3a17=fjia15.fjihea16)break;/if(linshi3a17='0')linshi40=fjia15.fjihea16;linsh

18、i41='0' strcat(linshi3,linshi4);strcat(fji2a15.fjihe2,linshi3);follow2 fw2100;int b11,b12,b13;for(b11=0;b11<n;b11+)fw2b11.fow20='0'for(b12=0;b12<=n;b12+)for(b13=0;b13<n;b13+)if(b12!=b13 && shizib12.left=shizib13.left)strcat(fwb12.fow,fwb13.fow);char linshi6100;char l

19、inshi72;int b15,b16,b17,b19=0,b21,b18;/for(b15=0;b15<n;b15+)for(b21=0;b21<99;b21+)linshi6b21='0'for(b16=0;b16<strlen(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<<"