编译原理实验一CHOMSKY文法类型

编译原理实验告实名

文法型断实时

年10月29院

计机学电技系班

算软学

JP114065姓

唐

韩强

徐维

试验目的：熟设计一个Chomsky文法断0型、、型和实验原理：G=(Vn,Vt,P,S)，如果它的每个产生α->βα(Vn∪*而β∈∪*则个0若P式α->β|βα仅法G是若P式α->βα，∈∪*为2型的或上下文设若中或，其中A和B都是非，∈*则G是实验内容：

#include"stdafx.h"#include<iostream>#include<string>usingnamespacestd;typedefstructCSS定义一个产生式结构体{stringleft;//定义产生式的部stringright;定产生式的右部}CSS;boolZero(CSSn)判型法{inti,j;for(i=0;i<n;i++)//循环n次即遍历所有产生式{for(j=0;j<p[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)判断文法{inti;if(Zero(p,n))先断是否是0型法{for(i=0;i<n;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)判断型法{inti;if(First(p,n))//同上，判断低级文法是否成立{for(i=0;i<n;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)判断文法{inti;if(Second(p,n))//同上，先断是否是2型文法{for(i=0;i<n;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;i<n;i++){if(p[i].right.length()==2){if(!(p[i].right[1]>='A'&&p[i].right[1]<='Z'))break;}}if(i==n){该法属于3型法<<endl;}elsecout<<"该文法属于2型文"<<endl;}elsecout<<"该法属于2型"<<endl;}elsecout<<"结束<<endl;}voidmain(){inti,j,n;stringinput;cout<<"请输入文法产生式个数N";cin>>n;CSS*p=newCSS[n];//初始化产生式数组for(i=0;i<n;i++)输产式数组{input.erase();清cin>>input;输for(j=0;j<input.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");

}测试用例1：7S->aSBES->aBEEB->BaB->abbB->bbbE->beeE->ee运行结果：测试用例2：文法：S->aBEEB->BEaB->abbE->beeE->ee运行结果：

测试用例3：文法：S->aABA->bBS->aA->aAA->aS运行结果：测试用例4：

文法：S->aAA->bBS->aA->aAA->aS运行结果见下页：实验心得：过Chomsky文法类型判断实验的实际操作该

压缩文法价变换2007-12-2813:30:33|分类：默认分类|举报字号订#include<iostream>#include<vector>usingnamespacebools_1(charid,char*left_2,charright_2[30][50],intn,intbools_2(charid,char*left_2,charright_2[30][50],intn,intboolfind(vector<char>&,char);boolend();voidadd_letter(vector<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);//是否继续判断条件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;chardo{cout<<"输入您的文法中所包含的规则数"<<endl;cin>>count;cout<<"入文法的识别符:"<<endl;cin>>id;for(i=0;i<count;i++){cout<<"输入规则"<<i+1<<"左端：cin>>left_1[i];cout<<"输入规则"<<i+1<<"右端：cin>>right_1[i];}intsize=0;for(i=0;i<count;i++)

{intpos=0;left_2[size]=left_1[i];for(j=0;j<right_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;i<size;i++)cout<<left_2[i]<<"::="<<right_2[i]<<endl;cout<<"面进行压缩文法等价变换"<<endl;compress(id,left_2,right_2,size,p);cout<<"缩后的结果："<<endl;for(i=0;i<size;i++)

if(p[i]!=3)cout<<left_2[i]<<"::="<<right_2[i]<<endl;}while(!end());}//查找加了标记的非终结符boolfind(<char>m){for(inti=0;p[i]!='\0';i++)if(p[i]==m)returntrue;returnfalse;}boolend(){charcout<<"想退出吗?[Y/N]";cin>>m;if(m=='y'||m=='Y')true;elsereturn}

//将加了标记的非终结符放到中voidadd_letter(vector<char>&p,charm){intlen=p.size();for(inti=0;i<len;i++)if(m==p[i])p.push_back(m);}//判断条件bools_1(charid,char*left_2,char(*right_2)[50],intn,int{intnew_p[30],j;for(intk=0;k<n;k++)new_p[k]=p[k];//new_p[k]将上一次规则的标记存储起来，以便下面用，看条件1否有改动vector<char>add_letter(lt,id);//标识符放入lt中do{intlen=lt.size();for(inti=0;i<n;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];//将规则的右部暂时存在for(j=0;j<length;j++)if(isalpha(temp[j])&&isupper(temp[j]))//寻找大写字母{将新找到的字母放进数组}}}if(len==lt.size())break;//lt中没有新添加的非终结符则跳出}while(1);for(j=0;j<n;j++)//扫描所有规则看是否有未加标记的{

switch(p[j]){case0:p[j]=3;break;//没有加标记的规则将其设置为3case1:break;case3:break;}}cout<<"断条件"<<endl;//for(intx=0;x<n;x++)cout<<p[k];//cout<<endl;for(intl=0;l<n;l++)//条件1改动，则返回falseif(p[l]!=new_p[l])returnfalse;returntrue;}//判断条件bools_2(charid,char*left_2,char(*right_2)[50],int*p){intnew_p[50];

for(intk=0;k<n;k++){new_p[k]=p[k];}cout<<endl;vector<char>for(inti=0;i<n;i++){if(p[i]==1){intm=0;for(;right_2[i][m]!='\0';)m=m+1;intlen=m;stringtemp=right_2[i];for(int看第i个规则右部是否全为终结符若是则将其左部加标记，并添加到lt中if(isalpha(temp[j])&&isupper(temp[j]))break;if(j==len){add_letter(lt,left_2[i]);p[i]=1;}}

}//for(intx=0;x<n;x++)cout<<p[k];//cout<<endl;do{intlen=lt.size();for(inti=0;i<n;i++){if(p[i]==0)//对剩余的没加标记的规则的操作，{stringtemp=right_2[i];intstr_len=temp.length();for(intj=0;j<str_len;j++)if(isalpha(temp[j])&&isupper(temp[j]))if(find(lt,temp[j])==false)break;if(j==str_len){规则右部终结符以加标记的规则左部加标记，并添加非终结符到lt中p[i]=1;}

}}新标记添加，}while(1);for(intj=0;j<n;j++)//对没添加标记的规则的标记符p[i]设置为3{switch(p[j]){case0:p[j]=3;break;case1:break;case