词法分析 编译原理和技术 张昱 551-636384,yuzhng@ustc.edu.cn 中国科学技术大学计算机科学与技术学院
本章内容 记号 (token) 源程序 词法分析器 取下一个记号 语法分析器 符号表 词法分析及问题 向前看 (Lookhed) 歧义 (Amiguities) 词法分析器的自动生成 词法记号的描述 : 正规式 ; 词法记号的识别 : 转换图 有限自动机 :NFA DFA 张昱 : 编译原理和技术 词法分析 2
2.1 词法记号及属性 记号 词法单元 模式
词法记号 模式 词法单元 记号名 词法单元举例 模式的非形式描述 if if 字符 i, f for for 字符 f, o, r reltion <, <=, =, < 或 <= 或 = 或 id sum, count, D5 由字母开头的字母数字串 numer 3.1, 1, 2.8 E12 任何数值常数 literl seg. error 引号 和 之间任意不含引号本身的字符串 whitespce 换行符 换行符 \n 无意义, 被丢弃, 不提供给语法分析器 张昱 : 编译原理和技术 词法分析 4
词法定义中的问题 关键字 保留字 关键字 (keyword): 有专门的意义和用途, 如 if else 保留字 : 有专门的意义, 不能当作一般的标识符使用例如,C 语言中的关键字是保留字 历史上词法定义中的一些问题 忽略空格带来的困难, 例如 Fortrn DO 8 I 3. 75 等同于 DO8I 3. 75 DO 8 I 3, 75 关键字不保留 IF THEN THEN THEN=ELSE; ELSE 张昱 : 编译原理和技术 词法分析 5
歧义和 lookhed 词法分析 从左到右读取输入串, 每次识别出一个 token 可能需要 lookhed 来判断当前是否是一个 token 的结尾 下一个 token 的 ( 尤其是在 Fortrn 语言中 ) DO 5 I = 1 DO 5 I = 1.25 DO 5 I = 1, 25 if (then.gt. else) then then = else else else = then endif 张昱 : 编译原理和技术 词法分析 6
词法分析器 : 实现 一个词法分析器的实现必须做两件事 1. 识别子串并对应到 tokens 2. 返回 token 的值或词法单元 (lexeme) 词法单元是子串 (token 的实例 ) 张昱 : 编译原理和技术 词法分析 7
词法记号的属性 position = initil + rte 6 的记号和属性值 : id, 指向符号表中 position 条目的指针 ssign _ op id, 指向符号表中 initil 条目的指针 dd_op id, 指向符号表中 rte 条目的指针 mul_ op numer, 整数值 6 张昱 : 编译原理和技术 词法分析 8
2.2 词法记号的描述与识别 描述 : 正规式 识别 : 转换图
串和语言 术语 字母表 : 符号的有限集合, 例 : = {, 1} 串 : 符号的有穷序列, 例 :11, 语言 : 字母表 上的一个串集 {,,,, }, {}, 句子 : 属于语言的串 串的运算 连接 ( 积 ) xy,s = s = s 幂 s 为,s i 为 s i-1 s(i > ) 张昱 : 编译原理和技术 词法分析 1
串和语言 语言的运算 例 并 : L M = {s s L 或 s M } 连接 : LM = {st s L 且 t M} 幂 : 闭包 : 正闭包 : L 是 {},L i 是 L i-1 L L = L L 1 L 2 L + = L 1 L 2 L: { A, B,, Z,,,, z }, D: {, 1,, 9 } L D, LD, L 6, L *, L(L D ) *, D + 优先级 : 幂 连接 并 张昱 : 编译原理和技术 词法分析 11
正规式 (regulr expression) 正规式用来表示简单的语言, 叫做正规集 正规式 定义的语言 备注 {} {} (r) L(r) r 是正规式 (r) (s) L(r) L(s) r 和 s 是正规式 (r)(s) L(r)L(s) r 和 s 是正规式 (r) * (L(r)) * r 是正规式 (() () * ) (c) 可以写成 * c 优先级 : 闭包 * 连接 选择 张昱 : 编译原理和技术 词法分析 12
正规式举例 = {, } {, } ( ) ( ) {,,, } {,,, } * 由字母 构成的所有串的集合 ( ) * 由 和 构成的所有串的集合 复杂的例子 ( 11 ( (1 1) ( 11) (1 1) ) ) 句子 :1111111111 张昱 : 编译原理和技术 词法分析 13
正规定义 (regulr definition) 对正规式命名, 使正规式表示简洁 d 1 r 1 d 2 r 2... d n r n 各个 d i 的名字都不同 每个 r i 都是 {d 1, d 2,, d i-1 } 上的正规式 C 语言的标识符是字母 数字和下划线组成的串 letter_ A B Z z _ digit 1 9 id letter_(letter_ digit) * 张昱 : 编译原理和技术 词法分析 14
正规定义举例 无符号数集合, 例 1946,11.28,63E8,1.99E6 digit 1 9 digits digit digit * optionl_frction.digits optionl_exponent ( E ( + ) digits ) numer digits optionl_frction optionl_exponent 简化的表示 numer digit + (.digit + )? (E(+ -)? digit + )? 张昱 : 编译原理和技术 词法分析 15
词法记号的识别 : 转换图 转换图 (trnsition digrm) 关系算符的转换图 1 < = 5 > 2 > 3 4 return(relop, EQ) 状态 = 6 other 7 8 = other * * 双圈表示接受状态 return(relop, LE) return(relop, NE) return(relop, LT) 星号表示将输入回退一个位置 return(relop, GE) return(relop, GT) 张昱 : 编译原理和技术 词法分析 16
转换图 标识符和关键字的转换图 letter 或 digit * letter other 9 1 11 return(instllid( )) 无符号数的转换图 digit numer digit + (.digit + )? (E(+ -)? digit + )? E digit digit digit digit. digit E +/ digit 12 13 14 15 16 17 18 other other other * 张昱 : 编译原理和技术 词法分析 17 return( instllnum( ) ) 19
转换图 空白的转换图 delim lnk t newline ws delim+ delim * delim other 2 21 22 张昱 : 编译原理和技术 词法分析 18
基于转换图的词法分析 例 :relop 的转换图的概要实现 TOKEN getrelop() { TOKEN rettoken = new(relop); while (1) { switch (stte) { cse : c = nextchr(); if (c == '<') stte = 1; else if (c == '=') stte = 5; else if (c == '>') stte = 6; } } else fil(); rek; cse 1:...... cse 8: retrct(); rettoken.ttriute = GT; return(rettoken); } 出错处理, 要能从错误恢复 回退 = 5 > 张昱 : 编译原理和技术 词法分析 19 < 1 6 = > other = other 2 3 4 7 * * 8
词法分析中的冲突及解决 R = Whitespce Integer Identifier + 分析 foo+3 f 匹配 R, 更精确地说是 Identifier 但是 fo 也匹配 R, foo 也匹配, 但 foo+ 不匹配 如何处理输入? 如果 x 1 x i L(R) 并且 x 1 x K L(R) Mximl munch 规则 : 选择匹配 R 的最长前缀 最长匹配规则在实现时 :lookhed, 不符合则回退 张昱 : 编译原理和技术 词法分析 2
词法分析 : 分类的不确定性 R = Whitespce new Integer Identifier 分析 new foo new 匹配 R, 更精确地说是 new 但是也匹配 Identifier, 此时该选哪个? 一般地, 如果 x 1 x i L(R j ) 和 x 1 x i L(R k ) 规则 : 选择先列出的模式 (j 如果 j < k) 必须将 new 列在 Identifier 的前面 张昱 : 编译原理和技术 词法分析 21
词法错误 词法分析器对源程序采取非常局部的观点 例 : 难以发现下面的错误 fi ( == f (x) ) 在实数是 数字串. 数字串 格式下, 可以发现下面的错误 123.x 紧急方式的错误恢复 删掉当前若干个字符, 直至能读出正确的记号 错误修补 进行增 删 替换和交换字符的尝试 张昱 : 编译原理和技术 词法分析 22
例题 1 写出语言 所有相邻数字都不相同的非空数字 串 的正规定义 12331357167983579123 解答 : nswer ( no_ ) (no_ ) (no_ ) no_ no_ (1 no_-1 1 ) (no_-1 1 ) (no_-1 ) no_-1... no_-8 9 将这些正规定义逆序排列就是答案 张昱 : 编译原理和技术 词法分析 23
例题 2 下面 C 语言编译器编译下面的函数时, 报告 prse error efore else long gcd(p,q) long p,q; { if (p%q == ) /* then prt */ return q 此处遗漏了分号 } else /* else prt */ return gcd(q, p%q); 张昱 : 编译原理和技术 词法分析 24
例题 2 现在少了第一个注释的结束符号后, 反而不报错了 long gcd(p,q) long p,q; { if (p%q == ) /* then prt return q else /* else prt */ return gcd(q, p%q); } 张昱 : 编译原理和技术 词法分析 25
2.3 有限自动机 描述分析器 :NFA DFA 自动机的转换 NFADFA 化简的 DFA
有限自动机 不确定的有限自动机 (NFA) (nondeterministic finite utomton) 一个数学模型, 它包括 : 1 有限的状态集合 S 2 输入符号集合 3 转换函数 move : S ( {} ) P(S) 4 状态 s 是唯一的状态状态 5 F S 是接受状态集合 识别语言 ( ) * 的 NFA 接受状态 1 2 张昱 : 编译原理和技术 词法分析 27
转换表 NFA 的转换表 识别语言 ( ) * 的 NFA 输入符号 {, 1} {} 1 {2} 2 1 2 张昱 : 编译原理和技术 词法分析 28
例题 3 识别 * * 的 NFA 1 2 3 4 张昱 : 编译原理和技术 词法分析 29
确定的有限自动机 确定的有限自动机 (DFA) 一个数学模型, 它包括 : 1 有限的状态集合 S 2 输入符号集合 3 转换函数 move : S S, 且可以是部分函数 4 状态 s 是唯一的状态 5 F S 是接受状态集合 识别语言 ( ) * 的 DFA 1 2 张昱 : 编译原理和技术 词法分析 3
例题 4 构造一个 DFA, 它能识别 {,1} 上能被 5 整除的二进制数 解答 已读过 尚未读 已读部分的值 某时刻 11 111 5 读进 11 111 5 2 = 1 读进 1 111 11 1 2 + 1= 21 引入 5 个状态即可, 分别代表已读部分的值除以 5 的余数 张昱 : 编译原理和技术 词法分析 31
例题 4 构造一个 DFA, 它能识别 {,1} 上能被 5 整除的二进制数 解答 1 1 1 2 1 3 1 11 2 = 1 1 4 1 111 2 = 7 1 张昱 : 编译原理和技术 词法分析 32
例题 5 构造一个 DFA, 它能接受 和 1 的个数都是偶数的 字符串 偶 偶 1 1 1 1 偶 奇 1 奇 偶 1 2 1 1 3 奇 奇 1 张昱 : 编译原理和技术 词法分析 33
NFA 到 DFA 的变换 子集构造法 (suset construction) 1. DFA 的一个状态是 NFA 的一个状态集合 2. 读了输入 i 后, NFA 能到达的所有状态 :s 1, s 2,, s k, 则 DFA 到达一个状态, 对应于 NFA 的 {s 1, s 2,, s k } {} {, 1} 1 2 {, 2} 未画完 张昱 : 编译原理和技术 词法分析 34
NFA 到 DFA 的变换 子集构造法 (suset construction) 1. - 闭包 ( - closure) 状态 s 的 - 闭包是 s 经 转换所能到达的状态集合 2. NFA 的初始状态的 - 闭包对应于 DFA 的初始状态 3. 针对每个 DFA 状态 NFA 状态子集, 求输入每个 i 后能到达的 NFA 状态的 - 闭包并集, 该集合对应于 DFA 中的一个已有状态, 或者是一个要新加的 DFA 状态 张昱 : 编译原理和技术 词法分析 35
例题 6 正规式 ( )* 对应的 NFA 如下, 把它变换为 DFA 2 3 1 6 7 8 9 4 5 张昱 : 编译原理和技术 词法分析 36
例题 6 状态 输入符号 2 3 1 6 7 8 9 4 5 张昱 : 编译原理和技术 词法分析 37
例题 6 A = {, 1, 2, 4, 7} 状态 A 输入符号 2 3 1 6 7 8 9 4 5 张昱 : 编译原理和技术 词法分析 38
例题 6 A = {, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} 状态 A 输入符号 B 2 3 1 6 7 8 9 4 5 张昱 : 编译原理和技术 词法分析 39
例题 6 A = {, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} 状态 A B 输入符号 B 2 3 1 6 7 8 9 4 5 张昱 : 编译原理和技术 词法分析 4
例题 6 A = {, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} C = {1, 2, 4, 5, 6, 7} 状态 输入符号 A B C B 2 3 1 6 7 8 9 4 5 张昱 : 编译原理和技术 词法分析 41
例题 6 A = {, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} C = {1, 2, 4, 5, 6, 7} 2 3 1 6 7 8 9 4 5 状态 输入符号 A B C B C 张昱 : 编译原理和技术 词法分析 42
例题 6 A = {, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} C = {1, 2, 4, 5, 6, 7} 2 3 1 6 7 8 9 4 5 状态 输入符号 A B C B B C 张昱 : 编译原理和技术 词法分析 43
例题 6 A = {, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} C = {1, 2, 4, 5, 6, 7} D = {1, 2, 4, 5, 6, 7, 9} 2 3 1 6 7 8 9 4 5 状态 输入符号 A B C B B D C 张昱 : 编译原理和技术 词法分析 44
例题 6 A = {, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} C = {1, 2, 4, 5, 6, 7} D = {1, 2, 4, 5, 6, 7, 9} 2 3 1 6 7 8 9 4 5 状态 输入符号 A B C B B D C D 张昱 : 编译原理和技术 词法分析 45
例题 6 A = {, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} C = {1, 2, 4, 5, 6, 7} D = {1, 2, 4, 5, 6, 7, 9} 2 3 1 6 7 8 9 4 5 状态 输入符号 A B C B B D C B C D 张昱 : 编译原理和技术 词法分析 46
例题 6 A = {, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} C = {1, 2, 4, 5, 6, 7} D = {1, 2, 4, 5, 6, 7, 9} 2 3 1 6 7 8 9 4 5 状态 输入符号 A B C B B D C B C D B C 张昱 : 编译原理和技术 词法分析 47
例题 6 A C B D 状态 输入符号 A B C B B D C B C D B C 2 3 1 6 7 8 9 4 5 张昱 : 编译原理和技术 词法分析 48
例题 6 识别语言 ( ) * 的 DFA A C B D 1 2 2 3 1 6 7 8 9 4 5 张昱 : 编译原理和技术 词法分析 49
识别语言 ( ) * 的 DFA 例题 6 A C B D 2 3 1 6 7 8 9 4 5 子集构造法不一定得到最简 DFA 1 2 张昱 : 编译原理和技术 词法分析 5
DFA 的化简 该方法用于化简转换函数是全函数的 DFA 死状态 (ded stte) 当转换函数由部分函数改成全函数表示时引入左图引入死状态 E, A C B E D A C B 张昱 : 编译原理和技术 词法分析 51 D
DFA 的化简 可区别的状态 (distinguishle sttes) s 和 t 分别从 s t 出发, 存在一个输入符号 w, 使得一个到达接受状态, 另一个到达非接受状态 A 和 B 是可区别的状态 : 从 A 出发, 读入 后到达非接受状态 C; 从 B 出发, 读过 后到达接受状态 D A 和 C 是不可区别的状态 : 无任何输入符号可用来区别它们 C A B 张昱 : 编译原理和技术 词法分析 52 D
DFA 的化简 方法 1. 按是否是接受状态来区分 {A, B, C}, {D} 1 2 move({a, B, C}, ) = {B} move({a, B, C}, ) = {C, D} 2. {A, C}, {B}, {D} C move({a, C}, ) = {B} move({a, C}, ) = {C} A B 张昱 : 编译原理和技术 词法分析 53 D
例题 7 叙述下面的正规式描述的语言, 并画出接受该语言的最简 DFA 的状态转换图 (1 1)* * 解答 描述的语言是, 所有不含子串 1 的 由 和 1 组成的串 1 1. strt 1 2 3 刚读过的不是 连续读过一个 连续读过 不少于两个 张昱 : 编译原理和技术 词法分析 54
解答 例题 8 用状态转换图表示接受如下正规式的 DFA strt ( ) ( )( ) 张昱 : 编译原理和技术 词法分析 55
2.4 从正规式到有限自动机 分析器的自动构造 正规式 NFADFA 化简的 DFA 采用语法制导的算法来构造 NFA
语法制导的构造算法 语法制导 : 按正规式的语法结构来指导构造 构造识别 和字母表中一个符号的 NFA 重要特点 : 仅一个接受状态 i f i f 识别正规式 的 NFA 识别正规式 的 NFA 对于带括号的正规式 (s), 使用 s 对应的 NFA N(s) 本身作为它的 NFA 张昱 : 编译原理和技术 词法分析 57
语法制导的构造算法 构造识主算符为选择的正规式的 NFA 重要特点 : 仅一个接受状态 N (s) i f N (t) 识别正规式 s t 的 NFA 张昱 : 编译原理和技术 词法分析 58
语法制导的构造算法 构造识主算符为连接的正规式的 NFA 重要特点 : 仅一个接受状态 i N (s) N (t) f 识别正规式 st 的 NFA 张昱 : 编译原理和技术 词法分析 59
语法制导的构造算法 构造识主算符为闭包的正规式的 NFA 重要特点 : 仅一个接受状态, 且接受状态没有出边 i N (s) f 优化 i N (s) f 识别正规式 s * 的 NFA 张昱 : 编译原理和技术 词法分析 6
语法制导的构造算法 本方法产生的 NFA 有下列性质 N(r) 的状态数最多是 r 中符号和算符总数的两倍 N(r) 只有一个接受状态, 接受状态没有向外的转换 N(r) 的每个状态有一个用 的符号标记指向其它结点的 转换, 或者最多两个指向其它结点的 转换 2 3 1 6 7 8 9 4 5 张昱 : 编译原理和技术 词法分析 61
NFA 构造过程举例 ( ) * 的分解 ( r 4 r 3 r 9 r 7 r 8 r 5 r 6 * ) r 1 r 2 2 3 1 6 7 8 9 4 5 张昱 : 编译原理和技术 词法分析 62
NFA 构造过程举例 ( ) * 的分解 ( r 4 r 3 r 9 r 7 r 8 r 5 r 6 * ) r 1 r 2 2 3 1 6 7 8 9 4 5 张昱 : 编译原理和技术 词法分析 63
NFA 构造过程举例 ( ) * 的分解 ( r 4 r 3 r 9 r 7 r 8 r 5 r 6 * ) r 1 r 2 2 3 1 6 7 8 9 4 5 张昱 : 编译原理和技术 词法分析 64
NFA 构造过程举例 ( ) * 的分解 ( r 4 r 3 r 9 r 7 r 8 r 5 r 6 * ) r 1 r 2 2 3 1 6 7 8 9 4 5 张昱 : 编译原理和技术 词法分析 65
NFA 构造过程举例 ( ) * 的分解 ( r 4 r 3 r 9 r 7 r 8 r 5 r 6 * ) r 1 r 2 2 3 1 6 7 8 9 4 5 张昱 : 编译原理和技术 词法分析 66
NFA 构造过程举例 ( ) * 的分解 ( r 4 r 3 r 9 r 7 r 8 r 5 r 6 * ) r 1 r 2 2 3 1 6 7 8 9 4 5 张昱 : 编译原理和技术 词法分析 67
NFA 构造过程举例 ( ) * 的分解 ( r 4 r 3 r 9 r 7 r 8 r 5 r 6 * ) r 1 r 2 2 3 1 6 7 8 9 4 5 张昱 : 编译原理和技术 词法分析 68
NFA 的手工构造和算法构造 ( ) * 的两个 NFA 的比较 手工构造 : 1 2 算法构造 : 2 3 1 6 7 8 9 4 5 张昱 : 编译原理和技术 词法分析 69
2.5 词法分析器的生成器 Lex: flex jflex ntlr
用 Lex 建立词法分析器 词法分析器 - Lexicl nlyzer, scnner 生成器 - genertor Flex https://githu.com/westes/flex ; JFlex http://jflex.de/ Lex 源程序 lex.l lex.yy.c Lex 编译器 C 编译器 lex.yy.c.out 输入流.out 记号序列 张昱 : 编译原理和技术 词法分析 71
Lex 程序 Lex 程序包括三个部分 声明 %% 翻译规则 %% 辅助过程 Lex 程序的翻译规则 p 1 { 动作 1} p 2 { 动作 2} p n { 动作 n} 张昱 : 编译原理和技术 词法分析 72
Lex 文件举例 声明部分 %{ /* 常量 LT, LE, EQ, NE, GT, GE, %} WHILE, DO, ID, NUMBER, RELOP 的定义 */ /* 正规定义 */ delim [ \t \n ] ws {delim}+ letter [A Z z] digit id numer [9] {letter}({letter} {digit})* {digit}+(\.{digit}+)?(e[+\]?{digit}+)? %{ 和 %} 包含的代码将直接复制到生成的分析器源程序文件中 张昱 : 编译原理和技术 词法分析 73
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);} 张昱 : 编译原理和技术 词法分析 74
Lex 文件举例 辅助过程部分 instllid ( ) { /* 把词法单元装入符号表并返回指针 yytext 指向该词法单元的第一个字符, yyleng 给出的它的长度 */ } instllnum ( ) { } /* 类似上面的过程, 但词法单元不是标识符而是数 */ 张昱 : 编译原理和技术 词法分析 75
ANTLR 的文法文件.g4 格式 grmmr MyG; options { } import ; tokens { } @ctionnme { } rulenme : <stuff> ; 正规定义, DIGIT 不是记号 模式定义词法状态 rulenme 词法 : 大写字母开头 语法 : 小写字母开头 纯词法分析器 lexer grmmr MyG; 词法规则 INT : DIGIT+ ; frgment DIGIT : [-9] ; LQUOTE : '"' -> more, mode(str) ; mode STR; STRING : '"' -> mode(default_mode); 模式调用 张昱 : 编译原理和技术 词法分析 76
ANTLR:Lexer 命令 命令格式 TokenNme : < 选项 > -> 命令名 [( 参数 )] 命令 skip: 不返回记号给 prser, 如识别出空白符或注释 type(t): 设置当前记号的类型 chnnel(c): 设置当前记号的通道, 缺省为 Token.DEFAULT_CHANNEL( 值为 );Token.HIDDEN_CHANNEL( 值为 1) mode(m): 匹配当前记号后, 切换到模式 M pushmode(m): 与 mode(m) 类似, 但将当前模式入栈 popmode: 从模式栈弹出模式, 使之成为当前模式 张昱 : 编译原理和技术 词法分析 77
本章要点 词法分析器的作用和接口, 用高级语言编写词法分析器等 掌握下面的相关概念, 它们之间转换的技巧 方法或算法 非形式描述的语言 正规式 正规式 NFA 非形式描述的语言 NFA NFA DFA DFA 最简 DFA 非形式描述的语言 DFA( 或最简 DFA) 张昱 : 编译原理和技术 词法分析 78