第2章词法(new)

1、第二章第二章 词词 法法 分分 析析u2.1 词法分析器的设计方法词法分析器的设计方法u2.2 一个简单的词法分析器示例一个简单的词法分析器示例u2.3 正规表达式与有限自动机简介正规表达式与有限自动机简介u2.4 正规表达式到有限自动机的构造正规表达式到有限自动机的构造u2.5 词法分析器的自动生成词法分析器的自动生成1词法分析是编译第一个阶段，其任务是：从左至右逐个词法分析是编译第一个阶段，其任务是：从左至右逐个字符地对源程序进行扫描，字符地对源程序进行扫描，产生产生一个个一个个单词符号单词符号，把字，把字符串形式的源程序改造成为单词符号串形式的中间程序。符串形式的源程序改造成为单词符号串

2、形式的中间程序。执行词法分析的程序称为执行词法分析的程序称为词法分析程序，词法分析程序，也称为也称为词词法分析器或扫描器。法分析器或扫描器。词法分析器的功能是词法分析器的功能是输入源程输入源程序，输出单词符号。序，输出单词符号。2(1) 把词法分析程序作为主程序把词法分析程序作为主程序。将词法分析工作将词法分析工作作为独立的一遍来完成，即把词法分析与语法分析明作为独立的一遍来完成，即把词法分析与语法分析明显分开，由词法分析程序将字符串形式的源程序改造显分开，由词法分析程序将字符串形式的源程序改造成单词符号串形式的成单词符号串形式的中间程序中间程序，以这个中间程序作为，以这个中间程序作为语法分析

3、程序的输入。语法分析程序的输入。词法分析词法分析可以采用如下两种处理结构：可以采用如下两种处理结构：3在这种处理结构中，在这种处理结构中，词法分析和语法分析是分别实现词法分析和语法分析是分别实现的，的，如图如图2-1(a)所示。所示。图图2-1(a) 词法分析程序作为主程序词法分析程序作为主程序4(2) 把词法分析程序作为语法分析程序调用的把词法分析程序作为语法分析程序调用的子程序。子程序。在进行语法分析时，每当语法分析程序需在进行语法分析时，每当语法分析程序需要一个单词时便调用要一个单词时便调用词法分析程序词法分析程序，词法分析程序每，词法分析程序每一次调用便从字符串源程序中识别出一次调用便

4、从字符串源程序中识别出一个单词一个单词交给交给语语法分析程序法分析程序。5图图2-1 (b) 词法分析程序作为子程序词法分析程序作为子程序在这种处理结构中，词法分析和语法分析实际上是在这种处理结构中，词法分析和语法分析实际上是交交替进行替进行的，如图的，如图2-1(b)所示。所示。62.1.1 单词符号的分类与输出形式单词符号的分类与输出形式1. 单词符号分类单词符号分类2.1 词法分析器的设计方法词法分析器的设计方法词法分析程序简单地说就是词法分析程序简单地说就是读单词程序读单词程序，该程序扫描用，该程序扫描用高级语言编写的源程序，将源程序中由高级语言编写的源程序，将源程序中由单词符号单词符

5、号组成的组成的字符串字符串分解出一个个分解出一个个单词单词来。来。单词符号单词符号是程序语言的是程序语言的基本语法基本语法单位，具有确定的语单位，具有确定的语法意义。程序语言的法意义。程序语言的单词符号单词符号通常可分为下面通常可分为下面五种五种。7(1) 保留字保留字(也称基本字也称基本字)：如：如C语言中的语言中的if、else、while和和do等，这些字保留了语言所规定的含义，是编译程等，这些字保留了语言所规定的含义，是编译程序识别各类语法成分的依据。几乎所有程序语言都限序识别各类语法成分的依据。几乎所有程序语言都限制用户使用保留字来作为标识符。制用户使用保留字来作为标识符。(2) 标

