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

1、精选优质文档-倾情为你奉上实验三：正规文法转正规式实验日期：2012.4.27 教师签字： 成绩： 实验名称： 由正规文法构造正规式实验原理：对于任意一个正规文法GS,都存在一个正规式与其等价，故可以使用RG构造RE运行结果：/* *版权 (c) 2012 Part of Regular Grammar to Regular Expression *文件名zgwftozgs.cpp*Sid: E *AuthorYangxiagnyu *Description 2012/04/25 */ #include<iostream>#include<cstdio>#include

2、<map>#include<string>#include<vector>#include<algorithm>#define _CLR(a) memset(a,0,sizeof(a) #define _lastchar(a) a(a).length()-1using namespace std;class grammartypedef unsigned char uchar;typedef multimap<uchar,string>:iterator MMAPI;typedef pair<int,string> MMA

3、PE;typedef map<int,uchar>:iterator MAPI;typedef pair<MMAPI,MMAPI> MMAPRange;private:multimap<uchar,string> production;/key is the nonterminalmap<uchar,int> symbolidx;map<int,uchar> symboltable;map<uchar,bool> symbolmark;int symbnum;int genint;string expression;voi

4、d addSymbol(uchar _c)if(symbolidx_c>0)return;symbnum+;symbolidx_c=symbnum;symboltablesymbnum=_c;symbolmark_c=false;void addProductionPhase2(uchar keymultimap,string &_tstr)string:iterator s,t;for(s=t=_tstr.begin();s+)if(s=_tstr.end()| *s='|' )production.insert(make_pair(keymultimap,st

5、ring(t,s);if(s=_tstr.end()break;else t=s+1;struct pnodechar t;MMAPI location;pnode()path1000;void killloop(int len,char t)int i;for(i=0;i<=len;i+)if(pathi.t=t)break;string tmp("");for(;i<=len;i+)tmp=tmp.substr(0,tmp.length()-1)+pathi.location->second;tmp="#Loop#"+tmp.sub

6、str(0,tmp.length()-1);production.insert(MMAPE(t,tmp);string removeLoop(int dep,char t)symbolmarkt=true;MMAPRange range=production.equal_range(t);string exp,exp1;for(MMAPI i=range.first;i!=range.second;i+)if(symbolidx_lastchar(i->second)!=0)pathdep.t=t;pathdep.location=i;if(!symbolmark_lastchar(i-

7、>second)exp=exp+i->second.substr(0,i->second.length()-1)+"("+removeLoop(dep+1,_lastchar(i->second)+")|"elsekillloop(dep,_lastchar(i->second);elseif(i->second.find("#Loop#")=0)exp1+=i->second.substr(6,i->second.length()+"|"else exp=exp+i

8、->second+"|"if(!exp.empty()exp=exp.substr(0,exp.length()-1);if(!exp1.empty()exp1=exp1.substr(0,exp1.length()-1);exp1="("+exp1+")*"if(!exp.empty()&&!exp1.empty()exp="|("+exp+")"symbolmarkt=false;exp1+=exp;return exp1;public:grammar()genint=

9、127;symbnum=0;production.clear();symboltable.clear();symbolidx.clear();symbolmark.clear();bool AddProduction(string rawstr)string _tstr(rawstr.begin()+3,rawstr.end();uchar keymultimap=rawstr0;addSymbol(keymultimap);addProductionPhase2(keymultimap,_tstr);return true;void Grammar2Expression()expressio

10、n=removeLoop(0,'S');void AnsOutput()cout<<"S="<<expression<<endl;void ConsoleOutput(int idx)switch(idx)case 0:cout<<"Regular Grammar to Regulat Expression (Author:Yangxiangyu Data:2012-04-25)n"cout<<"Assume all the input are legal.n"break;case 1:cout<<"Number of productionn"break;case 2:cout<<"Productionsn"break;case 3:cout<<"Regular Expression"<<endl;break;int main()ConsoleOutput(0);grammar grm;string str;int nofp;ConsoleOutput(1);cin>>n