编译原理和技术.

Slides:



Advertisements
Similar presentations
1 、谁能说说什么是因数? 在整数范围内( 0 除外),如果甲数 能被乙数整除,我们就说甲数是乙数的 倍数,乙数是甲数的因数。 如: 12÷4=3 4 就是 12 的因数 2 、回顾一下,我们认识的自然数可以分 成几类? 3 、其实自然数还有一种新的分类方法, 你知道吗?这就是我们今天这节课的学.
Advertisements


3 的倍数的特征 的倍数有 : 。 5 的倍数有 : 。 既是 2 的倍数又是 5 的倍数有 : 。 12 , 18 , 20 , 48 , 60 , 72 , , 25 , 60 ,
2 和 5 的倍数的特征 运动热身 怎样找一个数的倍数? 从小到大写出 2 的倍数( 10 个): 写出 5 的倍数( 6 个) 2 , 4 , 6 , 8 , 10 , 12 , 14 , 16 , 18 , 20 5 , 10 , 15 , 20 , 25 , 30.
2.5 函数的微分 一、问题的提出 二、微分的定义 三、可微的条件 四、微分的几何意义 五、微分的求法 六、小结.
练一练: 在数轴上画出表示下列各数的点, 并指出这些点相互间的关系: -6 , 6 , -3 , 3 , -1.5, 1.5.
2 、 5 的倍数特征 集合 2 的倍数(要求) 在百数表上依次将 2 的倍数找出 并用红色的彩笔涂上颜色。
编译原理和技术 大连理工软件学院 江 贺 课 程 简 介课 程 简 介课 程 简 介课 程 简 介 教材和参考书 陈意云、张昱,编译原理,高等教育出版社, 2003 Louden, K.C, 《编译原理及实践(英文版)》. 中信出版社 Alfred V.Aho,
《程序设计实践》 孙辉 理工配楼104A
第一章 引 论 名词解释 编译器从逻辑上可以分成若干个阶段 每个阶段把源程序从一种表示变换成另一种表示
ASP .NET 程序设计(C#版) 第二版 机械工业出版社同名教材 配套电子教案
——Windows98与Office2000(第二版) 林卓然编著 中山大学出版社
Tool Command Language --11级ACM班 金天行.
巧用叠词,妙趣横生.
中国科学技术大学 计算机科学与技术学院 陈意云
编 译 原 理 指导教师:杨建国 二零一零年三月.
第三章 词法分析 赵建华 南京大学计算机系 2009年2月.
《数据库原理及应用》课程介绍 信息工程学院 孙俊国
2.2 语法分析器生成器YACC 分析器的构造步骤: 产生式→识别活前缀的DFA→分析表(+驱动器) YACC概述
Last Lecture Revisited
Lexical analyzer generator
第二章 词法分析 词法记号及属性 词法记号的描述与识别 有限自动机 DFA构建 DFA化简 词法模式的识别过程 子集构造法.
编译原理与技术 词法分析(1) 2018/11/28 《编译原理与技术》讲义.
编译原理与技术 2018/11/30 《编译原理与技术》讲义.
编译原理 第三章 词法分析.
語法與修辭 骨&肉 老師:歐秀慧.
第三章 词法分析.
Part3词法分析 授课:胡静.
Last Lecture Revisited
管理信息结构SMI.
走进编程 程序的顺序结构(二).
第一单元 初识C程序与C程序开发平台搭建 ---观其大略
编译原理与技术 词法分析 (2) 2018/12/30 《编译原理与技术》讲义.
第五讲 四则运算计算器(一) 精品教程《C#程序设计与应用(第2版)清华大学出版社 谭恒松 主编
第一章 函数 函数 — 研究对象—第一章 分析基础 极限 — 研究方法—第二章 连续 — 研究桥梁—第二章.
编译器设计与实现 梁红瑾
第二、三章习题讲解
第二章 Java语言基础.
2.3 正则表达式 主要内容: 1.正则表达式和正则集; 2.正则表达式和有限自动机的相互转化。.
《编译原理与技术》 期末复习 计算机科学与技术学院 郑启龙 李 诚 25/12/2018.
分布式程序设计 姚斌 计算机科学与工程系 上海交通大学.
宁波市高校慕课联盟课程 与 进行交互 Linux 系统管理.
第一章 函数与极限.
C语言程序设计 主讲教师:陆幼利.
简单介绍 用C++实现简单的模板数据结构 ArrayList(数组, 类似std::vector)
学习目标 1、什么是字符集 2、字符集四个级别 3、如何选择字符集.
编译原理总结-1 第3~5章.
编译原理.
微机原理与接口技术 微机原理与接口技术 朱华贵 2015年11月13日.
实验七 安全FTP服务器实验 2019/4/28.
计算机网络与网页制作 Chapter 07:Dreamweaver CS5入门
项目二:HTML语言基础.
成绩是怎么算出来的? 16级第一学期半期考试成绩 班级 姓名 语文 数学 英语 政治 历史 地理 物理 化学 生物 总分 1 张三1 115
第4章 Excel电子表格制作软件 4.4 函数(一).
第九节 赋值运算符和赋值表达式.
词法分析
1.2 子集、补集、全集习题课.
1.设A和B是集合,证明:A=B当且仅当A∩B=A∪B
多层循环 Private Sub Command1_Click() Dim i As Integer, j As Integer
本节内容 C语言的汇编表示 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
第二章 Java基本语法 讲师:复凡.
第二节 函数的极限 一、函数极限的定义 二、函数极限的性质 三、小结 思考题.
C++语言程序设计 C++语言程序设计 第一章 C++语言概述 第十一组 C++语言程序设计.
编译原理 编译原理.
编译原理 Compiler Principles 第三章 词法分析 湖南大学信息科学与工程学院 软件工程系 杨金民 2019/02.
第三章:词法分析 戴新宇 南京大学 计算机科学与技术系.
编译原理 第一章 编译程序概述 第二章 PL/0编译程序的实现 第三章 文法和语言 第四章 词法分析 第五章 自顶向下语法分析方法
编译原理实践 6.程序设计语言PL/0.
编译原理实践 --词法分析程序的自动生成器LEX
§2 自由代数 定义19.7:设X是集合,G是一个T-代数,为X到G的函数,若对每个T-代数A和X到A的函数,都存在唯一的G到A的同态映射,使得=,则称G(更严格的说是(G,))是生成集X上的自由T-代数。X中的元素称为生成元。 A变, 变 变, 也变 对给定的 和A,是唯一的.
Presentation transcript:

编译原理和技术

课 程 简 介 课程内容 介绍编译器构造的一般原理和基本实现方法 介绍的理论知识:形式语言和自动机理论、语法制导的定义和属性文法、类型论等 强调形式描述技术和自动生成技术 强调对编译原理和技术的宏观理解,不把注意力分散到枝节算法,不偏向于某种源语言或目标机器 1.本课程介绍编译器构造的一般原理和基本实现方法,主要介绍编译器的各个阶段:词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成。反映直至20世纪末的一些重要成果,如有关类型制导的编译思想。 2.本课程在介绍命令式程序设计语言实现技术的同时,强调一些相关的理论知识,如形式语言和自动机理论、语法制导的定义和属性文法、类型论等。它们是计算机专业理论知识的重要一部分,在本书中结合应用来介绍这些知识,有助于学生较快领会和掌握。 3.本课程强调形式化描述技术,并以语法制导定义作为翻译的主要描述工具。 4.本课程强调对编译原理和技术在宏观上的理解,而不把读者的注意力分散到一些枝节的算法上,如计算开始符号集合和后继符号集合的算法,回填技术等。作为原理性的教材,本书介绍基本的理论和方法,而不偏向于某种源语言或目标机器。

课 程 简 介 学习的意义 对编程语言的设计和实现有深刻的理解,对和编程语言有关的理论有所了解,对宏观上把握编程语言来说,起一个奠基的作用。 从软件工程看,编译器是一个很好的实例,所介绍的概念和技术能应用到一般的软件设计之中。 大多数程序员同时是简单语言的设计者,有助于提高对这些语言的设计水平。 在软件逆向工程、程序理解和软件安全等方面有着广泛的应用。 虽然只有少数人从事构造或维护程序设计语言的编译器,但是本课程对本科生来说是一门重要课程。 1.本课程能使学生对编程语言的设计和实现有深刻的理解,对和编程语言有关的理论(形式语言和自动机理论、类型论等)有所了解,对宏观上把握编程语言来说,起一个奠基的作用。 2.对软件工程来说,编译器是一个很好的实例(基本设计、模块划分等),也是本科期间能碰到的唯一的大型例子,学生从本课程的学习也能了解到软件工程中的一些技术(如基于事件驱动的编程)。本课程所介绍的概念和技术能应用到一般的软件设计之中。 3.大多数程序员同时是语言的设计者,虽然是一些简单的语言(如输入输出),本课程的学习有助于提高对这些语言的设计水平。 4.编译技术在软件逆向工程、程序理解和软件安全等方面有着广泛的应用 软件逆向工程:以另外一种形式创建系统同一层次的表示或者更高层次的抽象, 应用:技术仿造、软件维护。 程序理解:通过分析、抽象和一般化来获取软件知识的演绎过程。(1)基于机器代码和中间代码层的理解,需要借助于反汇编和反编译技术;(2)基于源代码的理解;(3)基于语法层的理解,程序分段、程序切片和程序分析等技术就是其中的最典型代表;(4)基于程序语义层的理解,模式匹配、格局识别(plan recognition)、概念赋值(concept assigned)和概念分析(concept analysis)等都是进行语义级的软件理解和分析技术。 软件安全:满足安全策略。基本安全策略:类性安全、控制流安全和内存安全。还有信息流安全。用到词法、语法和语义分析、类性系统和类性检查、控制流分析和数据流分析等。编译器将走向类型制导的编译器。 美国的名牌大学:都有编程语言和编译器方面的课程,80%有这方面的研究。国内对这方面的人才需求将增加。

课 程 简 介 教材和参考书 陈意云、张昱,编译原理,高等教育出版社, 2003 A. Aho, R. Sethi, and J. D. Ullman, Compilers: Principles, Techniques, and Tools , 2nd edition, Addison-Wesley, 1986 陈意云、张昱,编译原理习题精选与解析,高等教育出版社,2005 教学资源网页:http://staff.ustc.edu.cn/~yiyun

课 程 简 介 课程要求 目标:师生共同努力,达国内最好水平 讲课进展较快,平时不复习并加深理解,后面将听不懂 作业较多,要求独立完成 上机实验,不要轻视 阅读PL/0编译器,会有很大收获 考试开卷,决不会轻松 学期总评 = 考试成绩占70%,作业占15%,上机实验5%,阅读PL/0编译器占10% 上课时间安排

对 课 程 的 评 论 本校94少年班某同学,Stanford大学博士(1999年) 本系某考研同学(2006年) Actually I think the quality of the compiler course in USTC is really very good and can be compared with any universities here. 本系某考研同学(2006年) 感觉您出的题目很有创意,也很有深度 ,没有局限于固定的算法和题型,只看课本和复习往年的题目而不深入思考的人是做不出来的,能够真正从本质上考察一个考生的水平。 西南科技大学某考研学生(2004年) 看过你编的书后,感觉编译的原理可以一下子和我平常学的很多学科和语言都联系起来了,可以学到很多可以实际用到的东西,虽然是在讲同样的东西,但您的教学方式让我很适应,学起来也很有兴趣,大大减轻了我考研的疲劳感。

第一章 引 论 翻译器、编译器、解释器 编译器从逻辑上可以分成若干阶段 每个阶段把源程序从一种表示变换成另一种表示 第一章 引 论 翻译器、编译器、解释器 编译器从逻辑上可以分成若干阶段 每个阶段把源程序从一种表示变换成另一种表示 通过描述编译器的各个阶段来介绍编译这个课题

第一章 引 论 词法分析器 语法分析器 语义分析器 源程序 中间代码生成器 代码优化器 代码生成器 目标程序 出错管理器 符号表管理器

position := initial + rate * 60 第一章 引 论 词法分析器 id1 := id2 + id3 * 60 position := initial + rate * 60 符 号 表 position initial rate . . . 1 2 3

第一章 引 论 表达式的语法特征 任何一个标识符都是表达式; 任何一个数都是表达式; 如果e1和e2都是表达式,那么  e1 + e2 第一章 引 论 表达式的语法特征 任何一个标识符都是表达式; 任何一个数都是表达式; 如果e1和e2都是表达式,那么  e1 + e2  e1 * e2  (e1) 也都是表达式 表达式 标识符 (initial) (rate) 数 (60) * + 先介绍语法,然后才介绍语法分析。

第一章 引 论 id1 := id2 + id3 * 60 语法分析器 := + * 60 id1 id2 id3 符 号 表 第一章 引 论 语法分析器 id1 := id2 + id3 * 60 := + * 60 id1 id2 id3 符 号 表 position initial rate . . . 1 2 3

第一章 引 论 语义分析器 := + * 60 id1 id2 id3 inttoreal 符 号 表 position initial 第一章 引 论 语义分析器 := + * 60 id1 id2 id3 inttoreal 符 号 表 position initial rate . . . 1 2 3

第一章 引 论 前三个阶段完成对源程序的分析 词法分析器 语法分析器 语义分析器 源程序 中间代码生成器 代码优化器 代码生成器 目标程序 第一章 引 论 词法分析器 语法分析器 语义分析器 源程序 中间代码生成器 代码优化器 代码生成器 目标程序 出错管理器 符号表管理器 前三个阶段完成对源程序的分析

第一章 引 论 中间代码生成器 temp1 := inttoreal(60) temp2 := id3 * temp1 第一章 引 论 中间代码生成器 temp1 := inttoreal(60) temp2 := id3 * temp1 temp3 := id2 + temp2 id1 := temp3 := + * 60 id1 id2 id3 inttoreal 符 号 表 position initial rate . . . 1 2 3

第一章 引 论 代码优化器 temp1 := inttoreal(60) temp2 := id3 * temp1 第一章 引 论 代码优化器 temp1 := inttoreal(60) temp2 := id3 * temp1 temp3 := id2 + temp2 id1 := temp3 temp1 := id3 * 60.0 id1 := id2 + temp1 符 号 表 position initial rate . . . 1 2 3

第一章 引 论 代码生成器 temp1 := id3 * 60.0 id1 := id2 * temp1 符 号 表 position 第一章 引 论 temp1 := id3 * 60.0 id1 := id2 * temp1 符 号 表 position initial rate . . . 1 2 3 代码生成器 MOVF id3, R2 MULF #60.0, R2 MOVF id2, R1 ADDF R2, R1 MOVF R1, id1

第一章 引 论 后三个阶段对源程序进行综合 词法分析器 语法分析器 语义分析器 源程序 中间代码生成器 代码优化器 代码生成器 目标程序 第一章 引 论 词法分析器 语法分析器 语义分析器 源程序 中间代码生成器 代码优化器 代码生成器 目标程序 出错管理器 符号表管理器 后三个阶段对源程序进行综合

第一章 引 论 词法分析器 语法分析器 语义分析器 源程序 中间代码生成器 代码优化器 代码生成器 目标程序 出错管理器 符号表管理器

第一章 引 论 解释器和编译器的区别 词法分析器 语法分析器 语义分析器 源程序 中间代码生成器 代码优化器 代码生成器 目标程序 第一章 引 论 词法分析器 语法分析器 语义分析器 源程序 中间代码生成器 代码优化器 代码生成器 目标程序 出错管理器 符号表管理器 解释器和编译器的区别

第一章 引 论 BASIC语言年代解释器 Java语言年代解释器 第一章 引 论 BASIC语言年代解释器 功能:它将高级语言的源程序翻译成一种中间语言程序,然后对中间语言程序进行解释执行 在那个年代,编译和解释两个功能是合在一个程序中,该程序被称为解释器 Java语言年代解释器 解释器的上述两个功能分在两个程序中 前一个编译器,它把源程序翻译成一种叫做字节码的中间语言程序 后一个叫做解释器,它对字节码程序进行解释执行

第一章 引 论 阶段分组 前端 后端 词法分析器 语法分析器 语义分析器 源程序 中间代码生成器 代码优化器 代码生成器 目标程序 第一章 引 论 词法分析器 语法分析器 语义分析器 源程序 中间代码生成器 代码优化器 代码生成器 目标程序 出错管理器 符号表管理器 阶段分组 前端 后端

第一章 引 论 阶段分组 遍 词法分析器 语法分析器 语义分析器 源程序 中间代码生成器 代码优化器 代码生成器 目标程序 出错管理器 第一章 引 论 词法分析器 语法分析器 语义分析器 源程序 中间代码生成器 代码优化器 代码生成器 目标程序 出错管理器 符号表管理器 阶段分组 遍

第二章 词法分析 本章内容 词法分析器:把构成源程序的字符流翻译成记号流,还完成和用户接口的一些任务 围绕词法分析器的自动生成展开 第二章 词法分析   词法分析器 语法分析器 符号表 记号 取下一个记号 源程序 本章内容 词法分析器:把构成源程序的字符流翻译成记号流,还完成和用户接口的一些任务 围绕词法分析器的自动生成展开 介绍正规式、状态转换图和有限自动机概念

2.1 词法记号及属性 2.1.1 词法记号、模式、词法单元 词法记号 词法单元例举 模式的非形式描述 var var var 词法记号 词法单元例举 模式的非形式描述 var var var for for for relation < , < = , = , … < 或 <= 或 = 或 … id sum, count, D5 由字母开头的字母数字串 num 3.1, 10, 2.8 E12 任何数值常数 literal “seg. error” 引号“和”之间的任意字符 串,但引号本身除外

2.1 词法记号及属性 历史上词法定义中的一些问题 关键字、保留字和标准标识符的区别 忽略空格带来的困难 DO 8 I  3. 75 DO8I  3. 75 DO 8 I  3, 75 关键字是否保留 IF THEN THEN THEN=ELSE;ELSE … 关键字、保留字和标准标识符的区别

2.1 词法记号及属性 2.1.2 词法记号的属性 position := initial + rate * 60的记号和属性值: id,指向符号表中position条目的指针 assign _ op,  id,指向符号表中initial条目的指针 add_op,+ id,指向符号表中rate条目的指针 mul_ op, * num,整数值60

2.1 词法记号及属性 2.1.3 词法错误 词法分析器对源程序采取非常局部的观点 难以发现下面的错误 fi (a == f (x) ) … 在实数是a.b格式下,可以发现下面的错误 123. 紧急方式的错误恢复 错误修补

2.2 词法记号的描述与识别 2.2.1 串和语言 串的运算 字母表:符号的有限集合, 例: = {0, 1} 串:符号的有穷序列,例:0110,  语言:字母表上的一个串集 {, 0, 00, 000, …}, {},  句子:属于语言的串 串的运算 连接 xy,s = s = s 积(指数) s0为,si为si -1s(i > 0)

2.2 词法记号的描述与识别 语言的运算 例 和:L  M = {s | s L 或 s  M } 连接:LM = {st | s  L 且 t  M} 指数:L0是{ },Li是Li -1L 闭包:L = L0  L1  L2  … 正闭包: L+ = L1  L2  … 例 L: { A, B, …, Z, a, b, …, z }, D: { 0, 1, …, 9 } L  D, LD, L6, L*, L(L  D )*, D+

2.2 词法记号的描述与识别 2.2.2 正规式 正规式用来表示简单的语言,叫做正规集 正规式 定义的语言 备注  {} 正规式 定义的语言 备注  {} a {a} a   (r) | (s) L(r)∪L(s) r和s是正规式 (r)(s) L(r)L(s) r和s是正规式 (r)* (L(r))* r是正规式 (r) L(r) r是正规式 ((a) (b)*)| (c)可以写成ab*| c

2.2 词法记号的描述与识别 正规式的例子  = {a, b} 复杂的例子 句子:01001101000010000010111001 a | b {a, b} (a | b) (a | b ) {aa, ab, ba, bb} aa | ab | ba | bb {aa, ab, ba, bb} a* 由字母a构成的所有串集 (a | b)* 由a和b构成的所有串集 复杂的例子 ( 00 | 11 | ( (01 | 10) (00 | 11)  (01 | 10) ) )  句子:01001101000010000010111001

2.2 词法记号的描述与识别 2.2.3 正规定义 对正规式命名,使表示简洁。 d1  r1 d2  r2 . . . dn  rn 各个di的名字都不同 每个ri都是 {d1, d2, …, di-1 }上的正规式

2.2 词法记号的描述与识别 正规定义的例子 Pascal语言的标识符集合 letter  A | B | … | Z | a | b | … | z digit  0 | 1 | … | 9 id  letter(letter|digit)*

2.2 词法记号的描述与识别 正规定义的例子 Pascal无符号数集合,例1946,11.28,63E8,1.99E6 digit  0 | 1 | … | 9 digits  digit digit* optional_fraction  .digits| optional_exponent  (E ( + |  |  ) digits ) |  num  digits optional_fraction optional_exponent 简化表示 num  digit+ (.digit+)? (E(+|)? digit+)?

2.2 词法记号的描述与识别 正规定义的例子 while  while do  do relop  < | < = | = | < > | > | > = id  letter (letter | digit )* num  digit+ (.digit+)? (E (+ | )? digit+)? delim  blank | tab | newline ws  delim+

2.2 词法记号的描述与识别 2.2.4 转换图  关系算符的转换图 return(relop, LE) 2 = >   5 1 6 2 4 8 3 7 return(relop, LE) return(relop, NE) return(relop, LT) return(relop, GE) return(relop, GT) return(relop, EQ) 开始 < = > * other

2.2 词法记号的描述与识别 标识符和保留字的转换图 开始 letter other letter或digit 9 10 11 开始 letter other * letter或digit return(install_id( ))

2.2 词法记号的描述与识别 无符号数的转换图 num  digit+ (.digit+)? (E (+ | )? digit+)? 开始 19 12 13 14 15 16 17 18 digit other . E +/ return( install_num( ) ) *

2.2 词法记号的描述与识别 空白的转换图 delim  blank | tab | newline ws  delim+ 21 22 开始 delim other * 20

2.3 有 限 自 动 机 2.3.1 不确定的有限自动机(简称NFA) 一个数学模型,它包括: 状态集合S; 输入符号集合; 2.3 有 限 自 动 机 2.3.1 不确定的有限自动机(简称NFA) 一个数学模型,它包括: 状态集合S; 输入符号集合; 转换函数move : S  ({})  P(S); 状态s0是开始状态; F  S是接受状态集合。 1 2 开始 a b 识别语言 (a|b)*ab 的NFA

2.3 有 限 自 动 机 NFA的转换表 输 入 符 号 a b {0, 1} {0} 1  {2} 2 状 态 1 2 开始 a b 2.3 有 限 自 动 机 NFA的转换表 输 入 符 号 a b {0, 1} {0} 1  {2} 2 状 态 1 2 开始 a b 识别语言 (a|b)*ab 的NFA

2.3 有 限 自 动 机 例 识别aa*|bb*的NFA 1 2 开始 a b 3 4 

2.3 有 限 自 动 机 2.3.2 确定的有限自动机(简称DFA) 一个数学模型,包括: 状态集合S; 输入字母表; 2.3 有 限 自 动 机 2.3.2 确定的有限自动机(简称DFA) 一个数学模型,包括: 状态集合S; 输入字母表; 转换函数move : S    S; 唯一的初态 s S; 终态集合F  S; 1 2 开始 a b 识别语言 (a|b)*ab 的DFA

2.3 有 限 自 动 机 例:识别 ={0,1}上能被能5整除的二进制数 《编译原理习题精选》1.5题。 101 0111000 2.3 有 限 自 动 机 例:识别 ={0,1}上能被能5整除的二进制数 1 2 3 开始 4 《编译原理习题精选》1.5题。 101 0111000 1010 111000 10101 11000

2.3 有 限 自 动 机 例:识别 ={0,1}上能被能5整除的二进制数 1 2 3 开始 4

2.3 有 限 自 动 机 例:识别 ={0,1}上能被能5整除的二进制数 1 2 3 开始 4

2.3 有 限 自 动 机 例:识别 ={0,1}上能被能5整除的二进制数 1 2 3 开始 4

2.3 有 限 自 动 机 例:识别 ={0,1}上能被能5整除的二进制数 1 2 3 开始 4

2.3 有 限 自 动 机 例:识别 ={0,1}上能被能5整除的二进制数 1 2 3 开始 4

2.3 有 限 自 动 机 例:识别 ={0,1}上能被能5整除的二进制数 1 2 3 开始 4

2.3 有 限 自 动 机 例:识别 ={0,1}上能被能5整除的二进制数 1 2 3 开始 4

2.3 有 限 自 动 机 例:识别 ={0,1}上能被能5整除的二进制数 1 2 3 开始 4

2.3 有 限 自 动 机 例:识别 ={0,1}上能被能5整除的二进制数 1 2 3 开始 4

2.3 有 限 自 动 机 例:识别 ={0,1}上能被能5整除的二进制数 1 2 3 开始 4

2.3 有 限 自 动 机 例:识别 ={0,1}上能被能5整除的二进制数 10102 = 1010 1112 = 710 1 2 3 2.3 有 限 自 动 机 例:识别 ={0,1}上能被能5整除的二进制数 1 2 3 开始 4 10102 = 1010 1112 = 710

2.3 有 限 自 动 机 例:DFA,接受 0和1的个数都是偶数的字符串 3 1 2 开始 偶0偶1 奇0奇1 奇0偶1 偶0奇1

2.3 有 限 自 动 机 2.3.3 NFA到DFA的变换 子集构造法 DFA的一个状态是NFA的一个状态集合 2.3 有 限 自 动 机 2.3.3 NFA到DFA的变换 子集构造法 DFA的一个状态是NFA的一个状态集合 读了输入a1 a2 … an后, NFA能到达的所有状态:s1, s2, …, sk,则 DFA到达状态{s1, s2, …, sk} 1 2 a 开始 b

2.3 有 限 自 动 机 2.3.3 NFA到DFA的变换 子集构造法 DFA的一个状态是NFA的一个状态集合 2.3 有 限 自 动 机 2.3.3 NFA到DFA的变换 子集构造法 DFA的一个状态是NFA的一个状态集合 读了输入a1 a2 … an后, NFA能到达的所有状态:s1, s2, …, sk,则 DFA到达状态{s1, s2, …, sk} 1 2 a 开始 b {0} {0, 1} a

2.3 有 限 自 动 机 2.3.3 NFA到DFA的变换 子集构造法 DFA的一个状态是NFA的一个状态集合 2.3 有 限 自 动 机 2.3.3 NFA到DFA的变换 子集构造法 DFA的一个状态是NFA的一个状态集合 读了输入a1 a2 … an后, NFA能到达的所有状态:s1, s2, …, sk,则 DFA到达状态{s1, s2, …, sk} 1 2 a 开始 b {0} {0, 1} a b

2.3 有 限 自 动 机 2.3.3 NFA到DFA的变换 子集构造法 DFA的一个状态是NFA的一个状态集合 2.3 有 限 自 动 机 2.3.3 NFA到DFA的变换 子集构造法 DFA的一个状态是NFA的一个状态集合 读了输入a1 a2 … an后, NFA能到达的所有状态:s1, s2, …, sk,则 DFA到达状态{s1, s2, …, sk} 1 2 a 开始 b {0} {0, 1} a b

2.3 有 限 自 动 机 2.3.3 NFA到DFA的变换 子集构造法 DFA的一个状态是NFA的一个状态集合 2.3 有 限 自 动 机 2.3.3 NFA到DFA的变换 子集构造法 DFA的一个状态是NFA的一个状态集合 读了输入a1 a2 … an后, NFA能到达的所有状态:s1, s2, …, sk,则 DFA到达状态{s1, s2, …, sk} 1 2 a 开始 b {0} {0, 1} a b {0, 2}

2.3 有 限 自 动 机 输入符号 a b 状态 1 9 开始  a b 6 7 8 2 3 4 5

2.3 有 限 自 动 机 输入符号 a b A A = {0, 1, 2, 4, 7} 状态 1 9 开始  a b 6 7 8 2 3 2.3 有 限 自 动 机 输入符号 a b A A = {0, 1, 2, 4, 7} 状态 1 9 开始  a b 6 7 8 2 3 4 5

2.3 有 限 自 动 机 输入符号 a b A B A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} 状态 1 9 开始  a b 6 7 8 2 3 4 5

