编译原理—chapter2讲义.ppt

* * * * 比较手工构造的NFA和用教材上语法制导的算法构造的NFA。鼓励学生写出引入尽可能少的? 转换的语法制导的算法，在将来的解题中使用这个算法。 * * 1972年贝尔实验室 Unix 实现 Unix/Linux .out same as .exe in windows * * * * * * * * * * * 《编译原理习题精选》1.3。 * 《编译原理习题精选》1.3。 * 《编译原理习题精选》1.3。 * 《编译原理习题精选》1.3。 * 《编译原理习题精选》1.3。 * * * * * 闭包运算—最高优先级，左结合 连接运算—次高优先级，左结合 选择运算—最低优先级，左结合 * * * * * * * * * * * * * * 《编译原理习题精选》1.5题。 * 从转换表构造转换图。 * 将前面的DFA和现在的DFA进行比较，引出DFA化简问题。 * 将前面的DFA和现在的DFA进行比较，引出DFA化简问题。 * * * * * * * * * * * 2.4 从正规式到有限自动机 对于加括号的正规式(s)，使用N(s)本身作为它的NFA。 2.4 从正规式到有限自动机 本方法产生的NFA有下列性质: N(r)的状态数最多是r中符号和算符总数的两倍 N(r)只有一个开始状态和一个接受状态，接受状态没有向外的转换 N(r)的每个状态有一个用?的符号标记的指向其它结点的转换，或者最多两个指向其它结点的?转换 2.4 从正规式到有限自动机 1 9 开始 ? 0 a b ? a b 6 7 8 2 3 4 5 ? ? ? ? ? ? r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 a | b a b (a|b)*ab的分解 2.4 从正规式到有限自动机 1 9 开始 ? 0 ? a b 6 7 8 a b 2 3 4 5 ? ? ? ? ? ? r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 a | b a b (a|b)*ab的分解 2.4 从正规式到有限自动机 ? 1 9 开始 ? 0 a b ? a b 6 7 8 2 3 4 5 ? ? ? ? ? r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 a | b a b (a|b)*ab的分解 2.4 从正规式到有限自动机 1 9 开始 ? 0 a b ? a b 6 7 8 2 3 4 5 ? ? ? ? ? ? r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 a | b a b (a|b)*ab的分解 2.4 从正规式到有限自动机 1 9 开始 ? 0 a b ? a b 6 7 8 2 3 4 5 ? ? ? ? ? ? r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 a | b a b (a|b)*ab的分解 2.4 从正规式到有限自动机 1 9 开始 ? 0 a b ? a b 6 7 8 2 3 4 5 ? ? ? ? ? ? r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 a | b a b (a|b)*ab的分解 2.4 从正规式到有限自动机 1 9 开始 ? 0 a b ? a b 6 7 8 2 3 4 5 ? ? ? ? ? ? r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 a | b a b (a|b)*ab的分解 2.4 从正规式到有限自动机 (a|b)*ab的两个NFA的比较 1 2 开始 a 0 a b b 1 9 开始 ? 0 a b ? a b 6 7 8 2 3 4 5 ? ? ? ? ? ? 手工构造: 算法构造: 2.4 从正规式到有限自动机 小结：从正规式建立识别器的步骤 从正规式构造NFA 把NFA变成DFA 将DFA化简 存在其它办法 2.5 词法分析器的生成器 Lex(lexical analyzer generator) 用Lex建立词法分析器的步骤 Lex 编译器 Lex源程序lex.l lex.yy.c C 编译器 lex.yy.c a.out a.out 输入流 记号序列 2.5 词法分析器的生成器 Lex程序包括三个部分 声明 ％％ 翻译规则 ％％ 辅助过程 Lex程序的翻译规则 p1 {动作1} p2 {动作2} … … pn {动作n} 2.5 词法分析器的生成器 例声明部分 %{ /* 常量LT, LE, EQ, NE, GT, GE, WHILE, DO, ID, NUMBER, RELOP的定义*/ %} /* 正规定义 */ delim [ \t \n ] ws