计算first集follow集

《计算first集follow集》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、编译原理实验报告实验名称计算first集合和follow集合实验时间2016年6月8日院系计算机科学与技术班级计算机科学与技术（1）班学号姓名1.试验目的：输入：任意的上下文无关文法。输出：所输入的上下文无关文法一切非终结符的first集合和follow集合。2.实验原理：设文法G[S]＝（VN，VT，P，S），则首字符集为：FIRST（α）＝{a

2、αaβ，a∈VT，α,β∈V*}。若αε，ε∈FIRST（α）。由定义可以看出，FIRST（α）是指符号串α能够推导出的所有符号串中处于串首的终结符号组成的集合。所以FIRST集也称为首符号集。设α＝x1x2…xn，FIRST（α）可按下列方

3、法求得：令FIRST（α）＝Φ，i＝1；（1）若xi∈VT，则xi∈FIRST（α）；（2）若xi∈VN；①若εFIRST（xi），则FIRST（xi）∈FIRST（α）；②若ε∈FIRST（xi），则FIRST（xi）－{ε}∈FIRST（α）；（3）i＝i+1，重复（1）、（2），直到xi∈VT，（i＝2，3，…，n）或xi∈VN且若εFIRST（xi）或i>n为止。当一个文法中存在ε产生式时，例如，存在A→ε，只有知道哪些符号可以合法地出现在非终结符A之后，才能知道是否选择A→ε产生式。这些合法地出现在非终结符A之后的符号组成的集合被称为FOLLOW集合。下面我们给出文法的FOLL

4、OW集的定义。设文法G[S]＝（VN，VT，P，S），则FOLLOW（A）＝{a

5、S…Aa…，a∈VT}。若S…A，#∈FOLLOW（A）。由定义可以看出，FOLLOW（A）是指在文法G[S]的所有句型中，紧跟在非终结符A后的终结符号的集合。FOLLOW集可按下列方法求得：（1）对于文法G[S]的开始符号S，有#∈FOLLOW（S）；（2）若文法G[S]中有形如B→xAy的规则，其中x，y∈V*，则FIRST（y）－{ε}∈FOLLOW（A）；（3）若文法G[S]中有形如B→xA的规则，或形如B→xAy的规则且ε∈FIRST（y），其中x，y∈V*，则FOLLOW（B）∈FOLLOW（A

6、）；3.实验代码与结果：输入格式：每行输入一个产生式，左部右部中间的→用空格代替。非终结符等价于大写字母^表示空输入到文件结束，或用00结尾。以编译原理（清华大学第二版）5.6典型例题及答案中的例题一为例（96页）：#include#include#include

7、r>ter;//非终结符集合maptoEmpty;//非终结符能否推出空boolflag;setfir;//保存单个元素的first集setfollow;//保存单个元素的follow集vectorrightSide;//右部charBegin;boolcapL(charc)//字母是否大写{if(c<='Z'&&c>='A')returntrue;returnfalse;}boolCapLString(strings)//大写字符串{for(inti=0;i

8、urnfalse;}}returntrue;}boolisToEmpty(charch)//判断终结符能否推出空{boolflag;flag=false;multimap::iteratormIter=sentence.find(ch);intcnt=sentence.count(ch);for(inti=0;isecond=="^"){returntrue;}elseif(CapLString(mIter->second)){strings(mIter->second);boolflag2=true;fo

9、r(intj=0;j

10、

11、s[j]==ch){flag2=false;break;}}if(flag2){//右部全为终结符，全能推出空returntrue;}}}//}returnfalse;}voidgetFirst(charch,set&First)//求单个元素的FIRST集{multimap::iteratorimul=