实验六计算first集合和follow集合.doc

《实验六计算first集合和follow集合.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《编译原理》课程实验报告实验六：计算first集合和follow集合编译原理实验报告姓名：滕雯娟学号：E专业：计算机科学与技术年级：09级2班实验时间：2012/6/7成绩：实验六：计算first集合和follow集合实验目的：1．掌握求first和follow集合的算法2．熟悉运用C/C++语言对求first和follow集合进行实现实验要求：输入：任意的上下文无关文法。输出：所输入的上下文无关文法一切非终结符的first集合和follow集合实验原理：设α＝x1x2…xn，FIRST（α）可按下列

2、方法求得：令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→ε产生式。这些合

3、法地出现在非终结符A之后的符号组成的集合被称为FOLLOW集合。下面我们给出文法的FOLLOW集的定义。设文法G[S]＝（VN，VT，P，S），则FOLLOW（A）＝{a

4、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

5、）－{ε}∈FOLLOW（A）；（3）若文法G[S]中有形如B→xA的规则，或形如B→xAy的规则且ε∈FIRST（y），其中x，y∈V*，则FOLLOW（B）∈FOLLOW（A）；实验内容：程序代码如下：#include#includeusingnamespacestd;#definemax30typedefstructCSS//定义一个产生式结构体{stringleft;//定义产生式的左部stringright;//定义产生式的右部}CSS;stringcon

6、;//存放文法中的非终结符stringfirst[max];//存放非终结符的first集stringfollow[max];//存放非终结符的follow集//提取产生式中的非终结符voidsearch(CSS*p,intn){inti,j;for(i=0;i=0&&con.find(p[i].left[0])

7、();j++){if('A'<=p[i].right[j]&&p[i].right[j]<='Z'){if(con.find(p[i].right[j])>=0&&con.find(p[i].right[j])

8、x,y;intflag=0;for(i=0;i=p[i].right[0])first[mm]=first[mm]+p[i].right.substr(0,1);if(p[i].right[0]=='#')first[mm]=first[mm]+p[i].right.substr(0,1);if('A'<=p[i].right[0]&&'Z'>=p[i].right[0]){for(j=0;j

9、