编译原理和技术.

Presentation on theme: "编译原理和技术."— Presentation transcript:

1 编译原理和技术

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

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

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

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

6 对 课 程 的 评 论 本校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年） 看过你编的书后，感觉编译的原理可以一下子和我平常学的很多学科和语言都联系起来了，可以学到很多可以实际用到的东西，虽然是在讲同样的东西，但您的教学方式让我很适应，学起来也很有兴趣，大大减轻了我考研的疲劳感。

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

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

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

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

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

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

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

14 第一章 引 论 中间代码生成器 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

15 第一章 引 论 代码优化器 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

16 第一章 引 论 代码生成器 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

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

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

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

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

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

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

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

24 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” 引号“和”之间的任意字符 串，但引号本身除外

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

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

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

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

29 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+

30 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

31 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) ) )  句子：

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

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

34 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+)?

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

36 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

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

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

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

40 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

41 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

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

43 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

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

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

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

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

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

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

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

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

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

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

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

55 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

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

57 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

58 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

59 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

60 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

61 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}

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

63 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

64 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

65 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

66 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

67 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

68 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

69 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

70 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

71 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

72 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

73 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 从转换表构造转换图。

74 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化简问题。

75 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化简问题。

76 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

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

78 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

79 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

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

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

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

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

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

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

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

87 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

88 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

89 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的分解

90 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的分解

91 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的分解

92 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的分解

93 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的分解

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

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

96 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 输入流 记号序列

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

98 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}+)?

99 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);}

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

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

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

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

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

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

106 例 题 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

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

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

109 例 题 3 写出语言“所有相邻数字都不相同的非空数字串”的正规定义。 将这些正规定义逆序排列就是答案
例 题 3 写出语言“所有相邻数字都不相同的非空数字串”的正规定义。 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。

110 例 题 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。

111 例 题 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。

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