第二章词法分析

1、第二章第二章 词法分析词法分析本章内容本章内容 词法分析器：把构成源程序的字符流翻译成词法分析器：把构成源程序的字符流翻译成记号流，记号流，还完成和用户接口的一些任务还完成和用户接口的一些任务 围绕词法分析器的自动生成展开围绕词法分析器的自动生成展开 介绍正规式、状态转换图和有限自动机概念介绍正规式、状态转换图和有限自动机概念词法分析器词法分析器语法分析器语法分析器符号表符号表记号记号(token)取下一个记号取下一个记号源程序源程序2.1 词法记号及属性词法记号及属性 2.1.1 词法记号、模式、词法单元词法记号、模式、词法单元 记号名记号名词法单元例举词法单元例举模式的非形式描述模式的非形

2、式描述 if if 字符字符i, f for for字符字符f, o, r relation , = , = , 或或 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 词法记号的描述与识别词法记号的描述

3、与识别 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*| c 2.2 词法记号的描述与识别词法记号的描述与识别 正规式的例子正规式的例子 = = a, b a | ba, b (a | b) (a | b )aa, ab, ba, bb aa | ab |

4、ba | bbaa, ab, ba, bb a*由字母由字母a构成的所有串集构成的所有串集 (a | b)*由由a和和b构成的所有串集构成的所有串集 复杂的例子复杂的例子( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 句子：句子：010011010000100000101110012.2 词法记号的描述与识别词法记号的描述与识别 2.2.3 正规定义正规定义 对正规式命名，使表示简洁对正规式命名，使表示简洁 d1 r1 d2 r2 . . . dn rn各个各个di的名字都不同的名字都不同每个每个ri都是都是 d1, d2, , di-1 上的正

5、规式上的正规式2.2 词法记号的描述与识别词法记号的描述与识别 正规定义的例子正规定义的例子 C语言的标识符是字母、数字和下划线组成的串语言的标识符是字母、数字和下划线组成的串 letter_ A | B | | Z | a | b | | z | _ digit 0 | 1 | | 9 id letter_( (letter_ | |digit) )* 2.2 词法记号的描述与识别词法记号的描述与识别 正规定义的例子正规定义的例子 无符号数集合，例无符号数集合，例1946, ,11.28, ,63E8, ,1.99E 6digit 0 | 1 | | 9digits digit digit*

6、optional_fraction . .digits| | optional_exponent ( E ( + | | ) digits ) | numberdigits optional_fraction optional_exponent 简化表示简化表示number digit+ (.digit+)? (E(+| )? digit+)?2.2 词法记号的描述与识别词法记号的描述与识别 正规定义的例子（进行下一步讨论的例子）正规定义的例子（进行下一步讨论的例子）while whiledo dorelop | = | = | | | =letter A | B | | Z | a | b

7、| | z id letter (letter | digit )*number digit+ (.digit+)? (E (+ | )? digit+)? delim blank | tab | newline ws delim+2.2 词法记号的描述与识别词法记号的描述与识别 2.2.4 转换图转换图 关系算符的转换图关系算符的转换图051624837return(relop, LE)return(relop, NE)return(relop, LT)return(relop, GE)return(relop, GT)return(relop, EQ)开始开始=*otherother2.2

8、 词法记号的描述与识别词法记号的描述与识别 标识符和关键字的转换图标识符和关键字的转换图91011开始开始letterother*letter或或digitreturn(installId( )2.2 词法记号的描述与识别词法记号的描述与识别 无符号数的转换图无符号数的转换图 number digit+ (.digit+)? (E (+ | )? digit+)?开始开始1912131415161718digitdigitdigitdigitdigitdigitother.E+/ Edigitotherotherreturn( installNum( ) )*2.2 词法记号的描述与识别词法记

9、号的描述与识别 空白空白的转换图的转换图delim blank | tab | newline ws delim+2122开始开始delimother*delim202.3 有有 限限 自自 动动 机机 2.3.1 不确定的有限自动机（简称不确定的有限自动机（简称NFA）一个数学模型，它包括：一个数学模型，它包括：1、有限的状态集合、有限的状态集合S2、输入符号集合、输入符号集合 3、转换函数、转换函数move : S ( ) P(S)4、状态、状态s0是唯一的开始状态是唯一的开始状态5、F S是接受状态集合是接受状态集合识别语言识别语言(a|b)*ab 的的NFA12开始开始a0abb输输

10、入入 符符 号号ab00, 10122状状 态态 NFA的转换表的转换表2.3 有有 限限 自自 动动 机机 识别语言识别语言(a|b)*ab 的的NFA12开始开始a0abb2.3 有有 限限 自自 动动 机机 例例 识别识别aa* *| |bb* *的的NFA12开始开始a0abb34 2.3.2 确定的有限自动机（简称确定的有限自动机（简称DFA) ) 一个数学模型，包括：一个数学模型，包括：1、有限的状态集合、有限的状态集合S2、输入字母集合、输入字母集合 3、转换函数、转换函数move : S S，且可以是部分函数且可以是部分函数4、唯一的开始状态、唯一的开始状态 s05、接受状态接

