编译原理教程02词法分析.

1、第2章词法分析 2.1 词法分析器设计方法词法分析器设计方法 2.2 一个简单的词法分析器示例一个简单的词法分析器示例 2.3 正规表达式与有限自动机简介正规表达式与有限自动机简介 2.4 正规表达式到有限自动机的构造正规表达式到有限自动机的构造 2.5 词法分析器的自动生成词法分析器的自动生成 习题二习题二 第第2章章词 法 分 析 第2章词法分析 词法分析的任务词法分析的任务 词法分析可以采用的处理结构词法分析可以采用的处理结构 第2章词法分析 任务：任务： 从左至右从左至右逐个逐个字符地对源程序进行扫描，产生一个个字符地对源程序进行扫描，产生一个个 单词单词符号，把符号，把字符串字符串形

2、式的源程序改造成为形式的源程序改造成为单词符号串单词符号串形形 式的中间程序。式的中间程序。 执行词法分析的程序称为执行词法分析的程序称为词法分析程序词法分析程序，或，或词法分析词法分析 器器或或扫描器扫描器。 输入输入是源程序，是源程序，输出输出是单词符号。是单词符号。 第2章词法分析 词法分析可以采用如下两种处理结构：词法分析可以采用如下两种处理结构： (1) 把词法分析程序作把词法分析程序作为主程序为主程序。 将词法分析工作作为独立的一遍来完成，即把将词法分析工作作为独立的一遍来完成，即把词法分析与语词法分析与语 法分析法分析明显分开，由明显分开，由词法分析程序词法分析程序将字符串形式的

3、将字符串形式的源程序源程序改造改造 成成单词符号串形式的中间程序单词符号串形式的中间程序，以这个，以这个中间程序中间程序作为作为语法分析语法分析 程序的输入。在这种处理结构中，程序的输入。在这种处理结构中，词法分析和语法分析词法分析和语法分析是分别是分别 实现的，如图实现的，如图21(a)所示。所示。 第2章词法分析 (2) 把词法分析程序作为把词法分析程序作为语法分析程序语法分析程序调用的子程序。调用的子程序。 在进行在进行语法分析语法分析时，每当语法分析程序时，每当语法分析程序需要需要一个单词时便一个单词时便调调 用用词法分析程序，词法分析程序每一次词法分析程序，词法分析程序每一次调用调用

4、便从字符串源程序便从字符串源程序 中中识别出一个单词识别出一个单词交给语法分析程序。在这种处理结构中，词交给语法分析程序。在这种处理结构中，词 法分析和语法分析实际上是法分析和语法分析实际上是交替交替进行的，如图进行的，如图21(b)所示。所示。 第2章词法分析 图图21 词法分析的两种处理结构词法分析的两种处理结构 (a) 词法分析程序作为主程序；词法分析程序作为主程序； (b) 词法分析程序作为子程序词法分析程序作为子程序 由于把词法分析器安排成一个子程序比较自然，因此，由于把词法分析器安排成一个子程序比较自然，因此， 词法分析程序词法分析程序通常通常采用采用第二种第二种处理结构。处理结构

5、。 第2章词法分析 2.1 词法分析器设计方法词法分析器设计方法 单词符号的分类与输出形式单词符号的分类与输出形式 状态转换图状态转换图 第2章词法分析 2.1.1 单词符号的分类与输出形式单词符号的分类与输出形式 1单词符号分类单词符号分类 词法分析程序词法分析程序简单地说简单地说就是读就是读单词程序单词程序，该程序扫描用高级，该程序扫描用高级 语言编写的源程序，将源程序中由语言编写的源程序，将源程序中由单词符号单词符号组成的字符串分解出组成的字符串分解出 一个个一个个单词单词来。因此，来。因此，单词符号单词符号是程序语言的基本语法单位，具是程序语言的基本语法单位，具 有确定的语法意义。有确

6、定的语法意义。 程序语言的程序语言的单词符号单词符号通常可分为下面五种。通常可分为下面五种。 (1) 保留字保留字(也称基本字也称基本字)：如：如C语言中的语言中的if、else、while和和do等，这些字等，这些字 保留了语言所规定的含义，是编译程序识别保留了语言所规定的含义，是编译程序识别各类语法各类语法成分的依据。几乎所有成分的依据。几乎所有 程序语言都程序语言都限制用户限制用户使用保留字来作为标识符。使用保留字来作为标识符。 第2章词法分析 (2) 标识符标识符：用来标记常量、数组、类型、变量、过程或函：用来标记常量、数组、类型、变量、过程或函 数名等，通常由数名等，通常由用户用户自

