编译原理与技术 词法分析 Ⅱ 计算机科学与技术学院李诚 13/09/2018
主要内容 记号 (token) 源程序 词法分析器 getnexttoken 语法分析器 符号表 词法分析器的自动生成 正则表达式 NFA DFA 化简的 DFA 词法分析器的生成器 Lex: flex jflex Fst lexicl nlyzer genertor 2/51
Regulr Expr to NFA 正则表达式 = Specifiction 有限自动机 = Implementtion NFA Regulr Expressions DFA Lexicl Specifiction Tle-driven Implementtion of DFA 3/23
Regulr Expr to NFA 正则表达式 = Specifiction 有限自动机 = Implementtion 二者之间的转换 : 用语法制导的算法, 它用正则表达式的语法结构来指导有限自动机的构造过程 4/23
语法制导的构造算法 首先构造识别 和字母表中一个符号 的 NFA 重要特点 : 仅一个接受状态, 它没有向外的转换 开始 i f 开始 i f 识别正则表达式 的 NFA 识别正则表达式 的 NFA 对于加括号的正则表达式 (s), 使用 N(s) 本身作为它的 NFA 5/23
语法制导的构造算法 构造识别主算符为选择的正则表达式的 NFA 重要特点 : 仅一个接受状态, 它没有向外的转换 开始 i N (s) N (t) f 识别正则表达式 s t 的 NFA 6/23
语法制导的构造算法 构造识别主算符为连接的正则表达式的 NFA 重要特点 : 仅一个接受状态, 它没有向外的转换 开始 i N (s) N (t) f 识别正则表达式 st 的 NFA 7/23
语法制导的构造算法 构造识别主算符为闭包的正则表达式的 NFA 重要特点 : 仅一个接受状态, 它没有向外的转换 开始 i N (s) f 识别正则表达式 s * 的 NFA 8/23
语法制导的构造算法 由本方法产生的 NFA 具有下列性质 : N(r) 的状态数最多是 r 中符号和算符总数的两倍 N(r) 只有一个接受状态, 接受状态没有向外的转换 2 3 开始 0 1 6 7 8 9 4 5 9/23
语法制导的构造算法 由本方法产生的 NFA 具有下列性质 : N(r) 的每个状态有一个用 的符号标记指向其它结点的转换, 或者最多两个指向其它结点的 转换 2 3 开始 0 1 6 7 8 9 4 5 10/23
NFA 构造过程举例 ( ) * 的分解 ( r 4 r 3 r 9 r 7 r 8 r 5 r 6 * ) r 1 r 2 2 3 开始 0 1 6 7 8 9 4 5 11/23
NFA 构造过程举例 ( ) * 的分解 ( r 4 r 3 r 9 r 7 r 8 r 5 r 6 * ) r 1 r 2 2 3 开始 0 1 6 7 8 9 4 5 12/23
NFA 构造过程举例 ( ) * 的分解 ( r 4 r 3 r 9 r 7 r 8 r 5 r 6 * ) r 1 r 2 2 3 开始 0 1 6 7 8 9 4 5 13/23
NFA 构造过程举例 ( ) * 的分解 ( r 4 r 3 r 9 r 7 r 8 r 5 r 6 * ) r 1 r 2 2 3 开始 0 1 6 7 8 9 4 5 14/23
NFA 构造过程举例 ( ) * 的分解 ( r 4 r 3 r 9 r 7 r 8 r 5 r 6 * ) r 1 r 2 2 3 开始 0 1 6 7 8 9 4 5 15/23
NFA 构造过程举例 ( ) * 的分解 ( r 4 r 3 r 9 r 7 r 8 r 5 r 6 * ) r 1 r 2 2 3 开始 0 1 6 7 8 9 4 5 16/23
NFA 构造过程举例 ( ) * 的分解 ( r 4 r 3 r 9 r 7 r 8 r 5 r 6 * ) r 1 r 2 2 3 开始 0 1 6 7 8 9 4 5 17/23
NFA 构造过程举例 ( )* 的两个 NFA 的比较 手工构造 : 开始 0 1 2 算法构造 : 2 3 开始 0 1 6 7 8 9 4 5 18/51
词法分析的自动生成 从正则表达式建立识别器的步骤 从正则表达式构造 NFA( 已介绍 ) 用语法制导的算法, 它用正规式语法结构来指导构造过程 把 NFA 变成 DFA ( 子集构造法, 已介绍 ) 将 DFA 化简 ( 合并不可区别状态, 也已介绍 ) 19/51
思考问题 正则表达式 ( )* 与 (* *)* 是否等价? 提示 : 可利用其最简化 DFA 的 20/23
主要内容 记号 (token) 源程序 词法分析器 getnexttoken 语法分析器 符号表 词法分析器的自动生成 正则表达式 NFA DFA 化简的 DFA 词法分析器的生成器 Lex: flex jflex 21/51
词法分析器的生成器 用 Lex 建立词法分析器的步骤 Lex 源程序 lex.l Lex 编译器 lex.yy.c lex.yy.c C 编译器.out 输入流.out 记号序列 22/51
Lex 程序 包括三个部分声明 %% 翻译规则 %% 辅助过程 Lex 程序的翻译规则 p 1 { 动作 1} p 2 { 动作 2} p n { 动作 n} 23/23
Lex 文件举例 声明部分 %{ /* 常量 LT, LE, EQ, NE, GT, GE, WHILE, DO, ID, NUMBER, RELOP 的定义 */ %} /* 正则定义 */ delim [ \t \n ] ws {delim}+ letter [A Z z] digit [09] id {letter}({letter} {digit})* numer {digit}+(\.{digit}+)?(e[+\]?{digit}+)? 24/23
Lex 文件举例 翻译规则部分 {ws} {/* 没有动作, 也不返回 */} while {return (WHILE);} do {return (DO);} {id} {yylvl = instll_id ( ); return (ID);} {numer} {yylvl = instll_num( ); return (NUMBER);} < {yylvl = LT; return (RELOP);} <= {yylvl = LE; return (RELOP);} = {yylvl = EQ; return (RELOP);} <> {yylvl = NE; return (RELOP);} > {yylvl = GT; return (RELOP);} >= {yylvl = GE; return (RELOP);} 25/51
Lex 文件举例 辅助过程部分 instllid ( ) { /* 把词法单元装入符号表并返回指针 yytext 指向该词法单元的第一个字符, yyleng 给出的它的长度 */ } instllnum ( ) { /* 类似上面的过程, 但词法单元不是标识符而是数 */ } 26/51
总结 词法分析器的作用和接口, 用高级语言编写词法分析器等内容 掌握下面涉及的一些概念, 它们之间转换的技巧 方法或算法 非形式描述的语言 正规式正规式 NFA 非形式描述的语言 NFA NFA DFA DFA 最简 DFA 非形式描述的语言 DFA( 或最简 DFA) 27/23
编译原理与技术 词法分析 Ⅱ KISS (Keep It Simple, Stupid!) It is esier to modify working system thn to get system working. Wisdom