编译原理实验1文法类型判断

学号L81514034专业网络工程姓名黄武伟实验日期2018/4/11教师签字成绩实验报告【实验名称】文法类型的判断和推导序列的生成【实验目的】输入：一组任意的文法规则和任意符号串输出：相应的Chomsky文法类型和推导【实验要求】（1）文法的输入应简便（不代表产生式少）（2）指明是哪一类Chomsky文法，给出相应的四元组形式（为方便起见，不考虑0型文法）（3）给出清晰的推导序列，并判断输入的符号串是否为该文法的句型以下为判断文法类型代码段：intyi=1,er=1,left=0,right=0;for(i=0;ik;i++){if(m[i].rm[i].l)yi=0;}if(yi==1){printf(该文法满足1型文法\n);若右边字符串大于左边字符串长度则满足1型文法，在此设置一个标志位，当有一个产生式不满足此条件时标志位置0则不满足1型文法。for(i=0;ik;i++){if(m[i].l1)er=0;}if(er==1){printf(该文法满足2型文法\n);在满足1型文法的基础上若左边字符串个数为1则满足2型文法，在此设置一个标志位，当有一个产生式不满足此条件时标志位置0则不满足1型文法。for(i=0;ik;i++){if(m[i].r2)break;//右部字符大于两个则退出if(m[i].r==1&&m[i].a[m[i].pos]=65&&m[i].a[m[i].pos]=90)break;//右部字符为一个非终结符则退出if(m[i].r==2&&(m[i].a[m[i].pos]65&&m[i].a[m[i].pos+1]65)||(m[i].a[m[i].pos]90&&m[i].a[m[i].pos+1]90))break;//右部字符为两个终结符则退出if(m[i].r==2&&m[i].a[m[i].pos]=65&&m[i].a[m[i].pos]=90&&m[i].a[m[i].pos+1]=65&&m[i].a[m[i].pos+1]=90)break;////右部字符为两个非终结符则退出if(m[i].r==2&&m[i].a[m[i].pos]=65&&m[i].a[m[i].pos]=65&&(m[i].a[m[i].pos+1]65||m[i].a[m[i].pos+1]90))left++;//左推倒加1if(m[i].r==2&&(m[i].a[m[i].pos]65||m[i].a[m[i].pos]90)&&m[i].a[m[i].pos+1]=65&&m[i].a[m[i].pos+1]=90)right++;//右推倒加1if(m[i].r==1&&(m[i].a[m[i].pos]65||m[i].a[m[i].pos]90)){left++;right++;}//左右推倒同时加1}if(left==k||right==k)printf(此文法满足3型文法\n);}}源代码如下：#includestdio.htypedefstruct{chara[10];//存储每组产生式intvn_r;//右边非终结符个数intvn_l;//左边非终结符个数intr;//右部符号个数intl;//左部符号个数intpos//右部第一个字符位置}GL;voidmain(){GLm[10];inti=0,j,k;for(i=0;i10;i++){scanf(%s,m[i].a);//输入时注意大写字母表示非终结符，小写字母和数字表示终结符，#结束if(m[i].a[0]=='#')break;}printf(\n);/*for(j=0;j10;j++){printf(%s\n,m[j].a);}*/for(i=0;i10;i++){m[i].vn_r=0;m[i].vn_l=0;m[i].r=0;m[i].l=0;m[i].pos=0;}//初始化结构体内各变量的值i=0;k=0;intthu;//标志位，判断字母在左部还是右部while(m[i].a[0]!='#'){thu=0;for(j=0;j10;j++){if(m[i].a[j]=='\0')break;if(m[i].a[j]=='-'){thu=1;j++;m[i].pos=j+1;//找到各生成式中右边第一个字母位置}else{if(m[i].a[j]=65&&m[i].a[j]=90&&thu==0){m[i].vn_l++;m[i].l++;}if(m[i].a[j]=65&&m[i].a[j]=90&&thu==1){m[i].vn_r++;m[i].r++;}if((m[i].a[j]65&&thu==0)||(m[i].a[j]90&&thu==1&&thu==0))m[i].l++;if((m[i].a[j]65&&thu==1)||(m[i].a[j]90&&thu==1&&thu==1))m[i].r++;}}i++;k++;}/*printf(vn_lvn_rlr\n);for(i=0;ik;i++)printf(%d%d%d%d\n,m[i].vn_l,m[i].vn_r,m[i].l,m[i].r);for(i=0;ik;i++)printf(%d\n,m[i].pos);*/intyi=1,er=1,left=0,right=0;for(i=0;ik;i++){if(m[i].rm[i].l)yi=0;}if(yi==1){printf(该文法满足1型文法\n);for(i=0;ik;i++){if(m[i].l1)er=0;}if(er==1){printf(该文法满足2型文法\n);for(i=0;ik;i++){if(m[i].r2)break;//右部字符大于两个则退出if(m[i].r==1&&m[i].a[m[i].pos]=65&&m[i].a[m[i].pos]=90)break;//右部字符为一个非终结符则退出if(m[i].r==2&&(m[i].a[m[i].pos]65&&m[i].a[m[i].pos+1]65)||(m[i].a[m[i].pos]90&&m[i].a[m[i].pos+1]90))break;//右部字符为两个终结符则退出if(m[i].r==2&&m[i].a[m[i].pos]=65&&m[i].a[m[i].pos]=90&&m[i].a[m[i].pos+1]=65&&m[i].a[m[i].pos+1]=90)break;////右部字符为两个非终结符则退出if(m[i].r==2&&m[i].a[m[i].pos]=65&&m[i].a[m[i].pos]=65&&(m[i].a[m[i].pos+1]65||m[i].a[m[i].pos+1]90))left++;//左推倒加1if(m[i].r==2&&(m[i].a[m[i].pos]65||m[i].a[m[i].pos]90)&&m[i].a[m[i].pos+1]=65&&m[i].a[m[i].pos+1]=90)right++;//右推倒加1if(m[i].r==1&&(m[i].a[m[i].pos]65||m[i].a[m[i].pos]90)){left++;right++;}//左右推倒同时加1}if(left==k||right==k)printf(此文法满足3型文法\n);}}printf(\n四元组为：\nS:);charVn[40];Vn[0]='\0';ints,e1,e2,tag;e1=e2=0;for(i=0;ik;i++){s=0;while(m[i].a[s]!='\0'){tag=0;e1=e2;for(j=0;j=e1;j++){if(Vn[j]==m[i].a[s])tag=1;}if(tag==0){Vn[e1]=m[i].a[s];e2++;}s++;}}Vn[e1+1]='\0';printf(%c\n,Vn[0]);printf(Vn:);for(i=0;ie1;i++){if(Vn[i]=65&&Vn[i]=90)printf(%c,Vn[i]);}printf(\nVt:);for(i=0;ie1;i++){if(Vn[i]40||Vn[i]90)printf(%c,Vn[i]);}printf(\nP:\n);for(i=0;ik;i++)printf(%s\n,m[i].a);}调试如下：【小结与讨论】通过本次编译原理实验课的学习，我对于Chomsky文法类型又有了进一步的认识，并且能够借助于高级程序设计语言完成对于一组给定的产生式判断其相对应的文法类型，因为文法类型的满足是层层递进的，所以在设计程序时用到的是嵌套，此外在判断3型文法是的if判断句用的比较多，由于满足的要求比较多，所以也很容易出错。