编译原理实验报告first集和follow集

《编译原理实验报告first集和follow集》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、编译原理实验报告实验名称计算first集合和follow集合实验时间院系计算机科学与技术班级软件工程1班学号姓名实验目的输入：任意的上下文无关文法。输出：所输入的上下文无关文法一切非终结符的first集合和follow集合。1.实验原理设文法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之后的符

4、号组成的集合被称为FOLLOW集合。下面我们给出文法的FOLLOW集的定义。设文法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→x

6、A的规则，或形如B→xAy的规则且ε∈FIRST（y），其中x，y∈V*，则FOLLOW（B）∈FOLLOW（A）；3.实验内容计算first集合和follow集合4.实验心得通过上机实验我对文法符号的FIRST集和FOLLOW集有了更深刻的理解，已经熟练的掌握了求解的思想和方法，同时也锻炼了自己的动手解决问题的能力，对编程能力也有所提高。5.实验代码与结果#include#include#includeusingnamespacestd;#defineMAXS50intNONE[

7、MAXS]={0};stringstrings;//产生式stringVn;//非终结符stringVt;//终结符stringfirst[MAXS];//用于存放每个终结符的first集stringFirst[MAXS];//用于存放每个非终结符的first集stringFollow[MAXS];//用于存放每个非终结符的follow集intN;//产生式个数structSTR{stringleft;stringright;};//求VN和VTvoidVNVT(STR*p){inti,j;for(i=0;i

8、;j<(int)p[i].left.length();j++){if((p[i].left[j]>='A'&&p[i].left[j]<='Z')){if(Vn.find(p[i].left[j])>100)Vn+=p[i].left[j];}else{if(Vt.find(p[i].left[j])>100)Vt+=p[i].left[j];}}for(j=0;j<(int)p[i].right.length();j++){if(!(p[i].right[j]>='A'&&p[i].right[j]<='Z')){if(Vt.find(

9、p[i].right[j])>100)Vt+=p[i].right[j];}else{if(Vn.find(p[i].right[j])>100)Vn+=p[i].right[j];}}}}voidgetlr(STR*p,inti){intj;for(j=0;j'){p[i].left=strings.substr(0,j);p[i].right=strings.substr(j+2,strings.length()-j)

10、;}}}//对每个文法符号求first集stringLetter_First(STR*p,charch){intt;if(!(Vt.find(ch)>100)){first[Vt.find(c