编译原理词法分析2.ppt_三一文库31doc.com

资源描述

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

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

2、外,2.1 词法记号及属性,历史上词法定义中的一些问题忽略空格带来的困难 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条目的指针 a

3、dd_op id，指向符号表中rate条目的指针 mul_ op number，整数值60,2.1 词法记号及属性,2.1.3 词法错误词法分析器对源程序采取非常局部的观点例：难以发现下面的错误 fi (a = f (x) ) 在实数是a.b格式下，可以发现下面的错误 123.x 紧急方式的错误恢复删掉当前若干个字符，直至能读出正确的记号错误修补进行增、删、替换和交换字符的尝试,2.2 词法记号的描述与识别,2.2.1 串和语言字母表：符号的有限集合，例： = 0, 1 串：符号的有穷序列，例：0110, 语言：字母表上的一个串集 , 0, 00, 000, , , 句子：属于语

4、言的串串的运算连接（积） xy，s = s = s 幂 s0为，si为si -1s（i 0）,2.2 词法记号的描述与识别,语言的运算并： L M = s | s L 或 s M 连接： LM = st | 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 L D, LD, L6, L*, L(L D )*, D+,2.2 词法记号的描述与识别,2.2.2 正规式正规式用来表示简单的语言，叫做正规集正规式定义的语言备注 a a a

5、 (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*| 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)

6、 ) ) 句子：01001101000010000010111001,2.2 词法记号的描述与识别,2.2.3 正规定义对正规式命名，使表示简洁 d1 r1 d2 r2 . . . dn rn 各个di的名字都不同每个ri都是 d1, d2, , di-1 上的正规式,2.2 词法记号的描述与识别,正规定义的例子 C语言的标识符是字母、数字和下划线组成的串 letter_ A | B | | Z | a | b | | z | _ digit 0 | 1 | | 9 id letter_(letter_ |digit)*,2.2 词法记号的描述与识别,正规定义的例子无符号数集合，例194

8、B | | Z | a | b | | z id letter (letter | digit )* number digit+ (.digit+)? (E (+ | )? digit+)? delim blank | tab | newline ws delim+,2.2 词法记号的描述与识别,2.2.4 转换图关系算符的转换图,2.2 词法记号的描述与识别,标识符和保留字的转换图,2.2 词法记号的描述与识别,无符号数的转换图 number digit+ (.digit+)? (E (+ | )? digit+)?,2.2 词法记号的描述与识别,空白的转换图 delim blank |

9、tab | newline ws delim+,2.3 有限自动机,2.3.1 不确定的有限自动机（简称NFA）一个数学模型，它包括： 1、状态集合S 2、输入符号集合 3、转换函数move : S ( ) P(S) 4、状态s0是唯一的开始状态 5、F S是接受状态集合,识别语言 (a|b)*ab 的NFA,状态,NFA的转换表,2.3 有限自动机,识别语言 (a|b)*ab 的NFA,2.3 有限自动机,例识别aa*|bb*的NFA,2.3.2 确定的有限自动机（简称DFA) 一个数学模型，包括：,1、状态集合S 2、输入字母集合 3、转换函数move : S

10、 S，且可以是部分函数 4、唯一的开始状态 s0 5、接受状态集合F S,识别语言 (a|b)*ab 的DFA,2.3 有限自动机,2.3 有限自动机,例 DFA，识别0,1上能被5整除的二进制数已读过尚未读已读部分的值某时刻 101 0111000 5 读进0 1010 111000 5 2 = 10 读进1 10101 11000 10 2 + 1= 21 5个状态即可，分别代表已读部分的值除以5的余数,例 DFA，识别0,1上能被5整除的二进制数,0,1,2,3,开始,4,2.3 有限自动机,10102 = 1010 1112 = 710,例 DFA,接受

11、 0和1的个数都是偶数的字符串,2.3 有限自动机,2.3.3 NFA到DFA的变换子集构造法 1、DFA的一个状态是NFA的一个状态集合 2、读了输入a1 a2 an后， NFA能到达的所有状态：s1, s2, , sk，则 DFA到达状态s1, s2, , sk,0,0, 1,0, 2,2.3 有限自动机,未画完,例 (a|b)*ab，NFA如下，把它变换为DFA,2.3 有限自动机,状态,2.3 有限自动机,状态,A = 0, 1, 2, 4, 7,2.3 有限自动机,状态,A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6,