2.3 有 限 自 动 机 输入符号 a b A B A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} 状态 1 9 开始  a b 6 7 8 2 3 4 5

2.3 有 限 自 动 机 输入符号 a b A B C A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} C = {1, 2, 4, 5, 6, 7} 状态 1 9 开始  a b 6 7 8 2 3 4 5

2.3 有 限 自 动 机 输入符号 a b A B C A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} C = {1, 2, 4, 5, 6, 7} 状态 1 9 开始  a b 6 7 8 2 3 4 5

2.3 有 限 自 动 机 输入符号 a b A B C A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} C = {1, 2, 4, 5, 6, 7} 状态 1 9 开始  a b 6 7 8 2 3 4 5

2.3 有 限 自 动 机 输入符号 a b A B C D A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} C = {1, 2, 4, 5, 6, 7} D = {1, 2, 4, 5, 6, 7, 9} 状态 1 9 开始  a b 6 7 8 2 3 4 5

2.3 有 限 自 动 机 输入符号 a b A B C D A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} C = {1, 2, 4, 5, 6, 7} D = {1, 2, 4, 5, 6, 7, 9} 状态 1 9 开始  a b 6 7 8 2 3 4 5

2.3 有 限 自 动 机 输入符号 a b A B C D A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} C = {1, 2, 4, 5, 6, 7} D = {1, 2, 4, 5, 6, 7, 9} 状态 1 9 开始  a b 6 7 8 2 3 4 5

