第三章词法分析 1. 词法分析的含义 ; 2. 词法分析的基本概念 ; 3. 正则表达式词法单元模式的表达 ; 4. 状态转换图 ; 5. 词法分析器构造工具 ; 6. 有穷状态自动机 ; 7. 从正则表达式到 NFA,DFA 的映射方法 ;

Size: px

Start display at page:

Download "第三章词法分析 1. 词法分析的含义 ; 2. 词法分析的基本概念 ; 3. 正则表达式词法单元模式的表达 ; 4. 状态转换图 ; 5. 词法分析器构造工具 ; 6. 有穷状态自动机 ; 7. 从正则表达式到 NFA,DFA 的映射方法 ;"

借璜别
5 years ago
Views:

1 编译原理 Compiler Principles 第三章词法分析湖南大学信息科学与工程学院软件工程系杨金民 2018

2 第三章词法分析 1. 词法分析的含义 ; 2. 词法分析的基本概念 ; 3. 正则表达式词法单元模式的表达 ; 4. 状态转换图 ; 5. 词法分析器构造工具 ; 6. 有穷状态自动机 ; 7. 从正则表达式到 NFA,DFA 的映射方法 ;

3 词法分析词法分析 / 扫描 (lexicl nlysis, scnning) 高级语言程序的源文件 ( 文本文件 ), 可将其看作字符流如何把源程序文件中的字符流它识别为词素流 ; 例如 :return (initil<=10)?100:(position+initil**2); return ( initil <= 10 )? 100 : ( position + initil ** 2 ) ;

