二章词法分析.ppt_三一文库31doc.com

资源描述

《二章词法分析.ppt》由会员分享，可在线阅读，更多相关《二章词法分析.ppt（82页珍藏版）》请在三一文库上搜索。

1、第二章词法分析,本章内容词法分析器：把构成源程序的字符流翻译成记号流，还完成和用户接口的一些任务围绕词法分析器的自动生成展开介绍正规式、状态转换图和有限自动机概念,2.1 词法记号及属性,2.1.1 词法记号、模式、词法单元词法记号词法单元例举模式的非形式描述 var var var for for for relation , = , = , 或 = 或 = 或 id sum, count, D5 由字母开头的字母数字串 num 3.1, 10, 2.8 E12 任何数值常数 literal “seg. error” 引号“和”之间的任意字符串，但引号本身除外,2.1 词法记

2、号及属性,历史上词法定义中的一些问题忽略空格带来的困难 DO 8 I 3. 75 DO8I 3. 75 DO 8 I 3, 75 关键字是否保留 IF THEN THEN THEN=ELSE；ELSE 关键字、保留字和标准标识符的区别,2.1 词法记号及属性,2.1.2 词法记号的属性 position := initial + rate * 60的记号和属性值： id，指向符号表中position条目的指针 assign _ op， id，指向符号表中initial条目的指针 add_op，+ id，指向符号表中rate条目的指针 mul_ op, * num，整数值60,2.1 词法记号

3、及属性,2.1.3 词法错误词法分析器对源程序采取非常局部的观点难以发现下面的错误 fi (a = f (x) ) 在实数是a.b格式下，可以发现下面的错误 123. 紧急方式的错误恢复错误修补,2.2 词法记号的描述与识别,2.2.1 串和语言字母表：符号的有限集合，例： = 0,1 串：符号的有穷序列，例：0110, 语言：字母表上的一个串集 ,0,00,000, , 句子：属于语言的串串的运算连接 xy，s = s = s 积（指数） s0为，si为si -1s（i 0）,2.2 词法记号的描述与识别,语言的运算和：LM = s | s L 或 s M 连接：LM = s

4、t | s L 且 t M 指数：L0是，Li是Li -1L 闭包：L = L0 L1 L2 正闭包： L+ = L1 L2 例 L: A, B, , Z, a, b, , z , D: 0, 1, , 9 LD, LD, L6, L*, L(LD )*, D+,2.2 词法记号的描述与识别,2.2.2 正规式正规式用来表示简单的语言，叫做正规集正规式定义的语言备注 a a a (r) | (s) L(r)L(s) r和s是正规式 (r)(s) L(r)L(s) r和s是正规式 (r)* (L(r)* r是正规式 (r) L(r) r是正规式 (a) (b)*)| (c)可以写成ab

