1、編譯原理實(shí)驗(yàn)報告 FIRST集和FOLLOW S編譯原理實(shí)驗(yàn)報告實(shí)驗(yàn)名稱 計算 first 集合禾口 follow 集合實(shí)驗(yàn)時間院系計算機(jī)科學(xué)與技術(shù)班級學(xué)號實(shí)驗(yàn)?zāi)康妮斎耄喝我獾纳舷挛臒o關(guān)文法。輸出：所輸入的上下文無關(guān)文法一切非終結(jié)符的卅集合和 follow 集合。實(shí) 驗(yàn)原理設(shè)文法GS二 (VN, VT, P, S),則首字符集為：*FIRST ( a ) =a | a =aB , aAVT, a z B UV *?若 a =E, cG FIRST ( a) 。由定義可以看出，F(xiàn)IRST (a )是指符號串a(chǎn)能夠推導(dǎo)出的所有符號串中處于串首的終結(jié)符號組成的集合。所以 FIRST 集也稱為首符號集

2、。設(shè) a=xiX2.x n, FIRST ( a )可按下列方法求得：令 FIRST ( a ) =n 為止。當(dāng)一個文法中存在產(chǎn)生式時，例如，存在A-戈只有知道哪些符號可以合法地出現(xiàn)在非終結(jié)符 A之后，才能知道是否選擇 Af 士產(chǎn)生式。這些合法地出現(xiàn)在非終結(jié)符 A 之后的符號組成的集合被稱為 FOLLOW 集合。下面我們給出文 法的 FOLLOW 集的定義。設(shè)文法 G|S= (VN, Vr, P, S),貝 IFOLLOW (A) =a | S=. Aa aev to*若 S=? A, #e FOLLOW (A)o由定義可以看出， FOLLOW (A) 是指在文法GS 的所有句型中，緊跟在非終

3、結(jié)符 A 后的終結(jié)符號的集合。FOLLOW 集可按下列方法求得：對于文法GS的開始符號S,#eFOLLOW (S);若文法GS中有形如B-xAy的規(guī)則，其中x, N,則FIRST (y)- cGFOLLOW (A) ；(3)若文法GS中有形如B-*xA的規(guī)則，或形如B-*xAy的規(guī)則且丘 FIRST (y),負(fù)中 x, yev 貝 0 FOLLOW (B) GFOLLOW (A);實(shí)驗(yàn)內(nèi)容計算 first 集合和 follow 集合實(shí)驗(yàn)心得通過上機(jī)實(shí)驗(yàn)我對文法符號的 FIRST集和FOLLOW1有了更深刻的理解,已經(jīng) 熟練的掌握了求解的思想和方法，同時也鍛煉了自己的動手解決問題的能 力，對編

4、程能力也有所提高。實(shí)驗(yàn)代碼與結(jié)果#include#include#include using namespace std;#define MAXS 50 int NONEMAXS=0; string strings;/ 產(chǎn)生式 string Vn;/ 非終結(jié)符 string Vt;/ 終結(jié)符 string firstMAXS; first 集 string FirstMAXS;/ 的 first 集 string FollowMAXS; 符的 follow 集 int N;/ 產(chǎn)生式個 數(shù) 用于存放每個終結(jié)符的用于存放每個非終結(jié)符/用于存放每個非終結(jié) TOC o 1-5 h z 6u 聲 8u

5、 2snFup6ao-+ M+ vO0H6EuOa42dQQMHAm衛(wèi)(00lx(ugla_E:d)pu2(zbvnld)!tdu elseif(Vt.find(pi.leftj)100)Vt +=pi.leftj; for(j=0;jv(int)pi.right.length();j+)if(!(pi.rightj=A&pi.rightj100)Vt +=pi.rightj; elseif(Vn.find(pi.rightj)100)Vn+=pi.rightj;void getlr(STR *p,int i)int j ； for(j=0;jvstrings .l ength();j+)if

6、(stringsj=-&stringsj+1=)pi .l eft=strings ? substr(0,j);pi .right=strings .substr(j+2,strings ength()-j); 對每個文法符號求 first 集string Letter_First(STR *p,char ch)int t;if(!(Vt .find(ch)100)firstVt .find(ch)=ch; return firstVt ?find(ch)-1;if(!(Vn.find(ch)100)for(int i=0;i1O0) if(FirstVn.find(ch).find(pi.r

7、ight0)1OO) FirstVn.find(ch)+=pi.right0;if(pi.right0=*)if(FirstVn.find(ch).find(*)100)FirstVn ? find(ch)+=*;if(!(Vn .find(pi .right0)100)if(pi .right ? length()=1)string ff; ff=Letter_First(p,pi right0); for(int i_i=0;i_ivff length();i_i+) if( FirstVn.find(ch).find(ffi_i)100)FirstVn.find(ch)+=ffi_i;

8、elsefor(intj=0 ； jvpi.right ength();j+)string TT;TT=Letter_First(p,pi ? rightj);if(!(TT. find(*)10 0)&(j+1)vpi .right .1 ength() )sort(TT ? begin(),TT .end();string tt;for(intt=1;tTT .length();t+)tt+=TTt;TT=tt;tt=;for(t=0;t100)FirstVn.find(ch)+=TTt;else for(t=0;t100)FirstVn.find(ch)+=TTt;break;retur

9、n FirstV n. find(ch);/求每個非終結(jié)符的 Follow 集string Letter_Follow(STR *p,char ch) int t,k;NONEV n. find(ch)+;if(NONEVn .find(ch)=2) NONEVn .find(ch)=0; return FollowV n. find(ch);for(int i=0;iN;i+)for(int j=0;j100) FollowVn .find(ch)+=ggk;else string FF;for(intjj=j+1;jjvpi.right.length();jj+)string TT;TT=

10、Letter_First(p,pi ? rightjj);if(!(TT .find(*)100)&(jj+1)pi .right .1 ength( )sort(TT ? begin(),TT .end();string tt;for(intt=1;tTT ? length();t+)tt+=TTt;TT=tt;tt=;for(t=0;t10 0&TTt!=*)FF+=TTt;elsefor(t=0;t100) FF+=TTt; break;if(FF.find(*)100)for(k=0;k100)FollowVn.find(ch)+=FFk; else for(k=0;k100)&FF

11、k!=*)FollowVn .find(ch)+=FFk;string dd;dd=Letter_Follow(p,pi .left0);NONEVn .find(pi .1eft0)=0; for(k=0;kvddlength();k+) if(FollowVn.find(ch).find(ddk)100)FollowVn.find(ch)+=ddk;return FollowVn.find(ch);void result()coutvvn 該文法不是LL(1)型文法vvendl;主函數(shù)int main()(int i,j,k;COUtVV請輸入產(chǎn)生式總數(shù):;cin? N;coutvvn 請輸入各產(chǎn)生式(*代表 空):vvendl;STR *p=new STRMAXS;for(i=0;istrings; getlr(p,i);VNVT(p);coutvvendl;coutvvn=vvendl;coutvv 非 終 結(jié) 符vvtvvFIRSTvvttvvFOLLOWvve ndl;for(i=0;iVnength();i+)coutvv vvVnivvtt;string pp;pp=Letter_First(p,Vni); for(j=0;j+lvpplength();j+)coutvvppjvv,;cou