2.3 有 限 自 动 机 输入符号 a b A B C D A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} C = {1, 2, 4, 5, 6, 7} D = {1, 2, 4, 5, 6, 7, 9} 状态 1 9 开始  a b 6 7 8 2 3 4 5

2.3 有 限 自 动 机 输入符号 a b A B C D 状态 从转换表构造转换图。 B D 开始 a A b C 1 9 开始  a 2.3 有 限 自 动 机 输入符号 a b A B C D 状态 B D 开始 a A b C 1 9 开始  a b 6 7 8 2 3 4 5 从转换表构造转换图。

2.3 有 限 自 动 机 识别语言 (a|b)*ab 的自动机 1 2 开始 a b B D 开始 a A b C 1 9 开始  a 2.3 有 限 自 动 机 识别语言 (a|b)*ab 的自动机 1 2 开始 a b B D 开始 a A b C 1 9 开始  a b 6 7 8 2 3 4 5 将前面的DFA和现在的DFA进行比较,引出DFA化简问题。

2.3 有 限 自 动 机 子集构造法不一定得到最简DFA 识别语言 (a|b)*ab 的自动机 1 2 开始 a b B D 开始 a A 2.3 有 限 自 动 机 识别语言 (a|b)*ab 的自动机 1 2 开始 a b B D 开始 a A b C 子集构造法不一定得到最简DFA 1 9 开始  a b 6 7 8 2 3 4 5 将前面的DFA和现在的DFA进行比较,引出DFA化简问题。

