第四章 词法分析

1、第四章第四章 词法分析词法分析 n词法分析的任务：从左至右逐个字符地对词法分析的任务：从左至右逐个字符地对 源程序进行扫描，按照语言的词法规则识源程序进行扫描，按照语言的词法规则识 别各类单词，并产生相应单词的属性字。别各类单词，并产生相应单词的属性字。 n词法分析器词法分析器(Lexical Analyzer) 又称扫描又称扫描 器器(Scanner)：执行词法分析的程序：执行词法分析的程序 第四章第四章 词法分析词法分析 例如：有如下例如：有如下C源程序片段源程序片段 int int1; int1 = 33; printf(“int1=%dn”,int1); 词法分析后识别出如下单词：词法

2、分析后识别出如下单词： int、int1、;、int1、=、 33、;、printf、(、 “int1=%dn”、,、int1、)、;、 第四章第四章 词法分析词法分析 说明：说明： 1、词法分析是编译程序的第一个阶段且是必、词法分析是编译程序的第一个阶段且是必 要阶段；要阶段； 2、词法分析的核心任务是扫描、识别单词且、词法分析的核心任务是扫描、识别单词且 对识别出的单词给出定性、定长的处理；对识别出的单词给出定性、定长的处理； 3、实现词法分析程序的常用途径：、实现词法分析程序的常用途径： 手工生成手工生成 自动生成自动生成 4.1 词法分析程序的任务词法分析程序的任务 一、单词一、单词

3、单词是语言中具有单词是语言中具有独立意义独立意义的的最小语法单位最小语法单位。 例如：例如： A*B，单词是，单词是“A”、“*”、“B” int int1，单词是，单词是“int”、“int1” A+*B，单词是，单词是“A”、“+”、“*”、 “B” 4.1 词法分析程序的任务词法分析程序的任务 常用的程序设计语言的单词类常用的程序设计语言的单词类 （1）关键字）关键字（亦称保留字、基本字等）（亦称保留字、基本字等） 关键字一般是语言系统本身定义的，通常是关键字一般是语言系统本身定义的，通常是 由字母组成的字符串。由字母组成的字符串。 例如：例如：C语言中的语言中的int、 char、fo

4、r、 break、 switch、 if、then等，通常不用作一般标识符。等，通常不用作一般标识符。 （2）标识符）标识符 用来表示各类名字的标识。如变量名、函数用来表示各类名字的标识。如变量名、函数 名、数组名、结构名、文件名等名、数组名、结构名、文件名等 4.1 词法分析程序的任务词法分析程序的任务 常用的程序设计语言的单词类常用的程序设计语言的单词类 （3）常数）常数 语言中各种类型的常数。如整型常数、实型常语言中各种类型的常数。如整型常数、实型常 数、不同进制的常数、布尔型常数、字符或字符数、不同进制的常数、布尔型常数、字符或字符 串常数等。串常数等。 整型：整型：12、-26、03

5、7、0 x123 实型：实型：3.4、2e-6 布尔型：布尔型：TRUE、FALSE、0或非或非0 字符或字符串型：字符或字符串型：a、A、“ABC” 4.1 词法分析程序的任务词法分析程序的任务 常用的程序设计语言的单词类常用的程序设计语言的单词类 （4）运算符）运算符 表示程序中算术运算、逻辑运算、字符及位串表示程序中算术运算、逻辑运算、字符及位串 等运算的确定字符（或串）。等运算的确定字符（或串）。 例如：各类语言较通用的例如：各类语言较通用的+、-、*、/等等 （5）界符）界符 如逗号、分号、括号和空白。如逗号、分号、括号和空白。 4.1 词法分析程序的任务词法分析程序的任务 二、属性

6、字二、属性字 对所识别的单词的数据结构表示。对所识别的单词的数据结构表示。 词法分析器所输出的单词符号常常表示成词法分析器所输出的单词符号常常表示成 如下的如下的二元式二元式： L1=（T，C） Token Code 属性字属性字 Token：表示单词种别，如标识符、运算符：表示单词种别，如标识符、运算符 Code：表示单词符号的属性值，：表示单词符号的属性值，可以为空可以为空 4.1 词法分析程序的任务词法分析程序的任务 二、属性字二、属性字 单词种别通常用整数编码表示单词种别通常用整数编码表示。 若一个种别只有一个单词符号，则种别编若一个种别只有一个单词符号，则种别编 码就代表该单词符号。