11、受状态集合集合F S12开始开始a0abbab识别语言识别语言(a|b)*ab 的的DFA2.3 有有 限限 自自 动动 机机 2.3 有有 限限 自自 动动 机机 例例 DFA，识别，识别0,1上能被上能被5整除的二进制数整除的二进制数已读过已读过尚未读尚未读已读部分的值已读部分的值某时刻某时刻10101110005读进读进01010 1110005 2 = 10读进读进110101 1100010 2 + 1= 215个状态即可，分别代表已读部分的值除以个状态即可，分别代表已读部分的值除以5的余数的余数 例例 DFA，识别，识别0,1上能被上能被5整除的二进制数整除的二进制数0123开始开

12、始410010101012.3 有有 限限 自自 动动 机机 10102 = 10101112 = 710 例例 DFA, ,接受接受 0和和1的个数都是偶数的字符串的个数都是偶数的字符串0000 3 211奇奇0奇奇1奇奇0偶偶1 1011开始开始偶偶0偶偶1偶偶0奇奇12.3 有有 限限 自自 动动 机机 2.3.3 NFA到到DFA的变换的变换 子集构造法子集构造法1、DFA的一个状态是的一个状态是NFA的一个状态集合的一个状态集合2、读了输入、读了输入a1 a2 an后后， NFA能到达的所有状态：能到达的所有状态：s1, s2, , sk，则则 DFA到达状态到达状态s1, s2,

13、, sk 12a开始开始 0abb00, 1aba0, 2b2.3 有有 限限 自自 动动 机机 未画完未画完19开始开始 0ab ab6782345 例例 (a|b)*ab，NFA如下，把它变换为如下，把它变换为DFA2.3 有有 限限 自自 动动 机机 19开始开始 0ab ab6782345 输入符号输入符号ab状态状态 2.3 有有 限限 自自 动动 机机 19开始开始 0ab ab6782345 输入符号输入符号abA状态状态 A = 0, 1, 2, 4, 7 2.3 有有 限限 自自 动动 机机 19开始开始 0ab ab6782345 输入符号输入符号abAB状态状态 A =

14、0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 2.3 有有 限限 自自 动动 机机 19开始开始 0ab ab6782345 输入符号输入符号abABB状态状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 2.3 有有 限限 自自 动动 机机 19开始开始 0ab ab6782345 输入符号输入符号abABCB状态状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 2.3 有有 限限 自自 动动 机机 19开始开始 0ab ab6782345

