實(shí)驗(yàn)六計(jì)算first集合和follow集合

1、精選優(yōu)質(zhì)文檔-傾情為你奉上編譯原理課程實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)六：計(jì)算first集合和follow集合編譯原理實(shí)驗(yàn)報(bào)告姓名：滕雯娟 學(xué)號(hào)：E 專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù) 年級(jí) ：09 級(jí)2班 實(shí)驗(yàn)時(shí)間：2012/6/7 成績：實(shí)驗(yàn)六：計(jì)算first集合和follow集合實(shí)驗(yàn)?zāi)康模?掌握求first和follow集合的算法2熟悉運(yùn)用C/C+語言對(duì)求first和follow集合進(jìn)行實(shí)現(xiàn)實(shí)驗(yàn)要求：輸入：任意的上下文無關(guān)文法。輸出：所輸入的上下文無關(guān)文法一切非終結(jié)符的first集合和follow集合實(shí)驗(yàn)原理：設(shè)x1x2xn，F(xiàn)IRST（）可按下列方法求得：令FIRST（），i1；（1）若xiVT，則xiFIRST（）

2、；（2）若xiVN； 若 FIRST（xi），則FIRST（xi）FIRST（）； 若FIRST（xi），則FIRST（xi）FIRST（）；（3）ii+1，重復(fù)（1）、（2），直到xiVT，（i2，3，n）或xiVN且若 FIRST（xi）或in為止。當(dāng)一個(gè)文法中存在產(chǎn)生式時(shí)，例如，存在A，只有知道哪些符號(hào)可以合法地出現(xiàn)在非終結(jié)符A之后，才能知道是否選擇A產(chǎn)生式。這些合法地出現(xiàn)在非終結(jié)符A之后的符號(hào)組成的集合被稱為FOLLOW集合。下面我們給出文法的FOLLOW集的定義。設(shè)文法GS（VN，VT，P，S），則 FOLLOW（A）a | S Aa ，aVT。若S A，#FOLLOW（A）。由定義

3、可以看出，F(xiàn)OLLOW（A）是指在文法GS的所有句型中，緊跟在非終結(jié)符A后的終結(jié)符號(hào)的集合。FOLLOW集可按下列方法求得：（1）對(duì)于文法GS的開始符號(hào)S，有#FOLLOW（S）；（2）若文法GS中有形如BxAy的規(guī)則，其中x，yV *，則FIRST（y）FOLLOW（A）；（3）若文法GS中有形如BxA的規(guī)則，或形如BxAy的規(guī)則且FIRST（y），其中x，yV *，則FOLLOW（B）FOLLOW（A）；實(shí)驗(yàn)內(nèi)容：程序代碼如下：#include#includeusing namespace std;#define max 30typedef struct CSS /定義一個(gè)產(chǎn)生式結(jié)構(gòu)體 s

4、tring left; /定義產(chǎn)生式的左部 string right; /定義產(chǎn)生式的右部CSS;string con;/存放文法中的非終結(jié)符string firstmax;/存放非終結(jié)符的first集string followmax;/存放非終結(jié)符的follow集/提取產(chǎn)生式中的非終結(jié)符void search(CSS *p,int n)int i,j;for(i=0;i=0&con.find(pi.left0)con.length()con=con+pi.left;for(j=0;jpi.right.length();j+)if(A=pi.rightj&pi.rightj=0&con.fin

5、d(pi.rightj)con.length()break;elsecon=con+pi.right.substr(j,1);/求文法中非終結(jié)符的First集void First(CSS *p,int n,char m,int mm)int length=con.length();string f;int i,j,x,y;int flag=0;for(i=0;in;i+)if(m=pi.left0)if(a=pi.right0) firstmm=firstmm+pi.right.substr(0,1);if(pi.right0=#) firstmm=firstmm+pi.right.subst

6、r(0,1);if(A=pi.right0)for(j=0;jpi.right.length();j+)if(A=pi.rightj&pi.rightj=Z)flag+;if(flag=j)/產(chǎn)生式的右部均為非終結(jié)符flag=0;for(j=0;jpi.right.length();j+)for(x=0;xn;x+)if(pi.rightj=px.left0&px.right0=#)flag+;break;if(flag=j)/產(chǎn)生式右部的全部非終結(jié)符均能推出空for(j=0;jpi.right.length();j+)for(x=0;xn;x+)if(pi.rightj=conx)break

7、;y=x;if(firsty=)First(p,n,pi.rightj,x); f=firsty;for(x=0;xf.length();x+)if(fx=#)if(x=f.length()-1)f=f.substr(0,x);else f=f.substr(0,x)+f.substr(x+1); firstmm=firstmm+f; firstmm=firstmm+#;elsefor(j=0;jpi.right.length();j+)for(x=0;xn;x+)if(pi.rightj=conx)break;y=x;if(firsty=)First(p,n,pi.rightj,x);f=f

8、irsty;for(x=0;xf.length();x+)if(fx=#)if(x=f.length()-1)f=f.substr(0,x);else f=f.substr(0,x)+f.substr(x+1); firstmm=firstmm+f;/求文法的follow集void Follow(CSS *p,int n,int m)int i,j,x,y,k;string fo;for(i=0;in;i+)for(j=0;jpi.right.length();j+)if(conm=pi.rightj)if(jpi.right.length()-1&a=pi.rightj+1&pi.right

9、j+1=z) followm=followm+pi.right.substr(j+1,1); if(jpi.right.length()-1&A=pi.rightj+1&pi.rightj+1=Z)for(y=0;ycon.length();y+)if(cony=pi.rightj+1)break;fo=firsty;for(x=0;xfirsty.length();x+)if(0=firsty.find(#)&firsty.find(#)firsty.length()fo=firsty.substr(0,firstm.find(#)+firsty.substr(firsty.find(#)+

10、1); followm=followm+fo; for(x=0;xn;x+)if(pi.rightj+1=px.left0&px.right0=#)break; if(x!=n)/非終結(jié)符后面的部分可以推出空for(y=0;yn;y+)if(pi.left0=cony)break; k=y; if(followk=)Follow(p,n,y); followm=followm+followk; if(j=pi.right.length()-1) for(y=0;yn;y+) if(pi.left0=cony)break; k=y; if(followk=)Follow(p,n,y); foll

11、owm=followm+followk; /去First集及follow集中的重復(fù)字符string erase(string s)int i,j;for(i=0;is.length();i+)for(j=0;js.length();j+)if(i!=j&si=sj)s=s.substr(0,j)+s.substr(j+1);return s;void main()int i,j,n,m;string input;char f;coutn;CSS *p=new CSSn; / 初始化產(chǎn)生式數(shù)組for(i=0;iinput; /輸入 for(j=0;jinput.length();j+)/改變輸入數(shù)據(jù)的形式 if(inputj=-) pi.left=input.substr(0,j); pi.right=input.substr(j+2,input.length(); cout請(qǐng)輸入該文法的開始符號(hào)：f;search(p,n);/提取產(chǎn)生式中的非終結(jié)符for(m=0;mcon.length();m+)if(firstm=)First(p,n,conm,m);cout該文法非終結(jié)符的first集：endl;for(i=0;icon.length();i+)firsti=erase(firsti);coutconi:firstiendl;for(m=0;mcon.lengt