第三章词法分析精选PPT.ppt

第三章词法分析第1页，本讲稿共54页源程序扫描器scanner1 1、关键字、关键字词法分析器的词法分析器的功能功能如下图所示：如下图所示：2 2、标识符、标识符5 5、界符、界符4 4、运算符、运算符3 3、常数、常数由程序语言定义的具有固定意义的标识符。也可称为保留字或基本字。例如：Pascal中的begin，end，if等。界符：如逗号、分号、括号、/*，*/等。它是确定的。运算符：如+、-、*、/等。它是确定的。常数的类型一般有整型、实型、布尔型、文字型等。它是不限的。用来表示各种名字，如变量名、数组名、过程名等。它是不限的。第2页，本讲稿共54页词法分析器的词法分析器的功能功能：输入源程序，输出单词符号。：输入源程序，输出单词符号。单词符号单词符号：一个程序语言的基本语法符号。分为以下：一个程序语言的基本语法符号。分为以下5 5种。种。1 1、关键字关键字：由程序语言定义的具有固定意义的标识符。也：由程序语言定义的具有固定意义的标识符。也可称为保留字或基本字。例如：可称为保留字或基本字。例如：PascalPascal中的中的beginbegin，endend，ifif等。它是等。它是确定确定的。的。2 2、标识符标识符：用来表示各种名字，如变量名、数组名、过程：用来表示各种名字，如变量名、数组名、过程名等。它是名等。它是不限不限的。的。3 3、常数常数：常数的类型一般有整型、实型、布尔型、文字型：常数的类型一般有整型、实型、布尔型、文字型等。它是等。它是不限不限的。的。4 4、运算符运算符：如：如+、-、*、/等。它是等。它是确定确定的。的。5 5、界符界符：如逗号、分号、括号、：如逗号、分号、括号、/*/*，*/等。它是等。它是确定确定的。的。第3页，本讲稿共54页单词符号的表示形式单词符号的表示形式：词法分析器所输出的单词符号常常表示成：词法分析器所输出的单词符号常常表示成 二元式（单词种别，单词自身的值）二元式（单词种别，单词自身的值）。单词种别单词种别可以用以下形式表示：可以用以下形式表示：1 1、一类单词统一用一个整数值代表其属性。例如：、一类单词统一用一个整数值代表其属性。例如：1 1代表关键字，代表关键字，2 2代表标识符等。代表标识符等。2 2、每一个单词一个类别。例如：、每一个单词一个类别。例如：1 1代表代表BEGINBEGIN，2 2代表代表ENDEND等。等。单词自身的值单词自身的值可以表示成：常量的二进制表示；常量、变量等在符号表可以表示成：常量的二进制表示；常量、变量等在符号表种的地址码，等等。种的地址码，等等。注意：注意：一个语言的单词符号如何分种，分几种，怎样编码，是一个技术问题。标识符一般同归为一种。常数则宜按类型（整、实、布尔）分。关键字可以将其全体视为一种，也可一字一种一字一种。运算符可采用一符一种，但也可把具有一定共性的视为一种。界符则一般采用一符一种一符一种。如何进行分种主要取决于处理上的方便。若是一符一种分种，单词自身值就不需要了。否则，要查符号表。第4页，本讲稿共54页例例3-13-1：151151FORTRANFORTRAN编译程序的词法分析器在扫描输入串编译程序的词法分析器在扫描输入串 IF(5EQIF(5EQM)GOTO 100M)GOTO 100 后，它输出的后，它输出的单词符号串单词符号串是：是：逻辑逻辑IF IF （3434，_ _）左括号左括号 （2 2，_ _）整常数整常数 （2020，55的二进制表示）的二进制表示）等号等号 （6 6，_ _）标识符标识符 （2626，MM）右括号右括号 （1616，_ _）GOTO GOTO （3030，_ _）标号标号 （1919，100100的二进制表示）的二进制表示）IFIF为关键字，种别编码为关键字，种别编码3434，采用一，采用一符一种的编码方式。符一种的编码方式。常数类型，种别编码常数类型，种别编码2020，单词自身的值，单词自身的值为为55的二进制表示。的二进制表示。(为界符，种别编码为界符，种别编码2 2，采用一符，采用一符一种的编码方式。一种的编码方式。等号为运算符，种别编码等号为运算符，种别编码6 6，采用，采用一符一种的编码方式。一符一种的编码方式。M M为标识符，种别编码为标识符，种别编码2626，单词自，单词自身值为身值为MM。)为界符，种别编码为界符，种别编码1616，采用，采用一符一种的编码方式。一符一种的编码方式。GOTOGOTO为关键字，种别编码为关键字，种别编码3030，采用一，采用一符一种的编码方式。符一种的编码方式。100100为标号，种别编码为标号，种别编码1919，单词内部，单词内部的值用的值用100100的二进制表示。的二进制表示。第5页，本讲稿共54页例例3-2 3-2：下述：下述C+C+代码段：代码段：while(i=j)i-while(i=j)i-；经词法分析器处理以后，它将被转换为如下的经词法分析器处理以后，它将被转换为如下的单词符号串单词符号串 (while(while，_)_)(，_)_)(id(id，指向，指向i i的符号表指针的符号表指针 )(=(=，_)_)(id(id，指向，指向j j的符号表指针的符号表指针 )()()，_)_)(id(id，指向，指向i i的符号表指针的符号表指针 )(-(-，_ _)(；，_)_)第6页，本讲稿共54页1 1、把词法分析从语法分析中脱离出来的、把词法分析从语法分析中脱离出来的优点优点：使编译程序的使编译程序的结构结构更加简洁、清晰和条理化。更加简洁、清晰和条理化。词法分析和语法分析词法分析和语法分析方法方法不同，词法分析可以使用正则文法自动构造不同，词法分析可以使用正则文法自动构造scannerscanner简单。简单。有利于提高语法分析的有利于提高语法分析的效率效率。可以改善词法分析的细节，甚至于一个语法分析配几个可以改善词法分析的细节，甚至于一个语法分析配几个scannerscanner，把不同，把不同的输入变成一种内部表示。的输入变成一种内部表示。2 2、把词法分析作为独立的一、把词法分析作为独立的一遍遍scannerscanner当作一遍。当作一遍。把把scannerscanner当作子程序。当作子程序。外存外存scannerscanner语法分析语法分析源程序单词符号scannerscanner作为一遍作为一遍语法语法分析分析scannerscanner源程序源程序scannerscanner作为子程序作为子程序第7页，本讲稿共54页设计前提设计前提：把把scannerscanner作为一个独立的子程序；作为一个独立的子程序；词法分析器的任务为输出单词符号。词法分析器的任务为输出单词符号。必要性必要性：编辑性字符如空白符、回车符等，除了出现在文字和编辑性字符如空白符、回车符等，除了出现在文字和 常数中以外，在别处出现都没有意义。常数中以外，在别处出现都没有意义。功功 能能：剔除无用字符。剔除无用字符。实实 现现：预处理子程序。预处理子程序。输入列表预处理预处理子程序子程序扫描器扫描器扫描缓冲区扫描缓冲区输入缓冲区输入缓冲区单词符号图图3.1 3.1 词法分析器词法分析器语法分析器语法分析器预预处处理理部部分分扫扫描描器器第8页，本讲稿共54页若若识别识别输入语句输入语句 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 起点指示器起点指示器搜索指示器搜索指示器两两 个个 互互 补补 输输 入入 缓缓 冲冲 区区120个字符个字符扫描缓冲区的扫描缓冲区的结构结构：缓冲区大小缓冲区大小：120120个字符。个字符。采用两个采用两个指示器指示器：起点指示器、搜索指示器。：起点指示器、搜索指示器。两个互补区两个互补区。第9页，本讲稿共54页单词符号识别的简单方法：单词符号识别的简单方法：超前搜索。关键字识别关键字识别：例如：在标准例如：在标准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 其中的其中的DODO、IFIF为关键字为关键字其中的其中的DODO、IFIF为标识符的为标识符的一部分一部分第10页，本讲稿共54页标识符的识别标识符的识别 多数语言的标识符是字母开头的多数语言的标识符是字母开头的“字母字母/数字数字”串，串，而且在程序中标识符的出现后都跟着算符或界符。因此，而且在程序中标识符的出现后都跟着算符或界符。因此，不难识别。不难识别。常数的识别常数的识别 对于某些语言的常数的识别也需要使用超前搜索。对于某些语言的常数的识别也需要使用超前搜索。算符和界符的识别算符和界符的识别 对于诸如对于诸如C+C+语言中的语言中的“+”+”、“-”-”，这种复，这种复合成的算符，需要超前搜索。合成的算符，需要超前搜索。第11页，本讲稿共54页转换图转换图：是一张有限方向图。在状态转换图中，：是一张有限方向图。在状态转换图中，结点结点代表代表 状态状态，用圆圈表示。状态之间用，用圆圈表示。状态之间用箭弧箭弧连接。箭弧上连接。箭弧上的的标记（字符）标记（字符）代表在射出结状态下可能出现的输代表在射出结状态下可能出现的输入字符或字符类。入字符或字符类。状态转换图的功能状态转换图的功能:用于识别一定的字符串。用于识别一定的字符串。初态初态：一张转换图的启动条件，至少有一个：一张转换图的启动条件，至少有一个,用圆圈表示。用圆圈表示。终态终态：一张转换图的结束条件，至少有一个，用双圈表示。：一张转换图的结束条件，至少有一个，用双圈表示。*：表示多读进了一个字符。：表示多读进了一个字符。第12页，本讲稿共54页1 12 23 3XY(a)(a)转换图示例转换图示例2 20 01 1字母字母其他其他字母或数字字母或数字*（b b）识别标识符的转换图）识别标识符的转换图其他其他2 20 01 1数字数字数字数字*（c c）识别整数的转换图）识别整数的转换图例例3-33-3：简单的状态转换图示例：简单的状态转换图示例：初态初态终态终态从从0 0状态到状态到1 1状态可状态可能出现字母能出现字母第13页，本讲稿共54页图图3.2 3.2 状态转换图状态转换图7 7*6 65 5数字数字1 10 01 1数字数字数字数字2 2数字数字3 3E E 或或 D D+或或数字数字其他其他E E 或或 D D数字数字其他其他数字数字例例3-43-4：识别：识别FORTRANFORTRAN实型常数实型常数的转换图：的转换图：例如下列实型常数可以例如下列实型常数可以被以下转换图识别：被以下转换图识别：1.23E+41.23E+4 .56E-7 .56E-7第14页，本讲稿共54页单词符号单词符号种别编码种别编码助忆符助忆符内码值内码值DIM1$DIMIF2$IFDO3$DOSTOP4$STOPEND 5$END标识符标识符6$ID常数（整）常数（整）7$INT内部字符串内部字符串8$ASSIGN标准二进制形式标准二进制形式 9$PLUS*10$STAR*11$POWER,12$COMMA(13$LPAR)14$RPAR例例3-53-5：综合实例：综合实例做出识别下表所示的小语言的做出识别下表所示的小语言的单词符号单词符号的状态转换图的状态转换图第15页，本讲稿共54页*1 12 20 0字母字母非字母与数字非字母与数字字母或数字字母或数字*空白空白5 54 43 3数字数字数字数字非数字非数字*6 610101111131312127 7*8 89 9*非*，（）其他其他。右图即为对上页所示右图即为对上页所示的简单语言进行的简单语言进行词法词法分析分析的状态转换图。的状态转换图。第16页，本讲稿共54页1、CHARCHAR 字符变量，存放最新读进的源程序字符。字符变量，存放最新读进的源程序字符。2 2、TOKENTOKEN 字符数组，存放构成单词的字符串。字符数组，存放构成单词的字符串。3 3、GETCHARGETCHAR 过程，将下一输入字符读入过程，将下一输入字符读入CHARCHAR，搜索指示器前移一个字符。，搜索指示器前移一个字符。4 4、GETBCGETBC 过程，检查过程，检查CHARCHAR中的字符是否为空白。若是，则调用中的字符是否为空白。若是，则调用GETCHARGETCHAR 直至直至CHARCHAR中进入一个非空白字符。中进入一个非空白字符。5 5、CONCAT CONCAT 过程，把过程，把CHARCHAR中的字符连接到中的字符连接到TOKENTOKEN之后。之后。6 6、LETTERLETTER 布尔函数过程，它们分别判断布尔函数过程，它们分别判断CHARCHAR中的字符是数字或是字母，中的字符是数字或是字母，DIGITDIGIT 从而给出真假值从而给出真假值TRUETRUE、FALSEFALSE。7 7、RESERVERESERVE 整型函数过程，用整型函数过程，用TOKENTOKEN中的字符串查保留字表，若是一个保留中的字符串查保留字表，若是一个保留 字则给予编码，否则回送字则给予编码，否则回送0 0值（假定值（假定0 0不是保留字的编码）。不是保留字的编码）。8 8、RETRACTRETRACT 过程，把搜索指示器回调一个字节，把过程，把搜索指示器回调一个字节，把CHARCHAR中的字符置为空白。中的字符置为空白。第17页，本讲稿共54页 以上函数和子程序过程都不难编制，使用它们能够方便以上函数和子程序过程都不难编制，使用它们能够方便的构造状态转换图的对应程序。一般，我们可以让每的构造状态转换图的对应程序。一般，我们可以让每一个状一个状态结态结对应对应一个程序段一个程序段。例如：我们可以让不含回路的分叉结，对应一个例如：我们可以让不含回路的分叉结，对应一个CASE CASE 语语句，或者是一组句，或者是一组IFTHENELSEIFTHENELSE语句。具体见后面实例。语句。具体见后面实例。终态结终态结一般对应一个一般对应一个RETURN(C,VAL)RETURN(C,VAL)语句。其中语句。其中C C为单词为单词种别编码；种别编码；VALVAL是字符数组的是字符数组的TOKEN TOKEN，或者是一个整数值，或，或者是一个整数值，或者无定义。具体见后面实例。者无定义。具体见后面实例。第18页，本讲稿共54页 为了把为了把状态转换图状态转换图转化成转化成程序程序，每个，每个状态状态要建立一段要建立一段程序程序，它要做的工作如下：，它要做的工作如下：第一步第一步：从输入缓冲区中取一个字符。为此，我们使用函：从输入缓冲区中取一个字符。为此，我们使用函数数GETCHARGETCHAR，每次调用它，推进先行指针，送回一，每次调用它，推进先行指针，送回一个字符。个字符。第二步第二步：确定在本状态下，哪一条箭弧是用刚刚来的输入：确定在本状态下，哪一条箭弧是用刚刚来的输入字符标识的。如果找到，控制就转到该弧所指向字符标识的。如果找到，控制就转到该弧所指向的状态；若找不到，那么寻找该单词的企图就失的状态；若找不到，那么寻找该单词的企图就失败了。败了。失失 败败：先行指针必须：先行指针必须重新回到重新回到开始指针处，并用另一状开始指针处，并用另一状态图来搜索态图来搜索另一另一单词。如果所有的状态转换图都单词。如果所有的状态转换图都试过之后，还没有匹配的，就表明这是一个词法试过之后，还没有匹配的，就表明这是一个词法错误，此时，调用错误校正程序。错误，此时，调用错误校正程序。GETCHAR是过程，将是过程，将下一输入字符读入下一输入字符读入CHAR，搜索指示器，搜索指示器前移一个字符。前移一个字符。第19页，本讲稿共54页例例3 36 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数字数字i ij jk kl l字母字母 /字符变量，存放最新字符变量，存放最新读进的源程序字符。读进的源程序字符。过程，将下一输入字符读过程，将下一输入字符读入入CHARCHAR，搜索指示器前，搜索指示器前移一个字符。移一个字符。第20页，本讲稿共54页对于如上的状态转换图，对于如上的状态转换图，状态状态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()2 20 01 1字母字母其他其他字母或数字字母或数字LETTER()是布尔函数是布尔函数过程，当且仅当过程，当且仅当C中的中的字符是字母，它返回字符是字母，它返回真假值真假值TRUE。FAIL()是例子程序，它移是例子程序，它移回回先行指针先行指针（lookahead pointer）,开始下一状态开始下一状态转换图，或调用出错程序。转换图，或调用出错程序。例例3-73-7：示例：示例如何把如何把状态结状态结对应于一段对应于一段程序程序：*第21页，本讲稿共54页对于如上的状态转换图，对于如上的状态转换图，状态状态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 goto state 1 1 else if else if DELIMITER(C)DELIMITER(C)then goto state 2 else else FAIL()FAIL()2 20 01 1字母字母其他其他字母或数字字母或数字DIGIT()是布尔函数过是布尔函数过程，当且仅当程，当且仅当C中的字中的字符是数字，它返回真假符是数字，它返回真假值值TRUE。DELIMITER(C)是过程，是过程，只要碰到标识符后的分界只要碰到标识符后的分界符，它返回符，它返回TRUE。分界分界符符一般为：空格、算术、一般为：空格、算术、逻辑符号，括号、逻辑符号，括号、；、.、，。*第22页，本讲稿共54页对于如上的状态转换图，终态对于如上的状态转换图，终态状态状态2 2的的代码如下所示：代码如下所示：state 2state 2：RETRACT()RETRACT();RETURN($id RETURN($id，INSTALL()INSTALL()2 20 01 1字母字母其他其他字母或数字字母或数字RETRACT()是过程，是过程，由于分界符不属于标识由于分界符不属于标识符，所以我们要把先行符，所以我们要把先行指针指针回调回调一个字符。一个字符。INSTALL()是过程，是过程，如我们识别出的标识符如我们识别出的标识符不在符号表中，我们把不在符号表中，我们把它装入它装入符号表符号表。我们。我们还要给语法分析程序还要给语法分析程序返回一个返回一个二元式二元式。*如果同时识别如果同时识别标识符标识符和和定义符定义符，则需要则需要修改修改为为State2：修改之后，修改之后，状态状态2 2的代码如下所示：的代码如下所示：state 2state 2：RETRACT()RETRACT();c:=c:=RESERVE();RESERVE();if c=0 if c=0 then then RETURN($id，INSTALL)else else RETURN(C,_)RETURN(C,_)RESERVE()整型函数整型函数过程过程,针对针对TOKEN中的中的字符串进行查找，看其字符串进行查找，看其是否是是否是保留字保留字，是保留，是保留字给出它的编码，否则字给出它的编码，否则回送回送0（假定（假定0不是保留不是保留字编码）。字编码）。第23页，本讲稿共54页例例3 38 8：以下程序段对应的状态图：以下程序段对应的状态图 state istate i：GETCHARGETCHAR；WHILE WHILE LETTERLETTER OR OR DIGITDIGIT DO DO GETCHARGETCHAR；state jstate j：布尔函数过程，它们分别判布尔函数过程，它们分别判断断CHARCHAR中的字符是数字或是中的字符是数字或是字母，从而给出真假值字母，从而给出真假值TRUETRUE、FALSEFALSE。i ij j其它其它字母或数字字母或数字第24页，本讲稿共54页例例3 39 9：以下程序段对应的状态图：以下程序段对应的状态图0 90 9：BEGINBEGIN WHILE WHILE DIGITDIGIT DO DO BEGIN BEGIN CONCATCONCAT；GETCHARGETCHAR END END；RETRACTRETRACT；RETURN($INT,DTB)RETURN($INT,DTB)；ENDEND；3 3非数字非数字数字数字数字数字4 4*RETURN RETURN 语句，对应终态结，语句，对应终态结，其中其中$INT为种别编码，为种别编码，DTB为为一个把十进制转换到二进制的一个把十进制转换到二进制的转换函数。它把转换函数。它把TOKENTOKEN中的数中的数字译成字译成标准二进制码标准二进制码，并以此，并以此为函数值返回。为函数值返回。第25页，本讲稿共54页正规式与正规集的递归定义：正规式与正规集的递归定义：1 1、和和都是都是字母表字母表上的正规式，它们所表示的正规集分别为上的正规式，它们所表示的正规集分别为 和和；2 2、任何、任何aa，a a是是上的一个上的一个正规式正规式，它所表示的，它所表示的正规集正规集为为aa；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)*（闭包）（闭包）仅由有限次使用上述三步骤而得到的表达式才是仅由有限次使用上述三步骤而得到的表达式才是上的上的正规式正规式。仅由这。仅由这 些正规式所表示的子集才是些正规式所表示的子集才是上的上的正规集正规集。运算符的优运算符的优先顺序：先先顺序：先“*”“*”，次，次“”，最后最后“|”|”“|”读读做做“或或”“”读做读做“连接连接”“*”读做读做“闭包闭包”*的子集的子集 U,V：积积 UV=|U U&V V n次积次积 V=VVV V V0=V的闭包的闭包 V*=V0 U V1 U V2 U V的正则闭包的正则闭包 V+=V V*第26页，本讲稿共54页例例3-113-11：令：令aa，bb，下面是，下面是上的上的正规式正规式和相应的和相应的正规集正规集：正规式正规式 正规集正规集 baba*上所有的以上所有的以b b为首，并且后跟任为首，并且后跟任 意多个意多个a a的字，的字，b,ba,baa,baaa,b,ba,baa,baaa,a(a|b)a(a|b)*上所有的以上所有的以a a为首的字为首的字 (a|b)*(aa|bb)(a|b)*(a|b)*(aa|bb)(a|b)*上所有含有两个连续的上所有含有两个连续的a a或者或者b b的字的字例例310310：令：令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。例如：例如：b(ab)b(ab)*=(ba)=(ba)*b b(a|b)(a|b)*=(a=(a*b b*)*第27页，本讲稿共54页令令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=VU|WU (V|W)U=VU|WU；5 5、U=UU=U=U=U。第28页，本讲稿共54页一个一个确定有限自动机（确定有限自动机（DFADFA）M M是一个五元式：是一个五元式：M M (S,(S,s,s0 0,F),F)，其中，其中 1 1、S S是一个有限集，它的每个元素称为一个是一个有限集，它的每个元素称为一个状态状态 2 2、是一个有穷是一个有穷字母表字母表，它的每个元素称为一个，它的每个元素称为一个输入字符输入字符 3 3、是一个从是一个从SS至至S S的单值部分映射。的单值部分映射。(s,a)=s(s,a)=s意味着：当现行状意味着：当现行状态为、输入字符为态为、输入字符为a a时，将转换到下一状态时，将转换到下一状态ss。我们称。我们称ss为为s s的一个的一个后继状态。后继状态。4 4、s s0 0SS是唯一的是唯一的初态初态 5 5、F S F S是一个是一个终态集终态集（可空）。（可空）。第29页，本讲稿共54页 显然，一个显然，一个DFADFA可用一个矩阵表示，该矩阵的行表示状态，可用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示列表示输入字符，矩阵元素表示(s,a)的值。这个矩阵称为的值。这个矩阵称为状态转换矩阵状态转换矩阵。例例3-123-12：有：有DFADFA M=(0,1,2,3,a,b,M=(0,1,2,3,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 状态状态ab012132213333相应的状态转换矩阵如下表：相应的状态转换矩阵如下表：第30页，本讲稿共54页 一个一个DFADFA也可用一张（确定的）也可用一张（确定的）状态转换图状态转换图来表示。假定来表示。假定DFA MDFA M含有含有m m个状态和个状态和n n个个输入字符输入字符，那么，这个状态转换图含有，那么，这个状态转换图含有m m个个状态结点状态结点，每个结点顶多有，每个结点顶多有n n条箭弧射出和别的结点相连接，条箭弧射出和别的结点相连接，整张图含有一个整张图含有一个初态结点初态结点和若干个（可以为和若干个（可以为0 0）终态结点终态结点。3 30 01 1图图3.5 3.5 状态转换图状态转换图2 2a aa aa aa ab bb bb b状态状态aB012132213333如下表所示的状态转换矩阵对应的如下表所示的状态转换矩阵对应的状态转换图如右图：状态转换图如右图：第31页，本讲稿共54页3 30 01 12 2a aa aa ab bb bb b上图所示的状态转换图的上图所示的状态转换图的S S、及及*如下：如下：S=0,1,2,3 S=0,1,2,3 =a,b =a,b *=|为为，或者，或者为为a、b的任意组合的任意组合 从初态从初态0 0到终态到终态3 3有如图有如图所示的通路，箭弧上到所示的通路，箭弧上到标记符连接起来的字标记符连接起来的字aaaa属于属于*，所以右图所示，所以右图所示的的DFADFA可以识别字可以识别字aaaa。同理：从初态同理：从初态0 0到终态到终态3 3还有如图所示的通路，还有如图所示的通路，箭弧上到标记符连接起箭弧上到标记符连接起来的字来的字bbabba属于属于*，所以，所以右图所示的右图所示的DFADFA可以识别可以识别字字bbabba。a a第32页，本讲稿共54页例例3-133-13：科学表示法中数字常量的：科学表示法中数字常量的正则表达式正则表达式对应的对应的DFADFA：digitdigitdigitdigitnatnat对应的对应的DFADFA如下图如下图 digit=0-9 digit=0-9 nat=digit nat=digit+signedNat=(+|-)?natsignedNat=(+|-)?natnumber=signedNat(“”nat)number=signedNat(“”nat)？signedNatsignedNat对应的对应的DFADFA如下图如下图加上可选的小数部分，加上可选的小数部分，数字常量的数字常量的正则表达式正则表达式number=signedNat(“”nat)？对应的对应的DFADFA如下图：如下图：+digitdigitdigitdigitdigitdigit-+digitdigitdigitdigitdigitdigit-digitdigitdigitdigit第33页，本讲稿共54页a ab bb bb b接受与接受与正则式正则式ab+|ab*|b*ab+|ab*|b*相同的语言的相同的语言的DFADFA如下所示：如下所示：第34页，本讲稿共54页例例3-143-14：串中：串中只有一个只有一个b b被如下所示的被如下所示的DFADFA接受接受：b bnot bnot bnot bnot b例例3-153-15：包含：包含最多一个最多一个b b的串被如下所示的的串被如下所示的DFADFA接受：接受：b bnot bnot bnot bnot b注意二者之注意二者之间的区别间的区别第35页，本讲稿共54页 定理定理：如果一个：如果一个DFA M DFA M 的的输入字母表输入字母表为为，则我们也称，则我们也称M M是是上的一个上的一个DFADFA。可以证明：。可以证明：上的一个字集上的一个字集V V *是正规是正规的，当且仅当存在的，当且仅当存在上的上的DFA MDFA M，使得，使得V=L(M)V=L(M)。DFA DFA的的确定性确定性表现在映射表现在映射：SSSS是一个是一个单值函数单值函数。即：对于任何状态即：对于任何状态sSsS和输入符号和输入符号a a，(s,a)(s,a)唯一确定了一唯一确定了一个状态。个状态。从转换图角度，我们也可以得到答案。从转换图角度，我们也可以得到答案。如果允许是一个如果允许是一个多值函数多值函数，我们就得到下一节要讲到的，我们就得到下一节要讲到的非确定自动机非确定自动机的概念。的概念。第36页，本讲稿共54页一个一个非确定有限自动机（非确定有限自动机（NFANFA）M M是一个五元式：是一个五元式：M M (S,(S,S,S0 0,F),F)，其中，其中 1 1、S S是一个有限集，它的每个元素称为一个是一个有限集，它的每个元素称为一个状态状态 2 2、是一个是一个有穷有穷字母表字母表，它的每个元素称为一个，它的每个元素称为一个输入字符输入字符 3 3、是一个从是一个从SS*至至S S的子集的映射，即的子集的映射，即：S S*2 2s s 4 4、S S0 0SS是唯一的是唯一的初态初态 5 5、F F S S是一个是一个终态集终态集（可空）。（可空）。第37页，本讲稿共54页 一个含有一个含有m m个状态和个状态和n n个输入字符的个输入字符的NFANFA可用一张如下的可用一张如下的状态转换图状态转换图来表示：该图含有来表示：该图含有m m个状态结点，每个结点可以射出若干条弧与别的结点相个状态结点，每个结点可以射出若干条弧与别的结点相连接，每条弧用连接，每条弧用*中的一个字（可以是不同的字，也可以是空字）做中的一个字（可以是不同的字，也可以是空字）做标记，整张图至少含有一个标记，整张图至少含有一个初态结点初态结点和若干个（可以为和若干个（可以为0 0）终态结点终态结点。某些结点既可以是初态结点也可以是终态结点。某些结点既可以是初态结点也可以是终态结点。1 1aaaaa,ba,b2 2bbbbabab0 0a,ba,b0 01 1ab,baab,baaa,bbaa,bbab,baab,baaa,bbaa,bb第38页，本讲稿共54页y yx x1 15 5a aa aa aa ab bb b4 43 32 26 6b bb b下图所示的状态转换图的下图所示的状态转换图的S S、及及*如下：如下：S=0,1,2,3 S=0,1,2,3 =a,b =a,b *=|为为，或者，或者为为a、b的任意组合的任意组合 对于对于*中的任何一个字中的任何一个字，若，若存在一条从某一初态结点到某一存在一条从某一初态结点到某一终态结点的通路，且这条通路上终态结点的通路，且这条通路上所有弧上的标记字依序连接成的所有弧上的标记字依序连接成的字（忽略字（忽略）等于）等于，则称，则称可可以为以为NFA MNFA M 识别识别。从初态从初态x x到终态到终态y y的连接通路弧上，有如下标记字：的连接通路弧上，有如下标记字：a a ，去除，去除，为，为aa，所以字，所以字aa可为可为NFA接受。接受。第39页，本讲稿共54页1 14 43 32 2a aa ab b例例3-163-16：上图所示的：上图所示的NFANFA的以下两个转换序列都可以接受串的以下两个转换序列都可以接受串abbabb：允许接允许接受受abab允许接受与允许接受与ab*ab*匹配的字匹配的字符串符串允许接受与允许接受与b*b*匹配的字匹配的字符串符串允许接受与允许接受与abab+匹配的字匹配的字符串符串由此，我们可以看出这由此，我们可以看出这个个NFANFA接受与正则式接受与正则式abab+|ab|ab*|b|b*相同的语言！相同的语言！接受接受abab接受接受abab接受接受abab接受接受abab接受接受abab接受接受abab*接受接受abab接受接受abab接受接受abab*接受接受b b*第40页，本讲稿共54页练习：考虑以下练习：考虑以下NFANFA通过怎样的转换通过怎样的转换接受串接受串acabacab：1010a a2 21 1b b3 37 75 56 64 48 89 9c c第41页，本讲稿共54页 DFADFA是是NFANFA的特例的特例，可以采用，可以采用子集法子集法将将NFANFA确定化。确定化。假定假定I I是是NFA MNFA M的状态集的一个的状态集的一个子集子集，我们定义我们定义_CLOSURE(I)_CLOSURE(I)为：为：1 1、若、若ssI I，则则s s _CLOSURE(I)(I)；2 2、若、若sIsI，那么从，那么从s s出发经过出发经过任意任意条条弧弧而能到而能到达的达的任何状态任何状态ss都属于都属于_CLOSURE(I)_CLOSURE(I)。状态集状态集_CLOSURE(I)_CLOSURE(I)称为称为I I的的_ _闭包闭包。第42页，本讲稿共54页 假定假定 I I 是是NFA MNFA M的状态集的的状态集的子集子集，a,a,定义定义 Ia=Ia=_CLOSURE(J)_CLOSURE(J)其中，其中，J J是那些可从是那些可从I I中的某一状态结点出发中的某一状态结点出发经过一条经过一条a a弧弧而而到达的状态结点的全体。到达的状态结点的全体。第43页，本讲稿共54页 =a1,a2,.ak =a1,a2,.ak。先先构造一张表构造一张表，该表每，该表每一行含有一行含有