大侠素材铺

Size: px

Start display at page:

Download "大侠素材铺"

动颖凤
5 years ago
Views:

1 编译原理与技术词法分析计算机科学与技术学院李诚 06/09/2018

2 主要内容记号 (token) 源程序词法分析器 getnexttoken 语法分析器符号表词法分析所面临的问题向前看 (Lookhed) 歧义 (Amiguities) 词法分析器的自动生成词法单元的描述 : 正则式词法单元的识别 : 转换图有限自动机 :NFA DFA 2/51

$词法分析程序示例 : if (i == j) printf( equl! ); else num5 = 1; 程序是以字符串的形式传递给编译器的 \tif (i == j)\n\t\tprintf( equl!$

3 词法分析程序示例 : if (i == j) printf( equl! ); else num5 = 1; 程序是以字符串的形式传递给编译器的 \tif (i == j)\n\t\tprintf( equl! );\n\telse\n\t\tnum5 = 1; 目的 : 将输入字符串识别为有意义的子串子串的种类 (Nme) 可帮助解释和理解该子串的属性 (Attriute) 可描述具有相同特征的子串的模式 (Pttern) 3/51

4 四个关键术语记号记号名 4/23

5 词法单元 ( 记号 ) 实例与模式 if (i == j) printf( equl! ); else num5 = 1; 记号名实例模式的非形式描述 if if 字符 i, f else else 字符 e, l, s, e reltion ==, <, <=, == 或 < 或 <= 或 id i, j, num5 由字母开头的字母数字串 numer 1, 3.1, 10, 2.8 E12 任何数值常数 literl equl! 引号和之间任意不含引号本身的字符串 5/51

6 词法单元 ( 记号 ) 的属性属性记录词法单元的附加属性, 影响语法分析对该词法单元的翻译例 : 标识符 id 的属性会包括词法单元实例类型第一次出现的位置等保存在符号表 (Symol tle) 中, 以便编译的各个阶段取用 6/51

7 词法单元由一个记号名和一个可选的属性值组成 token := <token_nme, ttriute_vlue> 7/23

8 词法单元由一个记号名和一个可选的属性值组成 token := <token_nme, ttriute_vlue> 示例 : position = initil + rte 60 的记号和属性值 : id, 指向符号表中 position 条目的指针 ssign _ op id, 指向符号表中 initil 条目的指针 dd_op id, 指向符号表中 rte 条目的指针 mul_ op numer, 整数值词素 ( 实例 ) 符号表 position... initil... rte... 8/23

9 词法定义中的一些问题怎么识别相近的实例? i vs. if 或者 = vs. == 忽略空格带来的困难 DO 8 I 等同于 DO8I DO 8 I 3, 75 其中 DO 是关键字,8 是语句标号 9/51

10 词法定义中的一些问题关键字保留字关键字 (keyword): 有专门的意义和用途, 如 if else 保留字 : 有专门的意义, 不能当作一般的标识符使用例如,C 语言中的关键字是保留字关键字不保留 IF THEN THEN THEN=ELSE;ELSE 10/51

11 歧义和 lookhed 词法分析从左到右读取输入串, 每次识别出一个 token 实例可能需要 lookhed 来判断当前是否是一个 token 实例的结尾下一个实例的开始 ( 尤其是在 Fortrn 语言中 ) 11/51

12 复习一下词法分析的目标将输入字符流识别成记号的实例 ( 词素 ) 识别出每个实例对应的记号 ( 词法单元 ) 从左到右的扫描 => 需要向前看 (lookhed) 这样的方式 12/23

13 设计词法分析器的挑战是? 一种可以描述记号所对应的全部实例的方法 id => {,, ct, dog, } 一种可以消除歧义的方法 if 是关键字 if 还是两个变量 i,f? == 是两个等号 = =? 13/23

14 主要内容记号 (token) 源程序词法分析器 getnexttoken 语法分析器符号表词法分析所面临的问题向前看 (Lookhed) 歧义 (Amiguities) 词法分析器的自动生成词法单元的描述 : 正则式词法单元的识别 : 转换图有限自动机 :NFA DFA 14/51

15 串和语言术语字母表 : 符号的有限集合, 例 : = { 0, 1} 串 : 符号的有穷序列, 例 :0110, 语言 : 字母表上的一个串集 {, 0, 00, 000, }, {}, 句子 : 属于语言的串串的运算连接 ( 积 ): xy,s = s = s 指数 ( 幂 ): s 0 为,s i 为 s i-1 s(i > 0) 15/51

16 串和语言语言的运算并 : L M = {s s L 或 s M } 连接 : LM = {st s L 且 t M} 幂 : L 0 是 {},L i 是 L i-1 L 闭包 : L = L 0 L 1 L 2 正闭包 : L + = L 1 L 2 优先级 : 幂连接并示例 L: { A, B,, Z,,,, z }, D: { 0, 1,, 9 } L D, LD, L 6, L *, L(L D ) *, D + 16/51

17 正则表达式 (Regulr Expr) 正则式用来表示简单的语言正则式定义的语言备注 {} {} (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 优先级 : 闭包 * 连接选择 17/51

18 正则表达式例子 = {, } {, } ( ) ( ) {,,, } {,,, } * 由字母构成的所有串集 ( ) * 由和构成的所有串集复杂的例子 ( ( (01 10) (00 11) (01 10) ) ) 句子 : /51

19 正则定义 ottom-up 方法对于比较复杂的语言, 为了构造简洁的正则式, 可先构造简单的正则式, 再将这些正则式组合起来, 形成一个与该语言匹配的正则序列 d 1 r 1 d 2 r 2... d n r n 各个 d i 的名字都不同每个 r i 都是 {d 1, d 2,, d i-1 } 上的正则式 19/51

20 正则定义的例子 C 语言的标识符是字母数字和下划线组成的串 letter_ A B Z z _ digit id letter_(letter_ digit) * 20/51

21 正则定义的例子无符号数集合, 例 1946,11.28,63E8,1.99E6 digit digits digit digit * optionl_frction.digits optionl_exponent ( E ( + ) digits ) numerdigits optionl_frction optionl_exponent 简化表示 numer digit + (.digit + )? (E(+ )? digit + )? 21/51

22 正则定义的例子 while while do do relop < < = = < > > > = letter A B Z z id letter (letter digit ) * numer digit + (.digit + )? (E (+ )? digit + )? delim lnk t newline ws delim + 问题 : 正则式是静态的定义, 如何通过正则式动态识别输入串? 22/51

23 主要内容记号 (token) 源程序词法分析器 getnexttoken 语法分析器符号表词法分析所面临的问题向前看 (Lookhed) 歧义 (Amiguities) 词法分析器的自动生成词法单元的描述 : 正则式词法单元的识别 : 转换图有限自动机 :NFA DFA 23/51

24 词法记号的识别 : 转换图转换图 (trnsition digrm) 关系运算符 = 2 双圈表示接受状态 return(relop, LE) 1 > 3 return(relop, NE) 开始 0 < = > 5 other return(relop, EQ) 4 * return(relop, LT) 星号表示将输入回退一个位置开始状态 6 = other 7 8 * return(relop, GE) return(relop, GT) 24/51

25 转换图 ( 状态转换图 ) 标识符和关键字的转换图 letter 或 digit 开始 * letter other return(instllid( )) 25/51

26 转换图 ( 状态转换图 ) 无符号数的转换图 numer digit+ (.digit+)? (E (+ )? digit+)? digit E digit digit digit 开始 digit. digit E +/ digit other other other return( instllnum( ) ) 19 * 26/51

27 转换图 ( 状态转换图 ) 空白的转换图 delim lnk t newline ws delim+ delim 开始 delim other * 27/51

28 基于转换图的词法分析例 :relop 的转换图的概要实现 = 2 开始 1 < 0 = > 5 6 othe r = > other * * 28/23

29 基于转换图的词法分析例 :relop 的转换图的概要实现 TOKEN getrelop() { TOKEN rettoken = new(relop); while (1) { switch (stte) { cse 0: 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); } 开始出错处理, 要能从错误恢复 < 1 = 0 5 > 回退 6 = othe r = > other 29/ * *

30 基于转换图的词法分析例 :relop 的转换图的概要实现 TOKEN getrelop() { TOKEN rettoken = new(relop); = while (1) { > 1 switch (stte) { < cse 0: c = nextchr(); othe 问题 if :(c == 怎么为每一个正则定义 '<') stte = 1; 开始 = r else if (c == '=') stte = 5; 0 5 else if (c == '>') stte = 6; > 自动找到一个状态转换图? else fil(); = 6 other } } rek; cse 1: cse 8: retrct(); rettoken.ttriute = GT; return(rettoken); } 出错处理, 要能从错误恢复回退 30/ * *

31 主要内容记号 (token) 源程序词法分析器 getnexttoken 语法分析器符号表词法分析所面临的问题向前看 (Lookhed) 歧义 (Amiguities) 词法分析器的自动生成词法单元的描述 : 正则式词法单元的识别 : 转换图有限自动机 :NFA DFA 31/51

32 有限自动机不确定的有限自动机 ( 简称 NFA) 是一个数学模型, 它包括 : 有限的状态集合 S 输入符号集合转换函数 move : S ( {} ) P(S) 状态 s 0 是唯一的开始状态 F S 是接受状态集合幂集 32/23

33 有限自动机不确定的有限自动机 ( 简称 NFA) 是一个数学模型, 它包括 : 有限的状态集合 S 输入符号集合转换函数 move : S ( {} ) P(S) 状态 s 0 是唯一的开始状态 F S 是接受状态集合识别语言 ( ) * 的 NFA 开始 /23

34 有限自动机 NFA 的转换表识别语言 ( ) * 的 NFA 开始输入符号状态 0 {0, 1} {0} 1 {2} /23

35 有限自动机例识别 * * 的 NFA 35/23

36 有限自动机例识别 * * 的 NFA 开始 /23

37 有限自动机确定的有限自动机 ( 简称 DFA) 也是一个数学模型, 包括 : 有限的状态集合 S 输入符号集合转换函数 move : S S, 且可以是部分函数状态 s 0 是唯一的开始状态 F S 是接受状态集合识别语言 ( ) * 的 DFA 开始 /23

38 有限自动机例 DFA, 识别 {0,1} 上能被 5 整除的二进制数 38/23

39 有限自动机例 DFA, 识别 {0,1} 上能被 5 整除的二进制数开始 = = /23

40 有限自动机例 DFA, 接受 0 和 1 的个数都是偶数的字符串开始偶 0 偶偶 0 奇奇 0 偶奇 0 奇 1 40/23

41 有限自动机 NFA 到 DFA 的变换子集构造法 DFA 的一个状态是 NFA 的一个状态集合读了输入 1 2 n 后, NFA 能到达的所有状态 : s 1, s 2,, s k, 则 DFA 到达状态 {s 1, s 2,, s k } 41/23

42 NFA 到 DFA 的变换子集构造法 (suset construction) - 闭包 (- closure): 状态 s 的 - 闭包是 s 经转换所能到达的状态集合 NFA 的初始状态的 - 闭包对应于 DFA 的初始状态针对每个 DFA 状态 NFA 状态子集 A, 求输入每个 i 后能到达的 NFA 状态的 - 闭包并集 ( - closure(move(a, i ))), 该集合对应于 DFA 中的一个已有状态, 或者是一个要新加的 DFA 状态 42/23

43 NFA 到 DFA 的变换例 ( )*,NFA 如下, 把它变换为 DFA 开始 /23

44 NFA 到 DFA 的变换状态输入符号开始 /23

45 NFA 到 DFA 的变换 A = {0, 1, 2, 4, 7} 状态 A 输入符号开始 /23

46 NFA 到 DFA 的变换 A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} 状态 A 输入符号 B 开始 /23

47 NFA 到 DFA 的变换 A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} C = {1, 2, 4, 5, 6, 7} 状态输入符号 A B C 开始 /23

48 NFA 到 DFA 的变换 A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} C = {1, 2, 4, 5, 6, 7} 状态输入符号 A B C B B C B C 2 3 开始 /23

