Microsoft PowerPoint - ch2 [兼容模式]

Size: px

Start display at page:

Download "Microsoft PowerPoint - ch2 [兼容模式]"

侧谈
4 years ago
Views:

1 第 2 章词法分析记号 (token) 源程序词法分析器取下一个记号语法分析器符号表本章内容词法分析器 : 把构成源程序的字符流翻译成记号流, 还完成和用户接口的一些任务围绕词法分析器的自动生成展开介绍正规式状态转换图和有限自动机概念

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 引号和之间的任意字符串, 但引号本身除外

3 2.1 词法记号及属性历史上词法定义中的一些问题忽略空格带来的困难 ( 如 Fortrn 语言 ) DO 8 I DO8I DO 8 I 3, 75 关键字不保留 ( 如 Fortrn 语言 ) IF THEN THEN THEN=ELSE;ELSE 关键字保留字和标准标识符的区别保留字是语言预先确定了含义的词法单元标准标识符也是预先确定了含义的标识符, 但程序可以重新声明它的含义

4 2.1 词法记号及属性词法记号的属性 position = initil + rte 6 的记号和属性值 : id, 指向符号表中 position 条目的指针 ssign _ op id, 指向符号表中 initil 条目的指针 dd _ op id, 指向符号表中 rte 条目的指针 mul op numer, 整数值 6

5 2.1 词法记号及属性词法错误词法分析器对源程序采取非常局部的观点例 : 难以发现下面的错误 fi ( == f (x) ) 在实数是. 格式下, 可以发现下面的错误 123.x 紧急方式的错误恢复删掉当前若干个字符, 直至能读出正确的记号错误修补进行增删替换和交换字符的尝试

6 2.2 词法记号的描述与识别串和语言字母表 : 符号的有限集合, 例 : = {, 1} 串 : 符号的有穷序列, 例 :11, 语言 : 字母表上的一个串集 {,,,, }, {}, 句子 : 属于语言的串串的运算连接 ( 积 ) xy,s = s = s 幂 s 为,s i 为 s i -1 s(i > )

7 2.2 词法记号的描述与识别语言的运算并 : 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 +

8 2.2 词法记号的描述与识别正规式正规式用来表示简单的语言, 叫做正规集正规式定义的语言备注 {} {} (r) (s) L(r) L(s) r 和 s 是正规式 (r)(s) ) L(r)L(s) ) r 和 s 是正规式 (r) * (L(r)) * r 是正规式 (r) L(r) r 是正规式 (() () * ) (c) 可以写成 * c

9 2.2 词法记号的描述与识别正规式的例子 = {, } {, } ( )( ) {,,, } {,,, } * 由字母构成的所有串集, 含 ( ) * 由和构成的所有串集, 含复杂的例子 ( 11 ( (1 1) ( 11) (1 1) ) ) 句子 :

10 2.2 词法记号的描述与识别正规定义对正规式命名, 使表示简洁 d 1 r 1 d 2 r 2... d n r n 各个 d i 的名字都不同每个 r i 都是 {d 1, d 2,,dd i-1 1 } 上的正规式

11 2.2 词法记号的描述与识别正规定义的例子 C 语言的标识符是字母数字和下划线组成的串 ltt letter_ A B Z z _ digit 1 9 id letter_(letter_ ( digit) *

12 2.2 词法记号的描述与识别正规定义的例子无符号数集合, 例 1946,11.28,63E8,1.99E6 digit 1 9 digits digit digit * optionl_frction.digits it optionl_exponent (E(+ ) digits ) numerdigits i optionl_frction i optionl_exponent 简化表示 numer digit + (.digit + )? (E(+ )? digit + )?

13 2.2 词法记号的描述与识别正规定义的例子 ( 进行下一步讨论的例子 ) while while do do relop < < = = < > > > = letter A B Z z id letter (letter digit ) * numer digit + (.digit + )? (E (+ )?digit ) g + )? delim lnk t newline ws delim +

14 2.2 词法记号的描述与识别转换图关系算符的转换图 < = > = 2 > other 4 return(relop, EQ) = other 7 8 return(relop, LE) return(relop, NE) * return(relop, LT) * return(relop, GE) return(relop, GT)

15 2.2 词法记号的描述与识别标识符和保留字的转换图 letter 或 digit * letter other return(instllid( ))

16 2.2 词法记号的描述与识别无符号数的转换图 numer digit + (.digit + )? (E (+ )? digit + )? E digit digit digit digit digit. digit E +/ digit other other other return( instllnum()) 19 *

17 2.2 词法记号的描述与识别空白的转换图 delim lnk t newline ws delim+ delim * delim other

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

19 2.3 有限自动机 NFA 的转换表状态输入符号 {, 1} {} 1 {2} 2 识别语言 ( ) * 1 2 的 NFA

20 2.3 有限自动机例识别 * * 的 NFA

