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

实验三：正规文法转正规式实验日期：2012.4.27 教师签字： 成绩： 实验名称： 由正规文法构造正规式实验原理：对于任意一个正规文法GS,都存在一个正规式与其等价，故可以使用RG构造RE运行结果：/* *版权 (c) 2012 Part of Regular Grammar to Regular Expression *文件名zgwftozgs.cpp*Sid: E10914012 *AuthorYangxiagnyu *Description 2012/04/25 */ #include#include#include#include#include#include#define _CLR(a) memset(a,0,sizeof(a) #define _lastchar(a) a(a).length()-1using namespace std;class grammartypedef unsigned char uchar;typedef multimap:iterator MMAPI;typedef pair MMAPE;typedef map:iterator MAPI;typedef pair MMAPRange;private:multimap production;/key is the nonterminalmap symbolidx;map symboltable;map symbolmark;int symbnum;int genint;string expression;void addSymbol(uchar _c)if(symbolidx_c0)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,string(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(;isecond;tmp=#Loop#+tmp.substr(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-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-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=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()expression=removeLoop(0,S);void AnsOutput()coutS=expressionendl;void ConsoleOutput(int idx)switch(idx)case 0:coutRegular Grammar to Regulat Expression (Author:Yangxiangyu Data:2012-04-25)n;coutAssume all the input are legal.n;break;case 1:coutNumber of productionn;break;case 2:coutProductionsn;break;case 3:coutRegular Expressionnofp;Console