编译原理-西安交通大学(冯博琴)2_词法分析_30

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

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

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

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

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

11、析语法分析源程序单词符号scannerscanner作为一遍作为一遍语法语法分析分析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) =

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

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

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

17、其他数字数字例例2-42-4：识别：识别FORTRANFORTRAN实型常数实型常数的转换图：的转换图：例如下列实型常数可以例如下列实型常数可以被以下转换图识别：被以下转换图识别： 1.23E+41.23E+4 .56E-7 .56E-7例例2-52-5：综合实例：综合实例做出识别下表所示的小语言的做出识别下表所示的小语言的单词符号单词符号的状态转换图的状态转换图*字母字母非字母与数字非字母与数字字母或数字字母或数字*空白空白数字数字数字数字非数字非数字*非*，（）其他其他。右图即为对上页所示右图即为对上页所示的简单语言进行的简单语言进行词法词法分析分析的状态转换图。的状态转换图。1、CHAR

18、CHAR 字符变量，存放最新读进的源程序字符。字符变量，存放最新读进的源程序字符。2 2、TOKENTOKEN 字符数组，存放构成单词的字符串。字符数组，存放构成单词的字符串。3 3、GETCHARGETCHAR 过程，将下一输入字符读入过程，将下一输入字符读入CHARCHAR，搜索指示器前移一个字符。，搜索指示器前移一个字符。4 4、GETBCGETBC 过程，检查过程，检查CHARCHAR中的字符是否为空白。若是，则调用中的字符是否为空白。若是，则调用GETCHARGETCHAR 直至直至CHARCHAR中进入一个非空白字符。中进入一个非空白字符。5 5、CONCAT CONCAT 过程，

19、把过程，把CHARCHAR中的字符连接到中的字符连接到TOKENTOKEN之后。之后。6 6、LETTERLETTER 布尔函数过程，它们分别判断布尔函数过程，它们分别判断CHARCHAR中的字符是数字或是字母，中的字符是数字或是字母， DIGITDIGIT 从而给出真假值从而给出真假值TRUETRUE、FALSEFALSE。7 7、RESERVERESERVE 整型函数过程，用整型函数过程，用TOKENTOKEN中的字符串查保留字表，若是一个保留中的字符串查保留字表，若是一个保留 字则给予编码，否则回送字则给予编码，否则回送0 0值（假定值（假定0 0不是保留字的编码）。不是保留字的编码）。

20、8 8、RETRACTRETRACT 过程，把搜索指示器回调一个字节，把过程，把搜索指示器回调一个字节，把CHARCHAR中的字符置为空白。中的字符置为空白。 以上函数和子程序过程都不难编制，使用它们能够方便以上函数和子程序过程都不难编制，使用它们能够方便的构造状态转换图的对应程序。一般，我们可以让每的构造状态转换图的对应程序。一般，我们可以让每一个状一个状态结态结对应对应一个程序段一个程序段。 例如：我们可以让不含回路的分叉结，对应一个例如：我们可以让不含回路的分叉结，对应一个CASE CASE 语句，或者是一组语句，或者是一组IFTHENELSEIFTHENELSE语句。具体见后面实例。语

21、句。具体见后面实例。 终态结终态结一般对应一个一般对应一个RETURN(C,VAL)RETURN(C,VAL)语句。其中语句。其中C C为单词为单词种别编码；种别编码；VALVAL是字符数组的是字符数组的TOKEN TOKEN ，或者是一个整数值，或者是一个整数值，或者无定义。具体见后面实例。或者无定义。具体见后面实例。 为了把为了把状态转换图状态转换图转化成转化成程序程序，每个，每个状态状态要建立一段要建立一段程序程序，它要做的工作如下：，它要做的工作如下：第一步第一步：从输入缓冲区中取一个字符。为此，我们使用函：从输入缓冲区中取一个字符。为此，我们使用函数数GETCHARGETCHAR，每

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

23、匹配的，就表明这是一个词法错误，此时，调用错误校正程序。错误，此时，调用错误校正程序。GETCHAR是过程，是过程，将下一输入字符读入将下一输入字符读入CHAR，搜索指示器，搜索指示器前移一个字符。前移一个字符。例例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数

