陈火旺 编译原理 chapter3.

1、 P1 张 捷第三章第三章 词词 法法 分分 析析词法分析的主要任务：词法分析的主要任务： 自左至右逐个字符地对源程序进行扫描，自左至右逐个字符地对源程序进行扫描，产生一个个单词符号，把作为字符串的源程序产生一个个单词符号，把作为字符串的源程序改造为单词符号串的中间程序。改造为单词符号串的中间程序。 P2 张 捷3.1 3.1 对于词法分析器的要求对于词法分析器的要求3.1.1 3.1.1 词法分析器的功能和输出形式词法分析器的功能和输出形式（1） 词法分析器的功能：词法分析器的功能：输入源程序，输出单词符号输入源程序，输出单词符号l把构成源程序的字符串转换成语义上关联的单词符号的序列把构成源

2、程序的字符串转换成语义上关联的单词符号的序列5种单词符号：种单词符号： 关键字：程序语言定义的具有固定意义的标识关键字：程序语言定义的具有固定意义的标识符。符。 标识符：表示各种名字。标识符：表示各种名字。 常数：整型、实型、布尔型、文字型。常数：整型、实型、布尔型、文字型。 运算符：如、运算符：如、*、/ 界符：如界符：如 , ; () /* */ 等等 P3 张 捷（2 2）单词符号：一个程序语言的基本语法符号，输出的单）单词符号：一个程序语言的基本语法符号，输出的单词符号常表示成二元式：（词符号常表示成二元式：（单词种别单词种别，单词符号属性值单词符号属性值） l单词单词种别种别 标识符

3、标识符 一种一种 常数常数 一种，整数、实数、布尔一种，整数、实数、布尔用整数编码用整数编码 关键字关键字 全体视为一种或一字一种全体视为一种或一字一种 算符算符 一符一种一符一种 界符界符 一符一种一符一种 l单词单词符号属性值符号属性值 如果一个种别只含一个单词符号，那么，对于这个单词符号，种别如果一个种别只含一个单词符号，那么，对于这个单词符号，种别编码就完全代表它自身了。若一个种别含有多个单词符号，那么，对于编码就完全代表它自身了。若一个种别含有多个单词符号，那么，对于它的每个单词符号，除了给出种别编码之外，还应给出有关单词符号的它的每个单词符号，除了给出种别编码之外，还应给出有关单词

4、符号的属性信息属性信息。 单词符号属性是指单词符号的特性或特征，属性值则是反应特性或单词符号属性是指单词符号的特性或特征，属性值则是反应特性或特征的值特征的值。 P4 张 捷例如：例如： 某个标识符常将存放其相关信息的某个标识符常将存放其相关信息的符号表符号表项指针项指针作为其属性值；作为其属性值； 某个常数则将存放它的某个常数则将存放它的常数表项的指针常数表项的指针作作为其属性值。为其属性值。 P5 张 捷例如：例如：C+C+代码段：代码段：while (i=j) i- - ;while (i=j) i- - ; 经过词法分析器处理后转换为这样的单经过词法分析器处理后转换为这样的单词符号序列

5、：词符号序列： id , = , - = , - id , id , P6 张 捷6【课堂练习】写出下面程序的单词符号序列【课堂练习】写出下面程序的单词符号序列 while( while( * *p != 0 ) p+; p != 0 ) p+; while while while - ( ( ( - * * - p p ID != != != - 0 0 CONST ) ) ) - - p p ID + + + - ; ; ; - - P7 张 捷3.1.2 3.1.2 词法分析器作为一个独立子程序词法分析器作为一个独立子程序 在实现编译程序时，常将词法分析程序从语法在实现编译程序时，常将词

6、法分析程序从语法分析中独立出来，作为一个分析中独立出来，作为一个独立的阶段独立的阶段。这样做。这样做有什么好处？有什么好处？l 可使编译程序结构更简洁，清晰和条理化可使编译程序结构更简洁，清晰和条理化l 可用更有效的特殊方法和工具进行处理可用更有效的特殊方法和工具进行处理/ / 改进编改进编译程序的效率译程序的效率l 有利于集中力量考虑其他枝节问题有利于集中力量考虑其他枝节问题/ /增强编译程序增强编译程序的可移植性的可移植性但不一定是但不一定是独立的一遍独立的一遍（如果独立一遍则要保存源（如果独立一遍则要保存源程序的内码形式），可设计一个独立的子程序（语程序的内码形式），可设计一个独立的子程

7、序（语法分析器调用之）。法分析器调用之）。 P8 张 捷3.2 词法分析器的设计词法分析器的设计3.2.1 3.2.1 输入、预处理输入、预处理 输入缓冲区输入缓冲区（输入串存放其中）。（输入串存放其中）。 预处理（注释、没有意义的空格、跳格、预处理（注释、没有意义的空格、跳格、回车、换行等）回车、换行等） 预处理子程序：当词法分析器调用时处理预处理子程序：当词法分析器调用时处理一串确定长度的输入字符并装入一串确定长度的输入字符并装入扫描缓冲区扫描缓冲区。 词法分析器对扫描缓冲区扫描时采用词法分析器对扫描缓冲区扫描时采用2 2个个指示器：一个指向当前单词的开始位置（起点指示器：一个指向当前单词

