【MeiWei81-优质实用版文档】编译原理实验报告实验名称 计算first集合和follow集合 实验时间 院系 计算机科学与技术 班级 软件工程1班 学号 姓名 1. 实验目的输入：任意的上下文无关文法。输出：所输入的上下文无关文法一切非终结符的first集合和follow集合。2. 实验原理设文法GS（VN，VT，P，S），则首字符集为：FIRST（）a|a，aVT，,VG。若，FIRST（）。由定义可以看出，FIRST（）是指符号串能够推导出的所有符号串中处于串首的终结符号组成的集合。所以FIRST集也称为首符号集。设G1G2Gn，FIRST（）可按下列方法求得：令FIRST（），i1；（1） 若GiVT，则GiFIRST（）；（2） 若GiVN；若FIRST（Gi），则FIRST（Gi）FIRST（）；若FIRST（Gi），则FIRST（Gi）FIRST（）；（3） ii+1，重复（1）、（2），直到GiVT，（i2，3，n）或GiVN且若FIRST（Gi）或in为止。当一个文法中存在产生式时，例如，存在A，只有知道哪些符号可以合法地出现在非终结符A之后，才能知道是否选择A产生式。这些合法地出现在非终结符A之后的符号组成的集合被称为FOLLOW集合。下面我们给出文法的FOLLOW集的定义。设文法GS（VN，VT，P，S），则FOLLOW（A）a|SAa，aVT。若SA，#FOLLOW（A）。由定义可以看出，FOLLOW（A）是指在文法GS的所有句型中，紧跟在非终结符A后的终结符号的集合。FOLLOW集可按下列方法求得：（1） 对于文法GS的开始符号S，有#FOLLOW（S）；（2） 若文法GS中有形如BGAy的规则，其中G，yVG，则FIRST（y）FOLLOW（A）；（3） 若文法GS中有形如BGA的规则，或形如BGAy的规则且FIRST（y），其中G，yVG，则FOLLOW（B）FOLLOW（A）；3.实验内容计算first集合和follow集合4.实验心得通过上机实验我对文法符号的FIRST集和FOLLOW集有了更深刻的理解，已经熟练的掌握了求解的思想和方法，同时也锻炼了自己的动手解决问题的能力，对编程能力也有所提高。5.实验代码与结果#include#include#includeusingnamespacestd;#defineMAGS50intNONEMAGS=0;stringstrings;/产生式stringVn;/非终结符stringVt;/终结符stringfirstMAGS;/用于存放每个终结符的first集stringFirstMAGS;/用于存放每个非终结符的first集stringFollowMAGS;/用于存放每个非终结符的follow集intN;/产生式个数structSTRstringleft;stringright;/求VN和VTvoidVNVT(STRGp)inti,j;for(i=0;iN;i+)for(j=0;j=A&pi.leftj100)Vn+=pi.leftj;elseif(Vt.find(pi.leftj)100)Vt+=pi.leftj;for(j=0;j=A&pi.rightj100)Vt+=pi.rightj;elseif(Vn.find(pi.rightj)100)Vn+=pi.rightj;voidgetlr(STRGp,inti)intj;for(j=0;j)pi.left=strings.substr(0,j);pi.right=strings.substr(j+2,strings.length()-j);/对每个文法符号求first集stringLetter_First(STRGp,charch)intt;if(!(Vt.find(ch)100)firstVt.find(ch)=ch;returnfirstVt.find(ch)-1;if(!(Vn.find(ch)100)for(inti=0;i100)if(FirstVn.find(ch).find(pi.right0)100)FirstVn.find(ch)+=pi.right0;if(pi.right0=G)if(FirstVn.find(ch).find(G)100)FirstVn.find(ch)+=G;if(!(Vn.find(pi.right0)100)if(pi.right.length()=1)stringff;ff=Letter_First(p,pi.right0);for(inti_i=0;i_i100)FirstVn.find(ch)+=ffi_i;elsefor(intj=0;j100)&(j+1)pi.right.length()sort(TT.begin(),TT.end();stringtt;for(intt=1;tTT.length();t+)tt+=TTt;TT=tt;tt=;for(t=0;t100)FirstVn.find(ch)+=TTt;elsefor(t=0;t100)FirstVn.find(ch)+=TTt;break;returnFirstVn.find(ch);/求每个非终结符的Follow集stringLetter_Follow(STRGp,charch)intt,k;NONEVn.find(ch)+;if(NONEVn.find(ch)=2)NONEVn.find(ch)=0;returnFollowVn.find(ch);for(inti=0;iN;i+)for(intj=0;jpi.right.length();j+)if(pi.rightj=ch)if(j+1=pi.right.length()stringgg;gg=Letter_Follow(p,pi.left0);NONEVn.find(pi.left0)=0;for(intk=0;k100)FollowVn.find(ch)+=ggk;elsestringFF;for(intjj=j+1;jj100)&(jj+1)pi.right.length()sort(TT.begin(),TT.end();stringtt;for(intt=1;tTT.length();t+)tt+=TTt;TT=tt;tt=;for(t=0;tTT.length();t+)if(FF.fin