4 词法分析词素有类概念 : 预定义符和自定义符 ; 预定义符有 : 保留字, 运算符, 标点符, 特义符 ; 词素流 : 可以表达在符号表 : row_id nme type clss v_clss row_num 1 return 预留保留字 ( 预留特义符 initil 自定义局部变量 int <= 预留运算符 flot 自定义常量数值 120 6? 预留标点符号 120

5 语法分析中的三个概念词法单元 (token): 词素的类概念, 例如, 自定义符 ; 词素 (lexme): 字符序列 ; 词法单元的实例 ; 例如, 上例中的 position,initil 词法单元的模式 (pttern) 词法单元的构成规约 ;

6 词法分析要解决的问题要解决的问题 : 如何从字符流切分识别为词素流 return ( initil <= 10 )? 100 : ( position + initil ** 2 ) ; forwrd lexemebegin 词法单元的模式 : 从左到右的字符序列, 在其组成上的约束条件如果一个字符串匹配某个词法单元的模式, 就说它是该词法单元的一个实例, 称之为词素如何描述词法单元的模式? 正则表达式

7 模式表达中的概念字符 (chrcter): 字符集, 例如,ASCII 字符集 : 字母集, 数字集, 标点符号集 ; 串 (string): 某个字符集下的字符串注意 : 串不是集合串 s 的长度记为 s 空串用表示语言 (lnguge): 串的集合例如 :C 语言, Jv 语言, 英语, 汉语,{} 是语言在语言中, 串有语义字, 词, 句, 段, 文都是串串 s 的前缀 (prefix), 后缀 (suffix), 子串 (sustring), 子序列 (susequence): 去掉了一些其中的字符

8 串的运算串的连接运算 : 也叫乘积运算, 串 x 连接串 y 记为 xy 结果还是为串例如, x=my, y =house, 那么 xy =myhouse; 自然有 :s = s = s 表达串接特性串的指数运算 : s i = s i-1 s; s 0 = 例如, x=my, 那么 x 3 =mymymy; 表达重复串接性

9 语言的运算并运算, 联接, 闭包三种运算 : 结果还是为语言语言 L 和 M 并运算 :L M = L M = {s s L 或者 s M}; 可选性联接运算 : LM = {st s L, t M}; 串接的可搭配性闭包运算 :L 的 Kneene 闭包 : L L 的正闭包 : L * i 0 i 1 i L i L 重复次数的可随意性 L= {A, B,...,Z,,,..., z}, D = {0,1,2,3,4,5,6,7,8,9} L D,LD 中包含的串元素的个数各为多少? L 0 ={} L 4, L*, D +, L(L D)* 分别是什么?

10 语言运算的例子 L= {A, B,...,Z,,,..., z}, D = {0,1,2,3,4,5,6,7,8,9} L D = {A, B,...,Z,,,..., z, 0,1,2,3,4,5,6,7,8,9}; (L D) 2 = (L D)(L D) = {AA, AB, Az, A0, A9,..., 9A,9B, 99}, 其中的串元素各个数为 : C62 62 (L D)* = {} (L D) (L D) 2... (L D) 因此,L(L D)* 是以字母开头, 由字母和数字组成的串的集合 C 注意 :(L D) n 和 (L D) *,(L D) + 是完全不同的概念

11 正则表达式描述串接约束词法单元的模式语言运算表达式就称作正则表达式 (Regulr expression): 表达式中通常是变量 ( 斜体字 ) 运算表达式. 并运算符 : 或语言运算的结合律和交换律, 不言而喻 ; 但 ( )* * * 三种运算的优先级 :*( + ) > 联接 > 或正则表达式也可给它取一个名字, 随后用于其它正则表达式 : 例如,C 语言的自定义标示符的一个正则定义可以是 : letter_ A B... Z... z _ digit id letter_ (letter_ digit)*

12 正则表达式表达词法单元的模式 digit digits digit digit* = digit + optionlfrction. digits optionlexponent (E(+ - ) digits) numer digits optionlfrction optionlexponent 问题 :01 匹配 numer 吗? 1.0 匹配 numer 吗? 1. 匹配 numer 吗?

13 正则表达式的标记符扩展基本运算符 : 并连接 Kleene 闭包 (*) 扩展的标记符 : 0 个或多个实例 : (r)* = r*r, r* = r + 1 个或多个实例 :(r) + = rr* = r*r, r* = r + 0 个或 1 个实例 : r = r? 字符类 : 连续的字符中的任选其一, 例如 1 2 n = [ 1 2 n ] = [ 1 - n ] c d e = [ - e] 仅仅只是使正则表达式更简洁

14 简洁的正则表达式例子 letter_ [A- Z - z _ ] digit [0-9] id letter_ (letter_ digit)* digits digit + numer digits (.digits )?( E [+ - ]? digits)?

15 正则表达式的特性字符串在构成上的无缝串接约束 ; 这些串接约束必须相互独立, 不能重贴交叉 : 例如 :sdfgghjkweyr38839ssdf 只能约束 1 约束 2 约束 3 约束 1 约束 2 约束 3 id letter_ (letter_ digit)* digits digit + numer digits (. digits )?( E [+ - ]? digits)?

16 程序语言的词法单元及其正则表达式 letter_ [A- Z - z _ ] digit [0-9] digits digit + customed identifier: id letter_ (letter_ digit)* numer digits (. digits )?( E [+ - ]? digits)? reserved keywords: if digits else digits; opertor = < > == <= >=!= punctution ;, spce ( lnk t newline ) +

17 随堂测试 1 chrcter [A- Z - z 0-9] SQL 语言中可模糊查询, 比如 : LIKE zhng%, 为模糊查询, 其中 % 可以在任意位置, 请用正则表达式表达该类模糊查询的模式 IP 地址例子为 , 即 0~255 的四个数用点隔开请写出 IP 地址得正则表达式

18 正则表达式例子 letter_ [A- Z - z _ ] digit [0-9] id letter_ (letter_ digit)* digits digit + numer digits (.digits )?( E [+ - ]? digits)?

19 词法分析算法 return ( initil <= 10 )? 100 : ( position + initil ** 2 ) ; forwrd lexemebegin string s= ; i, RE[i].mth = true; // 所有词法单元的正则表达式 while ( i, RE[i].mth == true) { s = s + 下一个字符 ; i, if (RE[i].mth == true) 得出了词素, 也得出 if s does not mth RE[i] 了它所属的词法单元 RE[i].mth = flse; }

20 词法单元的正则表达式的状态转换图将字符流切分成词素流, 表达了一个词素的获取过程 < 2 = 4 return opertor. <= other 5 * return opertor. < strt 0 = 1 = 6 return opertor. == other 7 * return opertor. = > 3 = 8 return opertor. >= other 9 * return opertor. >

21 词法单元的正则表达式的状态转换图将字符流切分成词素流, 表达了一个词素的获取过程 < 2 = 4 return opertor. <= other 5 * return opertor. < strt 0 = 1 = 6 return opertor. == other 7 * return opertor. = > 3 = 8 return opertor. >= 状态转换图 other 9 * return opertor. >

22 正则表达式的状态转换图正则表达式 : id letter_ (letter_ digit)* letter_ digit strt 0 letter_ 10 ȯther 11 * 正则表达式 : if if strt 0 i 23 f not letter_ digit. 25 * 24

23 正则表达式的状态转换图正则表达式 : numer digits (. digits )?( E [+ - ]? digits)? digit digit digit strt 0 digit digit 15 E digit 18 other 19 other E digit 20 * other 21 *

24 正则表达式的兼容性 vs 最长匹配原则正则表达式 : id letter_ (letter_ digit)* letter_ digit strt 0 letter_ 10 ȯther 11 * 正则表达式 : if if strt 0 i 23 f not letter_ digit. 25 * 24

25 基于状态转换图的词法分析体系结构 stte = 0; while (1) { c = Chr(forwrd); swith(stte) { cse 0: if (c is letter_ ) // id stte =10; else if (c = '<') //opertor stte = 2; else if (c is digit) // numer stte =12; forwrd++; rek; cse 10: if (!(c is not letter_ or digit)) forwrd; find_id(lexemebegin, forwrd -1); lexemebegin = forwrd; stte = 0; } else forwrd++; rek; if(re>=len*h/2-2) forwrd lexemebegin letter_ digit 0 letter_ 10 ȯther 11 状态, 以及输入字符驱动下的状态变迁 *

26 随堂测试 2 1. 写出 ( )*( )( ) 的状态转换图 2. 对正则表达式 : numer digits (. digits )?( E [+ - ]? digits)? digit digit digit strt digit digit 15 E digit 18 other 19 other E digit 20 * other 21 * 写出该状态转换图的词法分析程序

27 3.5 词法分析器生成工具 Lex 词法单元的正则表达式状态转换图词法分析代码表达生成生成工具 Lex lex.l lex 工具 C 编译器 lex.yy.c.out 源程序的字符流.out 词素流

28 3.5 词法分析器生成工具 Lex 词法单元的正则表达式状态转换图词法分析代码表达生成生成工具 Lex lex.l lex 工具 C 编译器 lex.yy.c.out 源程序的字符流.out 词素流

29 词法分析器构造接下来要解决的问题从正则表达式状态转换图, 在前面是手工构造的, 能否有一种方法 ( 算法 ), 以正则表达式表达式为输入, 状态转换图为输出呢? 状态转换图有哪些类型? 各种类型之间的关系如何?

30 正则表达式的状态转换图的分类正则表达式 : numer digits (. digits )?( E [+ - ]? digits)? digit digit digit strt 12 digit digit 15 E digit 18 other 19 other E 20 * other 21 * digit ( )* strt

31 另一个例子语言 L((* *) 的状态转换图 : strt 开始状态 : 一个接受状态 : 可多个转换函数边上的标号

32 3.6 有穷自动机将状态转换图形式化, 上升为一种理论知识, 被称作有穷自动机 (finite utomt) 为两类: 非确定有穷自动机 NFA(Nondeterministic Finite Automt) 图中的某一状态结点, 一个驱动符号 ( 即边上的标号 ), 可引出多条边, 可以是边上的标号确定性有穷自动机 DFA( Deterministic Finite Automt): 图中的状态结点, 一个驱动符号, 有且仅有一条出边驱动符号不包含

33 NFA 正则表达式 ( )* 的 NFA 表示 NFA 的图表示 strt 开始状态 : 一个接受状态 : 可多个转换函数 ; 边上的标号 NFA 的表表示法 : 转换表

34 NFA 的另一个例子语言 L((* *) 的 NFA: strt 开始状态 : 一个接受状态 : 可多个转换函数边上的标号

35 DFA 匹配 (DFA 模拟 ) stte = 0; ; c = nextchr(); while (c!= eof ) { } stte = move(stte, c); c = nextchr(); if (stte 在接受状态集合 F) return true; else return flse;

36 NFA 中 -closure() 函数 strt 开始状态 0: -closure() 函数 :S = -closure(0) = {0,1,2,4, 7} ; 其中 0 是自己 ; 1,7 是直接的后继状态 ; 2 和 4 是通过 1 的间接后继 ; -closure(s) = s S -closure(s) = {0,1,2,4, 7}= S;

37 S 0 在字符驱动下的后继状态集 strt 开始状态的集合 :S 0 = -closure(0) = {0,1,2,4, 7}; 状态集合 S 0 在字符的驱动下的后继状态集合 T: S' 0, = move(s 0,) = {3, 8}; S 1,1 = -closure(s' 0, ) = {3,6,1,2,4,7,8};

38 S 0 在字符驱动下的后继状态集 strt 开始状态的集合 :S 0 = {0,1,2,4, 7}; 状态集合 S 0 在字符的驱动下的后继状态集合 : S' 0, = move(s 0,) = {5}; S 1,2 = -closure(s' 0, ) = {5,6,1,2,4,7};

39 DFA 和 NFA 的匹配对比 stte = 0; c = nextchr(); while (c!= eof ) { } stte = move(stte, c); c = nextchr(); if (stte 接受状态集 F!= ) return true; else return flse; sttes = -closure(0) ; c = nextchr(); while (c!= eof ) { } sttes=-closure(move(sttes,c); c = nextchr(); if (sttes 接受状态集 F!= ) return true; else return flse; DFA 匹配 NFA 匹配

40 3.7 从正则表达式到 NFA 正则表达式 r= ( )*, 先构建其语法分析树 : r 11 r 4 * ( ) r 3 r 7 r 9 r 5 r 6 r 8 r 10 仅只有三种运算 : r= s t r= st r= s* (s + ) r 1 r 2

41 正则表达式的 NFA 实例 strt 对于正则表达式 r= ( )*

42 3.7 简单正则表达式的 NFA 对于表达式, 构建其 NFA: strt i f 对于表达式 ( 例如 ( )*) 中的单个字符, 构建其 NFA: strt i f

43 并运算与 NFA 组合的对应对于表达式 r =s t, 构建其 NFA: strt is strt ir strt it t s f s f t f r strt i r i s t s f s f r i t f t

44 联接运算与 NFA 组合的对应对于表达式 r =s t, 构建其 NFA: strt strt is s f s strt it t f t strt is f s i t f t s t

45 * 运算与 NFA 组合的对应对于表达式 r =s*, 构建其 NFA: strt strt s ir is f s f r strt ir i s s f s f r

46 正则表达式的 NFA 构建例子 strt 对于正则表达式 r= ( )*

47 正则表达式的 NFA 构建例子 strt strt 对于正则表达式 r= ( )*

48 正则表达式的 NFA 构建例子 strt strt 对于正则表达式 r= ( )*

49 正则表达式的 NFA 构建例子 strt 对于正则表达式 r= ( )*

50 随堂测试 3 对正则表达式 :(( )*)*, 画出其 NFA

51 NFA 中的开始状态和后继状态 strt 开始状态的集合 :S = -closure(0) = {0,1,2,4, 7}; 其中 0 是自己 ; 1,7 是直接的后继状态 ; 2 和 4 是通过 1 的间接后继 ; -closure(s) = s S -closure(s) = {0,1,2,4, 7}; 状态集合 S 在字符的驱动下的后继状态集合 T: T = -closure(move(s,) )= -closure( s S move(s,)) ={3, 8};

52 NFA 中开始状态的闭包 strt 开始状态的集合 :S = -closure(0) = {0,1,2,4, 7}; 其中 0 是自己 ; 1,7 是直接的后继状态 ; 2 和 4 是通过 1 的间接后继 ; -closure(s) = s S -closure(s) = {0,1,2,4, 7};

53 NFA 中状态集的后继状态集 () strt 开始状态的集合 :S 0 = -closure(0) = {0,1,2,4, 7}; 状态集合 S 0 在字符的驱动下的后继状态集合 T: T = -closure(move(s,) )= -closure( s S move(s,)) ={3, 8};

54 状态集 {3,8} 的闭包 strt 开始状态的集合 :S 0 = {0,1,2,4, 7} 的后继状态集合 : S 1,1 = S 0 = -closure( {3, 8} ) = {1,2,3,4,6,7,8};

55 S 0 的后继状态 () strt 开始状态的集合 :S 0 = {0,1,2,4, 7}; S 1,2 = S 0 = -closure(move(s,) )=-closure( {5} )

56 NFA 中状态集 {5} 的闭包 strt S 1,2 = S 0 = -closure( {5} ) ={1,2,4,5,6,7};

57 NFA 中的状态集 S 1,1 的后继状态 () strt 已知状态的集合 :S 1,1 = {1,2,3,4,6,7,8}; S 2,1 = S 1,1 = = -closure(move(s 1,1, ) )= -closure( {3, 8} ) = S 1,1 ;

58 NFA 中状态集 S 1,1 的后继状态 () strt 已知状态的集合 :S 1,1 = {1,2,3,4,6,7,8}; S 2,2 = S 1,1 = = -closure(move(s 1,1, ) )= -closure( {5, 9} )

59 NFA 中状态集 {5,9} 的闭包 strt 已知状态的集合 :S 1,1 = {1,2,3,4,6,7,8}; S 2,2 = S 1,1 = = -closure(move(s 1,1, ) )= -closure( {5, 9} ) = {1,2,4,5,6,7,9} 新状态!!!

60 求 S 1,2 的后继状态集 () strt 已知状态的集合 :S 1,2 = {1,2,4,5,6,7}; S 2,3 = S 1,2 = = -closure(move(s 1,2, ) )= -closure( {3, 8} ) = S 1,1

61 求 S 1,2 的后继状态 () strt 已知状态的集合 :S 1,2 = {1,2,4,5,6,7}; S 2,4 = S 1,2 = = -closure(move(s 1,2, ) )= -closure( {5} ) = S 1,2

62 求 S 2,2 的后继状态 () strt 已知状态的集合 :S 2,2 = {1,2,4,5,6,7,9}; S 3,1 = S 2,2 = -closure(move(s 1,1, ) )= -closure( {3, 8} ) = S 1,1

63 求 S 2,2 的后继状态 () strt 已知状态的集合 :S 2,2 = {1,2,4,5,6,7,9}; S 3,2 = S 2,2 = -closure(move(s 1,1, ) )= -closure( {5, 10} ) = {1,2,4,5,6,7,10} 新状态!!!

64 求 S 3,2 的后继状态 () strt 已知状态的集合 :S 3,2 = {1,2,4,5,6,7,10}; S 4,1 = S 3,2 = -closure(move(s 1,1, ) )= -closure( {3, 8} ) = S 1,1

65 求 S 3,2 的后继状态 () strt 已知状态的集合 :S 3,2 = {1,2,4,5,6,7,10}; S 4,2 = S 3,2 = -closure(move(s 1,1, ) )= -closure( {5} ) = S 1,2

66 3.7.1 由 NFA 转化成 DFA( 子集构造法 ) 正则表达式 r= ( )*, 构建其 NFA, 然后转化为 DFA: S 1,2 strt S0 S 1,1 S 2,2 S 3,2

67 随堂测试 4 对正则表达式 :(( )*)*, 在上一随堂测试的基础上 ( 画出了其 NFA), 将其 NFA 转化为 DFA

68 3.9.6 最小化 DFA 的状态数量对于 DFA 中的状态, 分为两个集合 S 和 F: U strt S T Z Q

69 3.9.6 最小化 DFA 的状态数量对 S 集合中的任一元素 s, 如果 move(s,) 或者 move(s,) 不在 S 中, 则将其从 S 脱离出来 ; U strt S T Z Q

70 3.9.6 最小化 DFA 的状态数量对于表达式 r =s t, 构建其 NFA: U strt S T Z Q

71 3.9.6 最小化 DFA 的状态数量对于表达式 r =s t, 构建其 NFA: U strt S T Z Q

72 最小化 DFA 的状态数量对于表达式 r =s t, 构建其 NFA: U strt S T Z Q

73 最小化 DFA 的状态数量对于表达式 r =s t, 构建其 NFA: U strt S T Z Q

74 3.9.6 最小化 DFA 的状态数量 U strt S T Z Q strt S T Z Q

75 复习 : 空串在表达和衔接上很有用对于表达式 r =s t, 构建其 NFA: strt is strt ir strt it t s f s f t f r strt i r i s t s f s f r i t f t

76 复习 : 空串在表达和衔接上很有用对于表达式 r =s*, 构建其 NFA: strt strt s ir is f s f r strt ir i s s f s f r

77 复习 : 最小化 DFA 的状态数量 S 1,2 strt S0 T Z Q strt S T Z Q

78 为什么 S 0 和 S 1,2 可以合并 : 它们等价 S 0 strt S 1,2 strt

79 复习 : 软件构造方法学 : 用软件编软件词法分析器生成工具 Lex 词法单元的正则表达式状态转换图词法分析代码表达生成生成工具 Lex lex.l lex 工具 C 编译器 lex.yy.c.out 源程序的字符流.out 词素流

80 3.9 从正则表达式到 DFA 正则表达式 r= ( )* 构建其语法分析树 : *

81 3.9 从正则表达式到 DFA 正则表达式 r= ( )* 构建其语法分析树标识每一个叶结点实例 : * # 6 1 2

82 3.9 正则表达式的第一个字符, 和最后一个字符函数看其实例的第一个字符, 和最后一个字符只有一个实例 :, 它的 : 第一个字符来自位置 1: firstpos = 1; # 6 最后一个字符来自位置 1: lstpos = 1; 5 不是其实例 *

83 3.9 正则表达式的 firstpos, lstpos 1 # 叶的实例的第一个字符, 和最后一个字符只有一个实例 :, 它的 : firstpos = 1; lstpos = 1; 不是其实例, 于是 nullle = flse * nullle = flse # 6 {1} {1} 1 2

84 3.9 正则表达式的 firstpos, lstpos 2 # 叶的的第一个字符, 和最后一个字符只有一个实例 :, 它的 : firstpos = 2; lstpos = 2; * 4 nullle = flse 3 {1} {1} {2} {2} 1 2 nullle = flse 5 # 6

85 3.9 正则表达式的 firstpos, lstpos 结点的只有 2 个实例 : :firstpos = 1,lstPos = 1; :firstpos = 2,lstPos = 2; 不是其实例 nullle = flse * {1,2} {1,2} # 6 {1} {1} {2} {2} 1 2

86 3.9 正则表达式的 firstpos, lstpos 结点 ( )* 的实例 : :firstpos = 1,lstPos = 1; :firstpos = 2,lstPos = 2; :firstpos = 1,lstPos = 2; :firstpos = 2,lstPos = 1; 是其实例 nullle = true {1,2} * {1,2} {1,2} {1,2} # 6 {1} {1} {2} {2} 1 2

87 3.9 正则表达式的 firstpos, lstpos 结点 ( * 的实例 : :firstpos = 3,lstPos = 3; :firstpos = 2,lstPos = 3; :firstpos = 1,lstPos = 3; :firstpos = 1,lstPos = 3; 不是其实例 {1,2,3} {3} nullle = flse {1,2} * {1,2} {1,2} {1,2} {3} {3} # 6 {1} {1} {2} {2} 1 2

88 3.9 正则表达式的 firstpos, lstpos 结点 ( *# 实例 : #:firstpos = 3,lstPos = 6; #:firstpos = 1,lstPos = 6; #:firstpos = 2,lstPos = 6; * 1 2 {1,2,3} {6} 3 nullle =flse 4 5 # 6

89 3.9 正则表达式的 firstpos, lstpos 对语法分析树中的每一结点 n: {1,2,3} {6} nullle(n); firstpos(n); lstpos(n); {1,2,3} {3} {1,2} * {1,2} {1,2} {1,2} {1} {1} {2} {2} {1,2,3} {4} {1,2,3} {5} {4} {4} {3} {3} {5} {5} {6} # {6}

90 3.9 正则表达式的 firstpos, lstpos 语法分析树中, 自底向上的三个函数求解方法 : 结点 n nullle(n) firstpos(n) lstpos(n) 为的叶结点 true 序号为 i 的叶结点运算结点 : n = c 1 c 2 ct 运算结点 : n = c 1 c 2 * 运算结点 : n = c 1 * flse {i} {i} nullle(c 1 )OR nullle(c 2 ) nullle(c 1 )AND nullle(c 2 ) firstpos(c 1 ) firstpos(c 2 ) lstpos(c 1 ) lstpos(c 2 ) if nullle(c 1 ) firstpos(c 1 ) firstpos(c 2 ) else firstpos(c 1 ) true firstpos(c 1 ) lstpos(c 1 ) if nullle(c 2 ) lstpos(c 1 ) lstpos(c 2 ) else lstpos(c 2 )

91 对于叶结点 i 定义函数 followpos(i) 实例 : : 第一个的位置序号为 1, 紧接其后的标号的位置序号为 3; 所有可能接在其后 : 第一个的位置序号为 1, 紧接其后的标号的位置序号为 2; : 第一个的位置序号为 1; 紧接其后的标号的位置序号为 1; followpos(1)={1,2,3} * # 6

92 对于叶结点 i 定义函数 followpos(i) 实例 : : 第一个的位置序号为 2, 紧接其后的标号的位置序号为 3; 所有可能接在其后 : 第一个的位置序号为 2, 紧接其后的标号的位置序号为 1; : 第一个的位置序号为 2; 紧接其后的标号的位置序号为 2; followpos(2)={1,2,3} * # 6

93 函数 followpos(i) 的求法对于 ct 运算的结点 n: 其左子结点为 c 1, 右子结点为 c 2, i lstpos(c 1 ): followpos(i) = { j j firstpos(c 2 )}; 结点 n followpos(n) 1 {3} 2 {3} 3 {4} 4 {5} 5 {6} 6 {1,2,3} {6} {1,2,3} {5} {6} #{6} 6 {1,2,3} {4} {5} {5} 5 {1,2,3} {3} {4} {4} 4 {1,2} * {1,2} {3} {3} 3 # 1 2

94 函数 followpos(i) 的求法对于 * 运算的结点 n: j lstpos(n): followpos(j) = { i i firstpos(n)}; 结点 n followpos(n) 1 {1,2, 3} 2 {1,2, 3} 3 {4} 4 {5} 5 {6} 6 {1,2,3} {6} {1,2,3} {5} {6} # 6 {1,2,3} {4} {5} {5} 5 {1,2,3} {3} {4} {4} 4 {1,2} * {1,2} {3} {3} 3 1 2

95 函数 followpos(i) 的求法对于运算的结点 n: 不存在 followpos 判断的基础实例 : : 没有 followpos : 没有 followpos {1,2,3} {6} {1,2,3} {5} {6} # 6 {1,2,3} {4} {5} {5} 5 {1,2,3} {3} {4} {4} 4 {1,2} * {1,2} {3} {3} 3 1 2

96 S 0 =firstpos( 树根 )={1,2,3}; 从正则表达式直接构建 DFA S 1,1 = {j i S 0,chr(i) =, j followpos(i)} = {1,2,3,4}; S 1,2 ={j i S 0,chr(i) =, j followpos(i)} 结点 n = {1,2,3} = S 0 ; followpos(n) 1 {1,2, 3} 2 {1,2, 3} 3 {4} 4 {5} 5 {6} {1,2,3} {6} {1,2,3} {5} {6} # 6 {1,2,3} {4} {5} {5} 5 {1,2,3} {3} {4} {4} {1,2} 4 *{1,2} {3} {3} 3 1 2

97 从正则表达式直接构建 DFA S 2,1 = {j i S 1,1,chr(i) =, j followpos(i)}={1,2,3,4} =S 1,1 ; S 2,2 = {j i S 1,1,chr(i) =, j followpos(i)} = {1,2,3,5} {1,2,3} {6} 结点 n followpos(n) 1 {1,2, 3} 2 {1,2, 3} 3 {4} 4 {5} 5 {6} {1,2,3} {5} {6} # 6 {1,2,3} {4} {5} {5} 5 {1,2,3} {3} {4} {4} 4 {1,2} * {1,2} {3} {3} 3 1 2

98 从正则表达式直接构建 DFA S 3,1 = {j i S 2,2,chr(i) =, j followpos(i)}={1,2,3,4} =S 1,1 ; S 3,2 = {j i S 2,2,chr(i) =, j followpos(i)} {1,2,3} {6} = {1,2,3,6} 结点 n followpos(n) 1 {1,2, 3} 2 {1,2, 3} 3 {4} 4 {5} 5 {6} {1,2,3} {5} {6} # 6 {1,2,3} {4} {5} {5} 5 {1,2,3} {3} {4} {4} 4 {1,2} * {1,2} {3} {3} 3 1 2

99 从正则表达式直接构建 DFA S 4,1 = {j i S 3,2,chr(i) =, j followpos(i)}={1,2,3,4} =S 1,1 ; S 4,2 = {j i S 3,2,chr(i) =, j followpos(i)} {1,2,3} = {1,2,3}= S {6} 0 结点 n followpos(n) 1 {1,2, 3} 2 {1,2, 3} 3 {4} 4 {5} 5 {6} {1,2,3} {5} {6} # 6 {1,2,3} {4} {5} {5} 5 {1,2,3} {3} {4} {4} 4 {1,2} * {1,2} {3} {3} 3 1 2

100 从正则表达式直接构建 DFA 的含义 strt S0 S 1,1 S 2,2 S 3,2 123 可以, 可能, 所有可能 ( 意思是还没有发生, 还在等待发生 ) 1() 2() 3() 穷举策略一旦发生, 来了个, 那就变迁到下一个 ( 可以, 可能, 所有可能 )

101 从正则表达式直接构建 DFA strt S0 S 1,1 S 2,2 S 3,2 123 正因为结点是表示可以, 可能, 所有可能, 还没有发生, 还在等待, 所以 S 2,2 (1235) 并不表示是接受状态而 S 3,2 (1236) 则表示 5() 已经发生了, 自然是接受状态这就是为什么要在树中加一个 6(#) 的原因

102 有穷状态机中状态的含义 1 表明它有个历史 ; 即以前已经接受了哪些字符但历史可能不唯一 2 表明它当前可以, 可能, 所有可能, 还没有发生, 还在等待的字符 3 一旦接受了某个字符, 就会转到下一个可以, 可能, 所有可能, 还没有发生, 还在等待的状态

103 小结 1: 词法分析字符字符串语言 : 既有类概念, 也有实例概念词法单元 ( 类概念 ) 模式词素 ( 实例概念 ) 语言的类概念 : 词法单元的集合 ; 匹配语言的实例概念 : 词素的集合 ; 字符串的三种运算正则表达式

104 小结 2 正则表达式 DFA 语言的词法分析程序 NFA DFA 状态数的最小化

105 随堂测试 5 对正则表达式 :(( )*)*, 画出其 DFA. 证明它与 ( )* 等价

106 第二章作业 3.1.1, , 3.3.5(1-3,9), , ,3.4.2, 成绩好的学生选做 , 3.6.3, ,

107 第一次讨论课第一次讨论课的主题 : 词法分析小主题 : 1) 正则表达式转换 NFA; 2) NFA 确定化为 DFA; 3) DFA 最小化和词法分析器的状态图最小化 ; 4) DFA 代码化 ; 5) TINY 编译器与 TM 虚拟机 ; 6) 词法分析器自动工具 ( 如 :FLEX) 自己定题, 也可以选择如下内容 : 1) Unix/Linux 中的 grep 指令嵌套使用的典型应用案例 ; 2) 练习 3.3.5(4,5,6,8) 中的任何一个 ; 3) 其它习题也可以 ;

