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

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

ID:52701942

大小:62.50 KB

页数:13页

时间:2020-03-29

编译原理实验Chomsky文法类型判断.doc_第1页
编译原理实验Chomsky文法类型判断.doc_第2页
编译原理实验Chomsky文法类型判断.doc_第3页
编译原理实验Chomsky文法类型判断.doc_第4页
编译原理实验Chomsky文法类型判断.doc_第5页
资源描述:

《编译原理实验Chomsky文法类型判断.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、编译原理实验报告实验名称Chomsky文法类型判断实验时间2018年4月2日院系计算机科学与技术学院班级科技(2>班学号E01114174姓名徐帅1.实验目的输入:一组任意的规则。输出:相应的Chomsky文法的类型。2.实验原理1.0型文法<短语文法)如果对于某文法G,P中的每个规则具有下列形式:u::=v其中u∈V+,v∈V*,则称该文法G为0型文法或短语文法,简写为PSG。0型文法或短语结构文法的相应语言称为0型语言或短语结构语言L0。这种文法由于没有其他任何限制,因此0型文法也称为无限制文法,其相应的语言称为无限制性语言。任何0型语言都

2、是递归可枚举的,故0型语言又称递归可枚举集。这种语言可由图灵机

3、1型语言可由线性有界自动机来识别。3.2型文法<上下文无关文法)如果对于某文法G,P中的每个规则具有下列形式:U::=u其中U∈VN;u∈V+13/13,则称该文法G为2型文法或上下文无关文法,简写为CFG。按照这条规则,对于上下文无关文法,利用该规则进行推导时,无需考虑非终结符U所在的上下文,总能用u替换U,或者将u归约为U,显示了上下文无关的特点。RTCrpUDGiT2型文法所确定的语言为2型语言L2,2型语言可由非确定的下推自动机来识别。一般定义程序设计语言的文法是上下文无关的。如C语言便是如此。因此,上下文无关文法及相应语言引起了人们较

4、大的兴趣与重视。5PCzVD7HxA4.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型文法或正则文法,有时又称为有穷状态文法,简写为RG。按照定义,对于正则文法应用规则时,单个非终结符号只能被替换为单个终结符号,或被替换为单个非终结符号加上单个终结符号,或者被替换为单个终结符号加上单个

5、非终结符号。jLBHrnAILg3型文法所确定的语言为3型语言L3,3型语言可由确定的有限状态自动机来识别。在常见的程序设计语言中,多数与词法有关的文法属于3型文法。可以看出,上述4类文法,从0型到3型,产生式限制越来越强,其后一类都是前一类的子集,而描述语言的功能越来越弱,四类文法及其表示的语言之间的关系可表示为:xHAQX74J0X0型1型2型3型;即L0L1L2L33..实验内容该实验用C++进行编译,利用函数功能,调用不同的函数来判定0型文法,1型文法,2型文法,3型文法的判断。主要提高我们对文法类型的理解,也提高了我们编程的动手能力.

6、理论与实践结合,加深对文法概念的理解.LDAYtRyKfE1.实验心得1.明确四种文法的定义,根据文法定义的不同,利用程序将其区分开2.事先画好实验的流程图,可以帮助解决问题5.实验代码与结果#include#include13/13usingnamespacestd。intm。//文法产生式的个数charVn[100]。//记录非终结字符charVt[100]。//记录终结字符typedefstructGZ//定义一个产生式结构体{stringleft。//定义产生式的左部stringright。//定义产

7、生式的右部stringwhole。//定义整个产生式}GZ。boolwenfa0(GZ*p>//判断0型文法{inti,j。for(i=0。i//遍历所有的产生式{for(j=0。j。j++>//遍历整个产生式左式每一个字符{if((p[i].left[j]>='A'>&&(p[i].left[j]<='Z'>>//判断产生式左边是否含有非终结符Zzz6ZB2Ltk13/13break。}if(j==p[i].left.length(>>break。elsecontinue。}if(i==m>

8、return1。//说明该文法是0型else{cout<<"该文法不是0型文法!"</

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。