编译原理第三章词法分析

1、 词法分析的词法分析的任务任务： 从左至右逐个字符地扫描源程序，产生从左至右逐个字符地扫描源程序，产生一个个的一个个的单词符号单词符号，把作为字符串的源程序，把作为字符串的源程序改造成为单词符号串的改造成为单词符号串的中间程序中间程序。 词法分析器词法分析器/ /扫描器扫描器：执行词法分析的程序。执行词法分析的程序。源程序扫描器scanner1 1、关键字、关键字词法分析器的词法分析器的功能功能如下图所示：如下图所示：2 2、标识符、标识符5 5、界符、界符4 4、运算符、运算符3 3、常数、常数由程序语言定义的具有固定意义的标识符。也可称为保留字或基本字。例如：Pascal中的begin，e

2、nd，if等。界符：如逗号、分号、括号、/*，*/ 等。它是确定的。运算符：如+、-、*、/ 等。它是确定的。常数的类型一般有整型、实型、布尔型、文字型等。它是不限的。用来表示各种名字，如变量名、数组名、过程名等。它是不限的。词法分析器的词法分析器的功能功能：输入源程序，输出单词符号。：输入源程序，输出单词符号。单词符号单词符号：一个程序语言的基本语法符号。分为以下：一个程序语言的基本语法符号。分为以下5 5种。种。 1 1、关键字关键字：由程序语言定义的具有固定意义的标识符。也：由程序语言定义的具有固定意义的标识符。也可称为保留字或基本字。例如：可称为保留字或基本字。例如：PascalPas

3、cal中的中的beginbegin，endend，ifif等。它是等。它是确定确定的。的。 2 2、标识符标识符：用来表示各种名字，如变量名、数组名、过程：用来表示各种名字，如变量名、数组名、过程名等。它是名等。它是不限不限的。的。 3 3、常数常数：常数的类型一般有整型、实型、布尔型、文字型：常数的类型一般有整型、实型、布尔型、文字型等。它是等。它是不限不限的。的。 4 4、运算符运算符：如：如+ +、- -、* *、/ / 等。它是等。它是确定确定的。的。 5 5、界符界符：如逗号、分号、括号、：如逗号、分号、括号、/ /* *，* */ / 等。它是等。它是确定确定的。的。确定确定不限不

4、限单词符号的表示形式单词符号的表示形式：词法分析器所输出的单词符号常常表示成：词法分析器所输出的单词符号常常表示成 二元式（单词种别，单词自身的值）二元式（单词种别，单词自身的值）。 单词种别单词种别可以用以下形式表示：可以用以下形式表示： 1 1、一类单词统一用一个整数值代表其属性。例如：、一类单词统一用一个整数值代表其属性。例如：1 1代表关键字，代表关键字，2 2代表标识符等。代表标识符等。 2 2、每一个单词一个类别。例如：、每一个单词一个类别。例如：1 1代表代表BEGINBEGIN，2 2代表代表ENDEND等。等。单词自身的值单词自身的值可以表示成：常量的二进制表示；常量、变量等

5、在符号表可以表示成：常量的二进制表示；常量、变量等在符号表种的地址码，等等。种的地址码，等等。注意：注意：一个语言的单词符号如何分种，分几种，怎样编码，是一个技术一个语言的单词符号如何分种，分几种，怎样编码，是一个技术问题。标识符一般同归为一种。常数则宜按类型（整、实、布尔）分。问题。标识符一般同归为一种。常数则宜按类型（整、实、布尔）分。关键字可以将其全体视为一种，也可关键字可以将其全体视为一种，也可一字一种一字一种。运算符可采用一符一种，运算符可采用一符一种，但也可把具有一定共性的视为一种。界符则一般采用但也可把具有一定共性的视为一种。界符则一般采用一符一种一符一种。如何进。如何进行分种主

6、要取决于处理上的方便。行分种主要取决于处理上的方便。 若是一符一种分种，单词自身值就不需要了。否则，要查符号表。若是一符一种分种，单词自身值就不需要了。否则，要查符号表。例：例：151151FORTRANFORTRAN编译程序的词法分析器在扫描输入串编译程序的词法分析器在扫描输入串 IF (5EQIF (5EQM) GOTO 100M) GOTO 100 后，它输出的后，它输出的单词符号串单词符号串是：是： 逻辑逻辑IF IF （3434，_ _） 左括号左括号 （2 2，_ _） 整常数整常数 （2020，55的二进制表示）的二进制表示） 等号等号 （6 6，_ _） 标识符标识符 （262