2.3 有 限 自 动 机 2.3.4 DFA的化简 死状态 左图无须加死状态,右图加入死状态E。 B D 开始 a A b a, b C 2.3 有 限 自 动 机 2.3.4 DFA的化简 死状态 左图无须加死状态,右图加入死状态E。 B D 开始 a A b a, b C E B D 开始 a A b C

2.3 有 限 自 动 机 可区别的状态 A和B是可区别的状态 A和C是不可区别的状态 B D 开始 a A b C

2.3 有 限 自 动 机 方法 1. {A, B, C}, {D} move({A, B, C}, a} = {B} 2.3 有 限 自 动 机 方法 1. {A, B, C}, {D} move({A, B, C}, a} = {B} move({A, B, C}, b} = {C, D} 2. {A, C}, {B}, {D} move({A, C}, a} = {B} move({A, C}, b} = {C} B D 开始 a A b C

2.3 有 限 自 动 机 方法 1. {A, B, C}, {D} move({A, B, C}, a} = {B} 2.3 有 限 自 动 机 1 2 开始 a b 方法 1. {A, B, C}, {D} move({A, B, C}, a} = {B} move({A, B, C}, b} = {C, D} 2. {A, C}, {B}, {D} move({A, C}, a} = {B} move({A, C}, b} = {C} B D 开始 a A b C