6、识符标识符：用来标记常量、数组、类型、变量、过：用来标记常量、数组、类型、变量、过程或函数名等，通常由用户自己定义。程或函数名等，通常由用户自己定义。8(3) 常数：常数：包括各种类型的常数，例如整型常数包括各种类型的常数，例如整型常数386、实型常数实型常数0.618、布尔型常数、布尔型常数TRUE等。等。(4) 运算符运算符：如：如“+”、“- ”、“ * ”、“/ ”、“”、“j) i-;如果采用每种单词对应一个整数码，对应的二元式序列？五类单词的种别规定如下：保留字种别：1标识符种别：2运算符种别：3界符种别： 4常量种别： 513上面的子程序输出的二元式序列：( 1, while )

7、( 4, ( )( 2, i )( 3, )( 2, j )( 4, ) )( 2, i )( 3, - )( 4, ; )14(2) 单词自身的值。单词自身的值。单词自身的值是编译中其它阶段所单词自身的值是编译中其它阶段所需要的信息。对于单词符号来说，如果需要的信息。对于单词符号来说，如果一个种别只含一个种别只含有一个单词符号有一个单词符号，那么对于这个单词符号，那么对于这个单词符号，其种别编其种别编码就完全代表了它自身的值码就完全代表了它自身的值。15注意，注意，标识符自身的值就是标识符自身的字符串标识符自身的值就是标识符自身的字符串，而，而常数自身的值是常数本身的二进制数值常数自身的值是

8、常数本身的二进制数值。如果如果一个种别含有多个单词符号一个种别含有多个单词符号，那么对于它的每个单，那么对于它的每个单词符号词符号, 除了给出种别编码之外还应给出单词符号自身除了给出种别编码之外还应给出单词符号自身的值的值，以便把同一种类的不同单词区别开来。，以便把同一种类的不同单词区别开来。16此外，也可用指向某类表格中一个特定项目的此外，也可用指向某类表格中一个特定项目的指针来指针来区分同类中的不同单词。区分同类中的不同单词。例如，对于标识符，可以用例如，对于标识符，可以用它在它在符号表的入口指针符号表的入口指针作为它自身的值；而常数也可作为它自身的值；而常数也可用它在常数表的入口指针作为

9、它自身的值。用它在常数表的入口指针作为它自身的值。17在词法分析中，可以用在词法分析中，可以用状态转换图状态转换图来识别单词。状态来识别单词。状态转换图是转换图是有限的有向图有限的有向图，结点代表状态结点代表状态，用圆圈表示；，用圆圈表示；结点之间可由结点之间可由有向边有向边连接，连接，有向边上可标记字符有向边上可标记字符。2.1.2 状态转换图状态转换图18图图2-2 不同输入字符的状态转换不同输入字符的状态转换例如，图例如，图2-2表示在表示在状态状态i下，若输入字下，若输入字符为符为x，则读入，则读入x并并转换到状态转换到状态j；若输；若输入字符为入字符为y，则读入，则读入y并转换到状态

10、并转换到状态k。19状态状态(即结点即结点)数是有限的，其中必有一初始状态数是有限的，其中必有一初始状态以及若干终止状态，以及若干终止状态，终止状态终止状态(终态终态)的结点用双的结点用双圈圈表示以区别于其它状态。图表示以区别于其它状态。图2-3给出了用于识给出了用于识别标识符、无符号整数、无符号数的状态转换别标识符、无符号整数、无符号数的状态转换图，其图，其初始状态均用初始状态均用0状态状态表示。表示。20图图2-3 标识符及无符号数的状态转换图标识符及无符号数的状态转换图(a) 标识符；标识符；(b) 无符号整数；无符号整数；(c) 无符号数无符号数21u 当到达一类单词符号的当到达一类单

11、词符号的终止状态终止状态时即可给出相应的时即可给出相应的单词编码。单词编码。22u 某些终止状态是在读入了一个其它不属于该单词的符某些终止状态是在读入了一个其它不属于该单词的符号后才得到相应的单词编码的，这表明在识别单词的过号后才得到相应的单词编码的，这表明在识别单词的过程中程中多读入了一个符号多读入了一个符号，所以识别出单词后应将最后，所以识别出单词后应将最后多多读入的这个符号读入的这个符号予以回退予以回退；我们对此类情况的处理是在我们对此类情况的处理是在终态上以终态上以“*”作为标识作为标识。对于对于不含回路的分支状态不含回路的分支状态来说，可以让它对应来说，可以让它对应一个一个switc

