第3章 词法分析

1、ReviewReview：程序语言的语法描述程序语言的语法描述 几个概念几个概念: :考虑一个考虑一个有穷有穷 字母表字母表 字符集字符集其中每一个元素称为一个其中每一个元素称为一个字符字符上的上的字字( (也叫也叫字符串字符串) ) 是指由是指由中的字符所构中的字符所构成的一个有穷序列成的一个有穷序列不包含任何字符的序列称为不包含任何字符的序列称为空字空字，记为，记为用用* *表示表示上的所有字的全体上的所有字的全体, ,包含空字包含空字复习：复习：程序语言的语法描述程序语言的语法描述 *的子集的子集U和和V的的连接连接（积积）定义为）定义为UV | U & V V自身的自身的 n次积记为次

2、积记为Vn=VVV 规定规定V0= ，令，令 V*=V0V1V2V3 称称V*是是V的的闭包闭包; 记记 VVV* ，称，称V+是是V的正规闭包。的正规闭包。复习：复习：程序语言的语法描述程序语言的语法描述 上下文无关文法上下文无关文法的定义：的定义： 一个上下文无关文法一个上下文无关文法G G是一个四元式是一个四元式 G=(VG=(VT T，V VN N，S S，P)P)，其中，其中V VT T：终结符集合：终结符集合( (非空非空) )V VN N：非终结符集合：非终结符集合( (非空非空) )，且，且V VT T V VN N= =S S：文法的开始符号，：文法的开始符号，S S V V

3、N NP P：产生式集合：产生式集合( (有限有限) )，每个产生式形式为，每个产生式形式为P P， P P V VN N， ( (V VT T V VN N) )* *开始符开始符S S至少必须在某个产生式的左部出现一次。至少必须在某个产生式的左部出现一次。复习：复习：程序语言的语法描述程序语言的语法描述 定义：称定义：称 A 直接推出直接推出，即，即 A 仅当仅当A 是一个产生式，是一个产生式， 且且 ， (VT VN)* 。 如果如果 1 2 n，则我们称这个序，则我们称这个序列是从列是从 1到到 n的一个的一个推导推导。若存在一个从。若存在一个从 1到到 n的推导，则称的推导，则称 1

