实验3+由正规文法构造正规式

编译原理实验报告实验名称由正规文法构造正规式实验时间2023年6月5日星期三院系计算机 安徽大学Author:idiot10试验目的输入：任意的正规文法。输出：相应的正规式。实验原理3型文法〔正那么文法，线性文法〕如果对于某文法G，P中的每个规那么具有以下形式： U::=T或U::=WT其中T∈VT；U,W∈VN，那么称该文法G为左线性文法。如果对于某文法G，P中的每个规那么具有以下形式： U::=T或U::=TW其中T∈VT；U,W∈VN，那么称该文法G为右线性文法。左线性文法和右线性文法通称为3型文法或正那么文法，有时又称为有穷状态文法，简写为RG。按照定义，对于正那么文法应用规那么时，单个非终结符号只能被替换为单个终结符号，或被替换为单个非终结符号加上单个终结符号，或者被替换为单个终结符号加上单个非终结符号。3型文法所确定的语言为3型语言L3，3型语言可由确定的有限状态自动机来识别。程序设计语言的单词可由正那么文法产生，例如，标识符的定义可由正那么文法描述如下：<标识符>::=<字母>/<标识符><字母>/<标识符><数字>显然，该文法描述了以字母开头的字母数字串的集合。现在要引入另一种适合于描述单词的表示法——正那么表达式。正那么表达式又称为正那么式，每个正那么表达式描述的集合称为正那么集。之所以采用正那么表达式来描述，主要基于以下几点原因：词法规那么简单，无需上下文无关文法那样严格的表示法，用正那么式表示法来理解被定义的符号集合比理解由重写规那么集合定义的语言更为容易；从正那么式构造高效识别程序比上下文无关文法更容易；可以从某个正那么式自动地构造识别程序，它可以识别用该正那么式表示的字符串集合中的字符串，从而减轻后面要介绍的词法分析时的工作量。可用于其他各种信息流的处理，例如，已经应用于某些模式识别问题、文献目录检索系统以及正文编辑程序等。正那么表达式和正那么集设有字母表∑。∑上的正那么表达式和它所表示的正那么集递归地定义如下：ε和Φ都是∑上的正那么表达式，它们所表示的正那么集分别为{ε}和Φ，其中ε是空串，任意的a∈∑是正那么表达式，它所表示的正那么集是{a}；如果e1和e2是∑上的任意的正那么表达式，且分别表示的正那么集为L〔e1〕和L〔e2〕，那么：e1/e2也是正那么表达式，表示的正那么集为L〔e1/e2〕＝L〔e1〕∪L〔e2〕。e1e2也是正那么表达式，表示的正那么集为L〔e1e2〕＝L〔e1〕L〔e2〕。〔e1〕*也是正那么表达式，表示的正那么集为L〔〔e1〕*〕＝L〔e1〕*。定义中〔1〕和〔2〕定义了原子正那么表达式，而〔3〕那么说明字母表∑上的正那么表达式可由原子正那么表达式或较简单的正那么表达式通过联合、连接与闭包运算构成一般的正那么表达式。正那么表达式的性质如果两个正那么表达式e1和e2表示的正那么集相同，即值相等，那么称它们是等价的。记为e1＝e2。正那么表达式与正那么文法的关系一个正那么表达式的值是正那么集，它是正那么语言的另一种表示法。不难看出，除了符号Φ外，一个正那么表达式的含义类似于正那么文法的一个非终结符号规那么右部的含义。例如，对于<数字>::=0/1/2/…/9，由非终结符数字所产生的字符串集合与正那么表达式0/1/2/…/9所定义的字符串集合是相同的。正那么集Φ，它对应一个不包含任何句子的语言，引进的目的主要是为了理论上的完备性。3..实验内容由正规〔那么〕文法构造正规〔那么〕式4.实验心得通过实验明确了正规文法构造正规式的方法，对正规式及正规文法有了进一步的认识欲了解5.实验代码与结果测试数据1：A->xBA->yB->xBB->yA#测试数据2S->aAS->aA->aAA->dAA->aA->d#测试数据3S->aAS->cBS->aA->aBA->bBA->bB->cBB->bAB->c#源码：#include<iostream>#include<string>usingnamespacestd;stringss[30]={"",""};stringdww[15]={"",""};stringsnt="";stringdst[8]={"",""};stringdonesnt="";intnum=0;intdstl=0;intdwl=0;voidsetdst(){ for(inti=0;i<8;i++) dst[i]=""; dstl=0;}voidgetsnt(){ for(inti=0;i<num;i++) { if(snt.find(ss[i].at(0))==-1) snt+=ss[i].at(0); }}stringdispose1(stringtemp1) { stringdf=""; for(inti=0;i<temp1.size();i++) { intk=(int)temp1.at(i); stringft=ss[k].substr(3); if(i==0) df+=ft; else { df+='|'; df+=ft; } ss[k]=""; } returndf;}stringdispose3(stringtemp3){ stringdf=""; for(inti=0;i<temp3.size();i++) { intk=(int)temp3.at(i); stringtemp=ss[k].substr(3); stringsttr=temp.substr(0,temp.size()-1); if(i==0) df+=sttr; else { df+='|'; df+=sttr; } ss[k]=""; } returndf;}voiderass(){ for(inti=0;i<30;i++) { if(ss[i]=="") { for(intj=i+1;j<30;j++) { if(ss[j]!="") break; } ss[i]=ss[j]; ss[j]=""; } if(i==num) { ss[num]=""; break; } }}voidhandle(stringcs,stringssnot){ charcc=cs.at(0); stringtemp1=""; stringtemp2=""; stringtemp3=""; inti=0; boolflagg=false; while(!flagg) { flagg=true; for(i=0;i<num;i++) { for(intj=0;j<donesnt.size();j++) { if(ss[i].find(donesnt.at(j))!=-1) { flagg=false; boolflag=false; stringsk=ss[i]; for(intk=0;k<dwl;k++) { if(dww[k].at(0)==donesnt.at(j)) { stringdwtemp=dww[k].substr(3); if(!flag) { intlk=ss[i].find(donesnt.at(j)); ss[i].replace(lk,1,dwtemp); flag=true; } else { ss[num]=sk; intlk=ss[num].find(donesnt.at(j)); ss[num].replace(lk,1,dwtemp); num++; } } } } } } } setdst(); for(i=0;i<num;i++) { stringtemp=""; if(ss[i].at(0)==cc) { temp=ss[i].substr(3); if(temp.find(cc)!=-1) temp3+=i; else { boolflag=false; for(intj=0;j<ssnot.size();j++) { chardd=ssnot.at(j); if(temp.find(dd)!=-1) { temp2+=i; dst[dstl]=ss[i]; dstl++; ss[i]=""; flag=true; j=ssnot.size(); } } if(!flag) temp1+=i; } } } i=temp1.size(); num-=i; i=temp2.size(); num-=i; i=temp3.size(); num-=i; i=0; stringdis1str=""; stringdis2str=""; stringtemm=""; if(num>0) { dis1str="("; dis1str+=dispose1(temp1); dis1str+=")"; } else { if(temp3.size()==0) dis1str=dispose1(temp1); else { dis1str="("; dis1str+=dispose1(temp1); dis1str+=")"; } } temm+=dispose3(temp3); if(temp3.size()==0) dis2str=""; else { if(temm.size()==1) dis2str=temm; else { dis2str="("; dis2str+=temm; dis2str+=")"; } dis2str+="*"; } if(dis1str=="()") dis1str=""; dis2str+=dis1str; stringarrow="->"; arrow+=dis2str; dww[dwl]+=cs; dww[dwl]+=arrow; dwl++; for(i=0;i<dstl;i++) { dww[dwl]=dst[i]; dwl++; } erass();}intmain(){ cout<<"输入文法以#结束"<<endl; inti=0; for(;i<15;i++) { stringtem="";