8、的开始位置（起点指示器）；另一个用于向前搜索以寻找单词的指示器）；另一个用于向前搜索以寻找单词的终点（搜索指示器）。终点（搜索指示器）。 P9 张 捷扫描缓冲区的设计：扫描缓冲区的设计：起点指示器搜索指示器输入缓冲区预处理子程序扫描器扫描缓冲区输入单词符号列表图3.1 词法分析器 P10 张 捷二、二、扫描器扫描器词法分析的主要部分词法分析的主要部分扫描器的构造原理扫描器的构造原理 设置二个指示器（起点指示器、搜索指设置二个指示器（起点指示器、搜索指示器），一个可以互补使用的一分为二的示器），一个可以互补使用的一分为二的扫描缓冲区，一个指向当前正在识别的单扫描缓冲区，一个指向当前正在识别的单词

9、的开始位置（指向新单词的首字符），词的开始位置（指向新单词的首字符），另一个用于向前搜索以寻找单词的终点。另一个用于向前搜索以寻找单词的终点。扫描缓冲区总长度为扫描缓冲区总长度为2 2120120个字符，扫描个字符，扫描器单词长度的要求是单词长度器单词长度的要求是单词长度1/21/2扫描缓扫描缓冲区长度。冲区长度。 P11 张 捷2 2扫描器的工作原理扫描器的工作原理 调用预处理子程序，把调用预处理子程序，把120120个输入字符装个输入字符装进扫描缓冲区的某半区，搜索指针从起点进扫描缓冲区的某半区，搜索指针从起点指针开始向前寻找单词的终点，若在该半指针开始向前寻找单词的终点，若在该半区内查找

10、到单词的终点，便输出二元式，区内查找到单词的终点，便输出二元式，再把起点指针移到此处的后一个字符，继再把起点指针移到此处的后一个字符，继续搜索下一个单词，如果在搜索到该半区续搜索下一个单词，如果在搜索到该半区的边缘，尚未到达单词终点，那么就调用的边缘，尚未到达单词终点，那么就调用预处理子程序，把后续的预处理子程序，把后续的120120个字符装进另个字符装进另半区，继续搜索。半区，继续搜索。 P12 张 捷3.2.2 3.2.2 单词符号的识别：超前搜索单词符号的识别：超前搜索 超前搜索：识别的单词符号的简单方法超前搜索：识别的单词符号的简单方法 关键字的识别：象关键字的识别：象FORTRANF

11、ORTRAN这样的语言，对关键字不加这样的语言，对关键字不加保护，关键字的识别较麻烦。保护，关键字的识别较麻烦。 例如：例如：FORTRAN FORTRAN 中的如下代码中的如下代码1 DO99K = 11 DO99K = 1, ,10102 IF(5.EQ.M) 2 IF(5.EQ.M) I I = 10= 103 DO99K = 1.103 DO99K = 1.104 IF(5) 4 IF(5) = = 55 55 1 1、2 2是是DODO和和IFIF语句，语句，3 3、4 4是赋值语句。是赋值语句。 P13 张 捷标识符的识别：后跟算符或界符；标识符的识别：后跟算符或界符；常数的识别：

12、算术常数、布尔常数、字符串；常数的识别：算术常数、布尔常数、字符串；算符和界符的识别：对于复合运算符，超前搜索；算符和界符的识别：对于复合运算符，超前搜索； 了解某个源语言的词法规则就可以为它设计一了解某个源语言的词法规则就可以为它设计一个词法分析器了。设计词法分析器的一种非常好的个词法分析器了。设计词法分析器的一种非常好的工具就是状态转换图。工具就是状态转换图。 P14 张 捷三、状态转换图三、状态转换图- -设计词法分析器的好工具（好途径）设计词法分析器的好工具（好途径）1 1转换图是一张有限方向图转换图是一张有限方向图 结点结点 代表状态，用圆圈表示代表状态，用圆圈表示 箭弧箭弧 状态之

13、间的连接，箭弧上的标记（字符）代表状态之间的连接，箭弧上的标记（字符）代表 在射出结点状态下可能出现的输入字符或字符在射出结点状态下可能出现的输入字符或字符 类。类。 初态初态 识别出某一类字符串的开始，初态只有一个识别出某一类字符串的开始，初态只有一个 终态终态 识别出某一单词，至少有一个。用双圈表示识别出某一单词，至少有一个。用双圈表示 P15 张 捷3.2.33.2.3状态转换图状态转换图-设计词法分析器的好工具（好途径）设计词法分析器的好工具（好途径） 状态转换图是一个有限方向图，状态转换图是一个有限方向图，l结点结点 代表状态，用圆圈表示代表状态，用圆圈表示l箭弧箭弧 状态之间的连接

14、，箭弧上的标记（字符）代表在射出状态之间的连接，箭弧上的标记（字符）代表在射出结点状态下可能出现的输入字符或字符类。结点状态下可能出现的输入字符或字符类。l初态初态 识别出某一类字符串的开始，初态只有一个识别出某一类字符串的开始，初态只有一个l终态终态 识别出某一单词，至少有一个。用双圈表示识别出某一单词，至少有一个。用双圈表示1 13 32 2X XY Y(a)(a)转换图示例转换图示例0 01 1字母字母其它其它字母或数字字母或数字* *(b)识别标识符的转换图识别标识符的转换图 P16 张 捷0 01 1数字数字其它其它数字数字* *(c)识别整数的转换图识别整数的转换图0 01 12