4、可以可以推导推导出出 n 。 通常，用通常，用 表示：从表示：从 1 1出发，经过出发，经过一步或若干步一步或若干步，可以推出，可以推出 n n。n1n*1 用用 表示：从表示：从 1 1出发，经过出发，经过0 0步或步或若干步若干步，可以推出，可以推出 n n。* 所以所以 ： 即即 或或*S ,|)(*TV SGLq定义：假定定义：假定G G是一个文法，是一个文法，S S 是它的开始符号。是它的开始符号。如果如果 ，则，则 称是一个称是一个句型句型。仅含终结符。仅含终结符号的句型是一个号的句型是一个句子句子。文法。文法G G所产生的句子的全所产生的句子的全体是一个体是一个语言语言，将它记为

5、，将它记为 L(G)L(G)。复习：复习：程序语言的语法描述程序语言的语法描述 最左推导最左推导：任何一步：任何一步 都是对都是对 中的最中的最左非终结符进行替换。左非终结符进行替换。 最右推导最右推导：任何一步：任何一步 都是对都是对 中的最中的最右非终结符进行替换。右非终结符进行替换。复习：复习：程序语言的语法描述程序语言的语法描述 用一张图表示一个句型的推导用一张图表示一个句型的推导,称为称为语法树语法树。Ei+*()EiiEEEEE (E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)E (E)(E+E)(E+i)(E*E+i)(E*i+i)(i*i+i)复习：复习

6、：程序语言的语法描述程序语言的语法描述 定义定义：如果一个文法存在某个句子对应两如果一个文法存在某个句子对应两颗不同的语法树颗不同的语法树，则说这个则说这个文法是二义的文法是二义的。 语言的二义性：一个语言的二义性：一个语言是二义性的语言是二义性的，如，如果对它不存在无二义性的文法。果对它不存在无二义性的文法。复习：复习：程序语言的语法描述程序语言的语法描述 形式语言鸟瞰形式语言鸟瞰0型型(短语文法，图灵机短语文法，图灵机)： 产生式形如：产生式形如： 其中：其中： (VT VN)*且至少含有一个非终结符；且至少含有一个非终结符； (VT VN)*1型型(上下文有关文法，线性界限自动机上下文有

7、关文法，线性界限自动机)： 产生式形如：产生式形如： 其中：其中：| | | |，仅，仅 S 例外。例外。复习：复习：程序语言的语法描述程序语言的语法描述 形式语言鸟瞰形式语言鸟瞰 2型型(上下文无关文法，非确定下推自动机上下文无关文法，非确定下推自动机)： 产生式形如：产生式形如： A 其中：其中：A VN； (VT VN)*。 3型型(正规文法，有限自动机正规文法，有限自动机)： 产生式形如：产生式形如： A B 或或 A 其中：其中： VT*；A，B VN 产生式形如：产生式形如： A B 或或 A 其中：其中： VT*；A，B VN第章词法分析第章词法分析 任务：任务：从左至右逐个字符

8、地对源程序进行扫从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串。字符串的源程序改造成为单词符号串。词法分析器词法分析器(Lexical Analyzer) 又称扫描器又称扫描器(Scanner)：执行词法：执行词法分析的程序分析的程序3.1 对于词法分析器的要求对于词法分析器的要求3.2 词法分析器的设计词法分析器的设计3.3 正规表达式与有限自动机正规表达式与有限自动机3.4 词法分析器的自动产生（）词法分析器的自动产生（） 略略3.1 对于词法分析器的要求对于词法分析器的要求 一功能和输出形式一功能和输出形式

9、 二接口设计二接口设计. .对于词法分析器的要求对于词法分析器的要求一、功能和输出形式、功能：、功能：输入源程序，输出单词符号、单词符号的分类、单词符号的分类（）（）关键字:由程序语言定义的具有固定意义的标识符，也 称为保留字或基本字。 例如：Pascal 语言中 begin end if while 等。（）（）标识符：用来表示各种名字。如变量名、数组名、过程名等。（）（）常数：整型、实型、布尔型、文字型等例：100 3.14159 true sample（）（）运算符：+、-、*、/（）（）界符：，；（）等、输出的单词符号形式、输出的单词符号形式二元式：（单词种别，单词符号的属性值）. .

10、对于词法分析器的要求对于词法分析器的要求单词符号的编码：标识符：一般统归为一种常数：常按整型、实型、布尔型等分类关键字：全体视为一种一字一种运算符：一符一种界符：一符一种通常用通常用“整数编码整数编码”“单词符号的特征或特性单词符号的特征或特性”例：例：考虑下述+代码段：while ( i = j ) i - -;. .对于词法分析器的要求对于词法分析器的要求经词法分析器处理后，它将被转换为如下的经词法分析器处理后，它将被转换为如下的单词符号序列：单词符号序列： = , - 例例 FORTRAN程序程序 IF (5.EQ.M) GOTO 100IF (5.EQ.M) GOTO 100 输出单词

11、符号：输出单词符号：逻辑逻辑IFIF(34(34，-)-)左括号左括号(2(2，-)-)整常数整常数(20(20， 5 5的二进制的二进制) )等号等号(6(6，-)-)标识符标识符(26(26， M M) )右括号右括号(16(16，-)-)GOTOGOTO(30(30，-)-)标号标号(19(19， 100100的二进制的二进制) ). .对于词法分析器的要求对于词法分析器的要求二、接口设计、词法分析器作为独立的一遍、词法分析器作为独立的一遍词法分析字符流单词序列（源程序）（输出在一个中间文件上）、词法分析器作为一个独立的子程序，但并不、词法分析器作为一个独立的子程序，但并不一定作为独立的

12、一遍一定作为独立的一遍语法分析器词法分析器调用（取下一个单词）调用（取下一个单词）单词（至少一个）单词（至少一个）优点：优点：使整个编译程序的结构更简洁、清晰和条理化.词法分析器词法分析器词法分词法分析器析器语法分语法分析器析器符号表符号表源程序源程序单词符号单词符号取下一单词取下一单词.3.2 词法分析器的设计词法分析器的设计 一输入和预处理一输入和预处理 二单词符号的识别二单词符号的识别 三状态转换图及其实现三状态转换图及其实现词法分析器的结构词法分析器的结构预处理预处理子程序子程序扫描器扫描器输入缓冲区输入缓冲区扫描缓冲区扫描缓冲区单词符号单词符号输入输入列表列表3.2 词法分析器的设计

13、词法分析器的设计、预处理：、预处理：剔掉空白符、跳格符、回车符、换剔掉空白符、跳格符、回车符、换行符、注解部分等行符、注解部分等.一、输入、预处理. .词法分析器的设计词法分析器的设计编辑性字符编辑性字符除了出现在文字常数中之外，在别除了出现在文字常数中之外，在别处的任何出现都无意义处的任何出现都无意义.注解部分注解部分不是程序的必要组成部分，它的作用不是程序的必要组成部分，它的作用仅在于改善程序的易读性和易理解性仅在于改善程序的易读性和易理解性. 每当词法分析器调用时，就处理出一串确定长每当词法分析器调用时，就处理出一串确定长度（如度（如120个字符）的输入字符，并将其装进词法个字符）的输入

14、字符，并将其装进词法分析器所确定的分析器所确定的扫描缓冲区扫描缓冲区中。中。、预处理子程序：、预处理子程序：. .词法分析器的设计词法分析器的设计 起点指示器起点指示器搜索搜索指示器指示器一个指向当前正在识别的单词的一个指向当前正在识别的单词的开始位置开始位置（即新（即新单词的首字符）单词的首字符）起点指示器起点指示器一个用于向当前搜索以寻找单词的一个用于向当前搜索以寻找单词的终点终点搜索指示器搜索指示器图 _ 源程序输入缓冲区的对半互补结构. .词法分析器的设计词法分析器的设计二. 单词符号的识别超前搜索 1 1关键字的识别关键字的识别:-FORTRAN语言的需要超前搜索. 2 2标识符的识

15、别标识符的识别:在程序中标识符的出现都后跟着算符或界符. 3 3常数的识别常数的识别: 多数语言算术常数的表示大体相似,对它们的识 别也是很直接的;但对于某些语言的常数的识别 也需用超前搜索的方法;逻辑常数和用引号括起 来的字符串常数很容易识别. 4 4算符和界符的识别算符和界符的识别: 应将那些由多个字符复合成的算符和界符 拼合成一个单词符号,因为这些字符串是 不可分的整体,若分划开来,便失去了原来 的意义.-需用超前搜索的方法. .词法分析器的设计词法分析器的设计三、状态转换图及其实现1 1、状态转换图及其示例、状态转换图及其示例 状态转换图状态转换图: : 有限方向图有限方向图. . 结

16、点结点: : 代表状态代表状态, , 用圆圈表示用圆圈表示, , 状态之间用弧连接状态之间用弧连接. . 箭弧上的标记箭弧上的标记( (字符字符): ): 代表在射出结点代表在射出结点( (即始结点即始结点) )状状 态下可能出现的输入字符或字符类态下可能出现的输入字符或字符类. . 一张一张转换图转换图只包含只包含有限个有限个状态状态( (即有限个结点即有限个结点), ), 其中一其中一个为个为初态初态, ,而且实际上而且实际上至少至少要有要有一个终态一个终态( (用双圈表示用双圈表示). ). .词法分析器的设计词法分析器的设计例例: : 数字数字数字数字 其它其它 * 字母或数字字母或数

17、字字母字母 其它其它 *例例: : ( (课本课本4242页表页表3.1; 433.1; 43页图页图3.3)3.3). .词法分析器的设计词法分析器的设计2 2 例子例子q助忆符助忆符：直接用编码表示不便于记忆，：直接用编码表示不便于记忆，因此用助忆符来表示编码。因此用助忆符来表示编码。单单 词词 符符 号号 种种 别别 编编 码码 助助 忆忆 符符 内内 码码 值值 D DI IM M 1 1 $ $D DI IM M - - I IF F 2 2 $ $I IF F - - D DO O 3 3 $ $D DO O - - S ST TO OP P 4 4 $ $S ST TO OP P

18、 - - E EN ND D 5 5 $ $E EN ND D - - 标标 识识 符符 6 6 $ $I ID D 内内 部部 字字 符符 串串 常常 数数 ( (数数 ) ) 7 7 $ $I IN NT T 标标 准准 二二 进进 制制 形形 式式 = = 8 8 $ $A AS SS SI IG GN N - - _ _ 9 9 $ $P PL LU US S - - * * 1 10 0 $ $S ST TA AR R - - * * * 1 11 1 $ $P PO OW WE ER R - - ， 1 12 2 $ $C CO OM MM MA A - - ( ( 1 13 3

19、$ $L LP PA AR R - - ) ) 1 14 4 $ $R RP PA AR R - - 1 12 23 34 45 56 67 78 89 910101111121213130 0空白空白字母字母字母或数字字母或数字非字母与数字非字母与数字数字数字非数字非数字数字数字= =+ +* *非非* *, ,( () )其它其它* * * * * 几点重要限制几点重要限制不必使用超前搜索不必使用超前搜索 所有基本字都是保留字所有基本字都是保留字;用户不能用它们作自用户不能用它们作自己的标识符己的标识符 基本字作为特殊的标识符来处理基本字作为特殊的标识符来处理;不用特殊的不用特殊的状态图来

20、识别，只要查保留字表。状态图来识别，只要查保留字表。 如果基本字、标识符和常数如果基本字、标识符和常数(或标号或标号)之间没之间没有确定的运算符或界符作间隔，则必须使用一有确定的运算符或界符作间隔，则必须使用一个空白符作间隔。个空白符作间隔。DO99K=1，10 要写成要写成 DO 99 K=1，102 2、状态转换图的实现、状态转换图的实现 实现方法实现方法: : 用程序实现用程序实现, , 让每个状态结点对应一小段程序。让每个状态结点对应一小段程序。A、变量和过程说明、变量和过程说明ch字符变量，存放最新读进的源程序字符。字符变量，存放最新读进的源程序字符。strToken 字符数组，存放

21、构成单词符号的字符串。字符数组，存放构成单词符号的字符串。GetChar 子程序过程，将下一输入字符读到子程序过程，将下一输入字符读到ch中，搜索指中，搜索指 示器前移一字符位置。示器前移一字符位置。 GetBC子程序过程，检查子程序过程，检查ch中的字符是否为空白。若是，中的字符是否为空白。若是， 则调用则调用GetChar直至直至ch中进入一个非空白字符。中进入一个非空白字符。 Concat子程序过程，将子程序过程，将ch中的字符连接到中的字符连接到strToken之后之后. .词法分析器的设计词法分析器的设计IsLetter和和IsDigit 布尔函数过程，它们分别判断布尔函数过程，它们

22、分别判断ch中的中的字符是否为字母和数字。字符是否为字母和数字。Reserve整型函数过程，对整型函数过程，对strToken中的字符串查找中的字符串查找保留字表，若它是一个保留字则返回它的编码，否则返保留字表，若它是一个保留字则返回它的编码，否则返回回0值（假定值（假定0不是保留字的编码）。不是保留字的编码）。Retract 子程序过程，将搜索指示器回调一个字符位置，子程序过程，将搜索指示器回调一个字符位置，将将ch置为空白字符。置为空白字符。InsertId整型函数过程，将整型函数过程，将strToken中的标识符插入中的标识符插入符号表，返回符号表指针。符号表，返回符号表指针。Inser

23、tConst 整型函数过程，将整型函数过程，将strToken中的常数插入中的常数插入常数表，返回常数表指针。常数表，返回常数表指针。. .词法分析器的设计词法分析器的设计B、示例小程序、示例小程序图中结点图中结点i所对应的程序段可表示为：所对应的程序段可表示为：GetChar （）（）; if ( IsLetter( ) ) 状态状态j的对应程序段的对应程序段； else if ( IsDigit( ) ) 状态状态k的对应程序段的对应程序段； else if ( ch=/ ) 状态状态l的对应程序段的对应程序段； else 错误处理错误处理;图中结点图中结点i所对应的程序段可表示为：所对应

24、的程序段可表示为： GetChar （）（）; while (IsLetter ( ) or IsDigit ( ) ) GetChar ( );状态状态j的对应程序段的对应程序段字母字母数字数字/字母或数字字母或数字 其它其它. .词法分析器的设计词法分析器的设计C、示例大程序、示例大程序课本课本43页图页图3.3；45-46页页. .词法分析器的设计词法分析器的设计3.3 正规表达式与有限自动机正规表达式与有限自动机 一单词符号的描述一单词符号的描述 1. 正规式与正规集正规式与正规集 2. 正规文法正规文法 二有限自动机二有限自动机 1. . 3. NFA与与DFA的等价的等价 4. D

25、FA的化简的化简 三正规式与有限自动机的等价性三正规式与有限自动机的等价性 四正规文法与有限自动机的等价性四正规文法与有限自动机的等价性3.3 正规式和正规集正规式和正规集 正规集正规集可以用可以用正规表达式正规表达式（简称（简称正规式正规式）表示。表示。 正规表达式正规表达式是表示是表示正规集正规集一种方法。一一种方法。一个字集合是个字集合是正规集正规集当且仅当它能用当且仅当它能用正规正规式式表示。表示。. .正规表达式与有限自动机正规表达式与有限自动机一、单词符号的描述1正规式与正规集正规式与正规集 (1) 递归定义递归定义 都是上的正规式, 正规集-和，-正规式，正规集-正规式，正规集-

26、（）和（）， 那么（），（）和（）*也都是正规式， 正规集-（） （），（）（）和 （）. .正规表达式与有限自动机正规表达式与有限自动机例题：例题：、令，下面是，下面是上的正规式和相应的正规集上的正规式和相应的正规集ba*a(a|b)*(a|b)*(aa|bb)(a|b)* 上所有以上所有以b为首后跟任意多个为首后跟任意多个a的字的字上所有以上所有以a为首的字为首的字上所有含有两个相继的上所有含有两个相继的a或两个相继的或两个相继的b的字的字. .正规表达式与有限自动机正规表达式与有限自动机 (A|B)(A|B|0|1)* (0|1)(0|1)* 、令，则：，则：一个正规式的正规集与之完全等

27、价，只是表达形式不同一个正规式的正规集与之完全等价，只是表达形式不同 上的“标识符”的全体 上的“数”的全体. .正规表达式与有限自动机正规表达式与有限自动机(2) 运算运算“”（或）：表示从各选择对象中选择（或）：表示从各选择对象中选择“”（连接积）：表示（连接积）：表示“连接连接”起来起来（）（闭包）：任意（）（闭包）：任意有限次有限次的的自重复自重复连接连接注：注：S*= Sn= SSSL (r*)=L (r)*优先级：优先级：*”|”n=0. .正规表达式与有限自动机正规表达式与有限自动机例题：例题：、L (r|s) = L (rs) = L (a|b)c) = B、L(a|b)*)