24、字数字字母字母 / /字符变量，存放最新字符变量，存放最新读进的源程序字符。读进的源程序字符。过程，将下一输入字过程，将下一输入字符读入符读入CHARCHAR，搜索指，搜索指示器前移一个字符。示器前移一个字符。对于如上的状态转换图，对于如上的状态转换图，状态状态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( )字母字母其他其他字母或数字字母或数字

25、LETTER( )是布尔是布尔函数过程，当且仅函数过程，当且仅当当C中的字符是字中的字符是字母，它返回真假值母，它返回真假值TRUE。FAIL( )是例子程序，是例子程序，它移回它移回先行指针先行指针（lookahead pointer）, 开始下一开始下一状态转换图，或调用状态转换图，或调用出错程序。出错程序。例例2-72-7：示例：示例如何把如何把状态结状态结对应于一段对应于一段程序程序：*对于如上的状态转换图，对于如上的状态转换图，状态状态1 1的代码如下所示：的代码如下所示： state 1state 1： C := C := GETCHAR GETCHAR ; ; if if LET

26、TER( C)LETTER( C) or or DIGIT(C)DIGIT(C) then goto state then 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

27、。分界符分界符一般为：空格、一般为：空格、算术、逻辑符号，括号、算术、逻辑符号，括号、；、. 、，。*对于如上的状态转换图，终态对于如上的状态转换图，终态状态状态2 2的代码如下所示：的代码如下所示： state 2state 2： RETRACT( )RETRACT( ) ; ; RETURN($id RETURN($id ，INSTALL( ) )INSTALL( ) )字母字母其他其他字母或数字字母或数字RETRACT( )是过程，是过程，由于分界符不属于由于分界符不属于标识符，所以我们标识符，所以我们要把先行指针要把先行指针回调回调一个字符。一个字符。INSTALL( )是过程，是过程

28、，如我们识别出的标如我们识别出的标识符不在符号表中，识符不在符号表中，我们把它装入我们把它装入符号符号表表。我们还要给语。我们还要给语法分析程序返回一法分析程序返回一个个二元式二元式。*如果同时识别如果同时识别标识符标识符和和定义符定义符，则需要则需要修改修改为为State2：修改之后，修改之后，状态状态2 2的代码如下所示：的代码如下所示： state 2state 2： RETRACT( )RETRACT( ) ; ; c := c := RESERVE( );RESERVE( ); if c = 0 if c = 0 then then RETURN($id ，INSTALL ) els

29、e else RETURN(C , _ )RETURN(C , _ )RESERVE( ) 整型函数整型函数过程过程,针对针对TOKEN中的中的字符串进行查找，看其字符串进行查找，看其是否是是否是保留字保留字，是保留，是保留字给出它的编码，否则字给出它的编码，否则回送回送0（假定（假定0不是保留不是保留字编码）。字编码）。例例2 28 8：以下程序段对应的状态图：以下程序段对应的状态图 state istate i：GETCHARGETCHAR； WHILE WHILE LETTERLETTER OR OR DIGITDIGIT DO DO GETCHARGETCHAR； state jsta

30、te j： 布尔函数过程，它们分别布尔函数过程，它们分别判断判断CHARCHAR中的字符是数字中的字符是数字或是字母，从而给出真假或是字母，从而给出真假值值TRUETRUE、FALSEFALSE。其它其它字母或数字字母或数字例例2 29 9：以下程序段对应的状态图：以下程序段对应的状态图0 90 9：BEGINBEGIN WHILE WHILE DIGITDIGIT DO DO BEGIN BEGIN CONCATCONCAT；GETCHARGETCHAR END END； RETRACTRETRACT； RETURN($INT,DTB)RETURN($INT,DTB) ； ENDEND；非数