12、 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, 6, 7, 8 C = 1, 2, 4, 5,

13、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 = 1, 2, 4, 5, 6, 7 D = 1,

14、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 的自动机,子集构造法不一定得到最简DFA,2.3 有限自动机,2.3.4 DFA的化简死状态在转换函数由部分函数改成全函数表示时引入左图需要引入死状态E ；右图无须引入死状态,2.3 有

15、限自动机,可区别的状态 A和B是可区别的状态从A出发，读过串b，到达非接受状态C，而从B出发，读过串b，到达接受状态D 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 有限自动机,从正规式建立识别器的步骤从正规式构造NFA（本节介绍）用语法制导的算法，它用正规式语法结构来指导构造过程把NFA变成DFA

16、（子集构造法，已介绍）将DFA化简（合并不可区别状态，也已介绍）,2.4 从正规式到有限自动机,首先构造识别和字母表中一个符号的NFA 重要特点：仅一个接受状态，它没有向外的转换,2.4 从正规式到有限自动机,构造识别主算符为选择的正规式的NFA 重要特点：仅一个接受状态，它没有向外的转换,2.4 从正规式到有限自动机,构造识别主算符为连接的正规式的NFA 重要特点：仅一个接受状态，它没有向外的转换,2.4 从正规式到有限自动机,构造识别主算符为闭包的正规式的NFA 重要特点：仅一个接受状态，它没有向外的转换,2.4 从正规式到有限自动机,对于加括号的正规式(s)，使用N(s)本身作为它的

17、NFA,2.4 从正规式到有限自动机,本方法产生的NFA有下列性质 N(r)的状态数最多是r中符号和算符总数的两倍 N(r)只有一个接受状态，接受状态没有向外的转换,2.4 从正规式到有限自动机,本方法产生的NFA有下列性质 N(r)的每个状态有一个用的符号标记的指向其它结点的转换，或者最多两个指向其它结点的转换,2.4 从正规式到有限自动机,2.4 从正规式到有限自动机,2.4 从正规式到有限自动机,2.4 从正规式到有限自动机,2.4 从正规式到有限自动机,2.4 从正规式到有限自动机,2.4 从正规式到有限自动机,2.4 从正规式到有限自动机,(a|b)*ab的两个NFA的比较,手工构造

18、:,算法构造:,2.4 从正规式到有限自动机,小结：从正规式建立识别器的步骤从正规式构造NFA 把NFA变成DFA 将DFA化简存在其它办法,2.4 从正规式到有限自动机,用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

19、 Za z digit 09 id letter(letter|digit)* number digit+( .digit+)?(E+?digit+)?,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; retu

20、rn (RELOP); “ = ” yylval = GE; return (RELOP);,2.5 词法分析器的生成器,例辅助过程部分 install_ id ( ) /* 把词法单元装入符号表并返回指针。 yytext指向该词法单元的第一个字符， yyleng给出的它的长度 */ install_num ( ) /* 类似上面的过程，但词法单元不是标识符而是数 */ ,2.5 词法分析器的生成器,词法分析器的作用和接口，用高级语言编写词法分析器等内容掌握下面涉及的一些概念，它们之间转换的技巧、方法或算法非形式描述的语言正规式正规式 NFA 非形式描述的语言 NFA NFA DFA

22、-1 | ) | no_0-1 . . . no_0-8 9 将这些正规定义逆序排列就是答案,例题 3,下面C语言编译器编译下面的函数时，报告 parse error before else long gcd(p,q) long p,q; if (p%q = 0) /* then part */ return q 此处遗漏分号 else /* else part */ return gcd(q, p%q); ,例题 4,现在少了第一个注释的结束符号后，反而不报错了 long gcd(p,q) long p,q; if (p%q = 0) /* then part return q else /* else part */ return gcd(q, p%q); ,例题 4,第一次 2.3, 2.4 (f) (g) 第二次 2.7 (c) (d)，2.8 ( 仅为2.7 (c) )， 2.11，2.15,习题,

展开阅读全文