2.4 从正规式到有限自动机 从正规式建立识别器 从正规式构造NFA(本节介绍) 用语法制导的算法,它用正规式语法结构来指导构造过程。 把NFA变成DFA (子集构造法,已介绍) 将DFA化简 (合并不可区别状态,也已介绍)

2.4 从正规式到有限自动机 首先构造识别和字母表中一个符号的NFA i 开始  识别正规式的NFA a f 识别正规式a的NFA

2.4 从正规式到有限自动机 构造识别主算符为选择的正规式的NFA  f i 开始 识别正规式s | t的NFA N (s) N (t)

2.4 从正规式到有限自动机 构造识别主算符为连接的正规式的NFA i N (s) f 开始 识别正规式st 的NFA N (t)

2.4 从正规式到有限自动机 构造识别主算符为闭包的正规式的NFA N (s) f 开始 识别正规式s* 的NFA i 

2.4 从正规式到有限自动机 对于加括号的正规式(s),使用N(s)本身作为它的NFA。

2.4 从正规式到有限自动机 本方法产生的NFA有下列性质: N(r)的状态数最多是r中符号和算符总数的两倍。

2.4 从正规式到有限自动机 (a|b)*ab的分解 r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 a | b 1 9 开始  a b 6 7 8 2 3 4 5