28、= L(a|(b*) =C、a | bc* a | (b (c*) ab | c*d (ab) | (c*)d ) L(r) L(s)=r s=r, s L(r) L(s) = rs L(a|b) L(c)=a, bc=ac, bc, a, b, aa, ab, ba, bb, a, b, bb, bbb,(3)等价：等价：若两个正规式所表示的正规集相同，则认若两个正规式所表示的正规集相同，则认为二者等价为二者等价. 两个等价的正规式和，记为两个等价的正规式和，记为. .正规表达式与有限自动机正规表达式与有限自动机例：例：b(ab)*=(ba)*b(a|b)*=(a*b*)* 以以 b(ab)

29、*=(ba)*b 为例：为例：L( (ba)*b) = L(ba)*) L(b)= (L(ba)*L(b) = (L(b)L(a)* L(b) = ba* b = , ba, baba, 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() 令、均为正规式，则：令、均为正规式，则：

30、（交换律）（交换律） （）（）（）（）（结合律）（结合律） （）（）（）（）（结合律）（结合律） U（V|W）=UV|UW（分配律）（分配律） （V|W）U=VU|WU U=U=UU*=（U|）*U*=U*. .正规表达式与有限自动机正规表达式与有限自动机例题：例题：、已知字母表=a，b，c，试求在该字母表上的仅包括一个b的所有串的集合相对应的正规式. .正规表达式与有限自动机正规表达式与有限自动机B、已知字母表=a，b，c，若集合是包括了最多一个b的所有串，求其相应的正规式(a|c)*b(a|c)*(a|c)*|(a|c)*b(a|c)*. .正规表达式与有限自动机正规表达式与有限自动机(1

31、) 正规文法的形式正规文法的形式左线性文法左线性文法: 任何产生式为任何产生式为AB或或A, 其中其中VT*, A、B VN右线性文法右线性文法: 任何产生式为任何产生式为AB或或A, 其中其中VT*, A、BVN(2) 描述能力描述能力正规文法所描述的是正规文法所描述的是(VNVT)上的正规集。上的正规集。多数程序设计语言的单词的词法都能用正规文法来描述。多数程序设计语言的单词的词法都能用正规文法来描述。2、正规文法单词符号. .正规表达式与有限自动机正规表达式与有限自动机(3) 例题例题例例1.程序设计语言中的几类单词可用下述规则描述程序设计语言中的几类单词可用下述规则描述:标识符标识符

32、字母数字字母数字字母数字字母数字字母数字字母数字字母数字字母数字无符号整数无符号整数无符号整数无符号整数运算符运算符等号等号等号等号等号等号界符界符，；（），；（）中的任一英文字母；中的任一英文字母；中的任一数字中的任一数字. .正规表达式与有限自动机正规表达式与有限自动机二、有限自动机FA（ Finite Aufomofa） (1)定义定义: DFA M是一个五元式是一个五元式 M=（S， ，S0，F） S S有限集，其中的每个元素称为一个状态有限集，其中的每个元素称为一个状态 有穷字母表，其中的每个元素称为一个输入字符有穷字母表，其中的每个元素称为一个输入字符 ：S SS S（即（即状态状

33、态 sSsS，aa，（S S，a a）唯一的确定下一状态）唯一的确定下一状态） （S S，a a）=S=S: : 当现行状态为当现行状态为S S，输入字符为，输入字符为a a时，将转换到下一状态时，将转换到下一状态S S s s0 0SS，唯一的初态，唯一的初态 F FS S，是一个终态集（可空），是一个终态集（可空）1 1、确定有限自动机、确定有限自动机DFADFA. .正规表达式与有限自动机正规表达式与有限自动机(2) DFA的两种表达方式的两种表达方式A. 状态转换矩阵状态转换矩阵例：例：DFA M=（0，1，2，3，a，b，0，3）其中其中为：为：（0，a）=1 （0，b）=2（1，a

34、）=3 （1，b）=2（2，a）=1 （2，b）=3（3，a）=3 （3，b）=3则其状态转换矩阵为：则其状态转换矩阵为：状态状态ab012132213333. .正规表达式与有限自动机正规表达式与有限自动机B. 状态转换图状态转换图. .正规表达式与有限自动机正规表达式与有限自动机DFA Mm个状态：图中有个状态：图中有m个状态结点个状态结点n个字符：每个结点顶多有个字符：每个结点顶多有n条箭弧射出条箭弧射出 每条箭弧用每条箭弧用中的一个不同输入中的一个不同输入 字符作标记字符作标记整张图含有唯一的一个初态结点和若干个整张图含有唯一的一个初态结点和若干个 （可为（可为0）终态结点）终态结点

35、a a a aa ba b a a b b b b. .正规表达式与有限自动机正规表达式与有限自动机(3) 识别（读出识别（读出/接受）接受）对于任何对于任何*中的任何字中的任何字，若存在一条从初态，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有弧结点到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字等于的标记符连接成的字等于。则称。则称可为可为DFA M所识所识别（接受别（接受/读出）。读出）。若若MM的初态结点同时又是终态结点，则空字的初态结点同时又是终态结点，则空字可可 为为MM所识别所识别/ /接受。接受。DFA MDFA M所能识别的字的全体记为所能识别的字的全体

36、记为L L（MM）。）。若一个若一个DFA MDFA M的输入字母表为的输入字母表为，则称，则称MM是是上的一个上的一个DFADFA。. .正规表达式与有限自动机正规表达式与有限自动机(4) 定理定理 上的一个字集上的一个字集V*是正规的，当且仅是正规的，当且仅当存在当存在上的上的DFA M，使得，使得V=L（M）. .正规表达式与有限自动机正规表达式与有限自动机2、非确定有限自动机（、非确定有限自动机（NFA）(1) 一个一个NFA是一个五元式是一个五元式M=（S， ，S0，F）其中：其中：S S有限集，其中每个元素称为一个状态有限集，其中每个元素称为一个状态有穷字母表，其中的每个元素称为一

37、个输入字符有穷字母表，其中的每个元素称为一个输入字符：S S* *2 2S S S S0 0S S，是一个非空初态集，是一个非空初态集 F FS S，是一个终态集（可空），是一个终态集（可空）. .正规表达式与有限自动机正规表达式与有限自动机(2) 状态转换图状态转换图注：注：（1）每条弧用）每条弧用*中的一个字（可以是空字中的一个字（可以是空字）作为输入字）作为输入字（2）整张图）整张图至少至少含有一个初态结点以及含有一个初态结点以及若干个若干个（可为（可为0个）个） 终态结点终态结点（3）某些结点既可为初态结点也可为终态结点）某些结点既可为初态结点也可为终态结点. .正规表达式与有限自动机

38、正规表达式与有限自动机(3) 识别（读出识别（读出/接受）接受）对于对于*中的任何一个中的任何一个，若存在一条从某，若存在一条从某一初态结点到某一终态结点的通路，且这条通路一初态结点到某一终态结点的通路，且这条通路上所有弧的标记字依序连接成的字（忽略那些标上所有弧的标记字依序连接成的字（忽略那些标记为记为的弧）等于的弧）等于，则称，则称可为可为NFA M所识别所识别（读出（读出/接受）。接受）。若若MM的某些结点既是初态结点又是终态结点，或者存在的某些结点既是初态结点又是终态结点，或者存在 一条从某个初态结点到某个终态结点的一条从某个初态结点到某个终态结点的通路，则空字通路，则空字 可为可为M

39、M所接受。所接受。. .正规表达式与有限自动机正规表达式与有限自动机（1）NFA可有若干个开始状态，而可有若干个开始状态，而DFA只有一个只有一个（2）DFA的映像为：的映像为：SS NFA的映像为：的映像为：S*2S 从状态图中看从状态图中看NFA 和和DFA的区别：的区别： 1 弧上的标记可以是弧上的标记可以是 *中的一个字，而不一定是中的一个字，而不一定是单个字符；单个字符； 2 同一个字可能出现在同状态射出的多条弧上。同一个字可能出现在同状态射出的多条弧上。 DFA是是NFA的特例。的特例。021 a，baaa，bbba，b012abab识别所有含相继两个识别所有含相继两个a或相继两个

40、或相继两个b的字的字ambn | m，n 1. .正规表达式与有限自动机正规表达式与有限自动机3、正规式NFADFA(1)(1)正规式正规式NFANFA方法方法: :替换规则替换规则: :ABAB A/BA/B A A* *A A B BA AB B A A代之以代之以代之以代之以代之以代之以. .正规表达式与有限自动机正规表达式与有限自动机(2) NFA(2) NFADFADFA构造构造DFA MDFA M, ,使得使得L(ML(M)=L(M)=L(M)=L(M)=L(M)构造状态转换矩阵构造状态转换矩阵构造状态转换表构造状态转换表?. .正规表达式与有限自动机正规表达式与有限自动机例：已知

41、正规式例：已知正规式,求其对应的最简求其对应的最简DFA?步骤步骤:正规式正规式NFA状态转换矩阵状态转换矩阵重命名的重命名的状态转换表状态转换表化简后的化简后的状态表状态表DFA练习练习1：L(R) =(a|b)*abb，构造，构造NFA使使L(N)=L(R)练习练习2：L(R) =a*b*abb，构造，构造NFA使使L(N)=L(R). .正规表达式与有限自动机正规表达式与有限自动机例例:已知正规式已知正规式(a|b)*(aa|bb)(a|b)*,求其对应的最简求其对应的最简DFA?解解:(1)构造构造NFA M(a|b)(a|b)* *(aa|bb)(a|b)(aa|bb)(a|b)*

42、*(a|b)(a|b)* * aa|bb (a|b) aa|bb (a|b)* * a a a a aa aa bbbb b b b b a a a a a a a a b bb b b b b b 把上述把上述NFA确定化确定化采用子集法采用子集法.设设I是的状态集的一个子集，定义是的状态集的一个子集，定义I的的 -闭包闭包 -closure(I)为为: i) 若若s I，则，则s-closure(I)； ii) 若若s I，则从则从s出发经过任意条出发经过任意条 弧而能到达的弧而能到达的任何状态任何状态s都属于都属于 -closure(I) 即即 -closure(I)=I s|从某个从某

43、个s I出发经过任意条出发经过任意条 弧弧能到达能到达s 设设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，861a 234578aa 设设a是是 中的一个中的一个字符，定义字符，定义Ia= -closure(J) 其中，其中，J为为I中的某中的某个状态出发经过个状态出发经过一条一条a弧而到达弧而到达的状态集合。

44、的状态集合。 把把NFANFA确定化的过程确定化的过程: : 不失一般性，设字母表只包含两个不失一般性，设字母表只包含两个a a和和b b，我们构造一张表我们构造一张表: :IIaIb -Closure(X)首先，置第首先，置第1行第行第1列为列为 -closure(X)求出求出这一列的这一列的Ia，Ib；然后，检查这两个然后，检查这两个Ia，Ib，看它们是否已在，看它们是否已在表中的第一列中出现，把未曾出现的填入表中的第一列中出现，把未曾出现的填入后面的空行的第后面的空行的第1列上，求出每行第列上，求出每行第2，3列列上的集合上的集合.重复上述过程，知道所有第重复上述过程，知道所有第2，3列

45、子集全列子集全部出现在第一列为止。部出现在第一列为止。IIaIbX,5,15,3,15,4,15,3,15,2,3,1,6,Y5,4,15,4,15,3,15,2,4,1,6,Y5,2,3,1,6,Y5,2,3,1,6,Y5,4,6,1,Y5,4,6,1,Y5,3,6,1,Y5,2,4,1,6,Y5,2,4,1,6,Y5,3,6,1,Y5,2,4,1,6,Y5,3,6,1,Y5,2,3,1,6,Y5,4,6,1,YXY 514236ab ababab. .正规表达式与有限自动机正规表达式与有限自动机(2)构造构造DFA的状态转换矩阵的状态转换矩阵I II Ia aI Ib bX,5,15,3,

46、15,4,15,3,15,3,1,2,6,Y5,4,15,4,15,3,15,4,1,2,6,Y5,3,1,2,6,Y5,3,1,2,6,Y5,4,1,6,Y5,4,1,6,Y5,3,1,6,Y5,4,1,2,6,Y5,4,1,2,6,Y5,3,1,6,Y5,4,1,2,6,Y5,3,1,6,Y5,3,1,2,6,Y5,4,1,6,Y. .正规表达式与有限自动机正规表达式与有限自动机(3)构造重新命名后的状态转换矩阵构造重新命名后的状态转换矩阵DFA M L(M)=L(M)=L(M)Sab012132215334465565634. .正规表达式与有限自动机正规表达式与有限自动机等价状态等价状

47、态:假设假设DFA中有两个中有两个P和和Q,若从若从P出发能识别某一出发能识别某一 字符串字符串X而停止于终态而停止于终态,则从则从Q出发也能识别字符出发也能识别字符 串串X而停止于终态而停止于终态;反之亦然反之亦然,我们就称状态我们就称状态P和和Q 等价等价,若若P和和Q不等价不等价,则说则说P和和Q是可区分的。是可区分的。DFA M的最小化过程的最小化过程: 旨在将旨在将M的状态集分割成一些两两不相交的子集的状态集分割成一些两两不相交的子集, 使得使得任何两个不同的子集中的状态都是可区别的任何两个不同的子集中的状态都是可区别的,而同一子集中的而同一子集中的任何两个状态都是等价的任何两个状态

48、都是等价的,这样以一个状态作为代表而删去其这样以一个状态作为代表而删去其他等价的状态他等价的状态,就获得了状态个数最少的就获得了状态个数最少的DFA。. .正规表达式与有限自动机正规表达式与有限自动机(4)化简化简DFA M将将M的状态分为两组的状态分为两组:终态组终态组3,4,5,6;非终态组非终态组0,1,2考察考察3,4,5,63,4,5,6a3,4,5,6 3,4,5,6b3,4,5,6它不能再分划它不能再分划 再考察再考察0,1,2 0,1,2a=1,3而而1,3 3,4,5,6,1,3 0,1,20,1,2中三个状态不等价中三个状态不等价 将其分为将其分为1,0,2(1 3 , 0

49、|2 1)此时此时,整个分划中含有三组整个分划中含有三组: 3,4,5,6 , 1 , 0,2考察考察0,2b=2,5 3,4,5,6 , 1 , 0,2中任意一个中任意一个 将其分为将其分为:0 , 2aa. .正规表达式与有限自动机正规表达式与有限自动机 至此至此, 整个分划中含有四组整个分划中含有四组:3,4,5,6 , 0 , 1 , 2且每个组均不可再分且每个组均不可再分, 令令3,4,5,6为状态为状态3, 则则: a a b a a|b b b 试画出正规式试画出正规式 b*abb*(abb*)*所对应的所对应的NFAFA正规集正规集正规式正规式DFANFA正规文法正规文法3.3

50、.13.3.23.3.33.3.43.3.5DFA3.3.6三正规式与有限自动机的等价性三正规式与有限自动机的等价性关系定理定理定理: : 上的NFA M所能识别的语言L(M)可以用上的正规式来表示。即：对上的NFA M ，可构造一个正规式，使得L()=L(M).定理定理: : 上任何正规式 ，存在DFA M使得L(M)=L()。即：由 正规式可以构造一个DFA M，使得L(M)L(). .正规表达式与有限自动机正规表达式与有限自动机. .正规表达式与有限自动机正规表达式与有限自动机三正规式与有限自动机的等价性三正规式与有限自动机的等价性1 1、 有限自动机有限自动机=正规式正规式1) 1)把