15、输入符号输入符号abABCBC状态状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 2.3 有有 限限 自自 动动 机机 19开始开始 0ab ab6782345 输入符号输入符号abABCBBC状态状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 2.3 有有 限限 自自 动动 机机 19开始开始 0ab ab6782345 输入符号输入符号abABCBBDC状态状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3,

16、4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9 2.3 有有 限限 自自 动动 机机 19开始开始 0ab ab6782345 输入符号输入符号abABCBBDCD状态状态 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 有有 限限 自自 动动 机机 19开始开始 0ab ab6782345 输入符号输入符号abABCBBDCBCD状态状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3

17、, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9 2.3 有有 限限 自自 动动 机机 19开始开始 0ab ab6782345 输入符号输入符号abABCBBDCBCDBC状态状态 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 有有 限限 自自 动动 机机 19开始开始 0ab ab6782345 输入符号输入符号abABCBBDCBCDBC状态状态 BD开始开始aAabbabCba2.3 有

18、有 限限 自自 动动 机机 19开始开始 0ab ab6782345 BD开始开始aAabbabCba12开始开始a0abbab识别语言识别语言(a|b)*ab 的的自动机自动机2.3 有有 限限 自自 动动 机机 19开始开始 0ab ab6782345 BD开始开始aAabbabCba12开始开始a0abbab识别语言识别语言(a|b)*ab 的的自动机自动机子集构造法不一子集构造法不一定得到最简定得到最简DFA2.3 有有 限限 自自 动动 机机 BD开始开始aAabbaa, bCbaEb2.3.4 DFA的化简的化简 死状态死状态 在转换函数由部分函数改成全函数表示时引入在转换函数由部

19、分函数改成全函数表示时引入 左图需要引入死状态左图需要引入死状态E ；右图无须引入死状态；右图无须引入死状态BD开始开始aAabbabCba2.3 有有 限限 自自 动动 机机 可区别的状态可区别的状态 A和和B是可区别的状态是可区别的状态 从从A出发，读过单字符出发，读过单字符b构成的串，到达非接受构成的串，到达非接受状态状态C，而从，而从B出发，读过串出发，读过串b，到达接受状态，到达接受状态D A和和C是不可区别的状态是不可区别的状态 无任何串可用来像上面这样无任何串可用来像上面这样区别它们区别它们BD开始开始aAabbabCba2.3 有有 限限 自自 动动 机机 方法方法1. A,

20、B, C, Dmove(A, B, C, a) = Bmove(A, B, C, b) = C, D2. A, C, B, Dmove(A, C, a) = Bmove(A, C, b) = CBD开始开始aAabbabCba12开始开始a0abbab2.3 有有 限限 自自 动动 机机 从正规式建立识别器的步骤从正规式建立识别器的步骤从正规式构造从正规式构造NFA（本节介绍）本节介绍）用语法制导的算法，它用正规式语法结构来指导用语法制导的算法，它用正规式语法结构来指导构造过程构造过程把把NFA变成变成DFA （子集构造法，已介绍）子集构造法，已介绍） 将将DFA化简化简 （合并不可区别状态，

21、也已介绍）（合并不可区别状态，也已介绍）2.4 从正规式到有限自动机从正规式到有限自动机 首先构造识别首先构造识别 和字母表中一个符号的和字母表中一个符号的NFA重要特点：仅一个接受状态，它没有向外的转换重要特点：仅一个接受状态，它没有向外的转换i开始开始 识别正规式识别正规式 的的NFAafif开始开始识别正规式识别正规式a的的NFA2.4 从正规式到有限自动机从正规式到有限自动机 构造识别主算符为选择的正规式的构造识别主算符为选择的正规式的NFA重要特点：仅一个接受状态，它没有向外的转换重要特点：仅一个接受状态，它没有向外的转换 fi开始开始识别正规式识别正规式s | t 的的NFAN (

22、s)N (t) 2.4 从正规式到有限自动机从正规式到有限自动机 构造识别主算符为连接的正规式的构造识别主算符为连接的正规式的NFA重要特点：仅一个接受状态，它没有向外的转换重要特点：仅一个接受状态，它没有向外的转换识别正规式识别正规式 st 的的NFAiN (s)f开始开始N (t)2.4 从正规式到有限自动机从正规式到有限自动机 构造识别主算符为闭包的正规式的构造识别主算符为闭包的正规式的NFA重要特点：仅一个接受状态，它没有向外的转换重要特点：仅一个接受状态，它没有向外的转换N (s)f开始开始识别正规式识别正规式 s* 的的NFAi 2.4 从正规式到有限自动机从正规式到有限自动机 对

