计算first集follow集

1、标准文档编译原理实验报告实验名称 计算first 集合和follow集合实验时间2016 年6月8日院系计算机科学与技术班级计算机科学与技术（1）班学 号 姓 名 1 .试验目的：输入：任意的上下文无关文法。输出：所输入的上下文无关文法一切非终结符的first集合和follow集合。2 .实验原理：设文法GS= (Vn, V P, S),则首字符集为：*FIRST (a)=a | a=aB,aCVT, a,BCV *。 *若 a = e , FIRST ( a )。由定义可以看出，FIRST (a)是指符号用a能够推导出的所有符号用中处 于申首的终结符号组成的集合。所以 FIRST集也称为首符

2、号集。设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 ,重复(1)、(2),直到 Xi C Vt, (i =2, 3,，n)或 Xi CVn且若e更FIRST (Xi)或in为止。当一个文法中存在e产生式时，例如，存在 A-e ,只有知道哪些符号可 以合法地出

3、现在非终结符 A之后，才能知道是否选择 A- 8产生式。这些合法 地出现在非终结符A之后的符号组成的集合被称为 FOLLOW1合。下面我们给出 文法的FOLLOW1的定义。设文法 GS= (Vn, V P, S),则FOLLOW (A) =a | S = Aa ，aCV。 *若 S=A, #C FOLLOWA)。由定义可以看出，FOLLOWA)是指在文法 GS的所有句型中，紧跟在非 终结符A后的终结符号的集合。FOLLOW1可按下列方法求得：(1) 对于文法GS的开始符号S,有# FOLLOWS);(2) 若文法GS中有形如B-xAy的规则，其中x, yCV*,则FIRST (y) e e F

4、OLLOWA);(3) 若文法GS中有形如B, xA的规则，或形如 AxAy的规则且eC FIRST (y),其中 x, y V *,贝FOLLOWB) C FOLLOWA);3.实验代码与结果：输入格式：每行输入一个产生式，左部右部中间的一用空格代替。非终结符等价于大写字母A表不空输入到文件结束，或用 0 0结尾。以编译原理（清华大学第二版）5.6典型例题及答案中的例题一为例（96页）：#include #include #include #include #include using namespace std;char l;string r;存储产生式产生式逆转/非终结符集合/非终结符能

5、否推出空/保存单个元素的first 集保存单个元素的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) /判断终结符能否推出空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) /右部全为终结符，全能推出空return true;return false;void getFirst(char ch, set &First)求单个元素的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的直接或间/求单个元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) /判断是否是右部的最后一个非终结符follow +#follow.insert(#);else if(ch=(*iter)i & i(*iter).size()-1)/不是最后一个但之后全是非终结符且都能推出空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 的最后一个符号（直接或间接）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;/产生式非终结符/右部的集合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) /判断是否有 非终结符-”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