31、字非数字数字数字数字数字*RETURN RETURN 语句，对应终态语句，对应终态结，其中结，其中$INT为种别编为种别编码，码，DTB为一个把十进制为一个把十进制转换到二进制的转换函数。转换到二进制的转换函数。它把它把TOKENTOKEN中的数字译成中的数字译成标准二进制码标准二进制码，并以此为，并以此为函数值返回。函数值返回。正规式与正规集的递归定义：正规式与正规集的递归定义：1 1、和和都是都是字母表字母表上的正规式，它们所表示的正规集分别为上的正规式，它们所表示的正规集分别为 和和；2 2、任何、任何aa，a a是是上的一个上的一个正规式正规式，它所表示的，它所表示的正规集正规集为为a

32、a；3 3、 正规式正规式 正规集正规集 正规式正规式 正规集正规集 U L(U) U L(U) （U U | | V V） L(U)L(U)L(V)L(V) V L(V) V L(V) （U UV V） L(U)L(V)L(U)L(V) (U) (U)* * L(U)L(U)* *（闭包）（闭包） 仅由有限次使用上述三步骤而得到的表达式才是仅由有限次使用上述三步骤而得到的表达式才是上的上的正规式正规式。仅由这。仅由这 些正规式所表示的子集才是些正规式所表示的子集才是上的上的正规集正规集。运算符的优先顺序：运算符的优先顺序：先先“* *”，次，次“” ，最后最后“|”|”“| |”读读做做“或

33、或”“”读做读做“连接连接”“* *”读做读做“闭包闭包”* 的子集的子集 U , V： 积积 UV =| U U & V V n次积次积 V n= VVV V V0 = V的闭包的闭包 V* = V0 U V1 U V2 U V的正则闭包的正则闭包 V+ = V V* 例例2-112-11：令：令aa，bb，下面是，下面是上的上的正规式正规式和相应的和相应的正规集正规集： 正规式正规式 正规集正规集 baba* * 上所有的以上所有的以b b为首，并且后跟任为首，并且后跟任 意多个意多个a a的字，的字，b, ba,baa,baaa,b, ba,baa,baaa, a(a|b)a(a

34、|b)* * 上所有的以上所有的以a a为首的字为首的字 (a|b)(a|b)* * (aa|bb) (a|b) (aa|bb) (a|b)* * 上所有含有两个连续的上所有含有两个连续的a a或者或者b b的字的字例例2-102-10：令：令AA，B B，0 0，11，则：，则： 正规式正规式 正规集正规集 (A|B)(A|B|0|1)(A|B)(A|B|0|1)* * 上上“标识符标识符”的全的全体体 (0|1)(0|1)(0|1)(0|1)* * 上上“数数”的全体的全体若两个正规式表若两个正规式表示相同的正规集，示相同的正规集，则认为二者则认为二者等价等价，记为记为U=VU=V。例如：

35、。例如：b(ab)b(ab)* *=(ba)=(ba)* *b b(a|b)(a|b)* *=(a=(a* *b b* *) )* *令令U U、V V和和W W均为均为正规式正规式，显而易见，下列，显而易见，下列关系关系普遍成立：普遍成立： 1 1、U|V = V|UU|V = V|U（交换律）；（交换律）； 2 2、U|(V|W) = (U|V)|WU|(V|W) = (U|V)|W（结合律）；（结合律）； 3 3、U(VW) = (UV)WU(VW) = (UV)W（结合律）；（结合律）； 4 4、U(V|W) = UV|UWU(V|W) = UV|UW（分配律）（分配律） (V|W)U

36、 = VU|WU(V|W)U = VU|WU； 5 5、U = UU = U = U = U。 一个一个确定有限自动机（确定有限自动机（DFADFA） M M是一个五元式：是一个五元式： M M (S,(S,s,s0 0 ,F) ,F) ，其中，其中 1 1、S S是一个有限集，它的每个元素称为一个是一个有限集，它的每个元素称为一个状态状态 2 2、是一个有穷是一个有穷字母表字母表，它的每个元素称为一个，它的每个元素称为一个输入字符输入字符 3 3、是一个从是一个从S S至至S S的单值部分映射。的单值部分映射。 (s,a)=s(s,a)=s 意味着：当现行意味着：当现行状态为状态为S S、输