7、假定基本字、运算码就代表该单词符号。假定基本字、运算 符和界符都是一符一种。符和界符都是一符一种。 若一个种别有多个单词符号，则对于每个若一个种别有多个单词符号，则对于每个 单词符号，给出种别编码和自身的值。单词符号，给出种别编码和自身的值。 标识符单列一种；标识符自身的值表示成标识符单列一种；标识符自身的值表示成 按机器字节划分的内部码。按机器字节划分的内部码。 常数按类型分种；常数的值则表示成标准常数按类型分种；常数的值则表示成标准 的二进制形式。的二进制形式。 4.1 词法分析程序的任务词法分析程序的任务 二、属性字二、属性字 单词符号的属性是指单词符号的属性是指单词符号的特性或特单词符

8、号的特性或特 征。征。 对于标识符常将存放它的有关信息的符号对于标识符常将存放它的有关信息的符号 表项的指针作为其属性值表项的指针作为其属性值 对于常数常将存放它的常数表项的指针作对于常数常将存放它的常数表项的指针作 为其属性值为其属性值 4.1 词法分析程序的任务词法分析程序的任务 二、属性字二、属性字 例如：例如： while (i = j) i-; 输出单词符号：输出单词符号： =, - 4.1 词法分析程序的任务词法分析程序的任务 三、词法分析器作为一个独立子程序三、词法分析器作为一个独立子程序 词法分析是作为一个独立的阶段，是否词法分析是作为一个独立的阶段，是否 应当将其处理为一遍呢

9、？应当将其处理为一遍呢？ 作为独立阶段的优点：结构简洁、清晰和条作为独立阶段的优点：结构简洁、清晰和条 理化，有利于集中考虑词法分析一些枝节问理化，有利于集中考虑词法分析一些枝节问 题。题。 不作为一遍：将其处理为一个子程序。不作为一遍：将其处理为一个子程序。 4.1 词法分析程序的任务词法分析程序的任务 三、词法分析器作为一个独立子程序三、词法分析器作为一个独立子程序 词法分词法分 析器析器 语法分语法分 析器析器 符号表符号表 源程序源程序 单词符号单词符号 取下一单词取下一单词 . 4.2 词法分析器的设计词法分析器的设计 词法分析器的结构词法分析器的结构 预处理预处理 子程序子程序 扫

10、描器扫描器 输入缓冲区输入缓冲区 扫描缓冲区扫描缓冲区 单词符号单词符号 输入输入 列表列表 4.2 词法分析器的设计词法分析器的设计 一、输入、预处理一、输入、预处理 输入源程序是词法分析工作的第一步。输入源程序是词法分析工作的第一步。 输入串放在输入缓冲区中。输入串放在输入缓冲区中。 预处理子程序：剔除无用的空白、跳格、回车预处理子程序：剔除无用的空白、跳格、回车 和换行等编辑性字符和换行等编辑性字符; ;区分标号区、捻接续行区分标号区、捻接续行 和给出句末符等和给出句末符等 扫描缓冲区扫描缓冲区 起点起点 搜索搜索 指示器指示器 指示器指示器 4.2 词法分析器的设计词法分析器的设计 二

11、、单词符号的识别：超前搜索二、单词符号的识别：超前搜索 1 基本字识别基本字识别: 例如例如: DO99K=1，10 DO 99 K = 1，10 IF(5)GOTO55 IF (5) GOTO 55 DO99K=1.10 IF(5)=55 需要超前搜索才能确定哪些是基本字需要超前搜索才能确定哪些是基本字 4.2 词法分析器的设计词法分析器的设计 二、单词符号的识别：超前搜索二、单词符号的识别：超前搜索 2 2 标识符识别标识符识别: : 字母开头的字母数字串，后跟界符或算符字母开头的字母数字串，后跟界符或算符 3 3 常数识别常数识别: : 识别出算术常数并将其转变为二进制内码表示。有识别出