51、状态转换图的概念拓广把状态转换图的概念拓广，令每条弧上都可以用一个，令每条弧上都可以用一个正规式作标记。正规式作标记。2) 2)在在MM的转换图上加两个结点：的转换图上加两个结点：x, yx, y。从从 x x用用 弧连接到弧连接到MM的所有初态结点；从的所有初态结点；从MM的终态结点用的终态结点用 弧连接到弧连接到y y。这。这个新的个新的NFANFA为为MM，且，且L(M)=L(M)L(M)=L(M)3) 3)通过引入的通过引入的3 3条有限自动机替换规则条有限自动机替换规则逐步消去逐步消去MM中的中的所有结点，直到只剩下所有结点，直到只剩下x x和和y y为止。为止。这样，在这样，在x

52、x至至y y的弧的弧线上的标记就是线上的标记就是 上的正规式，也就是上的正规式，也就是MM接受的正规接受的正规 式。式。. .正规表达式与有限自动机正规表达式与有限自动机1 1、 有限自动机有限自动机=正规式正规式替换规则替换规则: :ABAB A|BA|B A A* *A A B B A A代之以代之以代之以代之以代之以代之以A AB B三正规式与有限自动机的等价性三正规式与有限自动机的等价性 从开始结点出发，探索一切到终点的路径即可。从开始结点出发，探索一切到终点的路径即可。 .当有循环时，即用（当有循环时，即用（.）*解决解决; .当有两条可选路径时，用当有两条可选路径时，用“”解决解决

