编译原理实验文法的判断

传播传播优秀％rd版文档・希垫对您有帝助・可双击去除!传播传播优秀％rd版文档・希垫对您有帝助・可双击去除!传播传播优秀％rd版文档・希垫对您有帝助・可双击去除!0/140/14文法类型的判断和推导序列的生成目录TOC\o"1-5"\h\z\o"CurrentDocument"一、 实验名称 2\o"CurrentDocument"二、 实验目的 2\o"CurrentDocument"三、 实验原理 2\o"CurrentDocument"1、 文法G進义为四元组(Vn,Vt,RS) 2\o"CurrentDocument"2、 文法类型的判断 2\o"CurrentDocument"四、 实验思路 2\o"CurrentDocument"2、接受产生式 3\o"CurrentDocument"2、 文法类型的判断 3\o"CurrentDocument"3、 将文法以四元组形式输岀 4\o"CurrentDocument"五、 实验小结 4\o"CurrentDocument"2、文法类型的判断条件 4\o"CurrentDocument"2、 产生式的存储问题 5\o"CurrentDocument"3、 文法以四元组形式输出问题 5\o"CurrentDocument"六、 附件 5\o"CurrentDocument"1、 源代码 5\o"CurrentDocument"2、 运行结果截图 10一、 实验名称文法类型的判断和推导序列的生成二、 实验目的输入：一组任意的文法规则和任意符号串。输出：相应的Chomsky文法类型和推导。三、 实验原理1、 文法G定义为四元组(Vn,Vt,P,S)其中Vn为非终结符(或语法实体，或变量)集：Vt为终结符集；P为规则(a->B)的集合，ae(VnUVt)*且至少包含一个非终结符，PG(VnUVt)*：Vn,Vt和P是非空有穷集。S称作识别符或开始符，它是一个非终结符，至少要在一条规则中作为左部出现。2、 文法类型的判断设G=(Vn,Vt,P,S)为一文法，若P中的每一个产生式a->B均满足I31>=1a|,仅仅S->e除外，则文法G是1型或上下文有关的。设G=(Vn,Vt,P,S),若P中的每一个产生式a->P满足：a是一个非终结符，Pe(VnUVt)*,则此文法称为2型的或上下文无关的。设G=(Vn,Vt,P,S),若P中的每一个产生式的形式都是A->aB或A->a,其中A和B都是终结符，aGVt*,则G是3型文法或正规文法。四、 实验思路本实验采取C卄来完成，用大写字母A到Z表示非终结符，小写字符d到z表示终结符。传播优秀传播优秀Word版文档.席垫对您有帝助.可双击去除!传播优秀传播优秀Word版文档.席垫对您有帝助.可双击去除!1、 接受产生式首先建立一个结构体siyuanzu,其成员有非终结符集合数组Vn,终结符集合数组Vt以及产生式集合数组rule,通过函数input来接受从键盘输入的产生式，并且存储于string类字符吊数组rule中。函数input实现接受产生式功能的思路为：先确定要输入的产生式数Hn,用for循环实现产生式的存储。2、 文法类型的判断函数Grammer实现判断文法类型的功能并且输出文法的类型。其实现功能的思路为：对rule数组中每一个产生式进行判断，以中的“-”作为判断条件,将产生式分为左部和右部分别计算左部和右部的长度。若youb小于左部则不是1型文法。输出0型文法；若右部大于或等于左部，则继续判断。判断文法是否为2型文法，经过a步骤的执行，若文法为1型文法，只需在此基础上判断文法的左部是否只有一个非终结符。通过判断条件zuo=l&&,<=a.rule[i][zuo~l]&&a.rule[i][zuoT]〈二'Z'确定是否为2型文法，若不满足判断条件则为1型文法，进行输出，若满足则继续判断。判断文法是否为3型文法，经过b步骤的执行，若文法为2型文法，只需在此基础上判断文法的右部是否为aB或<1形式或者是Ba或a形式。通过判断条件一((you==2)&&(a.ruletiZ[num+l]>=,a')&&(a.ruleCiZ[num+1]〈二'z')&&(a.rule[i][num+2]>=,A')&&(a.rule[i][num+2]〈二'ZJ))II((you=l)&&(a.rule[i][num+1]>=，a')&&(a.rule[i][num+gz'))判断是否满足aB或a形式,通过判断条件二((you=2)&&(a.rule[i][num+l]>二'A')&&(a.rule[i][num+1]〈二'Z')&&(a.rule[iZ[num+2]>='a)&&(a.ruleCiZ[num+2]〈二'z'))丨丨((you==l)&&(a.ruleliZ[num+1]>=，a')&&(a.rule[i][num+l]<=,z'))判断是否满足Ba或a形式。若所有产生式同时满足判断条件一或者同时满足判断条件二，则为3型文法进行输出。否则为2型文法进行输出。3、将文法以四元组形式输出函数output实现输出文法四元组形式的功能。具体思路为：将存放产生式的string类数组rule—分为二，用x数组存放rule中所有的大写字母即非终结符，用y数组存放rule中所有的小写字母即终结符。b.用双重for循环给x和y数组中重复的字符标记，重复的字符全部赋值为“f”C.将x数组中非“！”元素赋值给非终结符集Vn,将y数组中非“！”元素赋值给终结符集Vt。按照格式分别输出非终结符集Vn,终结符集Vt,产生式P以及开始符S。五、实验小结我运用C++解决了此次实验的文法类型判断的问题，在实际解决问题的过程中，主要遇到了以下儿个问题：1、 文法类型的判断条件《编译原理》书本上给出了儿类文法类型的定义，但是在实际的解决问题过程中，需要将书本上给的判断条件转换为C++语言中的判断条件，这需要对文法类型的定义有很好的理解。我通过判断产生式右部是否大于等于左部确定1型文法，在此基础上判断产生式左部是否为一个非终结符确定2型文法，最后在2型文法的基础上判断产生式是否全部满足aB或a形式或者是Ba或a形式确定3型文法。最终解决了文法类型判断条件的问题。2、 产生式的存储问题实验要求最少输入五条产生式，我最初是选择用C语言解决存储问题，但是发现C语言中对于字符串的处理不够灵活，于是选择了C++来解决。C++中可以用string类型来定义字符串数组，并且可以通过length函数求每个字符吊的长度，这样给每条产生式的判断都带来了极大的便捷。3、 文法以四元组形式输出问题实验需要输出文法的四元组，即需要输出非终结符集Vn,终结符集Vt,产生式P以及开始符S,由于我将产生式存储在string类数组rule中，因此，需要将rule中的元素分为两类，大写字母为非终结符，小写字母为终结符。但是分好类的数组存在元素重复的问题，我通过一个双重for循环给重复元素标记为“！”，再将非“！”元素赋值给字符数组Vn和Vt,解决了元素重复问题。最后需要安排一下输出的格式即解决了这个问题。通过本次实验，我深入的了解了文法类型的判断，对于文法类型的判断也更加的熟练。同时，对于文法的四元组的定义更加的熟悉，并且对于运用C++解决编译原理的问题有了一定的基础。六、附件1、源代码nclude〈iost:reain>传播传播优秀％rd版文档・希垫对您有帝助・可双击去除!传播传播优秀％rd版文档・希垫对您有帝助・可双击去除!}}#include〈string>usingnamespacestd;structsiyuanzu{charVn[50];charVt[50];stringrule[20];};intinput(siyuanzu*a){intn,i;cout«"请输入产生式数目：";cin>>n;cout<</，请输入产生式:\n";for(i=0;i<n;i++)cin>>(*&)・ruleLi];returnn;}voidoutput(siyuanzua,intn){inti,j,length,kl=0,k2=0,ml=0,m2=0;charx[50],y[50];for(i=0;i<n;i++){length=a・ruleLi].length();for(j二0;j<length;j++){if(a.rule[i][j]!=,-'&&a.rule[i][j]!=,>?){if(a.ruleLiZ[j]>二'A'&&a.ruleEiZ[j]〈二'Z‘){x[kl]=a.rule[i][j];kl++;}else{y[k2]=a.ruleLi][j];k2++;}}}}for(i=0;i<kl-l;i++)for(j=i+l;j<kl;j++)if(x[i]=x[j])x[jU!‘；}for(i=0;i<kl;i++){if(x[i]U!'){&Vn[ml]=x[i];ml++;}}for(i=0;i<k2-l;i++)for(j=i+l;j<k2;j++){if(y[il==y[jl)y[j]6;}for(i=0;i<k2;i++){if(y[i]U!'){a.Vt[m2]=y[i];m2++;}}cout«/z四元组G二(Vn,Vt,P,S)z，«endl;cout«"其中非终结符Vn二{";for(i二0;i<ml-l;i++)cout«a.Vn[i]〈<",”；cout<<a・Vn[mlT];cout<</，}";cout<<endl;c°ut«"终结符vt=r；for(i二0;i<m2~l;i++)cout«a.Vt[i]«z，,“；cout<<a.Vt[m2T];cout<</，}";cout<<endl;cout«"P由下列产生式组成:，，«endl;for(i=0;i<n;i++)cout«a・rule[i]«endl;cout〈<"开始符为:Sz/«endl;voidGrammer(siyuanzua,intn){inti,j,length,num,zuo,you;charc;for(i=0;i<n;i++)num=0;length=a・rule[i]・length();for(j二0;j<length;j++){c=a.rule[i][j];num++;辻(c二二'-')break;zuo=num-l;you二length-(num+l);if(you>=zuo)continue;elsebreak;}if(i==n)for(i=0;i<n;i++){num二0;length二a・rule[i]・length();for(j=0;j<length;j++)c=a.rule[i][j];num++;辻(d)break;zuo=num-l;辻(zuo==l&&，A*<=a.rule[i][zuo-l]&&a.rule[i][zuoT]〈二'Z')continue;elsebreak;if(i==n)for(i=0;i<n;i++)传播传播优秀％rd版文档・希垫对您有帝助・可双击去除!}}传播传播优秀％rd版文档・希垫对您有帝助・可双击去除!}}num二0;length二a・ruleTi].length();for(j=0;j<length;j++){c=a.ruleti][j];num++;辻(C='-')break;}you二length-(num+1);if(((you—2)&&(a.rule[i][num+1]>二'a)&&(a.rule[i][num+l]<=，z')&&(a.rule[i][num+2]>=，A')&&(a.rule[iZ[num+2]<=，Z，))II((you==l)&&(a.rule[i~[num+l]>二'a)&&(a.rule[i][num+lj<=,z')))continue;elsebreak;}if(i==n)cout«，z文法类型:3型文法，，«endl;else{for(i=0;i<n;i++){num=0;length=a・rule[i]・length();for(j=0;j<length;j++){c=a.rule[i][j];num++;if(c亠)break;}you=length-(num+1);辻(((you—2)&&(a.rule[i][num+1]>二'A')&&(a.rule[i][num+1]<=，Z')&&(a.rule[i][num+2]>=‘a*)&&(a.rule[i][num+2]〈二'z，))II((you==l)&&(a.rule[i~[num+1]>='a)&&(a.ruletiZ[num+1[〈二'z')))continue;elsebreak;传播优秀传播优秀Word版文档.席垫对您有帝助.可双击去除!}}传播优秀传播优秀Word版文档.席垫对您有帝助.可双击去除!}}if(i=n)cout«"文法类型：3型文法"〈endl;elsecout«"文法类型：2型文法〃《endl;}}elsecout«，/文法类型：1型文法，z«endl;}elsecout«，z文法类型：0型文法/，«endl;}intmain(){intn,r;siyuanzua;while(1){cout«，/ 文法类型判断(E21414020陈国柱) "«endl;cout«，/ 1.输入产生式z，«endl:cout«，z 2.输出文法类型及四元组〃《endl;cout«z， 3.结束"<〈endl;cout«，z输入功能号：，z«endl;cin»r;if(r>3r<l){do{cout«，/输入有误，重新输入z/«endl;cin»r;}while(r<=3&&r>=l);}switch(r){case1:n=input(&a);break;case2:Grammer(a,n);output(a,n);break;case3：exit(0);break;default：break;}}return0;2、运行结果截图传播优秀传播优秀Wxd版文档•希塑对您有帮助.可双击去除!传播优秀传播优秀Wxd版文档•希塑对您有帮助.可双击去除!a.实验开始图-文法类型判断（E21414020陈国栏〉 •输入产生式•输岀文法类型及四元组3.结束输入功罷号：b.非1型文法 文法类型丸断（E21414020陈国柱）输入产生式2•输出文法类型及四元组3.结束输入功能号：1请输入产生式数目：5请输入产生式：S-〉ABCDA->aAA-〉aB->bCD->bS),A,文法类型判断（E214140201.输入产生式•输出文法类型及四元组S),A,文法类型判断（E214140201.输入产生式•输出文法类型及四元组•结束B,C,D}陈国击ab>,3口>>-文-一DXIABCFF,s薦法,P={MT'vtvn6}3入型紿a,H:0(v结謀型匸终vt尸类缓非符卩法元中结硏2文四其烫FrfC.1型文法| 丈法类峑判析（E21414020陈国栏）1-输入产生式2•输出文法类型及四元组3.结束徐入功能号：1请输入产生式数目：