- 1、本文档共5页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
编译原理实验三
编译原理实验报告
实验名称 由正规文法构造正规式
实验时间 2014-4-30
院系 计算机科学与技术学院
班级
学号
姓名
试验目的
一个文法可以定义某种语言,而一个特定的语言也可以由文法来描述。法与语言之间并不存在一一对应的关系。
形式语言理论已经证明:
1给定一个文法,就能从结构上惟一地确定其语言,即
G→L(G)
2给出文法后,语言也就相应地确定了,其语言可以是有限的,也可以是无限的。
若输入任意的正规文法对应的输出相应的正规式。
实验原理
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。
按照定义,对于正则文法应用规则时,单个非终结符号只能被替换为单个终结符号,或被替换为单个非终结符号加上单个终结符号,或者被替换为单个终结符号加上单个非终结符号。
3型文法所确定的语言为3型语言L3,3型语言可由确定的有限状态自动机来识别。
程序设计语言的单词可由正则文法产生,例如,标识符的定义可由正则文法描述如下:
标识符::=字母/标识符字母/标识符数字
显然,该文法描述了以字母开头的字母数字串的集合。现在要引入另一种适合于描述单词的表示法——正则表达式。正则表达式又称为正则式,每个正则表达式描述的集合称为正则集。
之所以采用正则表达式来描述,主要基于以下几点原因:
词法规则简单,无需上下文无关文法那样严格的表示法,用正则式表示法来理解被定义的符号集合比理解由重写规则集合定义的语言更为容易;
从正则式构造高效识别程序比上下文无关文法更容易;
可以从某个正则式自动地构造识别程序,它可以识别用该正则式表示的字符串集合中的字符串,从而减轻后面要介绍的词法分析时的工作量。
可用于其他各种信息流的处理,例如,已经应用于某些模式识别问题、文献目录检索系统以及正文编辑程序等。
正则表达式和正则集
设有字母表∑。∑上的正则表达式和它所表示的正则集递归地定义如下:
ε和Φ都是∑上的正则表达式,它们所表示的正则集分别为{ε}和Φ,其中ε是空串,Φ是空集;
任意的a∈∑是正则表达式,它所表示的正则集是{a};
如果e1和e2是∑上的任意的正则表达式,且分别表示的正则集为L(e1)和L(e2),则:
e1/e2也是正则表达式,表示的正则集为L(e1 / e2)=L(e1)∪L(e2)。
e1 e2也是正则表达式,表示的正则集为L(e1 e2)=L(e1)L(e2)。
(e1)*也是正则表达式,表示的正则集为L((e1)*)=L(e1)*。
定义中(1)和(2)定义了原子正则表达式,而(3)则表明字母表∑上的正则表达式可由原子正则表达式或较简单的正则表达式通过联合、连接与闭包运算构成一般的正则表达式。
正则表达式的性质
如果两个正则表达式e1和e2表示的正则集相同,即值相等,则称它们是等价的。记为e1=e2。
正则表达式与正则文法的关系
一个正则表达式的值是正则集,它是正则语言的另一种表示法。不难看出,除了符号Φ外,一个正则表达式的含义类似于正则文法的一个非终结符号规则右部的含义。例如,对于数字 ::= 0/1/2/…/9,由非终结符数字所产生的字符串集合与正则表达式0/1/2/…/9所定义的字符串集合是相同的。正则集Φ,它对应一个不包含任何句子的语言,引进的目的主要是为了理论上的完备性。
.实验内容
输入:任意的正规文法。输出:相应的正规式。
正规文法与正规式的转换规则:
A-xB,B-y 则 A=xy
A-xA,A-y 则 A=x*y
A-x, A-y 则 A=x|y
利用字符串来输入文法,用结构体来保存文法产生式左部、右部
给定文法,判断文法类型
依照转换规则,给出正规式
实验心得
在编写此次实验,对于编写核心代码,是按照如下思路编写:
将正规文法转换为正规式,可以分为三种情况变换。
合并形如A-aA,A-bA的产生式为A-aA|bA的形式
合并形如S
您可能关注的文档
- 统计学原理公式及应用.doc
- 统计与可能性练习题.doc
- 监理部年度工作总结.doc
- 盖板涵安全施工方案.doc
- 统计学原理试卷A.doc
- 监理平行检测表-砼闸室段-底板.doc
- 统计学原理试题与答案.doc
- 统计学原理期末复习.doc
- 直流可变稳压电源设计.doc
- 直流伺服电机.doc
- 《中国通史》文字稿第12集春秋争霸.docx
- java教程--类与对象-讲义课件(演讲稿).ppt
- Vue应用程序开发-(1).pptx
- 东北师大版社劳动实践与评价指导手册一年级上册主题二活动一寻找五彩的树叶课时课件.pptx
- 外研版英语四年级上册 Module 4 Unit 2 How much is it单元教学设计.docx
- 外研版英语四年级上册Module 4 单元整体教学设计.docx
- 6《上课之前》课件 鄂科技版 心理健康教育一年级.pptx
- 《1~5的认识》说课课件(共25张PPT)人教版一年级上册数学.pptx
- 六《解决问题(1)》说课课件 人教版 三年级上册数学.pptx
- 七《解决问题》说课课件 人教版 二年级上册数学.pptx
文档评论(0)