21 2.3 有限自动机确定的有限自动机 ( 简称 DFA) 一个数学模型, 包括 : 1 有限的状态集合 S 2 输入符号集合 3 转换函数 move : S S, 且可以是部分函数 4 唯一的状态 s 5 接受状态集合 F S 识别语言 ( ) * 的 DFA 1 2

22 2.3 有限自动机例 DFA, 识别 {,1} 上能被 5 整除的二进制数已读过尚未读已读部分的值某时刻读进 = 1 读进 = 21 5 个状态即可, 分别代表已读部分的值除以 5 的余数

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

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

25 2.3 有限自动机例 ( )*,NFA,NFA 如下, 把它变换为 DFA

26 2.3 有限自动机状态输入符号

27 2.3 有限自动机 A = {, 1, 2, 4, 7} 状态 A 输入符号

28 2.3 有限自动机 A = {, 1, 2, 4, 7} B ={1 {1, 2, 3, 4678} 4, 6, 7, 状态 A 输入符号 B

29 2.3 有限自动机 A = {, 1, 2, 4, 7} B ={ } {1, 2, 3, 4, 6, 7, 状态 A B 输入符号 B

30 2.3 有限自动机 A = {, 1, 2, 4, 7} B ={ } {1, 2, 3, 4, 6, 7, C = {1, 2, 4, 5, 6, 7} 状态输入符号 A B C B

31 2.3 有限自动机 A = {, 1, 2, 4, 7} B ={ } {1, 2, 3, 4, 6, 7, C = {1, 2, 4, 5, 6, 7} 状态输入符号 A B C B C

32 2.3 有限自动机 A = {, 1, 2, 4, 7} B ={ } {1, 2, 3, 4, 6, 7, C = {1, 2, 4, 5, 6, 7} 状态输入符号 A B C B B C

33 2.3 有限自动机 A = {, 1, 2, 4, 7} B ={ } {1, 2, 3, 4, 6, 7, C = {1, 2, 4, 5, 6, 7} D = {1,2,4,5,6,7,9} 状态输入符号 A B C B B D C

34 2.3 有限自动机 A = {, 1, 2, 4, 7} B ={ } {1, 2, 3, 4, 6, 7, C = {1, 2, 4, 5, 6, 7} D = {1,2,4,5,6,7,9} 状态输入符号 A B C B B D C D

35 2.3 有限自动机 A = {, 1, 2, 4, 7} B ={ } {1, 2, 3, 4, 6, 7, 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

36 2.3 有限自动机 A = {, 1, 2, 4, 7} B ={ } {1, 2, 3, 4, 6, 7, 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

37 A 2.3 有限自动机状态输入符号 A B C B B D C B C D B C C B D

38 识别语言 ( ) * 的自动机 A 2.3 有限自动机 C B D

39 识别语言 ( ) * 的自动机 A 2.3 有限自动机子集构造法不一定得到最简 DFA C B D

40 2.3 有限自动机 234DFA 的化简死状态在转换函数由部分函数改成全函数表示时引入左图需要引入死状态 E ; 右图无须引入死状态, A C B E D A C B D

41 2.3 有限自动机可区别的状态 A 和 B 是可区别的状态从 A 出发, 读过串, 到达非接受状态 C, 而从 B 出发, 读过串, 到达接受状态 D A 和 C 是不可区别的状态无任何串可用来像上面这样区别它们 A C B D

42 2.3 有限自动机方法 1. {A, B, C}, {D} move({a, BC}) B, C}, = {B} move({a, B, C}, ) = {C, D} 2{A 2. {A, C}, {B}, {D} move({a, C}, ) = {B} move({a, C}) C}, = {C} A 1 2 C B D

43 2.4 从正规式到有限自动机从正规式建立识别器的步骤从正规式构造 NFA( 本节介绍 ) 用语法制导的算法, 它用正规式语法结构来指导构造过程把 NFA 变成 DFA ( 子集构造法, 已介绍 ) 将 DFA 化简 ( 合并不可区别的状态, 也已介绍 )

44 2.4 从正规式到有限自动机首先构造识别和字母表中一个符号的 NFA 重要特点 : 仅一个接受状态, 它没有向外的转换 i f i f 识别正规式的 NFA 识别正规式的 NFA

45 2.4 从正规式到有限自动机构造识别主算符为选择的正规式的 NFA 重要特点 : 仅一个接受状态, 它没有向外的转换 N (s) i f N (t) 识别正规式 s t 的 NFA

46 2.4 从正规式到有限自动机构造识别主算符为连接的正规式的 NFA 重要特点 : 仅一个接受状态, 它没有向外的转换 i N (s) N (t) f 识别正规式 st 的 NFA

47 2.4 从正规式到有限自动机构造识别主算符为闭包的正规式的 NFA 重要特点 : 仅一个接受状态, 它没有向外的转换 i N (s) f 识别正规式 s * 的 NFA

48 2.4 从正规式到有限自动机对于加括号的正规式 (s), 使用 N(s) 本身作为它的 NFA

49 2.4 从正规式到有限自动机本方法产生的 NFA 有下列性质 N(r) 的状态数最多是 r 中符号和算符总数的两倍 N(r) 只有一个接受状态, 接受状态没有向外的转换

50 2.4 从正规式到有限自动机本方法产生的 NFA 有下列性质 N(r) 的每个状态有一个用的符号标记的指向其他状态的转换, 或者最多两个指向其他状态的转换

51 2.4 从正规式到有限自动机 ( ) * 的分解 ( r 1 r 4 r 3 r 2 r 9 r 7 r 8 r 5 r 6 * )

52 2.4 从正规式到有限自动机 ( ) * 的分解 ( r 1 r 4 r 3 r 2 r 9 r 7 r 8 r 5 r 6 * )

53 2.4 从正规式到有限自动机 ( ) * 的分解 ( r 1 r 4 r 3 r 2 r 9 r 7 r 8 r 5 r 6 * )

54 2.4 从正规式到有限自动机 ( ) * 的分解 ( r 1 r 4 r 3 r 2 r 9 r 7 r 8 r 5 r 6 * )

55 2.4 从正规式到有限自动机 ( ) * 的分解 ( r 1 r 4 r 3 r 2 r 9 r 7 r 8 r 5 r 6 * )

56 2.4 从正规式到有限自动机 ( ) * 的分解 ( r 1 r 4 r 3 r 2 r 9 r 7 r 8 r 5 r 6 * )

57 2.4 从正规式到有限自动机 ( ) * 的分解 ( r 1 r 4 r 3 r 2 r 9 r 7 r 8 r 5 r 6 * )

58 2.4 从正规式到有限自动机 ( ) * 的两个 NFA 的比较手工构造 : 1 2 算法构造 :

59 2.4 从正规式到有限自动机例 DFA, 接受和 1 的个数都是偶数的字符串偶偶偶奇 1 奇偶奇奇 1

60 2.4 从正规式到有限自动机小结 : 从正规式建立识别器的步骤从正规式构造 NFA 把 NFA 变成 DFA 将 DFA 化简存在其他办法

61 2.5 词法分析器的生成器用 Lex 建立词法分析器的步骤 Lex 源程序 lex.l lex.yy.c 输入流 Lex 编译器 C 编译器.out lex.yy.c.out 记号序列

62 2.5 词法分析器的生成器 Lex 程序包括三个部分声明 %% 翻译规则 %% 辅助过程 Lex 程序的翻译规则 p 1 { 动作 1} p 2 { 动作 2} p n { 动作 n}

63 2.5 词法分析器的生成器例声明部分 %{ /* 常量 LT, LE, EQ, NE, GT, GE, WHILE, DO, ID, NUMBER, RELOP 的定义 */ %} /* 正规定义 */ delim [ \t \n ] ws {delim}+ letter [A ZZ z] digit [9] id {letter}({letter} {digit})* numer {digit}+(\.{digit}+)?(e[+\]?{digit}+)?

64 2.5 词法分析器的生成器例翻译规则部分 {ws} {/* 没有动作, 也不返回 */} while {return (WHILE);} do {return (DO);} {id} {yylvl = instllid ( ); return (ID);} {numer} {yylvl = instllnum( ); return (NUMBER);} < {yylvl = LT; return (RELOP);} <= {yylvl = LE; return (RELOP);} = {yylvl = EQ; return (RELOP);} <> {yylvl = NE; return (RELOP);} > {yylvl = GT; return (RELOP);} >= {yylvl l= GE; return (RELOP);}

65 2.5 词法分析器的生成器例辅助过程部分 instllid( ) { /* 把词法单元装入符号表并返回指向它的指针 yytext 指向该词法单元的第一个字符, yyleng 给出它的长度 */ } instllnum ( ) { /* 类似上面的过程, 但词法单元不是标识符而是数 *// }

66 本章要点词法分析器的作用和接口, 用高级语言编写词法分析器等内容掌握下面涉及的一些概念, 它们之间转换的技巧方法或算法非形式描述的语言正规式正规式 NFA 非形式描述的语言 NFA NFA DFA DFA 最简 DFA 非形式描述的语言 DFA( 或最简 DFA)

67 例题 1 叙述下面的正规式描述的语言, 并画出接受该语言的最简 DFA 的状态转换图 (1 1)* * 描述的语言是 : 所有不含子串 1 的和 1 的串 1 1. strt 刚读过的不是连续读过一个连续读过不少于两个

68 例题 2 用状态转换图表示接受 ( ) ( )( ) 的 DFA strt

69 例题 3 写出语言所有相邻数字都不相同的非空数字串的正规定义 nswer ( no_ )(no_ ) (no_ ) no_ no_ (1 no_-1 1)(no_-1 1) (no_-1 ) no_-1... no_-8 9 将这些正规定义逆序排列就是答案

70 例题 4 下面 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); }

71 例题 4 现在少了第一个注释的结束符号后, 反而不报错了 long gcd(p,q) long p,q; { if (p%q == ) /* then prt return q else /* else prt */ return gcd(q, p%q); }

大侠素材铺

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