12、算术常数并将其转变为二进制内码表示。有 些也要超前搜索。些也要超前搜索。 5.EQ.M 5.E085.EQ.M 5.E08 4 4 算符和界符的识别算符和界符的识别 把多个字符符合而成的算符和界符拼合成一个单一把多个字符符合而成的算符和界符拼合成一个单一 单词符号。单词符号。 :=:=， * *， +，-，= 4.2 词法分析器的设计词法分析器的设计 三、状态转换图三、状态转换图 1 1 概念概念 状态转换图是一张有限方向图。状态转换图是一张有限方向图。 21 3 X Y 结点代表状态，用圆圈表示结点代表状态，用圆圈表示。 状态之间用箭弧连结，箭弧上状态之间用箭弧连结，箭弧上 的标记的标记(

13、(字符字符) )代表代表在在射出结射出结点点 状态下可能出现的输入字符或状态下可能出现的输入字符或 字符类。字符类。 一张转换图只包含有限个状态，其中有一张转换图只包含有限个状态，其中有 一个为初态，至少要有一个终态。一个为初态，至少要有一个终态。 识别标识符的状态转换图识别标识符的状态转换图 123 字母字母其他其他 字母或数字字母或数字 * 识别识别整常数整常数的状态转换图的状态转换图 123 数字数字其他其他 数字数字 * 一个状态转换图可用于识别一个状态转换图可用于识别( (或接受或接受) )一定的字符一定的字符 串。串。 2 2 例子例子 q助忆符助忆符：直接用编码表示不便于记忆，：

14、直接用编码表示不便于记忆， 因此用助忆符来表示编码。因此用助忆符来表示编码。 表4.1 C语言子集的单词符号及内码值 单词符号种别编码助记符内码值 while1while if2if else3else switch4switch case5case 标识符6idid在符号表中的位置 常数7numnum在常数表中的位置 +8+ 9 *10* =11relopLE 11relopLT = =11relopEQ =12= ；13； 图45 简单词法分析的状态转换图 01 * 2 2 开始 空白 字母 字母或数字 非字母与数字 32 4 数字 数字*非数字 返回(id, id在符号表中的位置) 或返

15、回(保留字, ) 返回(num, num在常数表中的位置) 2 5 2 6 2 7 * 8 2 9 2 10 11 2 12 2 13 2 14 2 15 *其它 其它 * ； 其它 * 返回(, ) 返回(, ) 返回( , ) * 返回(relop, LE) 返回(relop, LT) 返回(relop, EQ) 返回(, ) 返回(；, ) 非法字符错 3 状态转换图的实现状态转换图的实现 思想：每个状态结点对应一小段程序。思想：每个状态结点对应一小段程序。 做法做法: : 1)1)对不含回路的分叉结点，可用一个对不含回路的分叉结点，可用一个CASECASE语句语句 或一组或一组IF-E

16、LSEIF-ELSE语句实现语句实现 GetChar( ); if (IsLetter( ) 状态状态j的对应程序段的对应程序段; else if (IsDigit( ) 状态状态k的对应程序段的对应程序段; else if (ch=) 状态状态l的对应程序段的对应程序段; else 错误处理错误处理; i j k l 字母字母 数字数字 3 状态转换图的实现状态转换图的实现 2)2)对含回路的状态结，可对应一段由对含回路的状态结，可对应一段由WHILEWHILE结构结构 和和IFIF语句构成的程序语句构成的程序. . i 字母或数字字母或数字 其它其它 j GetChar( ); while

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

18、字符串与character中的字符连接并作为 token中新的字符串。 (5) letter( )和digit( )：判断 character中的字符是否为字母和数字的 布尔函数，是则返回true，否则返回 false。 (6) reserve( )：按token数组中的字 符串查表4.1中的前五项(即判别其是否为 保留字)，若是保留字则返回它的编码， 否则返回0值。 (7) retract( )：扫描指针回退一个字 符，同时将character置为空白。 (8) buildlist( )：将标识符登录到符 号表或将常数登录到常数表。 (9) error( )：出现非法字符，显示出 错信息。

