编译原理 第三章 词法分析

3.8词法分析器生成工具的设计 词法分析器模型 图3.49 词法分析器工作方式 DFA模拟器 图3.27 NFA模拟器 图3.27

3.8词法分析器生成工具的设计 词法分析器生成工具工作方式 实例 3.26 任务包括多个正则表达式，且分别对应不同的语义动作。 a {模式P1的动作A1} abb {模式P2的动作A2} a*b+ {模式P3的动作A3}

3.8词法分析器生成工具的设计 词法分析器生成工具工作方式 NFA/DFA转换表的构造 把每个正则表达式转换为一个NFA 按照图3.50方式，把所有NFA合并为一个NFA。 把这个NFA转换为一个DFA，使用这个DFA识别与所有正则表达式相匹配的词素。

3.8词法分析器生成工具的设计 词法分析器生成工具的设计 基于NFA的模式匹配 图3.53 一直运行到达一个没有后续状态的输入点后，首先回头查找一个包含可接收状态的集合，即利用最长匹配确定可接受状态集合，然后根据重要性（例如根据正则表达式出现顺序）确定哪个正则表达式。最后进行forward指针修复，同时执行与此正则表达式相关的语义动作。

3.8词法分析器生成工具的设计 词法分析器生成工具的设计 基于DFA的模式匹配 图3.54 与NFA类似：DFA可接受状态包含一个或多个NFA可接受状态。

3.9直接从正则式到DFA（3.9.1-3.9.5） 转换方式：不需构造中间的NFA 动机：可能的状态转移只与某些状态相关 转移函数：move(s,a)/move(S,a) 存在一个非ε标号(Σ中字母) 离开该状态s，即存在某个 字母a, 转移函数move(s,a)非空。

3.9直接从正则式到DFA 构造原理 重要状态 拓广正则表达式 （r）# 对应于正则式中字母的每次出现位置，即抽象语法树的非ε叶子节点。 加入右端结束标记#确保接受状态是重要状态！ 实例 (a|b)*abb# 图3-56

3.9直接从正则式到DFA 构造原理 转换表：聚焦重要状态之间的转移 开始状态：可能出现在给定正则表达式描述的语言中任何一个串第一个符号位置的所有重要状态。 接受状态：和结尾#相关的位置

3.9直接从正则式到DFA 构造算法 定义四个函数：nullable、firstpos、lastpos、followpos

3.9直接从正则式到DFA 构造算法 计算nullable、firstpos、lastpos：图3.58&3.59

3.9直接从正则式到DFA 构造算法 计算followpos：图3.60&3.61

3.9直接从正则式到DFA 构造算法 算法3.36 图3.62 vs 图3.32子集构造法 初始状态：firstpos(n0) vs ε-closure(s0) 后续状态：S中和a对应的所有位置p的followpos(p) vs ε-closure(move(T,a)) S中有些p与a对应，有些不对应。

3.9直接从正则式到DFA 构造算法 实例 例3.37 得到的DFA状态比通过NFA得到的DFA状态少！

3.10 DFA最简化（3.9.6-3.9.7） DFA最简化原理 最简DFA唯一性：每一个正则式可以由一个状态数最少的DFA识别，且这个DFA唯一。 可行性：DFA存在不可区别状态，可以合并。 化简条件：确保DFA是全函数 DFA可能是部分函数：存在状态s符号a，move(s,a)不存在！ 解决方式：DFA化简前引入死状态（化简后可以去掉死状态）

3.10 DFA最简化 死状态 在转换函数由部分函数改成全函数表示时引入。 死状态对所有输入符号都转换到本身。 左图需要引入死状态E ；右图无须引入死状态。 B D 开始 a A b a, b C E B D 开始 a A b C

3.10 DFA最简化 可区别状态 状态s和t可区别：存在一个串x，分别从状态s和t出发，沿着标号为x的路径到达的两个状态中只有一个是接受状态。 A和B是可区别的状态：从A出发，通过串b，到达非接受状态C，而从B出发，通过过串b，到达接受状态D。 A和C是不可区别的状态（等价的状态）：无任何串可像上面这样区别它们。 B D 开始 a A b C

3.10 DFA最简化 最简化DFA算法：算法3.39 图3.64 构造状态集合的初始划分π：两个子集——接受状态子集F和非接受状态子集S – F 可以存在多个接受状态子集：每个对应不同词法单元的识别。 应用下面的过程构造πnew 对于π 中的每个子集G 把G划分为若干子集，G的两个状态 s 和 t 在同一子集中，当且仅当对任意输入符号 a ，s 和 t 的 a 转换都到 π 的同一子集中。 在πnew 中，用G的划分代替G 如果πnew = π，则πfinal = π；否则令π = πnew ，转上步 在πfinal的每个状态子集中选一个状态代表它（同一个状态子集中的各个状态等价，不可区别），即为最简DFA的状态。 最简DFA的开始状态：包含了原始DFA开始状态的组的代表 最简DFA的接受状态：包含了原始DFA接受状态的组的代表 转换表：对于πfinal 中状态子集G和H的代表s和r，如果存在move(s,a)=t且t属H，那么move(s,a)=r。

3.10 DFA最简化 最简化DFA算法：实例 S-F={A, B, C}, F={D} {A, C}, {B}, {D} move(A,a)=B move(B,a)=B move(C,a)=B move(A,b)=C move(B,b)=D move(C,a)=C 1 2 开始 a b B D 开始 a A b C

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

例 题 2 bbabaabb 用状态转换图表示接受 (a|b)a(a|b)(a|b)的DFA 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.10）

第三章：总结 第三章总结（3.10）

第三章：总结 第三章总结（3.10）