23、于加括号的正规式对于加括号的正规式(s)，使用使用N(s)本身作为本身作为它的它的NFA2.4 从正规式到有限自动机从正规式到有限自动机 本方法产生的本方法产生的NFA有有下列性质下列性质 N(r)的状态数最多是的状态数最多是r中符号和算符总数的两倍中符号和算符总数的两倍 N(r)只有一个接受状态，接受状态没有向外的转只有一个接受状态，接受状态没有向外的转换换2.4 从正规式到有限自动机从正规式到有限自动机19开始开始 0ab ab6782345 本方法产生的本方法产生的NFA有有下列性质下列性质 N(r)的每个状态有一个用的每个状态有一个用 的符号标记的指向其它的符号标记的指向其它结点的转换

24、，或者最多两个指向其它结点的结点的转换，或者最多两个指向其它结点的 转转换换2.4 从正规式到有限自动机从正规式到有限自动机19开始开始 0ab ab6782345 2.4 从正规式到有限自动机从正规式到有限自动机 19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解2.4 从正规式到有限自动机从正规式到有限自动机 19开始开始 0 ab678ab2345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解2.4 从正规式到有限自动机从正规式到有限自动机 19开始开始 0ab ab6782345

25、 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解2.4 从正规式到有限自动机从正规式到有限自动机 19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解2.4 从正规式到有限自动机从正规式到有限自动机 19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解2.4 从正规式到有限自动机从正规式到有限自动机19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解2.

26、4 从正规式到有限自动机从正规式到有限自动机 19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解 (a|b)*ab的两个的两个NFA的比较的比较 12开始开始a 0abb手工构造手工构造:算法构造算法构造:2.4 从正规式到有限自动机从正规式到有限自动机19开始开始 0ab ab6782345 小结：从正规式建立识别器的步骤小结：从正规式建立识别器的步骤从正规式构造从正规式构造NFA把把NFA变成变成DFA 将将DFA化简化简 存在其它办法存在其它办法2.4 从正规式到有限自动机从正规式到有限自动机 用用Lex建立词法分析

27、器的步骤建立词法分析器的步骤Lex编译器编译器Lex源程序源程序lex.llex.yy.cC编译器编译器lex.yy.ca.outa.out输入流输入流记号序列记号序列2.5 词法分析器的生成器词法分析器的生成器 Lex程序包括三个部分程序包括三个部分 声明声明 翻译规则翻译规则 辅助过程辅助过程 Lex程序的翻译规则程序的翻译规则 p1动作动作1 p2动作动作2 pn动作动作n2.5 词法分析器的生成器词法分析器的生成器 例例声明部分声明部分%/* * 常量常量LT, LE, EQ, NE, GT, GE, WHILE, DO, ID, NUMBER, RELOP的定义的定义* */%/*

28、* 正规定义正规定义 * */delim t n wsdelim+letterA Za zdigit0 9idletter(letter|digit)* *numberdigit+( .digit+)?(E+ ?digit+)?2.5 词法分析器的生成器词法分析器的生成器 例例翻译规则部分翻译规则部分ws/* * 没有动作，也不返回没有动作，也不返回 * */whilereturn (WHILE);doreturn (DO);idyylval = install_id ( ); return (ID);numberyylval = install_num( );return (NUMBER);

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