2.4 从正规式到有限自动机 (a|b)*ab的分解 r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 a | b 1 9 开始  a b 6 7 8 2 3 4 5

2.4 从正规式到有限自动机 (a|b)*ab的分解  1 9 开始 a b 6 7 8 2 3 4 5 r9 r7 r8 r4 r3 a b 6 7 8 2 3 4 5 r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 | (a|b)*ab的分解

2.4 从正规式到有限自动机 (a|b)*ab的分解 1 9 开始  a b 6 7 8 2 3 4 5 r9 r7 r8 r4 r3 a b 6 7 8 2 3 4 5 r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 | (a|b)*ab的分解

2.4 从正规式到有限自动机 (a|b)*ab的分解 1 9 开始  a b 6 7 8 2 3 4 5 r9 r7 r8 r4 r3 a b 6 7 8 2 3 4 5 r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 | (a|b)*ab的分解

2.4 从正规式到有限自动机 (a|b)*ab的分解 1 9 开始  a b 6 7 8 2 3 4 5 r9 r7 r8 r4 r3 a b 6 7 8 2 3 4 5 r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 | (a|b)*ab的分解

2.4 从正规式到有限自动机 (a|b)*ab的分解 1 9 开始  a b 6 7 8 2 3 4 5 r9 r7 r8 r4 r3 a b 6 7 8 2 3 4 5 r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 | (a|b)*ab的分解