37、入字符为、输入字符为a a时，将转换到下一状态时，将转换到下一状态s s 。我们称。我们称s s 为为s s的的一个后继状态。一个后继状态。 4 4、 s s0 0SS是唯一的是唯一的初态初态 5 5、 F SF S是一个是一个终态集终态集（可空）。（可空）。 显然，一个显然，一个DFADFA可用一个矩阵表示，该矩阵的行表示状态，可用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示列表示输入字符，矩阵元素表示(s,a)的值。这个矩阵称为的值。这个矩阵称为状态转换矩阵状态转换矩阵。例例2-122-12：有：有DFADFA M = (0,1,2,3,a,b,M = (0,1,2,3,

38、a,b,0,3),0,3)其中其中为为: : (0,a)=1 (0,b)=2 (1,a)=3 (1,b)=2 (2,a)=1 (2,b)=3 (3,a)=3 (3,b)=3 相应的状态转换矩阵如下表：相应的状态转换矩阵如下表： 一个一个DFADFA也可用一张（确定的）也可用一张（确定的）状态转换图状态转换图来表示。假定来表示。假定DFA MDFA M含有含有m m个状态和个状态和n n个个输入字符输入字符，那么，这个状态转换图含有，那么，这个状态转换图含有m m个个状态结点状态结点，每个结点顶多有，每个结点顶多有n n条箭弧射出和别的结点相连接，条箭弧射出和别的结点相连接，整张图含有一个整张图

39、含有一个初态结点初态结点和若干个（可以为和若干个（可以为0 0）终态结点终态结点。图图2.5 2.5 状态转换图状态转换图a aa aa aa ab bb bb b如下表所示的状态转换矩阵如下表所示的状态转换矩阵对应的状态转换图如右图：对应的状态转换图如右图：a aa aa ab bb bb b上图所示的状态转换图的上图所示的状态转换图的S S、及及* *如下：如下： S = 0,1,2,3S = 0,1,2,3 = a,b = a,b * *= | = | 为为，或者，或者为为a、b的任意组合的任意组合 从初态从初态0 0到终态到终态3 3有如有如图所示的通路，箭弧图所示的通路，箭弧上到标记

40、符连接起来上到标记符连接起来的字的字aaaa属于属于* *，所，所以右图所示的以右图所示的DFADFA可可以识别字以识别字aaaa。同理：从初态同理：从初态0 0到终到终态态3 3还有如图所示的还有如图所示的通路，箭弧上到标记通路，箭弧上到标记符连接起来的字符连接起来的字bbabba属于属于* *，所以右图，所以右图所示的所示的DFADFA可以识别可以识别字字bbabba。a a例例2-132-13：科学表示法中数字常量的：科学表示法中数字常量的正则表达式正则表达式对应的对应的DFADFA： digitdigitdigitdigitnatnat对应的对应的DFADFA如下图如下图 digit

41、= 0-9 digit = 0-9 nat = digit nat = digit + + signedNat = ( +|- )? nat signedNat = ( +|- )? natnumber = signedNat(“”nat)number = signedNat(“”nat)？signedNatsignedNat对应的对应的DFADFA如下图如下图加上可选的小数部分，加上可选的小数部分，数字常量的数字常量的正则表达式正则表达式number = signedNat(“”nat)？对应的对应的DFADFA如下图：如下图：+ +digitdigitdigitdigitdigitdigi

42、t-+ +digitdigitdigitdigitdigitdigit-digitdigitdigitdigita ab bb bb b接受与接受与正则式正则式ab+|abab+|ab* *|b|b* * 相同的语言的相同的语言的DFADFA如下所示：如下所示：例例2-142-14：串中：串中只有一个只有一个b b被如下所示的被如下所示的DFADFA接受接受：b bnot bnot bnot bnot b例例2-152-15：包含：包含最多一个最多一个b b的串被如下所示的的串被如下所示的DFADFA接受：接受：b bnot bnot bnot bnot b注意二者之注意二者之间的区别间的区别