7、己定义。自己定义。 (3) 常数常数：包括各种类型的常数，如整型常数：包括各种类型的常数，如整型常数386、实型常数、实型常数 0.618、布尔型常数、布尔型常数TRUE等。等。 (4) 运算符运算符：如：如“+”、“”、“*”、“/”、“”、“”等。等。 (5) 界符界符：在语言中是作为语法上的分界符号使用的，如：在语言中是作为语法上的分界符号使用的，如 “，”、“；”、“（”、“）”等。等。 注意注意一个程序语言的一个程序语言的保留字、运算符和界符保留字、运算符和界符的个数是确定的，的个数是确定的， 而而标识符或常数标识符或常数的使用则不限定个数。的使用则不限定个数。 第2章词法分析 2词

8、法分析程序输出单词的形式词法分析程序输出单词的形式 词法分析程序的输入是源程序字符串，而输出是与源程序等价的词法分析程序的输入是源程序字符串，而输出是与源程序等价的单词符单词符 号序列号序列，并且所输出的单词符号通常，并且所输出的单词符号通常表示成如下表示成如下的的二元式二元式： (单词单词种别种别，单词，单词自身的值自身的值) 第2章词法分析 2词法分析程序输出单词的形式词法分析程序输出单词的形式 (1) 单词种别单词种别。 单词种别表示单词的种类，它是语法分析所需要的信息。单词种别表示单词的种类，它是语法分析所需要的信息。 一个语言的单词符号一个语言的单词符号如何如何划分种类、分为几类、如

9、何编码都属于划分种类、分为几类、如何编码都属于技术性技术性问问 题，主要取决于处理上的方便。题，主要取决于处理上的方便。 通常通常让让每种每种单词对应一个整数码，这样可最大限度地把各个单词区别开来。单词对应一个整数码，这样可最大限度地把各个单词区别开来。 对于对于保留字保留字，可将其全体视为，可将其全体视为一种一种，也可，也可一字一种一字一种，采用，采用一字一种一字一种的分类的分类 方法处理起来比较方便；方法处理起来比较方便； 标识符标识符一般统归为一种；一般统归为一种；常数常数可统归为一种，也可按整型、实型、布尔型可统归为一种，也可按整型、实型、布尔型 等分为几种；等分为几种；运算符和界符运

10、算符和界符可采用一符一种的分法，也可统归为一种。可采用一符一种的分法，也可统归为一种。 第2章词法分析 (2) 单词单词自身自身的值。的值。 单词自身的值是单词自身的值是编译中其它阶段编译中其它阶段所需要的信息。所需要的信息。 对于对于单词符号单词符号来说，如果一个来说，如果一个种别种别只含有只含有一个一个单词符号，那么对于这个单单词符号，那么对于这个单 词符号，其词符号，其种别编码种别编码就完全代表了它自身的值。就完全代表了它自身的值。 如果一个如果一个种别种别含有含有多个单词多个单词符号，那么对于它的每个单词符号，除了给出符号，那么对于它的每个单词符号，除了给出 种别编码之外还应给出单词符

11、号种别编码之外还应给出单词符号自身的值自身的值，以便把同一种类的单词区别开来。，以便把同一种类的单词区别开来。 注意，标识符自身的值注意，标识符自身的值就是标识符自身的字符串，而就是标识符自身的字符串，而常数自身的值常数自身的值是常数是常数 本身的二进制数值。本身的二进制数值。 此外，此外，我们也可用我们也可用指向指向某类表格中一个特定项目的指针来区分同类中的不某类表格中一个特定项目的指针来区分同类中的不 同单词。例如，对于同单词。例如，对于标识符标识符，可以用它在符号表的，可以用它在符号表的入口指针入口指针作为它自身的值；作为它自身的值； 而而常数常数也可用它在常数表的也可用它在常数表的入口

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

13、2章词法分析 状态状态(即结点即结点)数是数是有限的有限的，其中，其中必有一必有一初始状态以及初始状态以及若干若干终终 止状态，止状态， 终止状态终止状态(终态终态)的结点用的结点用双圈表示双圈表示以区别于其它状态。以区别于其它状态。 图图23给出了用于识别给出了用于识别标识符标识符、无符号整数无符号整数、无符号数的状、无符号数的状 态转换图，其初始状态均用态转换图，其初始状态均用0状态表示。状态表示。 第2章词法分析 图图23 标识符及无符号数的状态转换图标识符及无符号数的状态转换图 (a) 标识符；标识符；(b) 无符号整数；无符号整数；(c) 无符号数无符号数 第2章词法分析 当到达一类

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

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