49 NFA 到 DFA 的变换 A = {0, 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} 状态输入符号 A B C B B C B C 2 3 开始 /23

50 NFA 到 DFA 的变换 A = {0, 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} 状态输入符号 A B C B B D C B C 2 3 开始 /23

51 NFA 到 DFA 的变换 A = {0, 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} 开始状态输入符号 A B C B B D C B C D B C 51/23

52 开始开始 NFA 到 DFA 的变换 A 0 B C D 状态输入符号 A B C B B D C B C D B C 52/23

53 识别语言 ( )* 的自动机开始开始 NFA 到 DFA 的变换 A 0 C B D 开始 0 子集构造法不一定得到最简 DFA /23

54 DFA 的化简 A 和 B 是可区别的状态从 A 出发, 读过单字符构成的串, 到达非接受状态 C, 而从 B 出发, 读过串, 到达接受状态 D A 和 C 是不可区别的状态无任何串可用来像上面这样区别它们可区别的状态要分开对待开始 A C B D 54/23

55 DFA 的化简 1. 按是否是接受状态来区分 {A, B, C}, {D} move({a, B, C}, ) = {B} move({a, B, C}, ) = {C, D} 开始 A C B 55/23 D

56 DFA 的化简 1. 按是否是接受状态来区分 {A, B, C}, {D} move({a, B, C}, ) = {B} move({a, B, C}, ) = {C, D} 2. 继续分解 {A, C}, {B}, {D} move({a, C}, ) = {B} move({a, C}, ) = {C} 开始 A C B 56/23 D

57 DFA 的化简 1. 按是否是接受状态来区分 {A, B, C}, {D} 开始 move({a, B, C}, ) = {B} move({a, B, C}, ) = {C, D} 2. 继续分解 {A, C}, {B}, {D} move({a, C}, ) = {B} move({a, C}, ) = {C} 开始 A A B C B D D 57/23

58 编译原理与技术词法分析 Computer science is no more out computers thn stronomy is out telescopes. Edsger Dijkstr

大侠素材铺

大侠素材铺编译原理与技术词法分析计算机科学与技术学院李诚 06/09/2018 主要内容源程序词法分析器记号 (token) getnexttoken 语法分析器符号表词法分析所面临的问题向前看 (Lookhed) 歧义 (Amiguities) 词法分析器的自动生成词法单元的描述 : 正则式词法单元的识别 : 转换图有限自动机 :NFA DFA 此课件参考了陈意云张昱老师及 MIT