53、;如此就可顺利写出正规式了如此就可顺利写出正规式了. .正规表达式与有限自动机正规表达式与有限自动机三正规式与有限自动机的等价性三正规式与有限自动机的等价性1 1、 有限自动机有限自动机=正规式正规式12354U1V1U2V2W2W11254V1(U1|U2)*W1V1(U1|U2)*W2V2(U1|U2)*W2V2(U1|U2)*W1例、例、（年，中科软件所）给出下列自动机所描述的语言。（年，中科软件所）给出下列自动机所描述的语言。 解答：从左到右可写为：解答：从左到右可写为：*化简化简 *用集合形式表达为：用集合形式表达为：，021 a，baaa，bbba，b练习：将下面的DFA M所接受

54、的语言表示 为正规式。 a a b a a，b b b 0-1-3: a(ba)*a(a|b)*0-1-2-3: ab(ab)*b(a|b)*q0q1q3q2ab100a,b,1a,b,1. .正规表达式与有限自动机正规表达式与有限自动机2 2、正规式、正规式=有限自动机有限自动机三正规式与有限自动机的等价性三正规式与有限自动机的等价性证明过程证明过程如下(略)（1）若正规式有零个运算符时： 正规式，构造NFA为： 对应正规式，构造NFA为： 对应正规式a，构造NFA为： （2）假设正规式有k(k=1)个运算符时结论成立。（3）则正规式有k+1(k=1)个运算符时：xyxyxya2 2、正规式

