编译原理课件：第三章 词法分析 (3).pptVIP

* * * * * 比较手工构造的NFA和用教材上语法制导的算法构造的NFA。鼓励学生写出引入尽可能少的? 转换的语法制导的算法，在将来的解题中使用这个算法。 * * * * * * * * * * * * * * * 《编译原理习题精选》1.3。 第三章 词法分析 上节回顾 正则表达式 ? NFA ? DFA ? 最简DFA 1 9 开始 ? 0 a b ? a b 6 7 8 2 3 4 5 ? ? ? ? ? ? 输入符号 a b A B C B B D C B C D B C 状态 B D 开始 a A a b b a b C b a NFA ? DFA 第三章 词法分析 上节回顾 正则表达式 ? NFA ? DFA ? 最简DFA 方法 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 a b b a b C b a 1 2 开始 a 0 a b b a b DFA ? 最简DFA 第三章 词法分析 上节回顾 实现词法分析器的方法： 正则表达式 ? NFA ? DFA ? 最简DFA 正则表达式 ? DFA 直接从正则式到DFA，不需要构造中间的NFA 例： 正则表达式 ? DFA 3.5 词法分析器的生成器 词法分析器生成工具的设计 3.5 词法分析器的生成器 词法分析器生成工具的设计 例： a {模式P1的动作A1} abb {模式P2的动作A2} a*b+ {模式P3的动作A3} 3.5 词法分析器的生成器 词法分析器生成工具的设计 例： a {模式P1的动作A1} abb {模式P2的动作A2} a*b+ {模式P3的动作A3} 3.5 词法分析器的生成器 词法分析器生成工具的设计 例： a {模式P1的动作A1} abb {模式P2的动作A2} a*b+ {模式P3的动作A3} 词法分析器的作用和接口，用高级语言编写词法分析器等内容 掌握下面涉及的一些概念，它们之间转换的技巧、方法或算法 非形式描述的语言 ? 正则式 正则式 ? NFA 非形式描述的语言 ? NFA NFA ? DFA DFA ? 最简DFA 非形式描述的语言 ? DFA（或最简DFA） 本 章 要 点 叙述下面的正则式描述的语言，并画出接受该语言的最简DFA的状态转换图 (1|01)* 0* 描述的语言是，所有不含子串001的0和1的串 3 start 0 0 1 . 1 0 1 2 刚读过的不是0 连续读过一个0 连续读过 不少于两个0 例 题 1 bbb a a b b a a b b start abb aaa aab aba bba baa bab a b a b a b a b bbabaabb 例 题 2 用状态转换图表示接受 (a|b)?a(a|b)(a|b)的DFA 写出语言“所有相邻数字都不相同的非空数字串”的正则定义 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 将这些正则定义逆序排列就是答案 例 题 3 * * * * * * * * * * * * * * * * 3.3.4 DFA的化简 构造最简DFA： 构造状态集合的初始划分π：两个子集——接受状态子集F和非接受状态子集S – F 应用下面的过程构造πnew For π 中的每个子集G ，do begin 把G划分为若干子集，G的两个状态 s 和 t 在同一子集中，当且仅当对任意输入符号 a ，s 和 t 的 a 转换都到 π 的同一子集中 在πnew 中，用G的划分代替G End 如果πnew = π，则πfinal = π；否则令π = πnew ，转上步 3.3 有 限 自 动 机 3.3.4 DFA的化简 构造最简DFA： 构造状态集合的初始划分π：两个子集——接受状态子集F和非接