陈意云全套配套课件编译原理原理与技术 第2章 词法分析2

《陈意云全套配套课件编译原理原理与技术 第2章 词法分析2》由会员分享，可在线阅读，更多相关《陈意云全套配套课件编译原理原理与技术 第2章 词法分析2（72页珍藏版）》请在金锄头文库上搜索。

1、第2章 词法分析 本章内容 词法分析器 把构成源程序的字符流翻译成 记号流 还完成和用户接口的一些任务 围绕词法分析器的自动生成展开 介绍正规式 状态转换图和有限自动机概念 词法分析器 语法分析器 符号表 记号 token 取下一个记号 源程序 2 1 词法记号及属性 2 1 1 词法记号 模式 词法单元 记号名词法单元例举模式的非形式描述 if if 字符i f for for字符f o r relation 或 0 2 2 词法记号的描述与识别 语言的运算 并 L M s s L 或 s M 连接 LM st s L 且 t M 幂 L0是 Li是Li 1L 闭包 L L0 L1 L2 正

2、闭包 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 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构成

3、的所有串集 含 复杂的例子 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 词法记号的描述与识别 正规定义的例子 C语言的标识符是字母 数字和下划线组成的串 letter A B Z a b z digit 0 1 9 id letter letter digit 2 2 词法记号的描述与识别 正规定义的例子 无符号数集合 例1946 11

4、28 63E8 1 99E 6 digit 0 1 9 digits digit digit optional fraction digits optional exponent E digits number digits optional fraction optional exponent 简化表示 number digit digit E digit 2 2 词法记号的描述与识别 正规定义的例子 进行下一步讨论的例子 while while do do relop letter A B Z a b z id letter letter digit number digit digit

5、E digit delim blank tab newline ws delim 2 2 词法记号的描述与识别 2 2 4 转换图 关系算符的转换图 0 6 1 7 2 4 9 3 8 return relop LE return relop NE return relop LT return relop GE return relop GT return relop EQ 开始 other other 5 2 2 词法记号的描述与识别 标识符和保留字的转换图 101112 开始 letterother letter或digit return installId 2 2 词法记号的描述与识别

6、无符号数的转换图 number digit digit E digit 开始 20 13 141516171819 digit digit digit digit digit digit other E E digit other other return installNum 2 2 词法记号的描述与识别 空白的转换图 delim blank tab newline ws delim 2223 开始delimother delim 21 2 3 有 限 自 动 机 2 3 1 不确定的有限自动机 简称NFA 一个数学模型 它包括 1 有限的状态集合S 2 输入符号集合 3 转换函数move

7、S P S 4 状态s0是唯一的开始状态 5 F S是接受状态集合 识别语言 a b ab 的NFA 12 开始a 0 a b b 输 入 符 号 ab 0 0 1 0 1 2 2 状 态 NFA的转换表 2 3 有 限 自 动 机 识别语言 a b ab 的NFA 12 开始a 0 a b b 2 3 有 限 自 动 机 例 识别识别 aa bb 的NFA 12 开始 a 0 a b b 34 2 3 2 确定的有限自动机 简称DFA 一个数学模型 包括 1 有限的状态集合S 2 输入符号集合 3 转换函数move S S 且可以是部分函数 4 唯一的开始状态 s0 5 接受状态集合F S

8、12 开始a 0 a b b a b 识别语言 a b ab 的DFA 2 3 有 限 自 动 机 2 3 有 限 自 动 机 例 DFA 识别 0 1 上能被5整除的二进制数 已读过尚未读已读部分的值 某时刻10101110005 读进01010 1110005 2 10 读进110101 1100010 2 1 21 5个状态即可 分别代表已读部分的值除以5的余数 例 DFA 识别 0 1 上能被5整除的二进制数 0123 开始 4 1 0 0 1 0 1 0 10 1 2 3 有 限 自 动 机 10102 1010 1112 710 2 3 3 NFA到DFA的变换 子集构造法 1 D