55、、正规式=有限自动机有限自动机 R=stR=s*xyN(s)N(s)N(t)xyN(s)N(t)R=s|t2 2、正规式、正规式=有限自动机有限自动机转换规则： 1)由正规式 构造一个如下仅有两个结点x, y的 状态图。2)按所引入的3条正规式分裂规则分裂 。3)重复步骤2直到每个弧上的标记是上的一个字符或一个字符或 为止。4)将所得的NFA M(因为包含弧)进行确定化就得到DFA。 x y 正规式分裂规则 12| 1 22 1 123 1 12 * 23例：根据正规式(a|b)*(aa|bb)(a|b)*, 构造DFA M，使之等价. x y (a|b)*(aa|bb)(a|b)* 1y(a

56、|b)*(a|b)* 2 x(aa|bb) 1y 2 xaa 5 bba|b 6 a|b 1y 2 xa 5 ba 6 abb34ab化简？化简？练习练习1：L(R) =(a|b)*abb，构造，构造NFA使使L(N)=L(R)练习练习2：L(R) =a*b*abb，构造，构造NFA使使L(N)=L(R)练习练习1：L(R) =(a|b)*abb，构造，构造NFA使使L(N)=L(R)解：解：xy(a|b)*abbxyabbabxyabba,bxyababbxy(a|b)*abb练习练习2：L(R) =a*b*abb，构造，构造NFA使使L(N)=L(R)解：解：xybab abxa*b*ab