2.4 从正规式到有限自动机 (a|b)*ab的两个NFA的比较 手工构造: 算法构造: 1 2 开始 a b b 手工构造: 算法构造: 1 9 开始  a b 6 7 8 2 3 4 5 比较手工构造的NFA和用教材上语法制导的算法构造的NFA。鼓励学生写出引入尽可能少的 转换的语法制导的算法,在将来的解题中使用这个算法。

2.4 从正规式到有限自动机 小结:从正规式建立识别器的步骤 从正规式构造NFA 把NFA变成DFA 将DFA化简 存在其它办法

2.5 词法分析器的生成器 用Lex建立词法分析器的步骤 Lex lex.yy.c Lex源程序lex.l 编译器 C a.out 记号序列 2.5 词法分析器的生成器 用Lex建立词法分析器的步骤 Lex 编译器 Lex源程序lex.l lex.yy.c C a.out 输入流 记号序列

2.5 词法分析器的生成器 Lex程序包括三个部分 Lex程序的翻译规则 声明 %% 翻译规则 辅助过程 p1 {动作1} p2 {动作2} 2.5 词法分析器的生成器 Lex程序包括三个部分 声明 %% 翻译规则 辅助过程 Lex程序的翻译规则 p1 {动作1} p2 {动作2} … … pn {动作n}