12、h()语句或一组语句或一组if-else语句语句。例如，图例如，图2-4(a)的状态的状态i所对应的所对应的switch语句如下：语句如下：23图图2-4(a) 含分支的状态含分支的状态i24s=getchar( );switch (s) case a:case b:case z: ; /*实现状态实现状态j功能的语句功能的语句*/case 0: case 1:case 9: ; /*实现状态实现状态k功能的语句功能的语句*/图图2-4(a) 含分支的状态含分支的状态i对于对于含回路的状态含回路的状态来说，可以让它对应来说，可以让它对应一个一个while语句语句。例如，图例如，图2-4(b)的

13、状态的状态i所对应的所对应的while语句如下：语句如下：getchar( );while(letter( )|digit( )getchar( ); /实现状态实现状态j功能的语句功能的语句图图2-4(b) 含回路的状态含回路的状态i25终态一般对应一个终态一般对应一个return( )语句语句。return意味着从词法分析器返回到调用段，一般指意味着从词法分析器返回到调用段，一般指返回到语法分析器返回到语法分析器。26大多数程序语言的单词符号都可以用大多数程序语言的单词符号都可以用状态转换图状态转换图予以识予以识别。作为一个综合例子，我们来构造一个别。作为一个综合例子，我们来构造一个C语言

14、子集语言子集的的简单简单词法分析器词法分析器。2.2 一个简单的词法分析器示例一个简单的词法分析器示例2.2.1 C语言子集的单词符号表示语言子集的单词符号表示27单词符号单词符号种别编码种别编码助忆符助忆符内码值内码值while1whileif2ifelse3elseswitch4switchcase 5case标识符标识符6idid在符号表在符号表中的位置中的位置常数常数 7numnum在符号在符号表中的位置表中的位置例：综合实例例：综合实例做出识别下表做出识别下表2.12.1所示的所示的C C语言子集的语言子集的单词符号单词符号的状态转换图（的状态转换图（P12P12）2829单词符号单

15、词符号种别编码种别编码助忆符助忆符内码值内码值+8+9*10*=11relopLE=11relopEQ=12=；13；在设计的状态转换图中，在设计的状态转换图中，首先首先对输入串做预处理，即对输入串做预处理，即剔除多余的空白符剔除多余的空白符(在实际的词法分析中，预处理还在实际的词法分析中，预处理还包括包括剔除注释和制表换行符等编辑性字符剔除注释和制表换行符等编辑性字符的工作的工作)，使词法分析工作既简单又清晰。使词法分析工作既简单又清晰。2.2.2 C语言子集对应的状态转换图语言子集对应的状态转换图30其次其次，将保留字作为一类特殊的标识符来处理，也即，将保留字作为一类特殊的标识符来处理，也

16、即对对保留字不专设对应的状态转换图保留字不专设对应的状态转换图，当转换图识别出，当转换图识别出一个标识符时就去查对表一个标识符时就去查对表2.1的前五项，确定它是否为的前五项，确定它是否为一个保留字。一个保留字。当然，也可以专设一个当然，也可以专设一个保留字表保留字表来进行处理。来进行处理。2.2.2 C语言子集对应的状态转换图语言子集对应的状态转换图31图图2-5 简单词法分简单词法分析的状态转换图析的状态转换图返回（返回（id，id在符号表在符号表中的位置）或返回（保中的位置）或返回（保留字，留字，）返回（返回（num，num在常在常数表中的位置）数表中的位置）* *1 12 20 0字母

17、字母非字母与数字非字母与数字字母或数字字母或数字* *空白空白5 54 43 3数字数字数字数字非数字非数字* *6 610101111131312127 7* *8 89 9其它其它；（其他其他返回（返回（+，）返回（返回（=，）返回（返回（relop，EQ）返回（返回（;）返回（返回（）非法字符错非法字符错32状态转换图非常容易用程序实现，最简单的办法是让状态转换图非常容易用程序实现，最简单的办法是让每个状态对应一小段程序每个状态对应一小段程序。对于图。对于图2-5所示的状态转换所示的状态转换图，我们首先引进一组变量和函数如下：图，我们首先引进一组变量和函数如下：2.2.3 状态转换图的实

18、现状态转换图的实现33(1) character：字符变量，存放最新读入的源程序字符。字符变量，存放最新读入的源程序字符。(2) token：字符数组，存放构成单词符号的字符串。：字符数组，存放构成单词符号的字符串。(3) getbe( )：若若character中的字符为空白，则调用中的字符为空白，则调用getchar( )，直至，直至character为非空白字符为止。为非空白字符为止。34(4) concatenation( )：将将token中的字符串与中的字符串与character中的字符连接并作为中的字符连接并作为token中新的字符串。中新的字符串。(5) letter( )和和

19、digit( )：判断判断character中的字符是否中的字符是否为字母和数字的布尔函数，是则返回为字母和数字的布尔函数，是则返回true(即即1)，否，否则返回则返回false(即即0)。35(6) reserve( )：按：按token数组中的字符串查表数组中的字符串查表2.1中的中的前五项前五项(即判别其是否为保留字即判别其是否为保留字)，若是保留字则返回，若是保留字则返回它的编码，否则返回它的编码，否则返回0值。值。(7) retract( )：扫描指针回退一个字符，同时将：扫描指针回退一个字符，同时将character置为空白。置为空白。36(8) buildlist( )：将标识

20、符登录到符号表中或将常数：将标识符登录到符号表中或将常数登录到常数表中。登录到常数表中。(9) error( )：出现非法字符，显示出错信息。：出现非法字符，显示出错信息。37token= ; /*对对token数组初始化数组初始化*/s=getchar( );getbe( ); /*滤除空格滤除空格*/switch(s) case a: case b: case z:相对于图相对于图2-5的词法分析器构造如下：的词法分析器构造如下：38while (letter( )digit( ) concatenation( ); /*将当前读入的字符送入将当前读入的字符送入token数组数组*/ ge

21、tchar( );retract( ); *扫描指针回退一个字符扫描指针回退一个字符*/c=reserve( );if (c=0)39 buildlist( ); /*将标识符登录到符号表中将标识符登录到符号表中*/ return(id，指向，指向id的符号表入口指针的符号表入口指针); else return(保留字码，保留字码，null);break;case 0:case 1: case 9:40while (digit( ) concatenation( ); getchar( );retract( );buildlist( ); /*将常数登录到常数表中将常数登录到常数表中*/ret

22、urn (num，num的常数表入口指针的常数表入口指针);break;case +:41return(+，null);break;case :return(，null);break;case *:return(*，null);break;case :getchar( );if (character = = =) return(relop,LE);else retract( ); return(relop，LT);break; case =:getchar( );42if(character= = =) return (relop, EQ);elseretract( ); return(=,

23、null);break; case ;: return(;, null); break; default: error( ); 43测试程序：if ( x 10 ) x = 20; else x = 9;状态转换图状态转换图对构造词法分析程序是行之有效的，为了对构造词法分析程序是行之有效的，为了便于词法分析器的自动生成，还须将便于词法分析器的自动生成，还须将状态转换图的概状态转换图的概念加以形式化念加以形式化。2.3 正规表达式与正规集正规表达式与正规集44正规表达式正规表达式就是一种就是一种形式化的表示法形式化的表示法，它可以表示单，它可以表示单词符号的结构，从而精确地定义单词符号集。词符号

24、的结构，从而精确地定义单词符号集。正规表达式与正规集正规表达式与正规集正规表达式正规表达式简称为简称为正规式正规式，它表示的集合即为，它表示的集合即为正规集正规集。45例如：程序语言中使用的标识符是一个以例如：程序语言中使用的标识符是一个以字母开头的字母开头的字母数字串字母数字串，如果字母用，如果字母用letter表示，数字用表示，数字用digit表示，表示，则标识符可表示为则标识符可表示为 letter(letter | digit)*46letter与与(letter | digit)*的并置表示两者的连接；的并置表示两者的连接；括号中的括号中的“ | ”表示表示letter或或digit

25、两者选一；两者选一；“*”表示零次或多次引用由表示零次或多次引用由“*”标记的表达式；标记的表达式；(letter | digit)* 是是letter | digit的的零次零次或或多次多次并置，即表并置，即表示一长度为示一长度为0、1、2、的字母数字串；的字母数字串；letter(letter | digit)*47letter(letter | digit)*表示以字母开头的字母数字串，表示以字母开头的字母数字串，也即标识符集。也即标识符集。letter(letter | digit)* 就是表示就是表示标识符的正规式标识符的正规式，而，而标标识符集识符集就是这个正规式所表示的就是这个正

26、规式所表示的正规集正规集。letter(letter | digit)*48(1) 和和都是都是上的正规式，它们所表示的正规集分上的正规式，它们所表示的正规集分别为别为和和。 (2) 对任一个对任一个a，a是是上的一个正规式，它所表示上的一个正规式，它所表示的正规集为的正规集为a。对于给定的字母表对于给定的字母表，正规式和正规集的递归定义正规式和正规集的递归定义如下：如下：49(3) 如果如果R和和S是是上的正规式，它们所表示的上的正规式，它们所表示的正规集分正规集分别为别为L(R)和和L(S)，则：，则： R | S是是上的正规式，它所表示的正规集为上的正规式，它所表示的正规集为L(R)L(

27、S)； (R)* 是是上的正规式，它所表示的正规集为上的正规式，它所表示的正规集为(L(R)*； RS是是上的正规式，它所表示的正规集为上的正规式，它所表示的正规集为L(R)L(S)；50(4) 仅由有限次使用规则仅由有限次使用规则(1)(3)得到的表达式是得到的表达式是上上的的正规式正规式，它所表示的集合是，它所表示的集合是上的上的正规集。正规集。在上述定义中，规则在上述定义中，规则(1)、(2)为基础规则，规则为基础规则，规则(3)为为归纳规则，规则归纳规则，规则(4)是是界限规则界限规则或者或者终止规则终止规则51另，另，上的一个上的一个字字是指由是指由中的字符所构成的一个中的字符所构成

28、的一个有穷有穷序列序列；不包含任何字符的序列称为；不包含任何字符的序列称为空字空字，用，用表示。表示。用用*表示表示上上所有字所有字的全体，则的全体，则空字空字也在其中。例如，也在其中。例如，若若=a，b，则，则* = ，a，b，aa，ab，ba，bb，aaa，。还用还用表示不含任何元素的表示不含任何元素的空集空集。这里需要注意。这里需要注意、和和的区别：的区别：是由是由空字空字组成的集合，而组成的集合，而则表示不则表示不含含任何字任何字的集合。的集合。52n 正规式间的运算符正规式间的运算符“ | ”表示或表示或，“ ”表示连接表示连接(通常可省略通常可省略)，“ * ”表示闭包表示闭包，使

29、用，使用括号括号可以改变可以改变运算的次序。运算的次序。53n 规定规定“*”优先于优先于“”，“”优先于优先于“ | ”，n 在不出现混淆的情况下在不出现混淆的情况下括号括号也可以省去也可以省去n注意注意，*的正规式的正规式R和和S的连接可以形式化地定义为的连接可以形式化地定义为RS = | R&SRn = RRR n个个54即集合即集合RS中的字是由中的字是由R和和S中的字连接而成的，且中的字连接而成的，且R自身的自身的n次连接记为次连接记为我们规定我们规定R0 = ，并令并令R* = R0R1R2R3，则称，则称R* 是是R的闭包的闭包；55 R+ = RR*，并称，并称R+ 是是R的正则闭包。的正则闭包。闭包闭包R* 中的中的每个字每个字都是由都是由R中的字中的字经过经过有限次连接有限次连接而生成的。而生成的。对于对于上的正规式上的正规式R和和S，如果它所表示的正规集，如果它所表示的正规集L(R) = L(S)，则称，则称R和和S等价等价并记为并记为R = S。不难证