計(jì)算first集follow集

1、標(biāo)準(zhǔn)文檔編譯原理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱 計(jì)算first 集合和follow集合實(shí)驗(yàn)時(shí)間2016 年6月8日院系計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)計(jì)算機(jī)科學(xué)與技術(shù)（1）班學(xué) 號(hào) 姓 名 1 .試驗(yàn)?zāi)康模狠斎耄喝我獾纳舷挛臒o關(guān)文法。輸出：所輸入的上下文無關(guān)文法一切非終結(jié)符的first集合和follow集合。2 .實(shí)驗(yàn)原理：設(shè)文法GS= (Vn, V P, S),則首字符集為：*FIRST (a)=a | a=aB,aCVT, a,BCV *。 *若 a = e , FIRST ( a )。由定義可以看出，F(xiàn)IRST (a)是指符號(hào)用a能夠推導(dǎo)出的所有符號(hào)用中處 于申首的終結(jié)符號(hào)組成的集合。所以 FIRST集也稱為首符

2、號(hào)集。設(shè)oc = XiX2Xn, FIRST (a)可按下列方法求得：令 FIRST ( a )=，i = 1;(1) 若 XiC Vr,則 Xi e FIRST (a);(2) 若 Xi e y；若 e 正 FIRST (Xi),貝 U FIRST (x。 FIRST (a);若 e C FIRST (Xi),貝 U FIRST (Xi) e C FIRST (a);(3) i =i+1 ,重復(fù)(1)、(2),直到 Xi C Vt, (i =2, 3,，n)或 Xi CVn且若e更FIRST (Xi)或in為止。當(dāng)一個(gè)文法中存在e產(chǎn)生式時(shí)，例如，存在 A-e ,只有知道哪些符號(hào)可 以合法地出

3、現(xiàn)在非終結(jié)符 A之后，才能知道是否選擇 A- 8產(chǎn)生式。這些合法 地出現(xiàn)在非終結(jié)符A之后的符號(hào)組成的集合被稱為 FOLLOW1合。下面我們給出 文法的FOLLOW1的定義。設(shè)文法 GS= (Vn, V P, S),則FOLLOW (A) =a | S = Aa ，aCV。 *若 S=A, #C FOLLOWA)。由定義可以看出，F(xiàn)OLLOWA)是指在文法 GS的所有句型中，緊跟在非 終結(jié)符A后的終結(jié)符號(hào)的集合。FOLLOW1可按下列方法求得：(1) 對(duì)于文法GS的開始符號(hào)S,有# FOLLOWS);(2) 若文法GS中有形如B-xAy的規(guī)則，其中x, yCV*,則FIRST (y) e e F

4、OLLOWA);(3) 若文法GS中有形如B, xA的規(guī)則，或形如 AxAy的規(guī)則且eC FIRST (y),其中 x, y V *,貝FOLLOWB) C FOLLOWA);3.實(shí)驗(yàn)代碼與結(jié)果：輸入格式：每行輸入一個(gè)產(chǎn)生式，左部右部中間的一用空格代替。非終結(jié)符等價(jià)于大寫字母A表不空輸入到文件結(jié)束，或用 0 0結(jié)尾。以編譯原理（清華大學(xué)第二版）5.6典型例題及答案中的例題一為例（96頁）：#include #include #include #include #include using namespace std;char l;string r;存儲(chǔ)產(chǎn)生式產(chǎn)生式逆轉(zhuǎn)/非終結(jié)符集合/非終結(jié)符能

5、否推出空/保存單個(gè)元素的first 集保存單個(gè)元素的follow集右部multimapchar, stringsentence; / multimap senRever; / set ter;map toEmpty;bool flag;set fir;set follow; / vector rightSide; / char Begin;bool capL(char c) / 字母是否大寫 if(c=A)return true;return false;bool CapLString(string s) /大寫 字符串for(int i=0; is.size(); i+) if(!capL(

6、si) return false; return true;bool isToEmpty(char ch) /判斷終結(jié)符能否推出空bool flag;flag = false;multimap:iterator miter = sentence.find(ch); int cnt = sentence.count(ch);for(int i=0; isecond=A) return true;else if(CapLString(mIter-second)string s(mIter-second);bool flag2 = true;for(int j=0; js.size(); j+) i

7、f(!isToEmpty(sj) | sj=ch) flag2 = false; break;if(flag2) /右部全為終結(jié)符，全能推出空return true;return false;void getFirst(char ch, set &First)求單個(gè)元素的FIRST 集multimap:iterator imul = sentence.find(ch);if(imul=sentence.end()return;int sum = sentence.count(imul-first);for(int i=0; isecond);for(int j=0; j=0; i-) if(c

8、h=si)return true;if(!capL(si) | toEmptysi =false) return false;return false;void getFollow(char ch, set &follow)素的 FOLLOWif(!capL(ch)return;for(vector:iteratoriter!=rightSide.end(); +iter) for(int i=0; i(*iter).size(); i+) /ch 是否是s的直接或間/求單個(gè)元iter=rightSide.begin();if(ch=(*iter)i & i!=(*iter).size()-1

9、) if(!capL(*iter)i+1) follow.insert(*iter)i+1);else getFirst(*iter)i+1, follow);if(ch=(*iter)i & i=(*iter).size()-1) /判斷是否是右部的最后一個(gè)非終結(jié)符follow +#follow.insert(#);else if(ch=(*iter)i & i(*iter).size()-1)/不是最后一個(gè)但之后全是非終結(jié)符且都能推出空follow +#bool flag1=true;for(int j=i+1;j(*iter).size(); j+) if(!capL(*iter)j)|

10、toEmpty(*iter)j=false) flagl = false;if(!capL(*iter)j) follow.insert(*iter)j);break;if(flag1 = true) follow.insert(#);if(isLast(*iter, ch) /ch 是*iter 的最后一個(gè)符號(hào)（直接或間接）int n = senRever.count(*iter);multimap:iteratormItersenRever.find(*iter);for(int i=0 ;isecond!=ch ) getFollow(mIter-second, follow); int

11、 main()int cnt=0;while(cinlr) if(cnt=0) Begin = l; cnt+;if(l=0)break;/產(chǎn)生式非終結(jié)符/右部的集合sentence.insert(make_pair(l, r); senRever.insert(make_pair(r,l); ter.insert(l);集合(左部)rightSide.push_back(r);for(set:iterator sIter = ter.begin(); sIter!=ter.end();+sIter) /判斷是否有 非終結(jié)符-”if(isToEmpty(*sIter) ) toEmpty*sIter = true;else toEmpty*sIter = false; for(set:iterator iter=ter.begin(); iter!=ter.end(); iter+) flag = false;cout*iter FIRST 集：”；fir.clear();getFirst(*iter, fir);for(set:iteratoriterF=fir.begin();iterF!=fir.end();iterF+) cout *iterF;coutendl;follow.clear();getFol