19、相对于图4-5的词法分析器构造如下： token= ; /*对token数组初 始化*/ s=getchar ( ); getbe ( ); /*滤除空格*/ switch (s) case a: case b: case z: while (letter ( )digit ( ) concatenation ( ); /*将当前读入的字符送入 token数组*/ getchar ( ); retract ( ); /*扫描指针回退一个字符*/ c=reserve ( ); if (c=0) buildlist ( ); /*将标识符登录到符号表中*/ return (id，指向id的符号表入

20、口指针); else return (保留字码，null); break; case 0: case 1: case 9: while (digit ( ) concatenation ( ); getchar ( ); retract ( ); buildlist ( ); /*将常数登录到常数 表中*/ return (num，num的常数表入口指针); break; case +: return (+，null); break; case ?: return (?，null); break; case *: return (*，null); break; case : getchar (

21、 ); if (character= =) return (relop,LE); else retract ( ); return (relop，LT); break; case =: getchar ( ); if (character= =) return (relop, EQ); else retract ( ); return (=, _ ); break; case ;: return (;, _ ); break; default: error ( ); 4.3 正规表达式与有限自动机正规表达式与有限自动机 一、正规式与正规集一、正规式与正规集 描述程序设计语言中单词的工具主要有描

22、述程序设计语言中单词的工具主要有 以下以下3种：种： n正则文法正则文法 n正规式正规式 n自动机自动机 如标识符可以由正则文法描述如下：如标识符可以由正则文法描述如下： | | 4.3 正规表达式与有限自动机正规表达式与有限自动机 一、正规式与正规集一、正规式与正规集 1、正规式、正规式：又称正则表达式，正则式。：又称正则表达式，正则式。 正规集正规集：每个正规式描述的集合。：每个正规式描述的集合。 2、正规式和正规集的递归定义、正规式和正规集的递归定义： 对给定的字母表对给定的字母表 1) 和和都是都是 上的正规式，它们所表示的正规上的正规式，它们所表示的正规 集为集为 和和; 2) 任何

23、任何a ，a是是 上的正规式，它所表示的上的正规式，它所表示的 正规集为正规集为a ; 4.3 正规表达式与有限自动机正规表达式与有限自动机 一、正规式与正规集一、正规式与正规集 3) 假定假定U U和和V都是都是 上的正规式，它们所表示的正上的正规式，它们所表示的正 规集为规集为L(U)和和L(V)，则：，则： i) (U|V)为正规式，它所表示的正规集为为正规式，它所表示的正规集为 L() L()， ii) (U.V)为正规式，它所表示的正规集为为正规式，它所表示的正规集为 L(U)L(V)， iii) ()*为正规式，它所表示的正规集为为正规式，它所表示的正规集为 (L(U)*， 仅由仅

24、由有限次有限次使用上述三步骤而定义的表达式才使用上述三步骤而定义的表达式才 是是 上的正规式，仅由这些正规式表示的字上的正规式，仅由这些正规式表示的字 集才是集才是 上的正规集。上的正规集。 4.3 正规表达式与有限自动机正规表达式与有限自动机 一、正规式与正规集一、正规式与正规集 例如，设有字母表例如，设有字母表 a,ba,b 则下列各式：则下列各式： baba* *，a(a|b)a(a|b)* *，(a|b)(a|b)* *(aa|bb)(a|b)(aa|bb)(a|b)* * 均为定义在均为定义在 上的正规式，它们所表示的正规集分别上的正规式，它们所表示的正规集分别 为：为： L(baL

25、(ba* *)=)=b b，baba，baabaa，baaabaaa， L(a(a|b)L(a(a|b)* *)=)=a a，aaaa，abab，aaaaaa，abbabb， L(a|b)L(a|b)* *(aa|bb)(a|b)(aa|bb)(a|b)* *)=aa)=aa，bbbb，aaaaaa，abbabb，baabaa， bbbbbb， 4.3 正规表达式与有限自动机正规表达式与有限自动机 一、正规式与正规集一、正规式与正规集 例如，设有字母表例如，设有字母表 A,BA,B，0 0，1 1 则：则： 正规式正规式 正规集正规集 (A|B)(A|B|0|1)(A|B)(A|B|0|1)*