15、23 34 45 5* *6 6数字数字数字数字数字数字数字数字数字数字数字数字其它其它其它其它数字数字 E E或或D DE E或或D D或或(d)(d)识别识别FORTRANFORTRAN实型常数的转换图实型常数的转换图 P17 张 捷17语言无符号整数的描述语言无符号整数的描述十进制整数十进制整数: ( DEC: ( DEC，值，值 ) ) dec 0 | ( 1|.|9 ) ( 0|.|9 )dec 0 | ( 1|.|9 ) ( 0|.|9 )* *BCA01-90-9其它其它 十进制整数十进制整数 P18 张 捷18识别标识符符过程识别标识符符过程12字母字母字母或数字字母或数字其它

16、其它初态初态* 终态终态3 P19 张 捷19利用状态转换图识别单词利用状态转换图识别单词 P20 张 捷 一个状态转换图可用于识别（或接受）一定的一个状态转换图可用于识别（或接受）一定的字符串。字符串。 大多数程序语言的单词符号都可以用转换图予大多数程序语言的单词符号都可以用转换图予以识别。作为一个综合例子，我们来构造一个识别以识别。作为一个综合例子，我们来构造一个识别某个简单语言的所有单词符号的转换图。表某个简单语言的所有单词符号的转换图。表3.13.1列出列出了这个小语言的所有单词符号，以及它们的种别编了这个小语言的所有单词符号，以及它们的种别编码和内部值。码和内部值。 P21 张 捷表

17、表3.13.1单词符号及内部表示单词符号及内部表示单词符号种别编码助忆符内码值 DIM1 $DIM- IF2 $IF- DO3 $DO- STOP4 $STOP- END5 $END- 标识符6 $IDID在符号表中的位置 常数(整)7 $INTINT在常数表中的位置 8 $ASSIGN- 9 $PLUS- *10 $STAR- *11 $POWER- ,12 $COMMA- (13 $LPAR - )14 $RPAR- P22 张 捷3 3点限制：点限制： 所有关键字都是保留字，避免采用超前搜索技所有关键字都是保留字，避免采用超前搜索技术。术。 保留字表；关键字不专设对应的转换图。保留字表；

18、关键字不专设对应的转换图。 关键字、标识符和常数之间无界符、算符，则关键字、标识符和常数之间无界符、算符，则必须至少用一个空白符隔开。必须至少用一个空白符隔开。 这些限制仅仅是为了现阶段将例子做得简单些；这些限制仅仅是为了现阶段将例子做得简单些；在这些限制下，多数单词符号的识别就不必使用超在这些限制下，多数单词符号的识别就不必使用超前搜索技术。前搜索技术。 P23 张 捷01空白字母字母或数字非字母或数字*3数字数字非数字*7*非*，()其它图3.3对简单语言进行词法分析的状态转换图 P24 张 捷注注：一个程序语言的所有单词符号的识别也可以通过多：一个程序语言的所有单词符号的识别也可以通过多

19、张状态转换图加以描述。张状态转换图加以描述。3.2.4 3.2.4 状态转换图的实现（程序实现）状态转换图的实现（程序实现）引进全局变量和过程：引进全局变量和过程： ch ch 字符变量，存放最新读进的源程序字符；字符变量，存放最新读进的源程序字符； strToken strToken 字符数组，存放构成单词符号的字符串；字符数组，存放构成单词符号的字符串； GetChar GetChar子程序过程，将下一个输入字符读到子程序过程，将下一个输入字符读到chch中，中，搜索指示器前移一字符位置；搜索指示器前移一字符位置； GetBC GetBC 子程序过程，检查子程序过程，检查ch ch 中的字

20、符是否为空白。中的字符是否为空白。若是则调用若是则调用GetCharGetChar直至直至chch中进入一个非空白字符；中进入一个非空白字符； P25 张 捷 Concat Concat子程序过程，将子程序过程，将chch中的字符连接到中的字符连接到strTokenstrToken之后；之后； IsLetter IsLetter和和IsDigitIsDigit布尔函数过程，分别判断布尔函数过程，分别判断chch中中的字符是否为字母和数字；的字符是否为字母和数字； Reserve Reserve 整型函数过程，对整型函数过程，对strTokenstrToken中的字符串中的字符串查找保留字表，如

21、果它是一个保留字则返回它的编码，查找保留字表，如果它是一个保留字则返回它的编码，否则返回否则返回0 0值（假定值（假定0 0不是保留字的编码）；不是保留字的编码）； Retract Retract子程序过程，将搜索指示器回调一个字符子程序过程，将搜索指示器回调一个字符位置，将位置，将chch置为空白字符；置为空白字符； InsertId InsertId 整型函数过程，将整型函数过程，将strTokenstrToken中的标识符中的标识符插入符号表，返回符号表指针；插入符号表，返回符号表指针； P26 张 捷 InsertConst InsertConst 整型函数过程，将整型函数过程，将st

22、rTokenstrToken中的常数中的常数插入常数表，返回常数表指针；插入常数表，返回常数表指针； 构造状态转换图对应的程序，一般让每个状态结点构造状态转换图对应的程序，一般让每个状态结点对应一段程序段。对应一段程序段。不含回路的分叉结点不含回路的分叉结点：可对应：可对应switchswitch语句或语句或ifif语句语句含回路的状态结点含回路的状态结点：可对应循环语句（：可对应循环语句（whilewhile）iljkij字母字母数字数字/ /字母或数字字母或数字其它其它（a）（b）图3.4 状态转换图（a）具有不含回路的分叉结点的转换图；（b）具有含回路的状态结点的转换图； P27 张 捷

