《编译原理原理与技术》第章 词法分析.ppt

* * * * * * * * * * * * * * * * * * 比较手工构造的NFA和用教材上语法制导的算法构造的NFA。鼓励学生写出引入尽可能少的? 转换的语法制导的算法，在将来的解题中使用这个算法。 * * * * * * * * * * 《编译原理习题精选》1.3。 * 《编译原理习题精选》1.3。 * 《编译原理习题精选》1.3。 * 例——翻译规则部分 {ws} {/* 没有动作，也不返回 */} while {return (WHILE);} do {return (DO);} {id} {yylval = installId ( ); return (ID);} {number} {yylval = installNum( ); return (NUMBER);} “ ” {yylval = LT; return (RELOP);} “ = ” {yylval = LE; return (RELOP);} “ = ” {yylval = EQ; return (RELOP);} “ ” {yylval = NE; return (RELOP);} “ ” {yylval = GT; return (RELOP);} “ = ” {yylval = GE; return (RELOP);} 2.5 词法分析器的生成器 例——辅助过程部分 installId( ) { /* 把词法单元装入符号表并返回指向它的指针。 yytext指向该词法单元的第一个字符， yyleng给出它的长度 */ } installNum ( ) { /* 类似上面的过程，但词法单元不是标识符 而是数 */ } 2.5 词法分析器的生成器 词法分析器的作用和接口，用高级语言编写词法分析器等内容 掌握下面涉及的一些概念，它们之间转换的技巧、方法或算法 非形式描述的语言 ? 正规式 正规式 ? 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 下面C语言编译器编译下面的函数时，报告 parse error before ‘else’ long gcd(p,q) long p,q; { if (p%q == 0) /* then part */ return q 此处遗漏分号 else /* else part */ return gcd(q, p%q); } 例 题 4 现在少了第一个注释的结束符号后，反而不 报错了 long gcd(p,q) long p,q; { if (p%q == 0) /* then part return q else /* else part */ return gcd(q, p%q); } 例 题 4 第一次 2.3, 2.4 (d) (e) 第二次 2.7 (c) (d)，2.8 ( 仅为2.7 (c) )， 2.9，2.11(a) 习 题 * * * * * * * * * * * * * * * * * * * * * * 《编译原理习题精选》1.5题。 * 1 9 开始 ? 0 a b ? a b 6 7 8 2 3 4 5 ? ? ? ? ? ? 输入符号 a b A B C B B C 状态 A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} C =