57、by. .正规表达式与有限自动机正规表达式与有限自动机四、正规文法与有限自动机的等价性四、正规文法与有限自动机的等价性关系定理关系定理:对每一个对每一个右线性正规文法右线性正规文法G或或左线性正规文法左线性正规文法G, 都都 存在一个有限自动机存在一个有限自动机 M, 使得使得 L(M) = L( G) .2. 对每一个对每一个FA M, 都存在一个都存在一个右线性正规文法右线性正规文法GR和和左线性正规文法左线性正规文法GL, 使得使得 L(M) = L(GR) = L(GL) . .正规表达式与有限自动机正规表达式与有限自动机 证明证明1: (1) 右线性正规文法（右线性正规文法（,） （

58、,0,），使得（）（）：），使得（）（）： 字母表字母表与与相同相同,则则 = 令中的令中的 为的一个为的一个状态状态, 的的开始符号开始符号是是开始开始 状态状态, 增加一个增加一个新状态新状态作为作为 的的终态终态, 则则 对中的形如对中的形如a的产生式，构造的一个转换函数的产生式，构造的一个转换函数 (, a)对中形如对中形如a 的产生式，其中的产生式，其中a为终结符或为终结符或 ，构造的，构造的一一 个转换函数个转换函数(, a)1. 正规文法正规文法FAF= Z 0 = S ,S= Z ,. .正规表达式与有限自动机正规表达式与有限自动机例题例题: 已知文法，画出与其等价的已知文法，画出与其等价的： GR(A) ：A0 | 0B | 1DB0D | 1CC0 | 0B | 1DD0D | 1D 从从GR出发构造出发构造NFA M = ，M的状态转换图的状态转换图如右图所示。如右图所示。 显然显然 L(M) = L(GR)。例例:右线性正规