计算first集follow集.docx

计算first集follow集编译原理实验报告实验名称计算first集合和follow集合实验时间2016年6月8日院系计算机科学与技术班级计算机科学与技术(1)班学号姓名 :输入:任意的上下文无关文法。输出:所输入的上下文无关文法一切非终结符的first集合和follow集合。:设文法G[S]=(VN,VT,P,S),则首字符集为:FIRST(α)={a|αaβ,a∈VT,α,β∈V*}。若αε,ε∈FIRST(α)。由定义可以看出,FIRST(α)是指符号串α能够推导出的所有符号串中处于串首的终结符号组成的集合。所以FIRST集也称为首符号集。设α=x1x2…xn,FIRST(α)可按下列方法求得:令FIRST(α)=Φ,i=1;若xi∈VT,则xi∈FIRST(α);若xi∈VN;①若εFIRST(xi),则FIRST(xi)∈FIRST(α);②若ε∈FIRST(xi),则FIRST(xi)-{ε}∈FIRST(α);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集可按下列方法求得:对于文法G[S]的开始符号S,有#∈FOLLOW(S);若文法G[S]中有形如B→xAy的规则,其中x,y∈V*,则FIRST(y)-{ε}∈FOLLOW(A);若文法G[S]中有形如B→xA的规则,或形如B→xAy的规则且ε∈FIRST(y),其中x,y∈V*,则FOLLOW(B)∈FOLLOW(A);:输入格式: 每行输入一个产生式,左部右部中间的→用空格代替。 非终结符等价于大写字母 ^表示空 输入到文件结束,或用00结尾。以编译原理(清华大学第二版)(96页):#include<iostream>#include<string>#include<map>#include<set>#include<vector>usingnamespacestd;charl;stringr; multimap<char,string>sentence;//存储产生式multimap<string,char>senRever;//产生式逆转set<char>ter; //非终结符集合map<char,bool> toEmpty; //非终结符能否推出空boolflag;set<char>fir; //保存单个元素的first集set<char>follow;//保存单个元素的follow集vector<string>rightSide;//右部charBegin;boolcapL(charc)//字母是否大写{ if(c<='Z'&&c>='A') returntrue; returnfalse;}boolCapLString(strings)//大写字符串{ for(inti=0;i<();i++){ if(!capL(s[i])){ returnfalse; } } returntrue;}boolisToEmpty(charch)//判断终结符能否推出空{ boolflag; flag=false; multimap<char,string>::iteratormIter=(ch); t=(ch); for(inti=0;t;++i,++mIter){ if(mIter->second=="^"){ returntrue; } elseif(CapLString(mIter->second)){ strings(mIter->second); boolflag2=true; for(intj=0;j<();j++){ if(!isToEmpty(s[j])||s[j]==ch){ flag2=false; break; } } if(flag2){ //右部全为终结符,全能推出空 returntrue; } } }// } returnfalse;}voidgetFirst(charch,set<char>&First) //求单个元素的FIRST集{ mu