搜索
编译原理实验报告实验名称Chomsky文法类型判断实验时间2013年10月29日院系计算机科学与电子技术系班级11计算机软件学号JV114001JV114095JP114065姓名唐茹韩强强徐思维1.试验目的：1.熟练掌握四种文法类型的概念及区别。2.设计一个Chomsky文法类型判别器，判断0型、1型、2型和3型文法。2.实验原理：1.设G=(Vn,Vt,P,S)，如果它的每个产生式α-β是这样一种结构：α∈(Vn∪Vt)*且至少含有一个非终结符，而β∈(Vn∪Vt)*，则G是一个0型文法。2.设G=(Vn,Vt,P,S)为一文法，若P中的每一个产生式α-β均满足|β|=|α|,仅仅S-ԑ除外，则文法G是1型或上下文有关的。3.设G=(Vn,Vt,P,S)为一文法，若P中的每一个产生式α-β均满足：α是一个非终结符，β∈(Vn∪Vt)*，则此文法称为2型的或上下文无关的。4.设G=(Vn,Vt,P,S)为一文法，若P中的每一个产生式的形式都是A-aB或A-a，其中A和B都是非终结符，a∈Vt*,则G是3型文法或正规文法。5.4个文法类的定义是逐渐增加限制的，因此可采用自顶向下的算法。3.实验内容：1.程序清单如下：#includestdafx.h#includeiostream#includestringusingnamespacestd;typedefstructCSS//定义一个产生式结构体{stringleft;//定义产生式的左部stringright;//定义产生式的右部}CSS;boolZero(CSS*p,intn)//判断0型文法{inti,j;for(i=0;in;i++)//循环n次，即遍历所有产生式{for(j=0;jp[i].left.length();j++)//遍历产生式左部每一个字符{if(p[i].left[j]='A'&&p[i].left[j]='Z')//判断字符是否是非终结符break;}if(j==p[i].left.length()){cout该文法不是0型文法endl;return0;break;}}if(i==n)return1;//如果每个产生时都能找到非终结符}boolFirst(CSS*p,intn)//判断1型文法{inti;if(Zero(p,n))//先判断是否是0型文法{for(i=0;in;i++){if((p[i].left.length()p[i].right.length())&&p[i].right.length()!=NULL)//判断产生式左部长度是否大于右部break;}if(i==n)return1;else{cout该文法是0型文法endl;return0;}}elsereturn0;}boolSecond(CSS*p,intn)//判断2型文法{inti;if(First(p,n))//同上，先判断低级文法是否成立{for(i=0;in;i++)//同上，遍历所有文法产生式{if((p[i].left.length()!=1)||!(p[i].left[0]='A'&&p[i].left[0]='Z'))//判断产生式左部长度是否为一，左部第一个是否是非终结符break;}if(i==n)return1;else{cout该文法是1型文法endl;return0;}}elsereturn0;}voidThird(CSS*p,intn)//判断3型文法{inti;if(Second(p,n))//同上，先判断是否是2型文法{for(i=0;in;i++)//同上，遍历文法所有的产生式{if((p[i].right.length()==0)||(p[i].right.length()=3)||(p[i].right[0]='A'&&p[i].right[0]='Z'))//判断产生式右部字符个数是否在12之间，判断右部第一个字符是否是非终结符break;}if(i==n){for(i=0;in;i++){if(p[i].right.length()==2){if(!(p[i].right[1]='A'&&p[i].right[1]='Z'))break;}}if(i==n){cout该文法属于3型文法endl;}elsecout该文法属于2型文法endl;}elsecout该文法属于2型文法endl;}elsecout结束endl;}voidmain(){inti,j,n;stringinput;cout请输入文法产生式个数N：;cinn;CSS*p=newCSS[n];//初始化产生式数组for(i=0;in;i++)//输入产生式数组{input.erase();//清除cininput;//输入for(j=0;jinput.length();j++)//改变输入数据的形式{if(input[j]=='-'){p[i].left=input.substr(0,j);p[i].right=input.substr(j+2,input.length());}}}Third(p,n);//调用文法类型判断，自顶向下system(pause);}2.程序运行结果：测试用例1：7S-aSBES-aBEEB-BaB-abbB-bbbE-beeE-ee运行结果：测试用例2：1型文法：7S-aSBES-aBEEB-BEaB-abbB-bbbE-beeE-ee运行结果：测试用例3：2型文法：9S-aABA-bBS-bBB-bBS-aB-bA-aAB-aA-aS运行结果：测试用例4：3型文法：9S-aAA-bBS-bBB-bBS-aB-bA-aAB-aA-aS运行结果见下页：4.实验心得：通过Chomsky文法类型判断实验的实际操作，知道和理解了该理论在计算机中是怎样执行的，对该理论在实践中的应用有深刻的理解。在这次课程设计中，我们组就是按照实验指导的思想来完成。加深了理解了文法规则的不同定义形式，培养了实践动手能力和程序开发能力。压缩文法等价变换2007-12-2813:30:33|分类：默认分类|举报|字号订阅#includeiostream#includevectorusingnamespacestd;bools_1(charid,char*left_2,charright_2[30][50],intn,int*p);bools_2(charid,char*left_2,charright_2[30][50],intn,int*p);boolfind(vectorchar&,char);boolend();voidadd_letter(vectorchar&,char);voidhelp();//压缩文法等价变换voidcompress(charid,charleft_2[],charright_2[30][50],intsz,intp[]){do{boolc1=s_1(id,left_2,right_2,sz,p);boolc2=s_2(id,left_2,right_2,sz,p);if(c1&&c2)break;}while(1);//是否继续判断条件1或2。由c1,c2的返回值决定}voidmain(){help();charleft_1[30],right_1[30][50],left_2[30],right_2[30][50];intp[30]={0};intcount,i,j;charid;do{cout请输入您的文法中所包含的规则数endl;cincount;cout输入文法的识别符:endl;cinid;for(i=0;icount;i++){cout请输入规则i+1的左端：;cinleft_1[i];cout请输入规则i+1的右端：;cinright_1[i];}intsize=0;for(i=0;icount;i++){intpos=0;left_2[size]=left_1[i];for(j=0;jright_1[i][j]!='\0';j++){if(right_1[i][j]=='|'){right_2[size][pos]='\0';pos=0;left_2[++size]=left_1[i];}elseright_2[size][pos++]=right_1[i][j];}right_2[size][pos]='\0';size++;}cout展开输出文法endl;for(i=0;isize;i++)coutleft_2[i]::=right_2[i]endl;cout下面进行压缩文法等价变换endl;compress(id,left_2,right_2,size,p);cout压缩后的结果：endl;for(i=0;isize;i++)if(p[i]!=3)coutleft_2[i]::=right_2[i]endl;}while(!end());}//查找加了标记的非终结符boolfind(vectorchar&p,charm){for(inti=0;p[i]!='\0';i++)if(p[i]==m)returntrue;returnfalse;}boolend(){charm;cout你想退出吗?[Y/N];cinm;if(m=='y'||m=='Y')returntrue;elsereturnfalse;}//将加了标记的非终结符放到p中voidadd_letter(vectorchar&p,charm){intlen=p.size();for(inti=0;ilen;i++)if(m==p[i])return;p.push_back(m);}//判断条件1bools_1(charid,char*left_2,char(*right_2)[50],intn,int*p){intnew_p[30],j;for(intk=0;kn;k++)new_p[k]=p[k];//new_p[k]将上一次规则的标记存储起来，以便下面用，看条件1是否有改动vectorcharlt;add_letter(lt,id);//标识符放入lt中do{intlen=lt.size();for(inti=0;in;i++)if(p[i]==0){if(find(lt,left_2[i])==true){p[i]=1;//加标记intm=0;for(;right_2[i][m]!='\0';)m=m+1;intlength=m;//规则右部的长度stringtemp=right_2[i];//将规则的右部暂时存在temp中for(j=0;jlength;j++)if(isalpha(temp[j])&&isupper(temp[j]))//寻找大写字母{add_letter(lt,temp[j]);//将新找到的字母放进数组}}}if(len==lt.size())break;//lt中没有新添加的非终结符则跳出}while(1);for(j=0;jn;j++)//扫描所有规则看是否有未加标记的{switch(p[j]){case0:p[j]=3;break;//没有加标记的规则将其p[]设置为3case1:break;case3:break;}}cout判断条件1endl;//for(intx=0;xn;x++)coutp[k];//coutendl;for(intl=0;ln;l++)//若条件1有改动，则返回falseif(p[l]!=new_p[l])returnfalse;returntrue;}//判断条件2bools_2(charid,cha