7、6，MM） 右括号右括号 （1616，_ _） GOTO GOTO （3030，_ _） 标号标号 （1919，100100的二进制表示）的二进制表示）IFIF为关键字，种别编码为关键字，种别编码3434，采用一符一种的编码方式。采用一符一种的编码方式。常数类型，种别编码常数类型，种别编码2020，单词自，单词自身的值为身的值为55的二进制表示。的二进制表示。(为界符，种别编码为界符，种别编码2 2，采，采用一符一种的编码方式。用一符一种的编码方式。等号为运算符，种别编码等号为运算符，种别编码6 6，采用一符一种的编码方式。采用一符一种的编码方式。M M为标识符，种别编码为标识符，种别编码26

8、26，单，单词自身值为词自身值为MM。)为界符，种别编码为界符，种别编码1616，采用一符一种的编码方式。采用一符一种的编码方式。GOTOGOTO为关键字，种别编码为关键字，种别编码3030，采用一符一种的编码方式。采用一符一种的编码方式。100100为标号，种别编码为标号，种别编码1919，单词，单词内部的值用内部的值用100100的二进制表示。的二进制表示。例：下述例：下述C+C+代码段：代码段：while ( i = j ) i - -while ( i = j ) i - -； 经词法分析器处理以后，它将被转换为如下的经词法分析器处理以后，它将被转换为如下的单词符号串单词符号串 ( w

9、hile ( while ，_ )_ )( ( ( ( ，_ )_ )( id ( id ，指向，指向i i的符号表指针的符号表指针 ) )( = ( = ，_ )_ )( id ( id ，指向，指向j j的符号表指针的符号表指针 ) )( ) ( ) ，_ )_ )( id ( id ，指向，指向i i的符号表指针的符号表指针 ) )( - - ( - - ，_ _ ) )( ( ； ，_ )_ )1 1、把词法分析从语法分析中脱离出来的、把词法分析从语法分析中脱离出来的优点优点：使编译程序的使编译程序的结构结构更加简洁、清晰和条理化。更加简洁、清晰和条理化。词法分析和语法分析词法分析和语

10、法分析方法方法不同，词法分析可以使用正则文法自动构造不同，词法分析可以使用正则文法自动构造scannerscanner简单。简单。有利于提高语法分析的有利于提高语法分析的效率效率。可以改善词法分析的细节，甚至于一个语法分析配几个可以改善词法分析的细节，甚至于一个语法分析配几个scannerscanner，把不同，把不同的输入变成一种内部表示。的输入变成一种内部表示。2 2、把词法分析作为独立的一、把词法分析作为独立的一遍遍scannerscanner当作一遍。当作一遍。把把scannerscanner当作子程序。当作子程序。 外存外存scannerscanner语法分析语法分析源程序单词符号s

11、cannerscanner作为一遍作为一遍语法语法分析分析scannerscanner源程序源程序scannerscanner作为子程序作为子程序设计前提设计前提： 把把scannerscanner作为一个独立的子程序；作为一个独立的子程序； 词法分析器的任务为输出单词符号。词法分析器的任务为输出单词符号。必要性必要性：编辑性字符如空白符、回车符等，除了出现在文字和编辑性字符如空白符、回车符等，除了出现在文字和 常数中以外，在别处出现都没有意义。常数中以外，在别处出现都没有意义。功功 能能： 剔除无用字符。剔除无用字符。实实 现现： 预处理子程序。预处理子程序。输入列表预处理预处理子程序子程序

12、扫描器扫描器扫描缓冲区扫描缓冲区输入缓冲区输入缓冲区单词符号图图2.1 2.1 词法分析器词法分析器语法分析器语法分析器预预处处理理部部分分扫扫描描器器若若识别识别输入语句输入语句 IF (5.EQ.M) GOTO 100，若缓冲区情况如下所示：，若缓冲区情况如下所示： IF (5.EQ.M) GO 起点指示器起点指示器 搜索指示器搜索指示器输入缓冲区输入缓冲区 TO 100 IF (5.EQ.M) GO 起点指示器起点指示器 搜索指示器搜索指示器输入缓冲区输入缓冲区TO 100 IF (5.EQ.M) GO 起点指示器起点指示器搜索指示器搜索指示器两两 个个 互互 补补 输输 入入 缓缓 冲