16、对应的所对应的 while语句如下：语句如下： getchar (); while (letter()|digit() getchar (); ; /*实现状态实现状态j功能的语句功能的语句*/ 终态终态一般对应一个一般对应一个return()语句。语句。return意味着从词法分意味着从词法分 析器返回到调用段，一般指返回到语法分析器。析器返回到调用段，一般指返回到语法分析器。 第2章词法分析 图24 含有分支或回路的状态示意 (a) 含分支的状态i；(b) 含回路的状态i 第2章词法分析 2.2 一个简单的词法分析器示例一个简单的词法分析器示例 C语言子集的单词符号表示语言子集的单词符号表

17、示 C语言子集对应的状态转换图语言子集对应的状态转换图 状态转换图的实现状态转换图的实现 第2章词法分析 2.2.1 C语言子集的单词符号表示语言子集的单词符号表示 一个非常重要的一个非常重要的事实事实是：大多数程序语言的是：大多数程序语言的单词符号单词符号都可都可 以用状态转换图予以识别。以用状态转换图予以识别。 作为一个作为一个综合例子综合例子，我们来构造一个，我们来构造一个C语言子集的简单词法语言子集的简单词法 分析器。表分析器。表2.1列出了这个列出了这个C语言子集的语言子集的所有所有单词符号以及它们单词符号以及它们 的的种别编码和内码值种别编码和内码值。由于直接使用整数编码不利于记忆

18、，故。由于直接使用整数编码不利于记忆，故 该例中用一些特殊符号来表示种别编码。该例中用一些特殊符号来表示种别编码。 第2章词法分析 表 2.1 C 语言子集的单词符号及内码值 单词符号 种别编码 助记符 内码值 while 1 while if 2 if else 3 else switch 4 switch case 5 case 标识符 6 id id 在符号表中的位置 常数 7 num num 在常数表中的位置 + 8 + ? 9 ? * 10 * = 11 relop LE 11 relop LT = = 11 relop EQ = 12 = ； 13 ； 第2章词法分析 2.2.2

19、C语言子集对应的状态转换图语言子集对应的状态转换图 在设计的状态转换图中，在设计的状态转换图中，首先首先对输入串做对输入串做预处理预处理，即，即剔除剔除多多 余的空白符余的空白符(在实际的词法分析中，预处理还包括剔除注释和制表在实际的词法分析中，预处理还包括剔除注释和制表 换行符等编辑性字符的工作换行符等编辑性字符的工作)，使词法分析工作既，使词法分析工作既简单又清晰简单又清晰。 其次，将其次，将保留字保留字作为一类特殊的标识符来处理，也即对保留作为一类特殊的标识符来处理，也即对保留 字字不专设不专设对应的对应的状态转换图状态转换图，当转换图识别出一个，当转换图识别出一个标识符标识符时就去时就

20、去 查查对表对表2.1的前五项，确定它是否为一个保留字。当然，也可以专的前五项，确定它是否为一个保留字。当然，也可以专 设一个保留字表来进行处理。设一个保留字表来进行处理。 图图25就是对应表就是对应表2.1这个简单词法分析的状态转换图。这个简单词法分析的状态转换图。 第2章词法分析 图25 简单词法分析的状态转换图 第2章词法分析 注意：注意：在状态在状态2时，所识别出的标识符应先与表时，所识别出的标识符应先与表2.1的前五项的前五项 逐一比较，逐一比较，若匹配若匹配，则该标识符是一个，则该标识符是一个保留字保留字，否则就是标识符。，否则就是标识符。 如果是标识符，应先查符号表，看表中是否有

21、此标识符。如果是标识符，应先查符号表，看表中是否有此标识符。 若表中若表中无此无此标识符，则将它登录到符号表中，然后返回其在标识符，则将它登录到符号表中，然后返回其在 符号表中的入口指针（地址）作为该标识符的符号表中的入口指针（地址）作为该标识符的内码值内码值； 在状态在状态4时，应将识别的常数转换成时，应将识别的常数转换成二进制常数二进制常数并将其登录并将其登录 到常数表中，然后返回其在常数表中的入口指针作为该常数的内到常数表中，然后返回其在常数表中的入口指针作为该常数的内 码值。码值。 第2章词法分析 2.2.3 状态转换图的实现状态转换图的实现 状态转换图非常容易用程序实现，状态转换图非

22、常容易用程序实现，最简单的办法是最简单的办法是让每个让每个 状态对应状态对应一小段程序。对于图一小段程序。对于图25所示的状态转换图，我们首先所示的状态转换图，我们首先 引进一组变量和过程如下：引进一组变量和过程如下： (1) character：字符变量，存放：字符变量，存放最新最新读入的源程序字符。读入的源程序字符。 (2) token：字符：字符数组数组，存放构成单词符号的字符串。，存放构成单词符号的字符串。 (3) getbe( )：若：若character中的字符为空白，则调用中的字符为空白，则调用 getchar( )，直至，直至character为为非空白字符非空白字符为止。为止

23、。 (4) concatenation( )：将：将token中的字符串与中的字符串与character中的中的 字符连接并作为字符连接并作为token中新的字符串。中新的字符串。 第2章词法分析 (5) letter( )和和digit( )：判断判断character中的字符是否为字母和中的字符是否为字母和 数字的布尔函数，数字的布尔函数，是是则返回则返回true，否否则返回则返回false。 (6) reserve( )：按：按token数组中的字符串数组中的字符串查表查表2.1中中的的前五项前五项 (即判别其是否为保留字即判别其是否为保留字)，若是若是保留字则返回它的编码，保留字则返回

24、它的编码，否则否则返返 回回0值。值。 (7) retract( )：扫描指针扫描指针回退一个字符，将回退一个字符，将character置为空白。置为空白。 (8) buildlist( )：将：将标识符标识符登录到符号表中或将常数登录到常登录到符号表中或将常数登录到常 数表中。数表中。 (9) error( )：出现非法字符，显示出错信息。：出现非法字符，显示出错信息。 第2章词法分析 相对于图相对于图25的的词法分析器构造词法分析器构造如下：如下： token= ; /*对对token数组初始化数组初始化*/ s=getchar ( ); getbe ( ); /*滤除空格滤除空格*/ s

25、witch (s) case a: case b: case z: 第2章词法分析 while (letter ( )digit ( ) concatenation ( ); /*将当前读入的字符送入将当前读入的字符送入token数组数组*/ getchar ( ); /*实现状态实现状态2功能的语句功能的语句*/ retract ( ); /*扫描指针回退一个字符扫描指针回退一个字符*/ c=reserve ( ); 第2章词法分析 if (c=0) buildlist ( ); /*将标识符登录到符号表中将标识符登录到符号表中*/ return (id，指向，指向id的符号表入口指针的符号

26、表入口指针); else return (保留字码，保留字码，null); break; 第2章词法分析 case 0: case 1: case 9: while (digit ( ) concatenation ( ); getchar ( ); /*实现状态实现状态4功能的语句功能的语句*/ retract ( ); /*将常数登录到常数表中将常数登录到常数表中*/ buildlist ( ); return (num，num的常数表入口指针的常数表入口指针); break; 第2章词法分析 case +: /*实现状态实现状态5功能的语句功能的语句*/ return (+，null);

27、 break; case : /*实现状态实现状态6功能的语句功能的语句*/ return (，null); break; case *: /*实现状态实现状态7功能的语句功能的语句*/ return (*，null); break; 第2章词法分析 case : getchar ( ); if (character= =) /*实现状态实现状态9功能的语句功能的语句*/ return (relop,LE); else /*实现状态实现状态10功能的语句功能的语句*/ retract ( ); return (relop，LT); break; 第2章词法分析 case =: getchar

28、( ); if (character= =) /*实现状态实现状态12功能的语句功能的语句*/ return (relop, EQ); else /*实现状态实现状态13功能的语句功能的语句*/ retract ( ); return (=, null); break; 第2章词法分析 case ;: /*实现状态实现状态14功能的语句功能的语句*/ return (;, null); break; default: /*实现状态实现状态15功能的语句功能的语句*/ error ( ); 第2章词法分析 2.3 正规表达式与有限自动机简介正规表达式与有限自动机简介 正规表达式与正规集正规表达式

29、与正规集 有限自动机有限自动机 状态转换图与状态转换矩阵状态转换图与状态转换矩阵 第2章词法分析 2.3.1 正规表达式与正规集正规表达式与正规集 状态转换图状态转换图对构造词法分析程序是行之有效的，为了便于对构造词法分析程序是行之有效的，为了便于 词法分析器的词法分析器的自动生成自动生成，还须将状态转换图的概念加以，还须将状态转换图的概念加以形式化形式化。 正规表达式正规表达式就是一种就是一种形式化形式化的表示法，它可以表示单词符的表示法，它可以表示单词符 号的结构，从而号的结构，从而精确地精确地定义单词符号集。定义单词符号集。 正规表达式正规表达式简称为简称为正规式正规式，它表示的，它表示

30、的集合集合即为即为正规集正规集。 第2章词法分析 程序语言中使用的程序语言中使用的标识符标识符是一个以字母开头的字母数字串，是一个以字母开头的字母数字串， 如果如果字母字母用用letter表示，表示，数字数字用用digit表示，则表示，则标识符标识符可表示为可表示为 letter (letter digit)* 其中，其中，letter与与 (letter digit)*的并置表示两者的连接；括号的并置表示两者的连接；括号 中的中的“ ”表示表示letter或或digit两者选一；两者选一； “*”表示零次或多次引用由表示零次或多次引用由“*”标记的表达式；标记的表达式； (letter di

31、git)*是是letter digit的零次或多次并置，即表示一长度的零次或多次并置，即表示一长度 为为0、1、2、的字母数字串；的字母数字串； letter (letter digit)*表示以表示以字母开头字母开头的字母数字串，也即的字母数字串，也即标标 识符集识符集。 letter (letter digit)*就是表示标识符的就是表示标识符的正规式正规式，而，而标识符集标识符集 就是这个正规式所表示的就是这个正规式所表示的正规集正规集。 第2章词法分析 对于给定的对于给定的字母表字母表，正规式和正规集的，正规式和正规集的递归定义递归定义如下：如下： (1) 和和都是都是上的正规式，它们

32、所表示的正规集分别为上的正规式，它们所表示的正规集分别为 和和。 (2) 对任一个对任一个a，a是是上的一个正规式，它所表示的正规上的一个正规式，它所表示的正规 集为集为a。 (3) 如果如果R和和S是是上的正规式，它们所表示的正规集分别为上的正规式，它们所表示的正规集分别为 L(R)和和L(S)，则：，则： R S是是上的正规式，它所表示的正规集为上的正规式，它所表示的正规集为L(R)L(S)； RS是是上的正规式，它所表示的正规集为上的正规式，它所表示的正规集为L(R)L(S)； (R)*是是上的正规式，它所表示的正规集为上的正规式，它所表示的正规集为(L(R)*。 第2章词法分析 (4)

33、 仅由仅由有限次有限次使用规则使用规则(1)(3)得到的表示式是得到的表示式是上的正规上的正规 式，它所表示的集合是式，它所表示的集合是上的正规集。上的正规集。 在上述定义中，规则在上述定义中，规则(1)、(2)为为基础规则基础规则，规则，规则(3)为归纳规为归纳规 则，规则则，规则(4)是界限规则或终止规则。是界限规则或终止规则。 上的一个上的一个字字是指由是指由中的字符所构成的一个有穷序列；中的字符所构成的一个有穷序列； 不包含任何字符的序列称为空字，用不包含任何字符的序列称为空字，用表示。表示。 我们用我们用*表示表示上所有字的全体，则空字上所有字的全体，则空字也在其中。例如，也在其中。

34、例如， 若若=a，b，则，则*=，a，b，aa，ab，ba，bb，aaa，。 我们还用我们还用表示不含任何元素的空集表示不含任何元素的空集。这里需要注意。这里需要注意、和和的区别：的区别： 是由空字组成的集合，而是由空字组成的集合，而则表示不含任何字的集合。则表示不含任何字的集合。 第2章词法分析 正规式间正规式间的运算符的运算符“ ”表示或，表示或，“ ”表示连接（通常可表示连接（通常可 省略），省略），“*”表示闭包，使用括号可以改变运算的次序。表示闭包，使用括号可以改变运算的次序。 如果规定如果规定“*”优先于优先于“ ”，“ ”优先于优先于“ ”，则在不出，则在不出 现混淆的情况下括号

35、也可以省去。现混淆的情况下括号也可以省去。 *的子集的子集R和和S的连接可以的连接可以形式化地定义形式化地定义为为: RS= R else return (keyword (id) 17 digit (digit)* val=int (id)； return (17, null)； return (val) 18(letter digit ( ) + * / = ；)* return (18，null)； inslit (id)； return (pointer，lenth) 第2章词法分析 该LEX源程序中用户子程序为空；其中识别规则A18语句 中调用过程“inslit (id)”是指将字符串常量id存放到字符表中， “po