编译原理03.ppt

上次课主要内容 2.3.1 不确定的有限自动机（续10） 2.3.2 确定的有限自动机（Deterministic Finite Automaton, DFA） 2.3.2 确定的有限自动机（续1） 2.3.2 确定的有限自动机（续2） 2.3.2 确定的有限自动机（续3） 2.3.3 有限自动机的等价 2.4 从正规式到词法分析器 2.4.1 从正规式到NFA 2.4.1 从正规式到NFA（续1） 2.4.1 从正规式到NFA（续2） 2.4.1 从正规式到NFA（续3） 2.4.2 从NFA到DFA 2.4.2 从NFA到DFA（续1） 2.4.2 从NFA到DFA（续2） 2.4.2 从NFA到DFA（续3） 2.4.2 NFA到DFA（续4） 2.4.2 NFA到DFA（续5） 2.4.2 NFA到DFA（续6） 2.4.2 NFA到DFA（续7） 2.4.2 NFA到DFA（续8） 2.4.2 NFA到DFA（续9） 上次课主要内容 2.4.2 NFA到DFA（续8） 2.4.2 NFA到DFA（续9） 2.4.3 最小化DFA 2.4.3 最小化DFA（续1） 2.4.3 最小化DFA（续1） 2.4.3 最小化DFA（续2） 2.4.3 最小化DFA（续3） 2.4.4 由DFA构造词法分析器 2 直接编码的词法分析器 2 直接编码的词法分析器（续1） 3 两类分析器的比较 2.5 本章小结 2.5 本章小结（续） 算法2.4 求ε-闭包 算法2.1 模拟DFA 在表驱动的词法分析器中，DFA是被动的，需要一个驱动器来模拟DFA的行为，以实现对输入序列的分析。 直接编码的词法分析器，将DFA和DFA识别输入序列的过程合并在一起，直接用程序代码模拟DFA识别输入序列的过程。 问题： 如何用程序模拟DFA识别输入序列的过程？即如何用程序模拟DFA的状态和它的状态转移？ 1. 状态和状态转移与语句的对应关系 ① 初态→程序的开始； ② 终态→程序的结束（不同终态return不同记号）； ③ 状态转移→分情况或者条件语句（case/if）； ④ 环→循环语句（loop）； ⑤ return满足最长匹配原则。 2. 识别(a|b)*abb的程序框架 void main(){ char buf[]=abba#, *ptr=buf; while (*ptr!=# ){ l0: while (*ptr==b) ptr++; // state 0 switch(*ptr) { case a: ptr++; l1: while (*ptr==a) ptr++; // state 1 switch (*ptr) { case b: ptr++; switch (*ptr) // state 2 { case a: ptr++; goto l1; case b: ptr++; switch (*ptr) // state3 { case a: ptr++; goto l1; case b: ptr++; goto l0; case #: coutyes; return; default: goto le; } default: goto le; } default: goto le; } default: goto le; } } le: cout no endl; } // 看实例运行 手工编写 工具生成 适合的编写方法 较小 较大 分析器的规模 有关 无关 程序与模式的关系 快 慢 分析器的速度 直接编码 表驱动 2.4.5 词法分析器生成器简介 1 构造词法分析器的全过程均有算法： 正规式－NFA－DFA－最小化DFA－词法分析器（分析表） 2 LEX的基本结构 根据正规式构造的分析表＋驱动器框架（不变的） 3 利用LEX构造词法分析器的关键 ① 用LEX提供的正规