13、冲 区区120个字符个字符扫描缓冲区的扫描缓冲区的结构结构： 缓冲区大小缓冲区大小：120120个字符。个字符。 采用两个采用两个指示器指示器：起点指示器、搜索指示器。：起点指示器、搜索指示器。 两个互补区两个互补区。单词符号识别的简单方法：单词符号识别的简单方法：超前搜索。关键字识别关键字识别： 例如：在标准例如：在标准FORTRANFORTRAN中中 1 1、DO99KDO99K = 1,10 = 1,10 2 2、IFIF(5.EQ.M)I = 10(5.EQ.M)I = 10 3 3、DO99KDO99K = 1.10 = 1.10 4 4、IFIF(5) = 55(5) = 55 其

14、中的其中的DODO、IFIF为关键字为关键字其中的其中的DODO、IFIF为标识符为标识符的一部分的一部分标识符的识别标识符的识别 多数语言的标识符是字母开头的多数语言的标识符是字母开头的“字母字母/ /数字数字”串，串，而且在程序中标识符的出现后都跟着算符或界符。因此，而且在程序中标识符的出现后都跟着算符或界符。因此，不难识别。不难识别。常数的识别常数的识别 对于某些语言的常数的识别也需要使用超前搜索。对于某些语言的常数的识别也需要使用超前搜索。算符和界符的识别算符和界符的识别 对于诸如对于诸如C+C+语言中的语言中的“+ +”+ +”、“- -”- -”，这种复，这种复合成的算符，需要超前

15、搜索。合成的算符，需要超前搜索。 转换图转换图：是一张有限方向图。在状态转换图中，：是一张有限方向图。在状态转换图中，结点结点代表代表 状态状态，用圆圈表示。状态之间用，用圆圈表示。状态之间用箭弧箭弧连接。箭弧上连接。箭弧上的的标记（字符）标记（字符）代表在射出结状态下可能出现的输代表在射出结状态下可能出现的输入字符或字符类。入字符或字符类。状态转换图的功能状态转换图的功能: :用于识别一定的字符串。用于识别一定的字符串。初态初态：一张转换图的启动条件，至少有一个：一张转换图的启动条件，至少有一个, ,用圆圈表示。用圆圈表示。终态终态：一张转换图的结束条件，至少有一个，用双圈表示。：一张转换图

16、的结束条件，至少有一个，用双圈表示。* * ：表示多读进了一个字符。：表示多读进了一个字符。XY(a)(a)转换图示例转换图示例字母字母其他其他字母或数字字母或数字*（b b）识别标识符的转换图）识别标识符的转换图其他其他数字数字数字数字*（c c）识别整数的转换图）识别整数的转换图例：简单的状态转换图示例：例：简单的状态转换图示例：初态初态终态终态从从0 0状态到状态到1 1状态状态可能出现字母可能出现字母图图2.2 2.2 状态转换图状态转换图*数字数字数字数字数字数字数字数字E E 或或 D D+ +或或数字数字其他其他E E 或或 D D数字数字其他其他数字数字例：识别例：识别FORT

17、RANFORTRAN实型常数实型常数的转换图：的转换图：例如下列实型常数可以例如下列实型常数可以被以下转换图识别：被以下转换图识别： 1.23E+41.23E+4 .56E-7 .56E-7一般，我们可以让每一般，我们可以让每一个状态结一个状态结对应对应一个程序段一个程序段。 例如：我们可以让不含回路的分叉结，对应一个例如：我们可以让不含回路的分叉结，对应一个CASE CASE 语句，或者是一组语句，或者是一组IFTHENELSEIFTHENELSE语句。具体见后面实例。语句。具体见后面实例。 终态结终态结一般对应一个一般对应一个RETURN(C,VAL)RETURN(C,VAL)语句。其中语