23、由状态转换图编写扫描器的一般方法由状态转换图编写扫描器的一般方法 P28 张 捷 P29 张 捷 终态结点对应一个形如终态结点对应一个形如 return(code,value)return(code,value)的语句，意味着从的语句，意味着从分析器返回到调用者（语法分析器）。分析器返回到调用者（语法分析器）。 对带星号对带星号* *的终态结点意味着多读入一个字符，这个字符的终态结点意味着多读入一个字符，这个字符应予退回，也就是说，必须把搜索指示器回调一个字符位置。应予退回，也就是说，必须把搜索指示器回调一个字符位置。应该使用应该使用RetractRetract过程来完成。过程来完成。 P30

24、 张 捷 状态转换图状态转换图3.3的词法分析器构造：的词法分析器构造：int code,value;strToken :=“ ”; /*置置strToken为空串为空串*/GetChar(); GetBC();if (IsLetter()begin while(IsLetter() or IsDigit() begin Concat(); GetChar(); end Retract(); code:=Reserve(); if(code=0) begin value:=InsertId(strToken); return($ID,value); end else return(code,-

25、);end P31 张 捷else if (IsDigit() begin while(IsDigit() begin Concat(); GetChar(); end Retract(); value:=InsertConst(strToken); return($INT,value);endelse if (ch=) return ($ASSIGN,-);else if(ch=+) return($PLUS,-);else if(ch=*) begin Getchar(); if(ch=*) return($POWER,-); Retract(); return($STAR,-);end

26、P32 张 捷else if (ch=;) return ($SEMICOLON,-);else if (ch=() return ($LPAR,-);else if (ch=) return ($RPAR,-);else if (ch=) return ($LBRACE,-);else if (ch=) return ($RBRACE,-);else ProcError();/*错误处理错误处理*/【实验】【实验】用一种程序设计语言设计上用一种程序设计语言设计上面的词法分析程序面的词法分析程序 P33 张 捷3.3 3.3 正规表达式与有限自动机正规表达式与有限自动机3.3.1 3.3.1

27、正规式与正规集正规式与正规集 递归定义：递归定义： 和和都是都是上的正规式，其所表示的正规集上的正规式，其所表示的正规集分别为：分别为： 和和； 任何任何aa，a a是是上的一个正规式，它所表示上的一个正规式，它所表示的正规集为的正规集为a a ； 假定假定U U和和V V都是都是上的正规式，它们所表示的正上的正规式，它们所表示的正规集分别记为规集分别记为L(U)L(U)和和L(V),L(V),那么那么(U|V)(U|V)、(UV)(UV)和和 (U)(U)* *也都是正规式，所表示的正规集分别为：也都是正规式，所表示的正规集分别为：L(U)L(V)L(U)L(V)、L(U)L(V)L(U)L

28、(V)和和(L(U)(L(U)* *； 仅由有限次使用上述三个步骤而得到的表达式才仅由有限次使用上述三个步骤而得到的表达式才是是上的正规式，由这些正规式所表示的字集才是上的正规式，由这些正规式所表示的字集才是上的正规集。上的正规集。 P34 张 捷34正规式和正规集的例子正规式和正规集的例子 P35 张 捷 例例3.1 令令= a , b , 下面是下面是上的正规式和相应的正规集。上的正规式和相应的正规集。正规式正规式正规集正规集ba* 上所有的以上所有的以b为首后跟任意多个为首后跟任意多个a的字的字a(a|b)* 上所有的以上所有的以a为首的字为首的字(a|b)*(aa|bb)(a|b)*

29、上所有含有上所有含有2个相继的个相继的a或者或者2个个 相继的相继的b的字的字例例3.2 令令= A , B , 0 , 1 , 下面是下面是上的正规式和相应的正规上的正规式和相应的正规集。集。正规式正规式正规集正规集(A|B)(A|B|0|1)* 上上 “标识符标识符” 的全体的全体(0|1)(0|1)* 上上 “ 数数 ” 的全体的全体 P36 张 捷36 P37 张 捷如果两个正规式所表示的正规集相同，则认为这两个正规式等如果两个正规式所表示的正规集相同，则认为这两个正规式等价：价：U=V L（U）=L（V）例如：例如：b(ab)*=(ba)*b , (a|b)*=(a*b*)*令令U、

30、V、W 均为正规式，则下面的关系普遍成立：均为正规式，则下面的关系普遍成立： U|V = V|U ( U|V = V|U (交换律交换律) ) U|(V|W) = (U|V)|W U|(V|W) = (U|V)|W （结合律）（结合律） U(VW) = (UV)W ( U(VW) = (UV)W (结合律结合律) ) U(V|W) = UV | UW ( U(V|W) = UV | UW (分配律分配律) ) (U|V)W = UW | VW (U|V)W = UW | VW U = U= U P38 张 捷38正规式运算符的优先级正规式运算符的优先级 P39 张 捷3.3.2 3.3.2 确

31、定有限自动机确定有限自动机(DFA (DFA deterministic finite automationdeterministic finite automation) ) 一个确定的有限自动机一个确定的有限自动机(DFA) M (DFA) M 是一个五元式：是一个五元式：M=( SM=( S，s s0 0，F )F )其中：其中： S S是有限状态集；是有限状态集；是有穷字母表；每个元素称是有穷字母表；每个元素称为一个输入字符。为一个输入字符。是是S S至至S S的单值部分映射，的单值部分映射，(s(s，a)=sa)=s表示现行状态表示现行状态s s，输入字符为，输入字符为a a时将转换

32、时将转换到下一状态到下一状态s s。称。称s s为为s s的一个后继状态。的一个后继状态。 s s0 0SS是唯一的初态；是唯一的初态； F F 是一个终态集（可为空）是一个终态集（可为空） P40 张 捷40DFA的例子的例子aSABZababab= P41 张 捷状态转换矩阵（行：状态，列：输入字符，矩阵元素为状态转换矩阵（行：状态，列：输入字符，矩阵元素为(s,a) (s,a) ） 例如：例如：DFA M=(0,1,2,3,a,b,DFA M=(0,1,2,3,a,b,0 ,3 ),0 ,3 )其中其中为：为：(0,a)=1(0,a)=1 (0,b)=2(0,b)=2(1,a)=3(1,

33、a)=3 (1,b)=2(1,b)=2(2,a)=1(2,a)=1 (2,b)=3(2,b)=3(3,a)=3 (3,a)=3 (3,b)=3(3,b)=3 对应状态转换矩阵如表对应状态转换矩阵如表3.2: 3.2: 表表3.2 3.2 状态转换矩阵状态转换矩阵状态ab012132213333 P42 张 捷 对应状态转换图对应状态转换图: : 一个一个DFADFA可以表示成一个（确定的）状态转换图。可以表示成一个（确定的）状态转换图。 假定假定DFA MDFA M含含m m个状态和个状态和n n个输入字符，则这个图含有个输入字符，则这个图含有m m个状态结点，每个结点顶多有个状态结点，每个结

34、点顶多有n n条箭弧射出和别的结点条箭弧射出和别的结点相连接，每条箭弧用相连接，每条箭弧用中的一个不同输入字符作标记。中的一个不同输入字符作标记。整张图含有唯一的一个初态结点和若干个（可以是整张图含有唯一的一个初态结点和若干个（可以是0 0个）个）终态结点终态结点 0 01 12 2a aa aa ab bb bb ba,ba,b图图3.5 3.5 状态转换图状态转换图识别所有含有相继两个识别所有含有相继两个a a或相继两个或相继两个b b的字。的字。 P43 张 捷3. 3.可识别可识别 对于*中的任何字，若存在一条从初态结点到某一终态结点的通路上所有弧的标识符连接成的字等于，则称可为DFA

35、 M所识别（读出或接受）。若M的初态结点同时又是终态结点，则空字可为M所识别（接受）。DFA M所能识别的字的全体记为L(M) , L(M)是一个正规集。 P44 张 捷定理定理如果一个如果一个DFA MDFA M的输入字母表为的输入字母表为 , , 则称则称M M是是上的一上的一个个DFADFA。可以证明：。可以证明：上的一个上的一个字集字集V V* *是正规的，是正规的，当且仅当存在当且仅当存在上的上的DFA MDFA M使得使得 V = L(M)V = L(M)。DFADFA的的确定性确定性： 映射映射：S SS S 是一个单值函数，是一个单值函数，即即sSsS，aa，(s,a)(s,a

36、)唯一确定下一状态。从转换唯一确定下一状态。从转换图的角度看，每一状态节点至多有图的角度看，每一状态节点至多有n n条弧射出，且每条条弧射出，且每条弧有各自不同输入字符。弧有各自不同输入字符。若允许若允许是一个多值函数，就得到是一个多值函数，就得到非确定有限自动机非确定有限自动机。 P45 张 捷3.3.3 3.3.3 非确定有限自动机非确定有限自动机(NFA)(NFA) 一个非确定的有限自动机一个非确定的有限自动机(NFA) M (NFA) M 是一个五元式：是一个五元式：M=( S,M=( S,S,S0 0,F ),F )其中：其中：S S 是有限状态集；是有限状态集；是有穷字母表；是有穷

37、字母表； 是是S S* *至至S S的幂集的映射即的幂集的映射即：S S* * 2 2s s S S0 0 S S是非空的初态集；是非空的初态集； F SF S是一个终态集（可为空）是一个终态集（可为空）NFANFA和和DFADFA的不同在于的不同在于: :l的值域是的值域是 S S 的幂集，的幂集， ：S S * * 22S Sl开始状态有不止一个开始状态有不止一个l箭弧上的输入字可以用正规式表示箭弧上的输入字可以用正规式表示 P46 张 捷46NFA的例子的例子SABZabababaaa P47 张 捷2 2表示形式表示形式 状态转换图状态转换图 一个含有一个含有m m个状态和个状态和n

38、n个输入字符的个输入字符的NFANFA可表示可表示成如下状态转换图。该图含有成如下状态转换图。该图含有m m个状态结点，每个个状态结点，每个结点可射出若干条箭弧与别的结点相连接，每条结点可射出若干条箭弧与别的结点相连接，每条弧用弧用* *中的一个字（可以相同的字且可以是空字中的一个字（可以相同的字且可以是空字) )作标记（输入字），整张图至少含有一个初态作标记（输入字），整张图至少含有一个初态结点以及若干个（可以是结点以及若干个（可以是0 0个）终态结点，某些结个）终态结点，某些结点既可以是初态结点也可以是终态结点。点既可以是初态结点也可以是终态结点。 P48 张 捷 对于对于* *中的任何一

39、个字中的任何一个字 ，若存在一条从某一初态结点到某，若存在一条从某一初态结点到某一终态结点的通路而且通路上所有的弧的标记字依次连接成的字一终态结点的通路而且通路上所有的弧的标记字依次连接成的字等于等于 ，则称，则称 可为可为NFANFA所识别（读出或接受）。所识别（读出或接受）。 若若M M的某些结点既是初态结点又时终态结点或者存在一条从某的某些结点既是初态结点又时终态结点或者存在一条从某个初态结点到某个终态结点的个初态结点到某个终态结点的的通路，那么空字的通路，那么空字可为可为M M所接受。所接受。识别所有含有相继两个识别所有含有相继两个a a或相继两个或相继两个b b的字。的字。图图3.6

40、3.6 非确定有限自动机非确定有限自动机3 30 01 12 2(a|b)(a|b)* *aa|bbaa|bb(a|b)(a|b)* * P49 张 捷 显然显然 ：DFADFA是是NFANFA的特例，但是对于的特例，但是对于每个每个NFA MNFA M存存在一个在一个DFA MDFA M, , 使得使得 L(M)=L(ML(M)=L(M) )证明：证明： 假定假定NFA M=SNFA M=F，对于，对于M M的状态的状态转换图进行以下改造：转换图进行以下改造： 引入新的初态结点引入新的初态结点X X和终态结点和终态结点Y Y； X,YX,Y S S，从从X X至至S S0 0中任意中任意初态

41、初态结点连一条结点连一条有向弧，从有向弧，从F F中任意中任意终态终态结点连一条结点连一条有向弧到有向弧到Y Y。 对对M M的状态转换图使用图的状态转换图使用图3.73.7所示的替换规则进所示的替换规则进行替换，其中行替换，其中k k是最新引入状态。是最新引入状态。 P50 张 捷 重复上述替换，直到每条弧的标记或为重复上述替换，直到每条弧的标记或为或为或为中中单个字母单个字母，即可得到，即可得到NFA MNFA M，显然，显然L(ML(M)=L(M)=L(M)。 将将M M变换成变换成DFADFA，方法如下：，方法如下： 假定假定 I I 是是M M状态集的子集，定义状态集的子集，定义I

42、I 的的闭包闭包 _closure(I)_closure(I)为：为： (a) (a) 若若qIqI，则，则qq_closure(I)_closure(I) (b) (b) 若若qIqI，则从，则从q q出发经过任意条出发经过任意条弧弧而能到而能到达的任何状态达的任何状态q q_closure(I)_closure(I)i ij jABAB代之以代之以i ij jk kA AB Bi i代之以代之以代之以代之以i ij jA|BA|Bj jA AB BA Ai ij jk ki ij jA A* *图图3.7 替换规则替换规则 P51 张 捷假定假定I I是是M M状态集的子集，状态集的子集，

43、aa，定义，定义 I Ia a=_closure(J)_closure(J) 其中其中J J是那些可从是那些可从 I I 中的某一状态结点出发经过一条中的某一状态结点出发经过一条a a弧弧而到达的状态结点的全体。而到达的状态结点的全体。分两步分两步：1 1、求、求J=Move(I,a);J=Move(I,a); 2 2、求求J J的的闭包闭包_closure(J)_closure(J)假定假定=a=a1 1,a,ak k ，构造表（即状态转换表）含，构造表（即状态转换表）含(k+1)(k+1)列，列，首行首列为首行首列为_closure(X)_closure(X)；如果某一行第一列的状态子集已

44、；如果某一行第一列的状态子集已经确定，例如记为经确定，例如记为I I，那么置该行的，那么置该行的i+1i+1列为列为I Iaiai(i=1,k)(i=1,k)；然后检查该行上的所有状态子集，看它们是否已在表的第一然后检查该行上的所有状态子集，看它们是否已在表的第一列中出现，将未曾出现者填入到后面空行的第一列。重复上列中出现，将未曾出现者填入到后面空行的第一列。重复上述过程直至出现在第述过程直至出现在第i+1i+1列列(i=1,k)(i=1,k)上所有的状态子集均上所有的状态子集均已在第一列上出现。因为已在第一列上出现。因为M M的状态子集个数是有限的，故必的状态子集个数是有限的，故必定在有限步

45、内终止。定在有限步内终止。 P52 张 捷 视该表为状态转换表，将其中每个状态子集视为视该表为状态转换表，将其中每个状态子集视为新的状态，显然，该表唯一地刻划了一个新的状态，显然，该表唯一地刻划了一个DFA MDFA M，初态初态是首行首列的那个状态，是首行首列的那个状态，终态终态是那些含有原终态的状态是那些含有原终态的状态子集。子集。 根据上述构造方法，显然有：根据上述构造方法，显然有：L(ML(M)= L(M)= L(M)= L(M)= L(M) 上述把上述把NFANFA确定为确定为DFADFA的方法为的方法为子集子集法法。【例【例3.33.3】 正规式正规式(a|b)(a|b)* *(a

46、a|bb)(a|b)(aa|bb)(a|b)* *对应的对应的NFANFA如图如图3.63.6所示，其中所示，其中X X为初态，为初态，Y Y为终态。按照上述证明过程为终态。按照上述证明过程构造出来的状态转换矩阵见表构造出来的状态转换矩阵见表3.33.3。 Y YX X5 53 34 41 12 26 6a ab ba aa ab bb ba ab b图图3.6 3.6 非确定有限自动机非确定有限自动机 P53 张 捷 正规式（正规式（a|b）*(aa|bb)(a|b) *对应的对应的NFA构造构造NFAX X5 53 34 41 12 26 6a ab ba aa ab bb ba ab b

47、 P54 张 捷表表3.3 3.3 对应于例对应于例3.33.3中正规式的状态转换矩阵中正规式的状态转换矩阵I II Ia aI Ib bX,5,1X,5,15,3,15,3,15,4,15,4,15,3,15,3,15,3,1,2,6,Y5,3,1,2,6,Y 5,4,15,4,15,4,15,4,15,3,15,3,15,4,1,2,6,Y5,4,1,2,6,Y5,3,1,2,6,Y5,3,1,2,6,Y 5,3,1,2,6,Y5,3,1,2,6,Y 5,4,1,6,Y5,4,1,6,Y5,4,1,6,Y5,4,1,6,Y5,3,1,6,Y5,3,1,6,Y5,4,1,2,6,Y5,4,1

48、,2,6,Y5,4,1,2,6,Y5,4,1,2,6,Y 5,3,1,6,Y5,3,1,6,Y5,4,1,2,6,Y5,4,1,2,6,Y5,3,1,6,Y5,3,1,6,Y5,3,1,2,6,Y5,3,1,2,6,Y 5,4,1,6,Y5,4,1,6,Y P55 张 捷 对表对表3.33.3中所有状态子集重新命名，得到表中所有状态子集重新命名，得到表3.43.4所所列的状态转换矩阵。列的状态转换矩阵。表表3.4 3.4 对表对表3.33.3中状态子集重新命名后的状态转换矩阵中状态子集重新命名后的状态转换矩阵状态状态a ab b0 01 12 21 13 32 22 21 15 53 33 3

49、4 44 46 65 55 56 65 56 63 34 4 P56 张 捷 与表与表3.43.4相对应的状态转换图如图相对应的状态转换图如图3.83.8所示。所示。其中其中0 0为初态，为初态，3 3，4 4，5 5，6 6为终态。为终态。2 21 10 0b bb bb ba ab bb bb bb ba aa aa aa aa aa a图图3.8 3.8 未化简的未化简的DFADFAa,ba43012b【课堂练习】【课堂练习】：将下面的：将下面的NFANFA确定化为确定化为DFA a(a|b)DFA a(a|b)* *b b P57 张 捷四、确定有限自动机的化简四、确定有限自动机的化简

50、 一个确定有限自动机M的化简是指：寻找一个状态数比M少的DFA M，使得L（M）=L（M）1 1状态等价和可区别状态等价和可区别（1）状态等价 假设s和t是M的两个不同状态，若从状态s出发能读出某个字而停于终态，那么，同样从t出发也能读出同样的字而停于终态，反之，若从t出发能读出某个字而停于终态，则从s出发也能读出同样的字而停于终态，则称s和t是等价的。（2）可区别 若DFA M的两个状态s和t不等价，则称s和t是可区别的 P58 张 捷2.2.化简（最少化）化简（最少化）一个一个DFA MDFA M的状态最少化过程旨在将的状态最少化过程旨在将M M的状态集分割成一些的状态集分割成一些不相交的

51、子集，使得任何不相交的子集，使得任何不同不同的两子集中的状态都是的两子集中的状态都是可区可区别别的，而的，而同一同一个子集中的任何两个状态都是个子集中的任何两个状态都是等价等价的，在每的，在每个子集中选出一个个子集中选出一个代表代表同时消去其它等价状态同时消去其它等价状态 例例1 1：终态和非终态是可区别的。：终态和非终态是可区别的。原因：终态能读出空字原因：终态能读出空字而非终态不能读出空字而非终态不能读出空字。例例2 2：图：图3.83.8中的状态中的状态1 1和状态和状态2 2是可区别的。是可区别的。2 21 10 0b bb bb ba ab bb bb bb ba aa aa aa

52、aa aa a图图3.8 3.8 未化简的未化简的DFADFA P59 张 捷分划步骤： （1）初始分划 将将S的终态和非终态分开成的终态和非终态分开成2个子集个子集(可区别可区别的的)，形成基本划分，形成基本划分； =Z，S-ZI(1),I(2)（2）进一步分划 设设含含m个子集：个子集：I(1),I(2),I(m)并且属于不同子集并且属于不同子集的状态是可区别的。分析的状态是可区别的。分析I(i)是否可进一步划分：是否可进一步划分： 对于某对于某I I(i)(i)，令，令I I(i)(i)=q=q1 1,q,q2 2,q,qk k ，若存在一个输入字符，若存在一个输入字符a a使得使得Ia

53、Ia(i)(i)不全包含不全包含在现行在现行的某一子集的某一子集I I(j)(j)中，就将中，就将I I(i)(i)一分为二。一分为二。例如，假定状态例如，假定状态s s1 1和和s s2 2经经a a弧分别达到状态弧分别达到状态t t1 1和和t t2 2，而，而t t1 1和和t t2 2属于属于现行现行m m的两个不同子集。将的两个不同子集。将I I(i)(i)分成两半，使得一半含有分成两半，使得一半含有s s1 1： I I(i1)(i1)=s|sI=s|sI(i1)(i1)且且s s经经a a弧到达弧到达t t1 1所在子集中的某状态所在子集中的某状态, 另一半含有另一半含有s s2

54、 2：I I(i2)(i2)=I=I(i)(i)-I-I(i1)(i1)。 I I(i1)(i1)中状态与中状态与I I(i2)(i2)中的状态是可区别的，形成新的分划。重中的状态是可区别的，形成新的分划。重复上述分划过程，直至分划中所含子集数不再增长为止。即每复上述分划过程，直至分划中所含子集数不再增长为止。即每个子集中状态是互相等价的，而不同子集中的状态则是可互相个子集中状态是互相等价的，而不同子集中的状态则是可互相区别的。区别的。 P60 张 捷（3）选代表 对于最后分划中的每一个子集，选取子集中的一个状态代表其它状态，I=q1,q2,，qk，挑选q1,凡导入到q2，qk的弧都改成导入到

55、q1中，然后将q2，qk从原来的状态集s中删除。（4）经如此化简之后得到的DFA M和原来的M是等价的，即L(M)=L(M)。 P61 张 捷2 21 10 0b bb bb ba ab bb bb bb ba aa aa aa aa aa a图图3.8 3.8 未化简的未化简的DFADFA【例3.6】对图3.8所示的DFA M化简 P62 张 捷解：1 初始分划 终态组3，4，5，6 非终态组0，1，2 2进一步分划 考察3，4，5，6 3，4，5，6a=3，6 3，4，5，6 3，4，5，6b=4，5 3，4，5，6 则3，4，5，6不能分划 P63 张 捷3 考察 0，1，2 0 ，1，

56、2a=1 ，33，4，5，6 1，30，1，2 应把 0，1，2一分为二 0 ，2a=1 ，1a=3 形成 0，2，1 至此整个分划含三组3，4，5，61 和0，2 4 考察0，2 0 ，2b=2，53，4，5，6 1 0，2 将0，2一分为二，得0 ， 2。 至此整个分划含四组0,1,2,3,4,5,6。每组不可再分。 P64 张 捷5选代表选代表 令状态3代表3，4，5，6，把原来导入4，5，6的弧全都导入3，并删除4，5，6，最后可得下图【作业】【作业】：P64：7(1)，12 0 01 12 2a aa aa ab bb bb ba,ba,b图图3.5 3.5 状态转换图状态转换图 P

57、65 张 捷3.3.4 3.3.4 正规文法与有限自动机正规文法与有限自动机(FA)(FA)的等价性的等价性 对于正规文法对于正规文法G G和有限自动机和有限自动机M M，如果，如果L(G)= L(M)L(G)= L(M)，则称则称G G和和M M是等价的。关于正规文法与有限自动机的等是等价的。关于正规文法与有限自动机的等价性，有以下结论：价性，有以下结论： 1 1 对于每一个右线性正规文法或左线性正规文法对于每一个右线性正规文法或左线性正规文法G G，都存在一个都存在一个FA MFA M，使，使L(M)= L(G)L(M)= L(G)。 2 2 对于每一个对于每一个FA MFA M，都存在一

58、个右，都存在一个右线性正规文法线性正规文法G GR R和和一个一个左线性正规文法左线性正规文法G GL L，使，使L(M)= L(GL(M)= L(GR R)= L(G)= L(GL L) )。 证明证明1: 1: (1) (1)给定右线性正规文法给定右线性正规文法G=(VG=(VT T,V,VN N,S,),S,),增加一个增加一个新的终结状态符号新的终结状态符号f f，f f V VN N ，令，令M=(Q,VM=(Q,VT T, , , ,S,FS,F), ), 其中，其中，F= F= f f ，Q= VQ= VN N f f 。 P66 张 捷状态转换函数状态转换函数 定义如下：定义如

59、下： (a) (a) 产生式产生式 A A a, a, 则令则令 (A,a)=f(A,a)=f (b) (b) 产生式产生式 A A aA aA1 1 aAaA2 2 . aAaAn n 则令则令 (A,a)= (A,a)= A A1 1,A,A2 2 ,.,A ,.,An n 显然，上述显然，上述M M是一个是一个NFANFA。 对于右线性正规文法对于右线性正规文法G G，在，在 的最左推导过程的最左推导过程中，利用中，利用A AaBaB一次就相当于在一次就相当于在M M中从状态中从状态A A经过一条经过一条a a弧到达状态弧到达状态B(B(包括包括a a)。利用。利用A Aa a一次则相当

60、于在一次则相当于在M M中从状态中从状态A A经过一条经过一条a a弧到达终态弧到达终态f(f(包括包括a a)。故而，。故而，在正规文法在正规文法G G中，中， 的充要条件是：在的充要条件是：在M M中，从状态中，从状态S S到状态到状态f f有一条通路，其所有弧上的符号连接起来恰好有一条通路，其所有弧上的符号连接起来恰好等于等于w w，即，即w wL(G)L(G)当且仅当当且仅当w wL(M)L(M)，故，故L(G)= L(M)L(G)= L(M)。 S Sw w S Sw w P67 张 捷 (2)(2)给定左线性正规文法给定左线性正规文法G=(VG=(VT T,V,VN N,S,S,)