5、*| c,2.2 词法记号的描述与识别,正规式的例子 = a, b a | b a, b (a | b) (a | b ) aa, ab, ba, bb aa | ab | ba | bb aa, ab, ba, bb a* 由字母a构成的所有串集 (a | b)* 由a和b构成的所有串集复杂的例子 ( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 01001101000010000010111001,2.2 词法记号的描述与识别,2.2.3 正规定义对正规式命名，使表示简洁。 d1 r1 d2 r2 . . . dn rn 各个di的名字都不

6、同每个ri都是 d1, d2, , di-1 上的正规式,2.2 词法记号的描述与识别,正规定义的例子 Pascal语言的标识符集合 letter A | B | | Z | a | b | | z digit 0 | 1 | | 9 id letter(letter|digit)*,2.2 词法记号的描述与识别,正规定义的例子 Pascal无符号数集合，例1946,11.28,63.6E8,1.99E6 digit 0 | 1 | | 9 digits digit digit* optional_fraction .digits| optional_exponent (E ( + | |

8、2.2 词法记号的描述与识别,标识符和保留字的转换图,2.2 词法记号的描述与识别,无符号数的转换图,num digit+ (.digit+)? (E (+ | )? digit+)?,2.2 词法记号的描述与识别,空白的转换图,delim blank | tab | newline ws delim+,2.3 有限自动机,2.3.1 不确定的有限自动机（简称NFA）一个数学模型，它包括: 状态集合S；输入符号集合；转换函数move : S () P(S)；状态s0是开始状态； F S是接受状态集合。,识别语言 (a|b)*ab 的NFA,2.3 有限自动机,识别语言

9、(a|b)*ab 的NFA,状态,NFA的转换表,2.3 有限自动机,例识别aa*|bb*的NFA,2.3 有限自动机,2.3.2 确定的有限自动机（简称DFA) 一个数学模型，包括：,状态集合S；输入字母表；转换函数move : S S；唯一的初态 s S；终态集合F S；,识别语言 (a|b)*ab 的DFA,2.3 有限自动机,例：识别 =0,1上能被能5整除的二进制数,101 0111000 1010 111000 10101 11000,2.3 有限自动机,例：识别 =0,1上能被能5整除的二进制数,2.3 有限自动机,例：识别 =

10、0,1上能被能5整除的二进制数,2.3 有限自动机,例：识别 =0,1上能被能5整除的二进制数,2.3 有限自动机,例：识别 =0,1上能被能5整除的二进制数,2.3 有限自动机,例：识别 =0,1上能被能5整除的二进制数,2.3 有限自动机,例：识别 =0,1上能被能5整除的二进制数,2.3 有限自动机,例：识别 =0,1上能被能5整除的二进制数,2.3 有限自动机,例：识别 =0,1上能被能5整除的二进制数,2.3 有限自动机,例：识别 =0,1上能被能5整除的二进制数,2.3 有限自动机,例：识别 =0,1上能被能5整除的二

11、进制数,2.3 有限自动机,例：识别 =0,1上能被能5整除的二进制数,10102 = 1010 1112 = 710,2.3 有限自动机,例：DFA，接受 0和1的个数都是偶数的字符串,2.3 有限自动机,2.3.3 NFA到DFA的变换子集构造法 DFA的一个状态是NFA的一个状态集合读了输入a1 a2 an后， NFA能到达的所有状态：s1, s2, , sk，则 DFA到达状态s1, s2, , sk,2.3 有限自动机,状态,2.3 有限自动机,状态,A = 0, 1, 2, 4, 7,2.3 有限自动机,状态,A = 0, 1,

12、2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8,2.3 有限自动机,状态,A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8,2.3 有限自动机,状态,A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7,2.3 有限自动机,状态,A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7,2.3 有限自动机,状态,A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4

13、, 6, 7, 8 C = 1, 2, 4, 5, 6, 7,2.3 有限自动机,状态,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,2.3 有限自动机,状态,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,2.3 有限自动机,状态,A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C

14、= 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9,2.3 有限自动机,状态,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,2.3 有限自动机,状态,2.3 有限自动机,识别语言 (a|b)*ab 的自动机,2.3 有限自动机,识别语言 (a|b)*ab 的自动机,2.3 有限自动机,2.3.4 DFA的化简死状态左图无须加死状态，右图加入死状态E。,2.3 有限自动机,可区别的状态

15、 A和B是可区别的状态 A和C是不可区别的状态,2.3 有限自动机,方法 1. A, B, C, D move(A, B, C, a = B move(A, B, C, b = C, D 2. A, C, B, D move(A, C, a = B move(A, C, b = C,2.3 有限自动机,方法 1. A, B, C, D move(A, B, C, a = B move(A, B, C, b = C, D 2. A, C, B, D move(A, C, a = B move(A, C, b = C,2.4 从正规式到有限自动机,从正规式建立识别器从正规式构造N

16、FA（本节介绍）用语法制导的算法，它用正规式语法结构来指导构造过程。把NFA变成DFA （子集构造法，已介绍）将DFA化简（合并不可区别状态，也已介绍）,2.4 从正规式到有限自动机,首先构造识别和字母表中一个符号的NFA,2.4 从正规式到有限自动机,构造识别主算符为选择的正规式的NFA,2.4 从正规式到有限自动机,构造识别主算符为连接的正规式的NFA,2.4 从正规式到有限自动机,构造识别主算符为闭包的正规式的NFA,2.4 从正规式到有限自动机,对于加括号的正规式(s)，使用N(s)本身作为它的NFA。,2.4 从正规式到有限自动机,本方法产生的NFA有下列性质: N(r)的状

17、态数最多是r中符号和算符总数的两倍。 N(r)只有一个开始状态和一个接受状态，接受状态没有向外的转换。 N(r)的每个状态有一个用的符号标记的指向其它结点的转换，或者最多两个指向其它结点的转换。,2.4 从正规式到有限自动机,2.4 从正规式到有限自动机,2.4 从正规式到有限自动机,2.4 从正规式到有限自动机,2.4 从正规式到有限自动机,2.4 从正规式到有限自动机,2.4 从正规式到有限自动机,2.4 从正规式到有限自动机,(a|b)*ab的两个NFA的比较,2.4 从正规式到有限自动机,小结：从正规式建立识别器的步骤从正规式构造NFA 把NFA变成DFA 将DFA化简存在其它办法

18、,2.5 词法分析器的生成器,用Lex建立词法分析器的步骤,2.5 词法分析器的生成器,Lex程序包括三个部分声明翻译规则辅助过程 Lex程序的翻译规则 p1 动作1 p2 动作2 pn 动作n,2.5 词法分析器的生成器,例-声明部分 % /* 常量LT, LE, EQ, NE, GT, GE, WHILE, DO, ID, NUMBER, RELOP的定义*/ % /* 正规定义 */ delim t n ws delim+ letter A Za z digit 09 id letter(letter|digit)* number digit+( .digit+)?(E+?digi

19、t+)?,2.5 词法分析器的生成器,例-翻译规则部分 ws /* 没有动作，也不返回 */ while return (WHILE); do return (DO); id yylval = install_id ( ); return (ID); number yylval = install_num( ); return (NUMBER); “ ” yylval = NE; return (RELOP); “ ” yylval = GT; return (RELOP); “ = ” yylval = GE; return (RELOP);,2.5 词法分析器的生成器,例-辅助过程部分 i

20、nstall_ id ( ) /* 把词法单元装入符号表并返回指针。 yytext指向该词法单元的第一个字符， yyleng给出的它的长度 */ install_num ( ) /* 类似上面的过程，但词法单元不是标识符而是数 */ ,本章要点,词法分析器的作用和接口，用高级语言编写词法分析器等内容，它们与词法分析器的实现有关。掌握下面涉及的一些概念，它们之间转换的技巧、方法或算法。非形式描述的语言正规式正规式 NFA 非形式描述的语言 NFA NFA DFA DFA 最简DFA 非形式描述的语言 DFA（或最简DFA）,例题1,叙述下面的正规式描述的语言，并画出接受该语言的最简

21、DFA的状态转换图。 (1|01)* 0* 描述的语言是，所有不含子串001的0和1的串。,例题2,用状态转换图表示接收(a|b)a(a|b)(a|b)的DFA。,例题2,用状态转换图表示接收(a|b)a(a|b)(a|b)的DFA。,例题2,用状态转换图表示接收(a|b)a(a|b)(a|b)的DFA。,例题2,用状态转换图表示接收(a|b)a(a|b)(a|b)的DFA。,例题3,写出语言“所有相邻数字都不相同的非空数字串”的正规定义。 123031357106798035790123 answer (0 | no_0 0 ) (no_0 0 ) (no_0 | ) | no_0 no_0 (1 | no_0-1 1 ) (no_0-1 1 ) (no_0-1 | ) | no_0-1 . . . no_0-8 9 将这些正规定义逆序排列就是答案,习题,第一次 2.3, 2.4 (f) (g) 第二次 2.7 (c) (d), 2.8 ( 仅为2.8 (c) )， 2.11 修改算法2.4, 使之尽可能少用转换，并保持所产生的NFA只有一个接受状态。,

展开阅读全文