26、 * 上的 上的“标识符标识符”的全体的全体 (0|1)(0|1)(0|1)(0|1)* * 上的 上的“数字数字”的全体的全体 4.3 正规表达式与有限自动机正规表达式与有限自动机 一、正规式与正规集一、正规式与正规集 所有词法结构一般都可以用正规式描述。所有词法结构一般都可以用正规式描述。 若两个正规式所表示的正规集相同，则称这两个若两个正规式所表示的正规集相同，则称这两个 正规式等价。如正规式等价。如 b(ab)*=(ba)*b L( (ba)*b) = L(ba)*) L(b) = (L(ba)*L(b) = (L(b)L(a)* L(b) = ba* b = , ba, baba,

27、bababa, b = b, bab, babab, bababab, L(b(ab)*) = L(b)L(ab)*) = L(b) (L(ab)* = L(b) (L(a)L(b)* =b ab* = b , ab, abab, ababab, = b, bab, babab, bababab, L(b(ab)*)= L( (ba)*b) b(ab)*=(ba)*b 4.3 正规表达式与有限自动机正规表达式与有限自动机 一、正规式与正规集一、正规式与正规集 1、正规式的性质、正规式的性质： 设设U、V和和W均为均为 上的上的正规式，则下列关系成立：正规式，则下列关系成立： （）（）| = |

28、 交换律交换律 （）（） |(|) = (|)| 结合律结合律 （）（）() = () 结合律结合律 （）（）(|) = | 分配律分配律 (|) = | 分配律分配律 （）（） = = 例4.1 令=a,b，设R=a(a b)* 是上的正规式，试求其表 示的正规集。 解答 L(R)=L(a(a b)*)=L(a)L(a b)*)=L(a)(L(a b)*=L(a)(L(a) L(b)* =a(ab)*=aa,b* =a, a, b, aa, ab, ba, bb, aaa, =a, aa, ab, aaa, aab, aba, abb, aaaa, 例4.2 判断下述正规式之间是否等价： (

29、1) (a b)*与a* b* (2) (ab)*与a*b* (3) (a b)*与(a*b*)* 解答 (1) (a b)*对应的正规集其a、b可任意交替出 现，如abbaaaba；而(a* b*)对应的正规集只可出 现任意个a或者任意个b；因此两者不等价。 (2) (ab)*对应的正规集是以任意个ab对出现的， 即ababab；而a*b*对应的正规集则是先出现任意 个a后接任意个b，即aabb；因此两者不等价。 (3) 由于(a b)*对应的正规集其a、b可任意交 替出现，如aababbb；而(a*b*)*可采用如下构造方 法得到字aababbb： (a*b*)2=(a*b*)0(a2b1

30、)1(a1b3)2=aababbb 反之，对(a*b*)*产生的任意字也可由(a b)*得到， 即两者是等价的。 4.3 正规表达式与有限自动机正规表达式与有限自动机 有限自动机（FA）是更一般化的状态转换图，它分为确定有限自动机 DFA和非确定有限自动机NFA两种。 二、确定有限自动机（）二、确定有限自动机（） 1、定义定义：确定有限状态自动机：确定有限状态自动机M是一个五元组：是一个五元组： M=（K，f，S，Z） nK是一个有穷集，它的每个元素称为一个状态；是一个有穷集，它的每个元素称为一个状态； n是一个有穷字母表，它的每个元素称为一个输入符号，所以也称是一个有穷字母表，它的每个元素称

31、为一个输入符号，所以也称 为输入符号表；为输入符号表； nf是转换函数，是在是转换函数，是在KK上的映射，即，如上的映射，即，如 f（ki，a）=kj， （kiK，kjK）就意味着，当前状态为）就意味着，当前状态为ki，输入符为，输入符为a时，将转换时，将转换 为下一个状态为下一个状态kj，我们把，我们把kj称作称作ki的一个后继状态；的一个后继状态； nSK是唯一的一个初态；是唯一的一个初态； nZ K是一个终态集，终态也称可接受状态或结束状态。是一个终态集，终态也称可接受状态或结束状态。 一个一个DFA 的例子的例子 DFA M=（S，U，V，Q，a，b，f，S，Q） 其中其中f定义为：定

32、义为： f（S，a）=Uf（V，a）=U f（S，b）=Vf（V，b）=Q f（U，a）=Qf（Q，a）=Q f（U，b）=Vf（Q，b）=Q DFA 的状态图表示的状态图表示 b S U V Q a a a b a，b b DFA 的矩阵表示的矩阵表示 ab SUV UQV VUQ QQQ 字符字符 状态状态 0 0 0 1 4.3 正规表达式与有限自动机正规表达式与有限自动机 二、确定有限自动机（）二、确定有限自动机（） DFA可以表示为状态转换图。假定可以表示为状态转换图。假定DFA M含有含有m 个状态和个状态和n个输入字符，那么，这个图含有个输入字符，那么，这个图含有m个个 状态结点

33、，每个结点顶多含有状态结点，每个结点顶多含有n条箭弧射出，且条箭弧射出，且 每条箭弧用每条箭弧用上的不同的输入字符来作标记。上的不同的输入字符来作标记。 对于对于 *中的任何字中的任何字 ，若存在一条从初态到某一，若存在一条从初态到某一 终态的道路，且这条路上所有弧上的标记符连接终态的道路，且这条路上所有弧上的标记符连接 成的字等于成的字等于 ，则称，则称 为为DFA M所所识别识别(接收接收)，若，若 M的初态结点同时又是终态结点，则空字的初态结点同时又是终态结点，则空字可以可以 为为M识别识别(接收接收)。 4.3 正规表达式与有限自动机正规表达式与有限自动机 二、确定有限自动机（）二、确

34、定有限自动机（） DFA M所识别的字的全体记为所识别的字的全体记为L(M)。 可以证明：可以证明： 上的字集上的字集V*是正规集，当且仅当是正规集，当且仅当 存在存在 上的上的DFA M，使得，使得VL(M)。 * *上的符号串上的符号串t t被被DFADFA M M接受接受 例例：证明证明t=baab被下图的被下图的DFA所接受所接受。 f（S，baab）=f（f（S，b），），aab） = f（V，aab）= f（f（V，a），），ab） =f（U，ab）=f（f（U，a），），b） =f（Q，b）=Q Q属于终态。属于终态。 得证。得证。 b S U V Q a b b a, b a

35、a 4.3 正规表达式与有限自动机正规表达式与有限自动机 三、非确定有限自动机（三、非确定有限自动机（NFA） 1、定义定义：非确定有限状态自动机：非确定有限状态自动机M是一个五元组：是一个五元组： M=（K，f，S，Z） nK是一个有穷集，它的每个元素称为一个状态；是一个有穷集，它的每个元素称为一个状态； n是一个有穷字母表，它的每个元素称为一个输是一个有穷字母表，它的每个元素称为一个输 入符号；入符号； nf是转换函数，是一个从是转换函数，是一个从K * 到到K的子集（的子集（2 K） 的一种映射的一种映射； nS K是一个非空初态集；是一个非空初态集； nZ K是一个终态集。是一个终态集

36、。 一个一个NFA 的例子的例子 NFA M=（S，P，Z，0，1，f，S，P，Z） 其中：其中： f（S，0）=P f（S，1）=S，Z f（P，1）=Z f（Z，0）=P f（Z，1）=P NFA 的状态图表示的状态图表示 S P Z 0 0,1 1 1 1 矩阵表示矩阵表示 01 SPS,Z0 PZ0 ZPP1 简化为简化为 01 SPS,Z0 P.Z0 ZPP1 4.3 正规表达式与有限自动机正规表达式与有限自动机 三、非确定有限自动机（三、非确定有限自动机（NFA） 0 2 1 a，b aa a，b bb a，b 012 ab ab 识别所有含相继两个识别所有含相继两个a 或相继两个

37、或相继两个b的字的字 ambn | m，n 1 4.3 正规表达式与有限自动机正规表达式与有限自动机 三、非确定有限自动机（三、非确定有限自动机（NFA） 2、从状态图中看、从状态图中看NFA 和和DFA的区别的区别 弧上的标记可以是弧上的标记可以是 *中的一个字，而不一定是单中的一个字，而不一定是单 个字符；个字符； 同一个字可能出现在同状态射出的多条弧上。同一个字可能出现在同状态射出的多条弧上。 DFA是是NFA的特例。的特例。 定义：对于任何两个有限自动机定义：对于任何两个有限自动机M和和M， 如果如果L(M)=L(M)，则称，则称M与与M等价。等价。 自动机理论中一个重要的结论：判定两

38、自动机理论中一个重要的结论：判定两 个自动机等价性的算法是存在的。个自动机等价性的算法是存在的。 确定有限自动机和不确定有限自动机确定有限自动机和不确定有限自动机 对于每个对于每个NFA M存在一个存在一个DFA M，使得，使得 L(M)=L(M)。亦即。亦即DFA与与NFA描述能力相描述能力相 同。同。 有一种算法，将有一种算法，将NFA转换成接受同样语言转换成接受同样语言 的的DFA.这种算法称为这种算法称为子集法子集法. 与某一与某一NFA等价的等价的DFA不唯一不唯一 1. 假定假定NFA M=，我们对，我们对M的的 状态转换图进行以下改造：状态转换图进行以下改造： 1) 引进新的初态

39、结点引进新的初态结点X和终态结点和终态结点Y，X,Y S， 从从X到到S中任意状态结点连一条中任意状态结点连一条 箭弧，箭弧， 从从Z 中任意状态结点连一条中任意状态结点连一条 箭弧到箭弧到Y。 2) 对对M的状态转换图进一步施行替换，其中的状态转换图进一步施行替换，其中k是是 新引入的状态。新引入的状态。 证明证明: 代之为代之为 ik AB j ij AB 代之为代之为 ij A|B ij B A 代之为代之为 ij A* ik j A 按下面的三条规则对按下面的三条规则对V进行分裂进行分裂: 逐步把这个图转变为每条弧只标记为逐步把这个图转变为每条弧只标记为 上的上的 一个字符或一个字符或

40、 ，最后得到一个，最后得到一个NFA M，显，显 然然L(M)=L(M) 识别所有含相继两个识别所有含相继两个a或相继两个或相继两个b的字的字 XY 51 4 2 3 6 a b a b a b a b 5126 a b a b aa bb 2. 把上述把上述NFA确定化确定化采用子集法采用子集法. （1）状态集合状态集合I的的 -闭包闭包 设设I是是M的状态集的一个子集，定义的状态集的一个子集，定义I的的 -闭包闭包 -closure(I)为为: i) 若若s I，则，则s-closure(I)； ii) 若若s I，则从则从s出发经过任意条出发经过任意条 弧而能到弧而能到 达的任何状态达的

