版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、1、原理Compiler Principles,徐小龙南京邮电大学.计算机学院,第二章形式语言基础知识,教材:编译技术原理及其实现方法王汝传篇,2,第二章形式语言基础知识2.1引言一,形式语言提出二,语言描述方法2.2用语法生成法描述语言一,巴斯正则二,语法和意义三语法树2.3形式语言基本概念和用语一、元语言二、符号和符号串三、生成式(规则)四、语法五、推导和归约六、即短语和简单短语十、最左推导和最右推导十一、语法二义性、2.4语法分析初步、自上而下语法分析二、自下而上语法分析二. 5语法和语言分类一、语法分类二、语法和奥数压缩语法的2.6语法其他表示法一、扩展巴克斯正规二、语法图2.1引言一
2、、形式语言提出二、语言记述方法2.2用语法生成法记述语言一、巴克斯正规二、语法和意义三、语法树2.3形式语言基本概念和用语一、元语言二、符号和符号串三、生成式(规则)四、语法五、导出和归约六、 的短句和简短句十,最左导出和最右导出十一,语法二义性,2.4语法分析初步一,自上而下语法分析二,自下而上语法分析二. 5语法和语言分类一,语法分类二,语法和自动机三,压缩语法的2.6语法及其他表示法一,扩展巴克斯正则二,语法图2.1引言一,形式语言提出二第二章形式语言基础知识,2.1引言一、形式语言提出二、语言记述方法,6,2.1引言一、形式语言提出形式语言是研究符号的语言,只考虑符号之间的关系,即数学
3、方法(不考虑语言的非形式记述:用于人们交流思想的工具。 对语言学本身来说也是古老的科学,不过,从很久以前以数学的方法开始语言学的研究。 1847年,俄罗斯数学家布拉克夫斯基用概率论进行语法语源和语言历史的比较研究。 1904年,波兰语言学家指出,语言学家不仅要学习初等数学,还要学习高等数学。 1931年,俄罗斯数学家用概率论研究俄语元音文字和辅音文字的排列。 自从1946年电子订书机诞生以来,更加促进了数学和语言学的结合研究。 7,2.1引言一、形式语言提出,1956年N.Chomsky在研究自然语言过程中提出了语法数学模型,奠定了形式语言理论的基础,成为计算机科学理论的重要分支,即形式语言和
4、自动机。 为什么要提出形式语言呢? 1、控制论出现,促进对语言的深入研究2 .在计算机上进行科技文献检索,要求在自动作文摘要和其他信息处理时将自然语言转换为一定形式的信息。 3 .要将自然语言从计算机上的自然语言翻译成其他自然语言,机器必须对语言进行形式化描述,以便进行分析和集成。 4 .修订机编译理论、人工智能、数据库等需要形式记述语言。8、第二章形式语言基础知识、2.1引言一、形式语言提交二、语言记述方法、9、第二章形式语言基础知识、2.1引言一、形式语言提交二、语言记述方法、10、2.1引言二、语言记述方法无论是自然语言还是编程语言都是一种语言的记述,一种语言的哪个句子是属于该语言的句子
5、,哪个句子是属于该语言的句子11,2.1引言二,语言记述方法我们可以用三种方法记述语言,列举法,语法生成法和机器人识别法:1.列举法:如果一种语言只包含有限个句子,可以用列举法记述该语言,即列举语言中的所有句子即可但是,枚举法显然无效,因为大多数重要语言都有无限的句子。 2 .语法生成法:使用有限个规则生成语言中无限个句子的规则集合称为语法。 3 .自动机识别法:用自动机识别语言中的句子,自动机是记述离散变量的系统(数学模型),由于在形式语言中被称为识别器,所以也可以看作识别程序。 不同的语言对应不同的自动机,对应某种语言的自动机接受那句话,否则不接受。 以语法生成法记述语言为重点进行研究。1
6、2、第二章形式语言基础知识2.1引言一、形式语言提出二、语言描述方法2.2用语法生成法描述语言一、巴克斯正则二、语法和意义三、语法树2.3形式语言基本概念和用语一、元语言二、符号和符号串三、生成式(规则)四、语法五、导出和归约六的短句和简短句十、最左导出和最右导出十一语法二义性,2.4语法分析初步一,自上而下语法分析二,自下而上语法分析二. 5语法和语言分类一,语法分类二,语法和自动机三,压缩语法的2.6语法其他表示法一,扩展巴克斯正则二,语法图2.1引言一,形式语言提出二,语言记述方法2.2语法生成法记述语言一,巴克斯语法和意义三,语法树2.3形式语言基本概念和用语一,元语言二,符号和符号串
7、三,生成式(规则)四,语法五,推导和归纳六,即短语和简单短语十,最左推导和最右推导十一,语法二义性,2.4语法分析初步,自上而下语法分析二,自下而上语法分析二. 5语法和语言分类一,语法分类二语法和自动机三,压缩语法的2.6语法其他表示法一,扩张巴科斯正规二,语法图2.2语法生成法记述语言1,巴科斯残奥时间2,语法和意义1 .语法2 .意义3,语法树,15,第二章形式语言基础知识,2.2语法生成法记述语言1,巴科斯残奥时间2,语法和意义1 语法树2.2使用语法生成法记述语言1、巴库斯正规形式的例子: The big elephant ate the peanut.(大象吃花生) The lit
8、tle boy ran quickly.(小) 如何描述给定语句在给定规则下是否成立?将“=”符号(或“”符号)表示定义为“”,用“|”符号表示“或”,用“”符号表示语法实体(语法单位)。 这些符号是元语言符号,17,句子=主语谓语主语=冠词名词冠词=the形容词=big谓语=动词宾语动词=ate宾语=冠词名词名词=elephant | peanut我们把记述这个语法规则的方法称为backkk,backkk和中的组合图层性质变更选项。 上述语法规则, 可以写成18用于步骤导出的规则1谓词2形容词名词谓词3 the形容词名词谓词4thebigelephant谓词5 thebigelephanta
9、te8thebigelephantate冠词9 thebigelephantate big elephant ate the peanut可以看出语句thebigelephantatethepeanut是成立的。 当然,也可以导出其他语句,例如the big peanut ate the elephant。 在这里,只考虑句子的语法,不考虑句子的意思。 根据以上规则,可以导出句子The big elephant ate the peanut。过程如下:19、巴斯残奥时间是记述语法规则的表现方法,这是巴斯最初在ALGOL60报告中为了记述ALGOL语言而提出的。 用这样的形式体系方式定义语法规则
10、,可以用简洁的形式严格且明确地记述各种语法规则。 例如,在高级语言中众所周知的语法成分标识符,在巴科斯正则表达式中表达为:标识符=字母|标识符字母|标识符数字,字母=A|B|C|D|Z数字=0|1|2|9,20、使用条形码按残奥时间表达语言以下9个句子都是正确的: weranheraniranweateheateiatewesathesatisat,只要我们用条形码的关残奥时间表现上述9个句子,就有几个规则就可以了。 句子=主语谓语主语=We | He | I谓语=ran | ate | sat表明,如果一种语言中有无限多个句子,在上述规则中就会有更加现实的意义。21、第二章形式语言基础知识、
11、2.2语法生成法描述语言1、巴斯残奥时间2、语法和意义1 .语法2 .意义3、语法树22、第二章形式语言基础知识、2.2语法生成法描述语言1、巴斯残奥时间2、语法和意义实际上语法是在字母上造句的一系列规则。 关于自然语言是造句的规则关于编程语言是写编程规则。 24,2.2用语法生成法描述语言2,语法和意义2 .意思是按照语法规则构成的结构的意思。 在自然语言中,意思是应该表现的意思在编程语言中,意思是程序完成的工作,或者是语法成分的意思。 很明显,一个句子在语法上是正确的,这在意义上也不是正确的。 例如,“The big peanut ate the elephant”在语法上是正确的,在意义
12、上是荒谬的。 在PASCAL语言中,标识符以字符开头是语法,而标识符的使用需要说明。 关于语法,目前的研究比较成熟,形式描述是可能的,而语义描述没有形式化,必须依靠自然语言。 25、编译器如何将源程序作为目标程序? 第一,语法分析,看源程序是否符合该语言的语法关系的第二,语义分析,从该语言的意义生成目标代码是两个核心问题。 2.2语法生成法描述语言二、语法和意义、26、第二章形式语言基础知识、2.2语法生成法描述语言一、巴斯正规二、语法和意义1 .语法2 .意义三、语法树,27、第二章形式语言基础知识2.2语法生成法描述语言一、巴斯残奥时间二、语法和意义1 .语法2 .意义三、语法树2.2语法
13、生成法记述语言三、语法树除了可以在上面根据语言语法规则导出句子外,还可以用图解形式表现。 用图解(树)形式记述句子的语法构造关系,称为语法树。、29、30、语法树除了可以基于上述语言语法规则导出句子外,还可以用图解形式表现。 用图解(树)形式记述句子的语法构造关系,称为语法树。 句子the man has a book的导出过程和对应的语法树、30、三、语法树,除了可以基于上述语言语法规则导出句子之外,还可以用图解形式表现。 用图解(树)形式记述句子的语法构造关系,称为语法树。 句子the man has a book的导出过程和对应的语法树、31、三、语法树,除了可以根据上述语言语法规则导出
14、句子之外,还可以用图解形式表现。 用图解(树)形式记述句子的语法构造关系,称为语法树。 句子the man has a book的导出过程和对应的语法树、32、the、三、语法树,除了可以根据上述语言语法规则导出句子之外,还可以用图解形式表现。 用图解(树)形式记述句子的语法构造关系,称为语法树。 与语句the man has a book的导出过程对应的语法树、33、man、the、三、语法树除了能够基于上述语言语法规则导出语句之外,还能够以图解形式表示。 用图解(树)形式记述句子的语法构造关系,称为语法树。 句子the man has a book的导出过程和对应的语法树、34、man、the、三、语法树,除了可以根据上述语言语法规则导出句子之外,还可以用图解形式表现。 用图解(树)形式记述句子的语法构造关系,称为语法树。 句子the man has a book的导出过程和对应的语法树、35、man、has、the、三、语法树,除了可以根据上述语言语法规则导出句子之外,还可以用图解形式表现。 用图解(树)形式记述句子的语法构造关系,称为语法树。 句子the man has a book的导出过程和对应的语法树、36、man、has、the、三、语法树,除了可以根据上述语言语法规则导出句子之外,还可以用图解形式记述句子的语法构造关系,
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- (新教材)人教版小学数学六年级上册第一单元确定位置《用方向和距离确定位置》第五课时示范课教学课件
- 初中化学九年级《二氧化碳实验室制法》专题复习教学设计
- 高中地理高三一轮复习《海洋空间资源与国家安全》教学设计
- 初中八年级综合实践活动“保护水资源”探究课教学设计
- 初中九年级心理健康教学设计:第五课坚持就是胜利核心素养导向下的深度学习实施策略
- 人教版初中数学九年级下册锐角三角函数第一课时教学设计
- 高二英语选择性必修一Unit 5 Starting Out教学设计
- 初中地理八年级复习课极地地区基础知识扫描教学设计
- 小学四年级道德与法治买东西的学问教学设计
- 高中一年级历史统编版必修第1课中华文明的起源与早期国家教学设计
- 2025年(完整版)三级安全教育真题及答案(2025年)
- 第二十七届大赛专用稿纸-国内
- 中国鼻炎诊疗指南(2026版)
- 2026年译林版九年级英语上册 Unit5 Music speaks单元测试卷(含答案)
- 2026年数据文员笔模拟题目及答案详解
- T/COSHA 48-2024医疗机构安全生产资料管理规范
- GB 48145-2026井工煤矿机电设备完好性要求
- IEC 61000-4-2-2025 中文版(静电放电抗扰度试验 2025 年 3 月发布)
- 人教PEP版六年级英语上册《Unit 4 Managing money well》单元测试卷(带答案)
- 2026年党员发展对象培训结业试题及答案
- 2026年邮储银行山西分行秋招无领导小组面试仿真题解析
评论
0/150
提交评论