安徽大学编译原理实验三正规文法转正规式.docx

《安徽大学编译原理实验三正规文法转正规式.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验三：正规文法转正规式实验日期：2012.4.27教师签字：成绩：实验名称：由正规文法构造正规式实验原理：对于任意一个正规文法G[S],都存在一个正规式与其等价，故可以使用RG构造RE运行结果：/**版权(c)2012PartofRegularGrammartoRegularExpression*文件名zgwftozgs.cpp*Sid:E*AuthorYangxiagnyu*Description2012/04/25*/#include#include#include

2、vector>#include#define_CLR(a)memset(a,0,sizeof(a))#define_lastchar(a)a[(a).length()-1]usingnamespacestd;classgrammar{typedefunsignedcharuchar;typedefmultimap::iteratorMMAPI;typedefpairMMAPE;typedefmap::iteratorMAPI;typedefpair

3、>MMAPRange;private:multimapproduction;//keyisthenonterminalmapsymbolidx;mapsymboltable;mapsymbolmark;intsymbnum;intgenint;stringexpression;voidaddSymbol(uchar_c){if(symbolidx[_c]>0)return;symbnum++;symbolidx[_c]=symbnum;symboltable[symbnu

4、m]=_c;symbolmark[_c]=false;}voidaddProductionPhase2(ucharkeymultimap,string&_tstr){string::iterators,t;for(s=t=_tstr.begin();;s++){if(s==_tstr.end()

5、

6、*s=='

7、'){production.insert(make_pair(keymultimap,string(t,s)));if(s==_tstr.end())break;elset=s+1;}}}structpnode{chart;MMAPIlocation;pnod

8、e(){}}path[1000];voidkillloop(intlen,chart){inti;for(i=0;i<=len;i++)if(path[i].t==t)break;stringtmp("@");for(;i<=len;i++){tmp=tmp.substr(0,tmp.length()-1)+path[i].location->second;}tmp="#Loop#"+tmp.substr(0,tmp.length()-1);production.insert(MMAPE(t,tmp));}stringremoveLoop(intdep,chart)

9、{symbolmark[t]=true;MMAPRangerange=production.equal_range(t);stringexp,exp1;for(MMAPIi=range.first;i!=range.second;i++){if(symbolidx[_lastchar(i->second)]!=0){path[dep].t=t;path[dep].location=i;if(!symbolmark[_lastchar(i->second)]){exp=exp+i->second.substr(0,i->second.length()-1)+"("+r

10、emoveLoop(dep+1,_lastchar(i->second))+")

11、";}else{killloop(dep,_lastchar(i->second));}}else{if(i->second.find("#Loop#")==0)exp1+=i->second.substr(6,i->second.length())+"

12、";elseexp=exp+i->second+"

13、";}}if(!exp.empty())exp=exp.substr(0,exp.length()-1);if(!exp1.empty()){exp1=exp1.substr(0