108 NFA 的化简基于迁移来减少 NFA 的状态数 strt strt 0 7 strt

109 正则表达式 (0?0?1) *0?0? 的 NFA strt S 0 ={0,1,2,3,4,5} S 0,1={3} ; -closure({3}) =S 0 S 0,0={1,2,4,5} ; -closure({1,2,4,5}) ={1,2,4,5} =S 1 S 1,1={3} = S 0 S 1,0={2,5} ; -closure({2,5}) ={2,5} =S 2 S 2,1={3} = S 0 S 2,0={ } ;

110 正则表达式 (0?0?1) *0?0? 的 DFA 1 1 strt 0 S0 S 1 0 S 2 1 S 0 ={0,1,2,3,4,5} S 0,1={3} ; -closure({3}) =S 0 S 0,0={1,2,4,5} ; -closure({1,2,4,5}) ={1,2,4,5} =S 1 S 1,1={3} = S 0 S 1,0={2,5} ; -closure({2,5}) ={2,5} =S 2 S 2,1={3} = S 0 S 2,0={ } ;

111 谢谢谢谢!

大侠素材铺

大侠素材铺编译原理与技术词法分析 Ⅱ 计算机科学与技术学院李诚 13/09/2018 主要内容记号 (token) 源程序词法分析器 getnexttoken 语法分析器符号表词法分析器的自动生成正则表达式 NFA DFA 化简的 DFA 词法分析器的生成器 Lex: flex jflex Fst lexicl nlyzer genertor 2/51 Regulr Expr to NFA 正则表达式

第三章词法分析 1. 词法分析的含义 ; 2. 词法分析的基本概念 ; 3. 正则表达式 词法单元模式的表达 ; 4. 状态转换图 ; 5. 词法分析器构造工具 ; 6. 有穷状态自动机 ; 7. 从正则表达式到 NFA,DFA 的映射方法 ;

第三章词法分析 1. 词法分析的含义 ; 2. 词法分析的基本概念 ; 3. 正则表达式词法单元模式的表达 ; 4. 状态转换图 ; 5. 词法分析器构造工具 ; 6. 有穷状态自动机 ; 7. 从正则表达式到 NFA,DFA 的映射方法 ;