2.5 词法分析器的生成器 例---声明部分 %{ /* 常量LT, LE, EQ, NE, GT, GE, WHILE, DO, ID, NUMBER, RELOP的定义*/ %} /* 正规定义 */ delim [ \t \n ] ws {delim}+ letter [A Za  z] digit [09] id {letter}({letter}|{digit})* number {digit}+(\ .{digit}+)?(E[+\]?{digit}+)?

2.5 词法分析器的生成器 例---翻译规则部分 {ws} {/* 没有动作,也不返回 */} 2.5 词法分析器的生成器 例---翻译规则部分 {ws} {/* 没有动作,也不返回 */} while {return (WHILE);} do {return (DO);} {id} {yylval = install_id ( ); return (ID);} {number} {yylval = install_num( ); return (NUMBER);} “ < ” {yylval = LT; return (RELOP);} “ <= ” {yylval = LE; return (RELOP);} “ = ” {yylval = EQ; return (RELOP);} “ <> ” {yylval = NE; return (RELOP);} “ > ” {yylval = GT; return (RELOP);} “ >= ” {yylval = GE; return (RELOP);}

2.5 词法分析器的生成器 例---辅助过程部分 install_ id ( ) { /* 把词法单元装入符号表并返回指针。 2.5 词法分析器的生成器 例---辅助过程部分 install_ id ( ) { /* 把词法单元装入符号表并返回指针。 yytext指向该词法单元的第一个字符, yyleng给出的它的长度 */ } install_num ( ) { /* 类似上面的过程,但词法单元不是标识符而是数 */

本 章 要 点 词法分析器的作用和接口,用高级语言编写词法分析器等内容,它们与词法分析器的实现有关。 本 章 要 点 词法分析器的作用和接口,用高级语言编写词法分析器等内容,它们与词法分析器的实现有关。 掌握下面涉及的一些概念,它们之间转换的技巧、方法或算法。 非形式描述的语言  正规式 正规式  NFA 非形式描述的语言  NFA NFA  DFA DFA  最简DFA 非形式描述的语言  DFA(或最简DFA)

例 题 1 叙述下面的正规式描述的语言,并画出接受该语言的最简DFA的状态转换图。 (1|01)* 0*

例 题 1 叙述下面的正规式描述的语言,并画出接受该语言的最简DFA的状态转换图。 (1|01)* 0* 例 题 1 叙述下面的正规式描述的语言,并画出接受该语言的最简DFA的状态转换图。 (1|01)* 0* 描述的语言是,所有不含子串001的0和1的串。

例 题 1 叙述下面的正规式描述的语言,并画出接受该语言的最简DFA的状态转换图。 (1|01)* 0* 例 题 1 叙述下面的正规式描述的语言,并画出接受该语言的最简DFA的状态转换图。 (1|01)* 0* 描述的语言是,所有不含子串001的0和1的串。 3 start 1 . 2 刚读过的不是0 连续读过一个0 连续读过不少于两个0

例 题 2 用状态转换图表示接收(a|b)a(a|b)(a|b)的DFA。

例 题 2 用状态转换图表示接收(a|b)a(a|b)(a|b)的DFA。 bbabaabb aaa baa aab start a 例 题 2 用状态转换图表示接收(a|b)a(a|b)(a|b)的DFA。 bbb a b start abb aaa aab aba bba baa bab bbabaabb

例 题 3 写出语言“所有相邻数字都不相同的非空数字串”的正规定义。 《编译原理习题精选》1.3。

例 题 3 写出语言“所有相邻数字都不相同的非空数字串”的正规定义。 123031357106798035790123 例 题 3 写出语言“所有相邻数字都不相同的非空数字串”的正规定义。 123031357106798035790123 《编译原理习题精选》1.3。

例 题 3 写出语言“所有相邻数字都不相同的非空数字串”的正规定义。 将这些正规定义逆序排列就是答案 例 题 3 写出语言“所有相邻数字都不相同的非空数字串”的正规定义。 123031357106798035790123 answer  (0 | no_0 0 ) (no_0 0 ) (no_0 |  ) | no_0 no_0  (1 | no_0-1 1 ) (no_0-1 1 ) (no_0-1 |  ) | no_0-1 . . . no_0-8  9 将这些正规定义逆序排列就是答案 《编译原理习题精选》1.3。

例 题 4 parse error before ‘else’ 下面C语言编译器编译下面的函数时,报告 long gcd(p,q) 例 题 4 下面C语言编译器编译下面的函数时,报告 parse error before ‘else’ long gcd(p,q) long p,q; { if (p%q == 0) /* then part */ return q 此处遗漏分号 else /* else part */ return gcd(q, p%q); } 《编译原理习题精选》1.3。

例 题 4 现在少了第一个注释的结束符号后,反而不报错了 long gcd(p,q) long p,q; { if (p%q == 0) 例 题 4 现在少了第一个注释的结束符号后,反而不报错了 long gcd(p,q) long p,q; { if (p%q == 0) /* then part return q 此处遗漏分号 else /* else part */ return gcd(q, p%q); } 《编译原理习题精选》1.3。

习 题 第一次 2.3, 2.4 (f) (g) 第二次 2.7 (c) (d), 2.8 ( 仅为2.7 (c) ), 2.11,2.15