9、FA的一个状态是NFA的一个状态集合 2 读了输入a1 a2 an后 NFA能到达的所有状态 s1 s2 sk 则 DFA到达状态 s1 s2 sk 12 a 开始 0 a b b 0 0 1 a b a 0 2 b 2 3 有 限 自 动 机 未画完 19 开始 0 a b ab 678 23 45 例 a b ab NFA如下 把它变换为DFA 2 3 有 限 自 动 机 19 开始 0 a b ab 678 23 45 输入符号 ab 状态 2 3 有 限 自 动 机 19 开始 0 a b ab 678 23 45 输入符号 ab A 状态 A 0 1 2 4 7 2 3 有 限 自

10、动 机 19 开始 0 a b ab 678 23 45 输入符号 ab AB 状态 A 0 1 2 4 7 B 1 2 3 4 6 7 8 2 3 有 限 自 动 机 19 开始 0 a b ab 678 23 45 输入符号 ab AB B 状态 A 0 1 2 4 7 B 1 2 3 4 6 7 8 2 3 有 限 自 动 机 19 开始 0 a b ab 678 23 45 输入符号 ab ABC B 状态 A 0 1 2 4 7 B 1 2 3 4 6 7 8 C 1 2 4 5 6 7 2 3 有 限 自 动 机 19 开始 0 a b ab 678 23 45 输入符号 ab A

11、BC B C 状态 A 0 1 2 4 7 B 1 2 3 4 6 7 8 C 1 2 4 5 6 7 2 3 有 限 自 动 机 19 开始 0 a b ab 678 23 45 输入符号 ab ABC BB C 状态 A 0 1 2 4 7 B 1 2 3 4 6 7 8 C 1 2 4 5 6 7 2 3 有 限 自 动 机 19 开始 0 a b ab 678 23 45 输入符号 ab ABC BBD C 状态 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 2 3 有 限 自 动 机 19 开始 0 a b ab

12、678 23 45 输入符号 ab ABC BBD 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 2 3 有 限 自 动 机 19 开始 0 a b ab 678 23 45 输入符号 ab ABC BBD CBC 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 2 3 有 限 自 动 机 19 开始 0 a b ab 678 23 45 输入符号 ab ABC BBD CBC DBC 状态 A 0 1 2 4 7 B 1 2 3 4

13、 6 7 8 C 1 2 4 5 6 7 D 1 2 4 5 6 7 9 2 3 有 限 自 动 机 19 开始 0 a b ab 678 23 45 输入符号 ab ABC BBD CBC DBC 状态 BD 开始a A a b b a b C b a 2 3 有 限 自 动 机 19 开始 0 a b ab 678 23 45 BD 开始a A a b b a b C b a 12 开始 a 0 a b b a b 识别语言 a b ab 的自动机 2 3 有 限 自 动 机 19 开始 0 a b ab 678 23 45 BD 开始a A a b b a b C b a 12 开始 a

14、 0 a b b a b 识别语言 a b ab 的自动机 子集构造法不一 定得到最简DFA 2 3 有 限 自 动 机 BD 开始a A a b b a a b C b a E b 2 3 4 DFA的化简 死状态 在转换函数由部分函数改成全函数表示时引入 左图需要引入死状态E 右图无须引入死状态 BD 开始a A a b b a b C b a 2 3 有 限 自 动 机 可区别的状态 A和B是可区别的状态 从A出发 读过串b 到达非接受状态C 而 从B出发 读过串b 到达接受状态D A和C是不可区别的状态 无任何串可用来像上面这样 区别它们 BD 开始a A a b b a b C b

15、a 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 BD 开始a A a b b a b C b a 1 2 开始 a 0 a b b a b 2 3 有 限 自 动 机 从正规式建立识别器的步骤 从正规式构造NFA 本节介绍 用语法制导的算法 它用正规式语法结构来指导 构造过程 把NFA变成DFA 子集构造法 已介绍 将DFA化简 合并不可区别的状态 也已介绍 2 4 从正规式到有限自动机 首先构造识别 和字母表中一个符号的NFA 重要特点 仅一个接受

16、状态 它没有向外的转换 i 开始 识别正规式 的NFA a fif 开始 识别正规式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 中符号和算符总数的两倍 N r 只有一个接受状态 接受状态没有向外的转 换 2 4 从正规式到有限自动机 1 9 开始 0 a b ab 678 23 45 本方法产生的NFA有下列性质 N r 的每个状态有一个用 的符号标记的指