41、任何状态s都属于都属于 -closure(I)， 即即 -closure(I)=I s|从某个从某个s I出发经过任意出发经过任意 条条 弧能到达弧能到达s （2）状态集合状态集合I的的a弧转换弧转换 设设a是是 中的一个字符，定义中的一个字符，定义 Ia= -closure(J) 其中，其中，J为为I中的某个状态出发经过一中的某个状态出发经过一 条条a弧而到达的状态集合。弧而到达的状态集合。 -closure(1)=1，2=I J=5，4，3 Ia= -closure(J)= -closure(5，4，3) =5，4，3，6，2，7，8 6 1 a 23 4 5 7 8 a a 设设a是是

42、中的一个中的一个 字符，定义字符，定义 Ia= -closure(J) 其中，其中，J为为I中的某中的某 个状态出发经过个状态出发经过 一条一条a弧而到达弧而到达 的状态集合。的状态集合。 把把NFA确定化的过程确定化的过程: 不失一般性，设字母表只包含两个不失一般性，设字母表只包含两个a a和和b b， 我们构造一张表我们构造一张表: : IIaIb -Closure(X) n首先，置第首先，置第1行第行第1列为列为 -closure(X)求求 出这一列的出这一列的Ia，Ib； n然后，检查这两个然后，检查这两个Ia，Ib，看它们是否已，看它们是否已 在表中的第一列中出现，把未曾出现的填在表

