编译原理实验报告材料FIRST集和FOLLOW集

实用标准文案编译原理实验报告实验名称 计算first集合和follow 集合实验时间院系 计算机科学与技术班级 软件工程1班学号姓名精彩文档实用标准文案实验目的输入：任意的上下文无关文法。输出：所输入的上下文无关文法一切非终结符的 first集合和follow 集合。实验原理设文法G[S]＝（VN，VT，P，S），则首字符集为：*FIRST（α）＝{a|α aβ，a∈VT，α,β∈V*}。*若α ε，ε∈FIRST（α）。由定义可以看出，FIRST（α）是指符号串α能够推导出的所有符号串中处于串首的终结符号组成的集合。所以 FIRST集也称为首符号集。设α＝x1x2⋯xn，FIRST（α）可按下列方法求得：令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集合。下面我们给出文法的FOLLOW集的定义。设文法G[S]＝（VN，VT，P，S），则精彩文档实用标准文案FOLLOW（A）＝{a|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*，则FIRSTy）－{ε}∈FOLLOW（A）；（3） 若文法G[S]中有形如B→xA的规则，或形如 B→xAy的规则且ε∈FIRST（y），其中x，y∈V*，则FOLLOW（B）∈FOLLOW（A）；精彩文档实用标准文案实验内容计算first集合和follow 集合实验心得通过上机实验我对文法符号的FIRST集和FOLLOW集有了更深刻的理解，已经熟练的掌握了求解的思想和方法，同时也锻炼了自己的动手解决问题的能力，对编程能力也有所提高。实验代码与结果#include<iostream>#include<string>#include<algorithm>usingnamespacestd;#defineMAXS50intNONE[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<N;i++){for(j=0;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(p[i].right[j])>100)Vt+=p