编译原理实验一Chomsky文法类型.doc

  1. 1、本文档共19页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
编译原理实验一Chomsky文法类型

编译原理实验报告 实验名称 Chomsky文法类型判断 实验时间 2013年10月29日 院系 计算机科学与电子技术系 班级 11计算机软件 学号 JV114001 JV114095 JP114065 姓名 唐茹 韩强强 徐思维 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.实验内容: 程序清单如下: #include stdafx.h #includeiostream #includestring using namespace std; typedef struct CSS //定义一个产生式结构体 { string left; //定义产生式的左部 string right; //定义产生式的右部 }CSS; bool Zero(CSS *p,int n) //判断0型文法 { int i,j; for(i=0;in;i++) //循环n次,即遍历所有产生式 { for(j=0;jp[i].left.length();j++) //遍历产生式左部每一个字符 { if(p[i].left[j]=Ap[i].left[j]=Z) //判断字符是否是非终结符 break; } if(j==p[i].left.length()) { cout该文法不是0型文法endl; return 0; break; } } if(i==n)return 1;//如果每个产生时都能找到非终结符 } bool First(CSS *p,int n) //判断1型文法 { int i; 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)return 1; else{ cout该文法是0型文法endl; return 0; } } else return 0; } bool Second(CSS *p,int n) //判断2型文法 { int i; if(First(p,n)) //同上,先判断低级文法是否成立 { for(i=0;in;i++) //同上,遍历所有文法产生式 { if((p[i].left.length()!=1) || !(p[i].left[0]=Ap[i].left[0]=Z)) //判断产生式左部长度是否为一,左部第一个是否是非终结符 break; } if(i==n)return 1; else{ cout该文法是1型文法endl; return 0; } } else return 0; } void Third(CSS *p,int n) //判断3型文法 { int i; 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]

文档评论(0)

quechui388620 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档