编译原理实验一CHOMSKY文法类型.docx
《编译原理实验一CHOMSKY文法类型.docx》由会员分享，可在线阅读，更多相关《编译原理实验一CHOMSKY文法类型.docx（18页珍藏版）》请在冰点文库上搜索。
编译原理实验一CHOMSKY文法类型
编译原理实验报告
实验名称Chomsky文法类型判断
实验时间2013年10月29日
院系计算机科学与电子技术系
班级11计算机软件
学号JV******JV******JP******
姓名唐茹韩强强徐思维
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.程序清单如下：
#include"stdafx.h"
#include
#include
usingnamespacestd;
typedefstructCSS//定义一个产生式结构体
{
stringleft;//定义产生式的左部
stringright;//定义产生式的右部
}CSS;
boolZero（CSS*p,intn）//判断0型文法
{
inti,j;
for（i=0;i{
for（j=0;j{
if（p[i].left[j]>='A'&&p[i].left[j]<='Z'）//判断字符是否是非终结符
break;
}
if（j==p[i].left.length（））
{
cout<<"该文法不是0型文法"<return0;
break;
}
}
if（i==n）return1;//如果每个产生时都能找到非终结符
}
boolFirst（CSS*p,intn）//判断1型文法
{
inti;
if（Zero（p,n））//先判断是否是0型文法
{
for（i=0;i{
if（（p[i].left.length（）>p[i].right.length（））&&p[i].right.length（）!
=NULL）//判断产生式左部长度是否大于右部
break;
}
if（i==n）return1;
else{
cout<<"该文法是0型文法"<return0;
}
}
else
return0;
}
boolSecond（CSS*p,intn）//判断2型文法
{
inti;
if（First（p,n））//同上，先判断低级文法是否成立
{
for（i=0;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型文法"<return0;
}
}
else
return0;
}
voidThird（CSS*p,intn）//判断3型文法
{
inti;
if（Second（p,n））//同上，先判断是否是2型文法
{
for（i=0;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{
if（p[i].right.length（）==2）
{
if（!
（p[i].right[1]>='A'&&p[i].right[1]<='Z'））break;
}
}
if（i==n）
{
cout<<"该文法属于3型文法"<}
else
cout<<"该文法属于2型文法"<}
elsecout<<"该文法属于2型文法"<}
else
cout<<"结束"<}
voidmain（）
{
inti,j,n;
stringinput;
cout<<"请输入文法产生式个数N：
";
cin>>n;
CSS*p=newCSS[n];//初始化产生式数组
for（i=0;i{
input.erase（）;//清除
cin>>input;//输入
for（j=0;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：
7
S->aSBE
S->aBE
EB->B
aB->ab
bB->bb
bE->be
eE->ee
运行结果：
测试用例2：
1型文法：
7
S->aSBE
S->aBE
EB->BE
aB->ab
bB->bb
bE->be
eE->ee
运行结果：
测试用例3：
2型文法：
9
S->aAB
A->bB
S->bB
B->bB
S->a
B->b
A->aA
B->a
A->aS
运行结果：
测试用例4：
3型文法：
9
S->aA
A->bB
S->bB
B->bB
S->a
B->b
A->aA
B->a
A->aS
运行结果见下页：
4.实验心得：
通过Chomsky文法类型判断实验的实际操作，知道和理解了该理论在计算机中是怎样执行的，对该理论在实践中的应用有深刻的理解。
在这次课程设计中，我们组就是按照实验指导的思想来完成。
加深了理解了文法规则的不同定义形式，培养了实践动手能力和程序开发能力。
压缩文法等价变换
2007-12-2813:
30:
33|分类：
默认分类|举报|字号订阅
#include
#include
usingnamespacestd;
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（vector&,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）;//是否继续判断条件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<<"请输入您的文法中所包含的规则数"<cin>>count;
cout<<"输入文法的识别符:
"<cin>>id;
for（i=0;i{
cout<<"请输入规则"<";
cin>>left_1[i];
cout<<"请输入规则"<";
cin>>right_1[i];
}
intsize=0;
for（i=0;i{intpos=0;
left_2[size]=left_1[i];
for（j=0;j='\0';j++）
{if（right_1[i][j]=='|'）
{right_2[size][pos]='\0';
pos=0;
left_2[++size]=left_1[i];
}
else
right_2[size][pos++]=right_1[i][j];
}
right_2[size][pos]='\0';
size++;
}
cout<<"展开输出文法"<for（i=0;icout<:
="<cout<<"下面进行压缩文法等价变换"<compress（id,left_2,right_2,size,p）;
cout<<"压缩后的结果：
"<for（i=0;iif（p[i]!
=3）
cout<:
="<}while（!
end（））;
}
//查找加了标记的非终结符
boolfind（vector&p,charm）
{
for（inti=0;p[i]!
='\0';i++）
if（p[i]==m）returntrue;
returnfalse;
}
boolend（）
{
charm;
cout<<"你想退出吗?
[Y/N]";
cin>>m;
if（m=='y'||m=='Y'）returntrue;
elsereturnfalse;
}
//将加了标记的非终结符放到p中
voidadd_letter（vector&p,charm）
{
intlen=p.size（）;
for（inti=0;iif（m==p[i]）return;
p.push_back（m）;
}
//判断条件1
bools_1（charid,char*left_2,char（*right_2）[50],intn,int*p）
{
intnew_p[30],j;
for（intk=0;kvectorlt;
add_letter（lt,id）;//标识符放入lt中
do
{
intlen=lt.size（）;
for（inti=0;iif（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;jif（isalpha（temp[j]）&&isupper（temp[j]））//寻找大写字母
{
add_letter（lt,temp[j]）;//将新找到的字母放进数组
}
}
}
if（len==lt.size（））break;//lt中没有新添加的非终结符则跳出
}while
（1）;
for（j=0;j{
switch（p[j]）
{
case0:
p[j]=3;break;//没有加标记的规则将其p[]设置为3
case1:
break;
case3:
break;
}
}
cout<<"判断条件1"<//for（intx=0;x//cout<for（intl=0;lif（p[l]!
=new_p[l]）
returnfalse;
returntrue;
}
//判断条件2
bools_2（charid,char*left_2,char（*right_2）[50],intn,int*p）
{
intnew_p[50];
for（intk=0;kcout<vectorlt;
for（inti=0;i{
if（p[i]==1）
{
intm=0;
for（;right_2[i][m]!
='\0';）m=m+1;
intlen=m;
stringtemp=right_2[i];
for（intj=0;jif（isalpha（temp[j]）&&isupper（temp[j]））break;
if（j==len）
{
add_letter（lt,left_2[i]）;
p[i]=1;
}
}
}
//for（intx=0;x//cout<do
{
intlen=lt.size（）;
for（inti=0;i{
if（p[i]==0）//对剩余的没加标记的规则的操作，
{
stringtemp=right_2[i];
intstr_len=temp.length（）;
for（intj=0;jif（isalpha（temp[j]）&&isupper（temp[j]））
if（find（lt,temp[j]）==false）
break;
if（j==str_len）
{
add_letter（lt,left_2[i]）;//对规则右部终结符以加标记的规则左部加标记，并添加非终结符到lt中
p[i]=1;
}
}
}
if（len==lt.size（））break;//无新标记添加，
}while
（1）;
for（intj=0;j{
switch（p[j]）
{
case0:
p[j]=3;break;
case1:
break;
case3:
break;
}
}
cout<<"判断条件2"<//intx;
//for（x=0;x//cout<for（intl=0;lif（p[l]!
=new_p[l]）returnfalse;
returntrue;
}
voidhelp（）
{cout<<""<<"**********"<<"压缩文法等价变换程序"<<"*********"<cout<<""<:
=U这样的规则。
"<cout<<""<"<}
升级会员 