43、中的第一列中出现，把未曾出现的填 入后面的空行的第入后面的空行的第1列上，求出每行第列上，求出每行第2，3 列上的集合列上的集合. n重复上述过程，直到所有第重复上述过程，直到所有第2，3列子集列子集 全部出现在第一列为止。全部出现在第一列为止。 IIaIb X,5,15,3,15,4,1 5,3,15,2,3,1,6,Y5,4,1 5,4,15,3,15,2,4,1,6,Y 5,2,3,1,6,Y5,2,3,1,6,Y5,4,6,1,Y 5,4,6,1,Y5,3,6,1,Y5,2,4,1,6,Y 5,2,4,1,6,Y5,3,6,1,Y5,2,4,1,6,Y 5,3,6,1,Y5,2,3,1

44、,6,Y5,4,6,1,Y XY 51 4 2 3 6 a b a b a b a b 现在把这张表看成一个状态转换矩阵，把现在把这张表看成一个状态转换矩阵，把 其中的每个子集看成一个状态。其中的每个子集看成一个状态。 这张表唯一刻划了一个确定的有限自动机这张表唯一刻划了一个确定的有限自动机 M，它的初态是，它的初态是 -closure(X) ，它的终，它的终 态是含有原终态态是含有原终态Y的子集。的子集。 不难看出，这个不难看出，这个DFA M与与M等价。等价。 Iab 012 132 214 334 465 565 634 0 1 2 3 5 4 6 a ab b b a b a a b

45、a b a b 4.3.4 4.3.4 确定有限自动机的化简确定有限自动机的化简 n 对对DFA M的化简的化简:寻找一个状态数比寻找一个状态数比M少的少的DFA M，使得，使得L(M)=L(M) n 最小状态最小状态DFA 没有多余状态没有多余状态(死状态死状态) ) 没有两个状态是互相等价（不可区别）没有两个状态是互相等价（不可区别） n 两个状态两个状态s和和t等价：满足等价：满足 一致性一致性同是终态或同是非终态同是终态或同是非终态 蔓延性蔓延性从从s出发读入某个出发读入某个a a和从和从 t出发出发读入某个读入某个a到达的状态等价。到达的状态等价。 n 两个状态不等价，则称它们是两个