43、 定理定理：如果一个：如果一个DFA M DFA M 的的输入字母表输入字母表为为，则我们也称，则我们也称M M是是上的一个上的一个 DFADFA。可以证明。可以证明: :上的一个字集上的一个字集V V * *是正规是正规的，当且仅当存在的，当且仅当存在上的上的DFA MDFA M，使得，使得V =L(M)V =L(M)。 DFA DFA的的确定性确定性表现在映射表现在映射： S SSS是一个是一个单值函数单值函数。即：对于任何状态即：对于任何状态sSsS和输入符号和输入符号a a， (s,a)(s,a)唯一确定了唯一确定了一个状态。一个状态。 从转换图角度，我们也可以得到答案。从转换图角度，

44、我们也可以得到答案。 如果允许是一个如果允许是一个多值函数多值函数，我们就得到下一节要讲到的，我们就得到下一节要讲到的非确定自动机非确定自动机的概念。的概念。一个一个非确定有限自动机（非确定有限自动机（NFANFA） M M是一个五元式：是一个五元式： M M (S,(S,S,S0 0 ,F),F) ，其中，其中 1 1、S S是一个有限集，它的每个元素称为一个是一个有限集，它的每个元素称为一个状态状态 2 2、是一个是一个有穷有穷字母表字母表，它的每个元素称为一个，它的每个元素称为一个输入字符输入字符 3 3、是一个从是一个从S S* *至至S S的子集的映射，即的子集的映射，即： S S*

45、 * 2 2s s 4 4、 S S0 0SS是唯一的是唯一的初态初态 5 5、 F F S S是一个是一个终态集终态集（可空）。（可空）。 一个含有一个含有m m个状态和个状态和n n个输入字符的个输入字符的NFANFA可用一张如下的状态可用一张如下的状态转换图来表示：该图含有转换图来表示：该图含有m m个状态结点，每个结点可以射出若干个状态结点，每个结点可以射出若干条弧与别的结点相连接，条弧与别的结点相连接，每条弧用每条弧用* *中的一个字（可以是不同中的一个字（可以是不同的字，也可以是空字）做标记的字，也可以是空字）做标记，整张图至少含有一个初态结点，整张图至少含有一个初态结点和若干个（

46、可以为和若干个（可以为0 0）终态结点。某些结点既可以是初态结点也）终态结点。某些结点既可以是初态结点也可以是终态结点。可以是终态结点。aaaaa,ba,bbbbbababa,ba,bab,baab,baaa,bbaa,bbab,baab,baaa,bbaa,bba aa aa aa ab bb bb bb b下图所示的状态转换图的下图所示的状态转换图的S S、及及* *如下：如下： S = 0,1,2,3S = 0,1,2,3 = a,b = a,b * *= | = | 为为，或者，或者为为a、b的任意组合的任意组合 对于对于* *中的任何一个字中的任何一个字，若，若存在一条从某一初态结点

47、到某一存在一条从某一初态结点到某一终态结点的通路，且这条通路上终态结点的通路，且这条通路上所有弧上的标记字依序连接成的所有弧上的标记字依序连接成的字（忽略字（忽略）等于）等于，则称，则称可可以为以为NFA MNFA M 识别识别。从初态从初态x x到终态到终态y y的连接通路弧上，有如下标记字：的连接通路弧上，有如下标记字： a a ，去除，去除，为，为aa，所以字，所以字aa可为可为NFA接受。接受。a aa ab b424243142421bbabba例例2-162-16：上图所示的：上图所示的NFANFA的以下两个转换序列都可以接受串的以下两个转换序列都可以接受串abbabb：允许接允许

48、接受受abab允许接受与允许接受与abab* *匹配的匹配的字符串字符串允许接受与允许接受与b b* *匹配的字匹配的字符串符串允许接受与允许接受与abab+ +匹配的字匹配的字符串符串由此，我们可以看由此，我们可以看出这个出这个NFANFA接受与正接受与正则式则式abab+ +|ab|ab* *|b|b* * 相相同的语言！同的语言！接受接受abab接受接受abab接受接受abab接受接受abab接受接受abab接受接受abab* *接受接受abab接受接受abab接受接受abab* *接受接受b b* *练习：考虑以下练习：考虑以下NFANFA通过怎样的转换通过怎样的转换接受串接受串aca

