




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
编译原理实验报告实验名称Chomsky文法类型判断实验时间2014年4月2日院系计算机科学与技术学院班级科技(2)班学号E01114174姓名徐帅试验目的输入:一组任意的规则。输出:相应的Chomsky文法的类型。实验原理1.0型文法(短语文法)如果对于某文法G,P中的每个规则具有下列形式: u::=v其中u∈V+,v∈V*,则称该文法G为0型文法或短语文法,简写为PSG。0型文法或短语结构文法的相应语言称为0型语言或短语结构语言L0。这种文法由于没有其他任何限制,因此0型文法也称为无限制文法,其相应的语言称为无限制性语言。任何0型语言都是递归可枚举的,故0型语言又称递归可枚举集。这种语言可由图灵机(Turning)来识别。2.1型文法(上下文有关文法)如果对于某文法G,P中的每个规则具有下列形式: xUy::=xuy其中U∈VN;u∈V+;x,y∈V*,则称该文法G为1型文法或上下文有关文法,也称上下文敏感文法,简写为CSG。1型文法的规则左部的U和右部的u具有相同的上文x和下文y,利用该规则进行推导时,要用u替换U,必须在前面有x和后面有y的情况下才能进行,显示了上下文有关的特性。1型文法所确定的语言为1型语言L1,1型语言可由线性有界自动机来识别。 3.2型文法(上下文无关文法)如果对于某文法G,P中的每个规则具有下列形式: U::=u其中U∈VN;u∈V+,则称该文法G为2型文法或上下文无关文法,简写为CFG。按照这条规则,对于上下文无关文法,利用该规则进行推导时,无需考虑非终结符U所在的上下文,总能用u替换U,或者将u归约为U,显示了上下文无关的特点。2型文法所确定的语言为2型语言L2,2型语言可由非确定的下推自动机来识别。一般定义程序设计语言的文法是上下文无关的。如C语言便是如此。因此,上下文无关文法及相应语言引起了人们较大的兴趣与重视。4.3型文法(正则文法,线性文法)如果对于某文法G,P中的每个规则具有下列形式: U::=T或U::=WT其中T∈VT;U,W∈VN,则称该文法G为左线性文法。如果对于某文法G,P中的每个规则具有下列形式: U::=T或U::=TW其中T∈VT;U,W∈VN,则称该文法G为右线性文法。左线性文法和右线性文法通称为3型文法或正则文法,有时又称为有穷状态 if(i==m) return1;//说明该文法是0型 else { cout<<"该文法不是0型文法!"<<endl; return0; }}boolwenfa1(GZ*p)//判断1型文法{ inti; if(wenfa0(p)) { for(i=0;i<m;i++)//遍历所有的产生式 { if(p[i].right.length()>=p[i].left.length())//判断产生式右边是否大于左边 continue; else break; } if(i==m) return1;//说明该文法是1型 else { cout<<"该文法是0型文法!"<<endl; return0; } } else return0;}boolwenfa2(GZ*p)//判断2型文法{ inti; if(wenfa1(p)) { for(i=0;i<m;i++)//遍历所有的产生式 { if(p[i].left.length()==1&&(p[i].left[0]>'A'&&p[i].left[0]<'Z')) continue; else break; } if(i==m) return1;//说明该文法是2型 else { cout<<"该文法是1型文法!"<<endl; return0; } } else return0;}boolwenfa3(GZ*p)//判断3型文法{ inti; if(wenfa2(p)) { for(i=0;i<m;i++)//遍历所有的产生式 { if((p[i].right[0]>='a'&&p[i].right[0]<='z')&&p[i].right.length()>=1&&p[i].right.length()<=2)//判断产生式右边第一个字符是否是终结符以及规定左边的字符个数为1或2 if((p[i].right.length()==2)&&(p[i].right[1]>='a'&&p[i].right[1]<='z')) break; else continue; else break; } if(i==m) { cout<<"该文法是3型文法!"<<endl; return1; } else { cout<<"该文法是2型文法!"<<endl; return0; } } else return0;}voidoutput(GZ*p)//输出终结符和非终结符{ inti,j,k; intvn=0;//记录非终结字符个数 intvt=0;//记录终结字符个数 for(i=0;i<m;i++)//遍历整个产生式 { for(j=0;j<p[i].whole.length();j++)//遍历产生式的整个字符 { if(p[i].whole[j]>='A'&&p[i].whole[j]<='Z')//判断字符是否为非终结字符 { for(k=0;k<=vn;k++)//遍历整个非终结符集合,判断是否有重复 { if(Vn[k]==p[i].whole[j]) break; else continue; } if(k>vn)//说明没有重复 { Vn[vn]=p[i].whole[j]; vn++; } } if(p[i].whole[j]>='a'&&p[i].whole[j]<='z')//判断字符是否为非终结字符 { for(k=0;k<=vt;k++)//遍历整个非终结符集合,判断是否有重复 { if(Vt[k]==p[i].whole[j]) break; else continue; } if(k>vt)//说明没有重复 { Vt[vt]=p[i].whole[j]; vt++; } } } } cout<<"\n"; cout<<"非终结符为:\n"; for(i=0;i<vn;i++)//输出非终结字符 cout<<Vn[i]<<""; cout<<"\n"; cout<<"\n"; cout<<"终结符为:\n"; for(i=0;i<vt;i++)//输出非终结字符 cout<<Vt[i]<<""; cout<<"\n";}voidmain(){ inti,j; stringin;//记录输入的产生式 cout<<"请输入文法产生式的个数!\n"; cin>>m; GZ*p=newGZ[m]; cout<<"请再输入文法规则:\n"; for(i=0;i<m;i++)//输入产生式数组 { cin>>in; for(j=0;j<in.length();j++)//将产生式分为左式和右式 { if(in[j]=='-') { p[i].left=in.substr(0,j);
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 安阳车管预约管理办法
- 自动监控资质管理办法
- 种植设备设施管理办法
- 福建游戏游艺管理办法
- 育婴护理知识培训课件
- 肥厚型心肌病
- 股票技术课件
- 原材料管理培训课件
- 肝癌中医教学课件
- 广东20年高考数学试卷
- 2025至2030中国血栓弹性成像仪行业发展趋势分析与未来投资战略咨询研究报告
- 建筑工程管理考试模拟题及答案
- 2025年 老年人能力评估师三级考试模拟试卷附答案
- 浙江省“桐浦富兴”教研联盟2024-2025学年高一下学期6月学考模拟化学试卷(含答案)
- 肛周良性疾病诊疗要点
- 【吉尔吉斯和国经商指南-法律篇】
- Q∕SY 01006-2016 二氧化碳驱注气井保持井筒完整性推荐作法
- 百家丽-中国-照明电器有限公司的精益生产应用
- 嵌入式软件助理工程师认证考试试题题库
- SH0622-95乙丙共聚物粘度指数改进剂
- SAP销售启用发出商品业务配置及操作手册(共15页)
评论
0/150
提交评论