46、状态不等价，则称它们是可区别可区别的。的。 消除多余状态消除多余状态 s1 s5 s2 s7 s2 s5 s5 s7 s5 s6 s3 s1 s8 s0 s0 s1 s3 s6 0 1 0 1 1 0 0 0 1 1 0 s0 s1 s2 s3 s4 s5 s6 s7 s8 s1 s5 s2 s7 s2 s5 s5 s7 s5 s6 s3 s1 s8 s0 s0 s1 s3 s6 0 1 0 1 1 0 0 0 1 1 0 s0 s1 s2 s3 s4 s5 s6 s7 s8 s1 s5 s2 s7 s2 s5 s5 s7 s3 s1 s0 s1 0 1 0 1 1 0 0 1 s0 s1 s

47、2 s3 s5 s7 如图，状态如图，状态0和和4是可区别的。是可区别的。 状态状态2和和3是可区别的，因为读入是可区别的，因为读入b后分后分 别到达别到达2和和4，而，而2和和4不是等价的。不是等价的。 b 0 2 134 a b a a a a b b b 图图4.6 DFA M 对一个对一个DFA M最少化采用最少化采用分割法分割法 算法的核心思想算法的核心思想: 把把M的状态集划分为一些不相交的的状态集划分为一些不相交的 子集，使得任何两个不同子集的状态是子集，使得任何两个不同子集的状态是 可区别的，而同一子集的任何两个状态可区别的，而同一子集的任何两个状态 是等价的。最后，让每个子集

48、选出一个是等价的。最后，让每个子集选出一个 代表，同时消去其它状态。代表，同时消去其它状态。 具体做法具体做法: 对对M的状态集进行划分的状态集进行划分 首先，把首先，把S划分为划分为终态终态和和非终态非终态两个子集，两个子集， 形成基本划分形成基本划分 。 假定到某个时候，假定到某个时候， 已含已含m个子集，记为个子集，记为 =I(1)，I(2)，I(m)，检查，检查 中的每个子中的每个子 集看是否能进一步划分集看是否能进一步划分: 对某个对某个I(i)，令，令I(i)=s1,s2, ,sk，若存在一，若存在一 个输入字符个输入字符a使得使得Ia(i) 不会包含在现行不会包含在现行 的的 某

49、个子集某个子集I(j)中，则至少应把中，则至少应把I(i)分为两个部分为两个部 分。分。 一般地，对某个一般地，对某个a和和I(i)，若，若Ia(i) 落入现行落入现行 中中 N个个 不同子集，则应把不同子集，则应把I(i)划分成划分成N个不相交的组，使得个不相交的组，使得 每个组每个组J的的Ja都落入的都落入的 同一子集。这样构成新的同一子集。这样构成新的 划分。划分。 重复上述过程，直到重复上述过程，直到 所含子集数不再增长。所含子集数不再增长。 对于上述最后划分对于上述最后划分 中的每个子集，我们选取每个中的每个子集，我们选取每个 子集子集I中的一个状态代表其他状态，则可得到化简中的一个

50、状态代表其他状态，则可得到化简 后的后的DFA M。 若若I含有原来的初态，则其代表为新的初态，若含有原来的初态，则其代表为新的初态，若I含含 有原来的终态，则其代表为新的终态。有原来的终态，则其代表为新的终态。 0 1 2 3 5 4 6 a ab b b a b a a b a b a b I(1)=0, 1, 2 I(2)=3, 4, 5, 6 Ia(1) =1, 3 I(11) =0, 2 I(12) =1I(2)=3, 4, 5, 6 I(11) =0, 2 Ia(11) =1 Ib(11) =2, 5 I(111) =0 I(112) =2I(12) =1 I(2)=3, 4, 5, 6 Ia(2) =3, 6 Ia(2) =4, 5 0 1 2 3 5 4 6 a ab b b a b a a b a b a b 0 1 2 3 a a bb b a a b 4.4 4.4 正规式与有限自动机的等价性正规式与有限自动机的等价性 定理定理： 1. 对于对于上的任何上的任何FA M，都存在一个，都存在一个上上 的正规式的正规式r，使得，使得L(r)=L(M)。 2.对于对于上的任何正规式上的任何正规式r，都存在一个，都存在一个 上的上的FA M，使得，使得