49、bacab：a ab bc c10987432765274321 bac DFA DFA是是NFANFA的特例的特例，可以采用，可以采用子集法子集法将将NFANFA确定化。确定化。假定假定I I是是NFA MNFA M的状态集的状态集(S)(S)的一个的一个子集子集， 我们定义我们定义_CLOSURE(I)_CLOSURE(I)为：为： 1 1、若、若ssI I，则则s s _CLOSURE(I)(I)；2 2、若、若sIsI，那么从，那么从s s出发经过出发经过任意任意条条弧弧而能而能到达的到达的任何状态任何状态ss都属于都属于_CLOSURE(I)_CLOSURE(I)。状态集状态集_CL

50、OSURE(I)_CLOSURE(I)称为称为I I的的_ _闭包闭包。 假定假定 I I 是是NFA MNFA M的状态集的的状态集的子集子集，a(aa(a是输是输入字符入字符),),定义定义 Ia Ia=_CLOSURE(J)_CLOSURE(J)其中，其中，J J是那些可从是那些可从I I中的某一状态结点出发中的某一状态结点出发经过一条经过一条a a弧弧而而到达的状态结点的全体。到达的状态结点的全体。 = a1,a2,.ak = a1,a2,.ak 。先先构造一张表构造一张表，该表每，该表每一行含有一行含有k+1k+1列。置该列。置该表的表的首行首列为首行首列为_CLOSURE(X)。

51、重复上述过程，重复上述过程，直至所有直至所有第二列第二列和和第三列第三列的的子集子集均已均已在在第一列第一列上出现了上出现了为止。为止。 如果某一行的第一列的如果某一行的第一列的状态子集已经确定，例如记状态子集已经确定，例如记为为I I, ,那么，求出这一行的第那么，求出这一行的第二个和第三个子集二个和第三个子集I Ia a和和I Ib b看看它们是否已它们是否已 在表的第一列在表的第一列出现，将未出现的出现，将未出现的填入填入到后到后面空行的第一列。面空行的第一列。 1 1 表的表的初始化初始化构造构造2 2 处理表的处理表的一行一行3 3 重复处理重复处理例例2-172-17：考虑下图所示

52、：考虑下图所示NFANFA的的确定化确定化：a aa aa aa ab bb bb bb bI=I=_CLOSUREX_CLOSUREX为为X,5,1X,5,1。从状从状态态I I出发经过一条出发经过一条a a弧而能到达的状态弧而能到达的状态全体全体J J为为5,3,5,3,而而_CLOSURE(J)=5, _CLOSURE(J)=5, 3,13,1。从而。从而Ia=5, Ia=5, 3,13,1。初态初态_ _闭包闭包X,5,1X,5,1JaJa为为5,35,3_CLOSURE(J)为为5,35,3，11（根据（根据_闭包闭包的定义）的定义）根据此方法依次求根据此方法依次求出左边表中的状态出

53、左边表中的状态转换矩阵即可。转换矩阵即可。对右下图表中的所有对右下图表中的所有子集子集重新命名，得到左图中的状态转换矩重新命名，得到左图中的状态转换矩阵形成如下状态转换矩阵，从而得到相应的阵形成如下状态转换矩阵，从而得到相应的DFADFA。如图所示：。如图所示：a aa aa aa ab bb bb ba ab bb ba ab b重命名为重命名为状态状态0 0重命名为重命名为状态状态1 1根据重命根据重命名的状态名的状态填写表格填写表格ab例例2-182-18：考虑下图所示：考虑下图所示NFANFA的确定化：的确定化：11在在letterletter上有到上有到22的转换的转换：2=2，3，4，5，7，10letterletter在在letterletter上有到上有到66的转换的转换：6=4，5，6，7，9，10letterletter在在 digitdigit上有到上有到88的转换的转换：8=4，5，7，8，9，10digitdigitletterletterdigitdigitdigitdigitle