18、句。其中C C为单词为单词种别编码；种别编码；VALVAL是字符数组的是字符数组的TOKEN TOKEN ，或者是一个整数值，或者是一个整数值，或者无定义。具体见后面实例。或者无定义。具体见后面实例。例例2 26 6：以下：以下CASECASE语句段对应的状态图语句段对应的状态图: :state istate i： GETCHARGETCHAR； CASE CASE CHARCHAR OF OF A.Z A.Z： state j state j ； 0.90.9： state k state k ； / / ： state l state l ； ENDEND； FAILFAIL数字数字字母字

19、母 / /字符变量，存放最新字符变量，存放最新读进的源程序字符。读进的源程序字符。过程，将下一输入字过程，将下一输入字符读入符读入CHARCHAR，搜索指，搜索指示器前移一个字符。示器前移一个字符。 为了把为了把状态转换图状态转换图转化成转化成程序程序，每个，每个状态状态要建立一段要建立一段程序程序，它要做的工作如下：，它要做的工作如下：第一步第一步：从输入缓冲区中取一个字符。为此，我们使用函：从输入缓冲区中取一个字符。为此，我们使用函数数GETCHARGETCHAR，每次调用它，推进先行指针，送回一，每次调用它，推进先行指针，送回一个字符。个字符。第二步第二步：确定在本状态下，哪一条箭弧是用

20、刚刚来的输入：确定在本状态下，哪一条箭弧是用刚刚来的输入字符标识的。如果找到，控制就转到该弧所指向字符标识的。如果找到，控制就转到该弧所指向的状态；若找不到，那么寻找该单词的企图就失的状态；若找不到，那么寻找该单词的企图就失败了。败了。失失 败败：先行指针必须：先行指针必须重新回到重新回到开始指针处，并用另一状开始指针处，并用另一状态图来搜索态图来搜索另一另一单词。如果所有的状态转换图都单词。如果所有的状态转换图都试过之后，还没有匹配的，就表明这是一个词法试过之后，还没有匹配的，就表明这是一个词法错误，此时，调用错误校正程序。错误，此时，调用错误校正程序。GETCHAR是过程，是过程，将下一输

21、入字符读入将下一输入字符读入CHAR，搜索指示器，搜索指示器前移一个字符。前移一个字符。对于如上的状态转换图，对于如上的状态转换图，状态状态0 0的代码如下所示：的代码如下所示： state 0state 0： C := C := GETCHAR GETCHAR ; ; if if LETTER(C)LETTER(C) then goto state 1 then goto state 1 else else FAIL( )FAIL( )字母字母其他其他字母或数字字母或数字LETTER( )是布尔是布尔函数过程，当且仅函数过程，当且仅当当C中的字符是字中的字符是字母，它返回真假值母，它返回真假

22、值TRUE。FAIL( )是例子程序，是例子程序，它移回它移回先行指针先行指针（lookahead pointer）, 开始下一开始下一状态转换图，或调用状态转换图，或调用出错程序。出错程序。例例2-72-7：示例：示例如何把如何把状态结状态结对应于一段对应于一段程序程序：*对于如上的状态转换图，对于如上的状态转换图，状态状态1 1的代码如下所示：的代码如下所示： state 1state 1： C := C := GETCHAR GETCHAR ; ; if if LETTER( C)LETTER( C) or or DIGIT(C)DIGIT(C) then goto state then

23、 goto state 1 1 else if else if DELIMITER(C)DELIMITER(C) then goto state 2 else else FAIL( )FAIL( )字母字母其他其他字母或数字字母或数字DIGIT( )是布尔函是布尔函数过程，当且仅当数过程，当且仅当C中的字符是数字，中的字符是数字，它返回真假值它返回真假值TRUE。DELIMITER(C)是过程，是过程，只要碰到标识符后的分只要碰到标识符后的分界符，它返回界符，它返回TRUE。分界符分界符一般为：空格、一般为：空格、算术、逻辑符号，括号、算术、逻辑符号，括号、；、. 、，。*对于如上的状态转换图，终态对于如上的状态转换图，终态状态状态2 2的代码如下所示：的代码如下所示： state 2state 2： RETRACT( )RETRACT( ) ; ; RETURN($id RETURN($id ，INSTALL( ) )INSTALL( ) )字母字母其他其他字母或数字字母或数字RETRACT( )是过程，是过程，由于分界符不属于由于分界符不属于标识符，所以我们标识符，所以我们要把先行指针要把先行指针回调回调一个字符。一个字符。INSTALL( )是过程，是