词法分析(编译原理陈火旺).ppt

v词法分析是编译的第一个阶段，在单词的 级别上分析和翻译源程序。 v理论基础： 有限自动机理论 有限自动机理论与正规文法、正规式之间 在描 述语言方面有一一对应的关系。 第3章 词法分析 1 v内容： 状态转换图、正规式和有限自动机、词法分析器的自动 生成 v掌握: 正规式、状态转换图，DFN的概念、NFA的概念，将 NFA转 换为DFA、DFA的化简、正规式与有限自动机间的转换 。 v理解: 正规文法与有穷自动机间的转换 词法分析器的自动产生工具LEX 第3章 词法分析 教学要求 2 本章在编译程序中的地位 表 格 管 理 词法分析器 语法分析器 语义分析与中间代码产生 优化器 目标代码生成器 源程序 单词符号 语法单位 中间代码 中间代码 目标代码 出 错 处 理 3 v执行词法分析的程序称为又称为词法分析 器或扫描器. v词法分析的任务：从左至右逐个地扫描源 程序的字符串, 按照词法规则识别出一个个 正确的单词，并转换为相应的二元式形式， 交给语法分析使用。 v把作为字符串的源程序改造成单词符号串 的词法分析是编译的基础。 3.1 设计词法分析器时应考虑的几个问题 4 3.1.1 词法分析阶段的必要性 v词法分析的工作纳入整个语法分析中一揽子地进行，原则 上是可行的。 v在设计一个编译程序时，通常是把对源程序的结构分析分 为词法分析和语法分析两个相对独立的阶段来完成。 第一，描述单词的结构比描述源程序的其它语法结构 要简单得多，仅使用3型文法也就基本够用了。 第二，由于把词法分析和语法分析分开，可使编译程 序各部分的功能更为单一，整个编译程序的结构也更加清晰 ，从而有利于编译程序的编写和调整。 v上述词法分析和语法分析两个阶段的划分，仅仅是对整个 编译程序的逻辑功能而言，而不一定指的是编译程序的执行 流程。5 3.1.2 词法分析器的输出形式 v词法分析器输出的单词常常表示为二元式形式 (单词种别,单词符号的属性值) 单词种别提供给语法分析程序使用； 单词符号的属性值提供给语义分析程序使用 。 具体的分类设计方法以方便语法分析程序使 用为原则。 6 3.1.2 词法分析器的输出形式 v程序语言的单词符号一般分为五种： 关键字(保留字或基本字)：如 if,then,else,while,do等 标识符：用来表示各种名字，如 x1 常量：如 256，3.14，true, abc 运算符：如 、*、/ 等等 分界符：如 逗号，分号，冒号等 7 3.1.2 词法分析器的输出形式 v单词种别: 一个语言的单词符号如何分类、分为几类、 如何编码主要取决于处理上的方便。通常，每种 单词对应一个整数码。 注意：保留字、运算符和界符的个数确定， 标识符和常数的个数不确定。 保留字：可全体视为一种，也可一字一种； 标识符：统归为一种； 常数：统归为一种,或按整、实、布尔等再分 ； 运算符和界符：一符一种，或统归为一种。 8 3.1.2 词法分析器的输出形式 v单词符号的属性值 单词符号的属性是指单词符号的特征值 。 如果一个种别只含有一个单词符号，那么对于 这个单词符号，种别编码就完全代表它自身了，因 而不需要属性值。 若一个种别含有多个单词符号，那么，对于它 的每个单词符号，除了给出种别编码之外，还应给 出有关单词符号的属性值。 9 3.1.2 词法分析器的输出形式 v单词符号的属性值 标识符和常数 标识符的内部码 (如ASCII码等等)和常数本身 的值 (二进制，逻辑值等)来表示。 标识符的符号表入口地址作为其单词符号的属 性值,常量在其常量表中的入口地址作为其单词符号的 属性值。 每个基本字占一个单词种别，单词符号的属性值缺 省。 对于界符，运算符通常一个符号一个种别，单词符 号的属性值缺省 例: 参见P42.表3.1 单词符号及种别编码 10 3.1.3 词法分析器作为独立子程序 v词法分析可采用如下两种处理结构： 把词法分析程序作为主程序。将词法分析作 为独立的一遍来完成。 把词法分析程序作为语法分析程序调用的子 程序。 v每当语法分析器需要一个单词符号时就调用这 个子程序。 v每一次调用，词法分析器从源程序字符串中识 别出一个单词符号，并把它的内部表示二元组交给语 法分析器处理。 11 3.1.4 源程序的输入、预处理 及超前搜索 n词法分析器工作的第一步是输入源程序文 本。 n输入串一般放在一个输入缓冲区中。词法 分析器的工作可以直接在输入缓冲区中进 行。但在许多情况下，可以先预处理输入 串，识别工作将更方便。（参见P40 图3.1 ） 12 3.1.4 源程序的输入、预处理及 超前搜索 v预处理的原因 源程序中包含回车,换行,多余空白符,注释行等编 辑字符, 它们对程序逻辑功能无任何影响， 在词法分析之 前,首先要剔除掉这些符号,使得词法分析更为简单。 一行语句结束应配上一个特殊字符说明。 有些语言要识别标号区，区分标号语句，找出续 行符连接成完整语句等。 输出源程序清单以便复核。 v 预处理子程序任务 从输入缓冲区中读取源程序，预处理后送入扫描 缓冲区。此时，扫描缓冲区的字符都是有效字符。 词法分析程序这时可以再对扫描缓冲区进行扫描 。 13 3.1.4 源程序的输入、预处理及 超前搜索 v超前搜索 对于有些语言，关键字不保护，关键字与用户自定 义标识符间没有界符，要在上下文环境中识别单词，这 时需要超前搜索方法来识别关键字。 例如：FORTRAN语言： 1.DO10K=1，50 2.DO10K=1.50 v扫描缓冲区的结构 (自学) 14 扫描缓冲区的结构 v词法分析器对扫描缓冲区进行扫描时一般使用 两个指示器，一个指向当前正在识别的单词的开 始位置, 即指向新单词的首字符; 另一个用于向 前搜索以寻找单词的终点。 v不论扫描缓冲区设得多大都不能保证单词符号 不会被缓冲区的边界所打断。因此，扫描缓冲区 最好使用如下一分为二的区域： 起点指示器搜索指示器 15 在扫描缓冲区中扫描 v假定每个半个区可容120个字符，而这两个半区 又是互补的。 v如果搜索指示器从单词起点出发搜索到一个半 区的边缘但尚未达到单词的终点，那么就调用预 处理子程序，令其把后续的120个字符装入另一个 半区。 v认定在另一半区一定可以达到单词的终点。这 意味着对标识符和常数的长度实际上必须加以限 制，否则即使缓冲区再大也无济于事。 23 ：=100； begin .ab1 起点搜索 16 词法分析程序设计 v 设计方法： 写出该语言的词法规则； 把词法规则转换为相应的状态转换图 ； 把各转换图的初态连在一起，构成识 别该 语言的自动机； (4)设计扫描器 17 3.2 正规文法和有限自动机 v 这节介绍词法规则的形式表示(正规式),从正 规式向有限自动机的转化. 正规式 有限自动机 词法分析器 控制程序 自动生成器 转化合成 18 3.2.1 正规文法、正规集与正规式 v正规文法：是chomsky3型文法。 例如：标识符这种单词可以用下面的规则描述 |（|） 表示任意字母， 表示任意数字 注：正规文法描述是正规集的文法，可用于描述程序设计 语言的语法部分。 19 v 对于一个正规文法的语言提炼出一个简洁的公式，用这 个式子来对它进行形式化的表示，这个式子叫正规式。 v正规式：也称正则表达式,是说明单词的模式的一种重要 的表示法（记号）；是定义正规集的数学工具；用来描述 单词符号。 3.2.1 正规文法、正规式与正规集 注：正规集是集合，可有穷也可无穷。 可通过正规式来形式化表示。 v 正规集：由正规文法产生的语言所构成的集合。 20 3.2.1 正规文法、正规式与正规集 下面以标识符为例说明正规式与正规集: 标识符标识符是以字母开头的字母数字串。 若用L表示字母, 用D表示数字, 则标识符可表示为: L(L|D)* 其中并置表示两者的 连接, |表示两者选一, *表示零次或多次引用。 L(L|D)* 为标识符的正规式， 该正规式表示的集合为标识符的正规集。 21 v下面是正规式和它所定义的正规集的递归定义。 1) , 是 上的正规式, 所表示的正规集为 , ; 2) 若 a,则 a 为正规式, 所表示的正规集为 a; 3) 设U,V 为 上的正规式, 所表示的正规集为 L(U),L(V); 则 U|V为 上的正规式, 所表示的正规集为 L(U) L(V); UV为 上的正规式, 所表示的正规集为 L(U) L(V); V* 为 上的正规式, 所表示的正规集为 (L(V)* ; 4) 仅当有限次使用上述三步骤而定义的表达式,才是 上 的正规式 ,而这些正规式所表示的字集才是上的正规集。 3.2.1 正规文法、正规式与正规集 或运算 连接积 22 说明： 1上的一个字指的是由中字符构成的一个有穷序列; 不包含任何字符的序列称为空字（）。 *表示上所有字的全体, 包括空字（）。 例如, 若=a, b 则*=, a, b, aa, ab, ba, bb, aaa, 2 表示不含任何元素的空集 。 注意、 和的区别： 表示不包含任何字符的序列,它是正规集中的一个元素 ； 表示不含任何字的集合, 它是一个空的正规集； 表示由空字组成的集合。 3.2.1 正规文法、正规式与正规集 23 3 使用括号可改变运算符的运算次序。 若规定*优先于, 优先于|, 则在不混淆情况 下,可省 去括号。 4 R自身的n次连接记为 Rn=RRR 5 R0=, R*=R0R1R2R3, R*为R的闭包 R+=RR*, 称R+是R的正闭包。 闭包R*中的每个字都是由R中的字经过有限次连接 而成的。 6 对于正规式R和S, 若它们表示的正规集L(R)=L(S), 则称R和S等价, 记为R=S。 3.2.1 正规文法、正规式与正规集 24 v 正规式具有下列性质： (1) 交换律：R|S = S|R (2) 结合律：R|(S|T) = (R|S)|T, R(ST) = (RS)T (3) 分配律：R(S|T) = RS|RT, (R|S)T = RT|ST (4) 同一律：R = R = R 3.2.1 正规文法、正规式与正规集 例3.1 =a,b, R=a(a|b)*是上正规式,试求R表示的正规集。 解: 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, 上所有以 a为首的字 25 例3.2 判断下述正规式之间是否等价： (1)b(ab)*与(ba)*b (2)(ab)*与a*b* 解: (1) b(ab)*对应的正规集是b后面出现任意多个ab对 L(b(ab)*)=b,bab,babab, (ba)*b对应的正规集是b前面可出现任意个ba对 L(ba)*b)=b,bab,babab, , 因此两者等价。 正规式b(ab)*及(ba)*b都描述以b开头且其后跟以零个或任意 多个ab所组成的字符串等。故我们说两个正规式等价， (2)(ab)*对应的正规集以任意个ab对出现，即 ababab, 而a*b*对应的正规集则是任意个a后接任意个b, 即 aabb, 因此两者不等价。 26 例3.3: 设 =a,b, 则正规式和正规集: ab (ab)(ab) a* (ab)* aab* a,b aa,ab,ba,bb ,a,aa,aaa,aaaa,= an|n0 ,a,b,aa,ab,ba,bb,aaa,aab,abb, bab,bba,bbb . = a, b* a,ab,abb,abbb,abbbb,. = abn |n0 27 v通过这一节的学习，要求能根据给出的简单正 规式，会写出其表示的正规集。 例3.4 令=a,b,其正规式和正规集如下： 正规式 正规集 1. ba* 2. a(a|b)* 3. (a|b)*(aa|bb)(a|b)* 上所有以b为首后跟着任意多个a的字。 上所有以a为首的字。 上所有含有两个相继的a或 两个相继的b 的字。 28 例3.5: 令=A,B,0,1 , 则： 正规式 正规集 v(A|B)(A|B|0|1)* v(0|1)(0|1)* v问: 正规式 , , 0 , 110 , 0|1 , 1* 表示的正规 集是? 答: 正规集分别是 , , 0, 110, 0,1, ,1,11,111,=1* =1n | n0。 上的“标识符”的全体 =A,B.A,B,0,1* 上“数”的全体 =0,1.0,1* 29 3.2.1 正规文法、正规式与正规集 v 三个概念之间的关系： 一个正规语言可以用正规文法来定义，也可以用正规 式来定义，有些正规语言很容易用文法定义，有些则用正 规式定义更容易。 一个正规语言是一个集合（正规集），那么这个集合 可以用正规文法来定义，也可以用正规式来定义。 30 3.2.2 有限自动机 v有限自动机（Finite Automata FA） 是一种识别装置，它能准确地识别正规集 。它为词法分析程序的构造提供了方法和工具。 是一种具有离散输入输出系统的数学模型 。它具有有限数目的内部状态，系统可以根据 当前所处的状态和面临的输入字符决定系统的 后继行为。其当前状态概括了过去处理的信息 。 31 3.2.2 有限自动机 v有限自动机模型： 输入带 注：状态分为初始状态、中间状态和终止状态。 终止状态可以有若干个，而初始状态一般只有一个。 状态变换 z e d c b a 有限状态控制器 读头 32 3.2.2 有限自动机 v有限自动机模型： 输入带 状态: 初态 z e d c b a 有限状态控制器 读头 z e d c b a 有限状态控制器 读头 状态: 中间 33 3.2.2 有限自动机 v有限自动机模型： 输入带 状态: 终态 z e d c b a 有限状态控制器 读头 z e d c b a 有限状态控制器 读头 状态: 非终态 注：读头全部读完，且此时状态为终态，则说明此输入串正确。 注：读头全部读完，而此时状态不是终态，则说明此输入串错误。 状态的变换和符号的读入用一个图形结构来表示。（状态转换图） 34 3.2.3 状态转换图 P41 v状态转换图：状态转换图是一张有限方向图，只包含 有限个状态，即有限个结点。P41 1. 结点代表状态，用圆圈表示 2. 终止状态用双圈表示 3. 初始状态前标记符号“ ”来表示（可省） 4. 状态之间用箭弧连结，箭弧上的标记代表在射出结点 （即箭弧始结点）状态下可能出现的输入字符或字符类， 箭弧标记表示状态转换的条件。 5. 状态图有一个初态，多个终态。 6. 状态转换图可识别一定的字符串（单词）。 7. 状态转换图用于表示单词结构,从状态转换图的初态到 终态间,每条路径上字符的连接,就构成了该状态图的合法 单词。 35 例3.6 P41 图3.2(a)表示： 在状态1下，若输入字符为X，则读进X，并转换 到状态2。 若输入字符为Y，则读进Y，并转换到状态3。 若输入字符非X和非Y，则此转换图不工作。 2 3 1 Y X 36 例3.7 P41 图3.2(b)表示：识别标识符的状态转换图如下: 其中状态0为初态，2为终态； 识别标识符的过程是：从初态0开始，若在状态0下输入字 符为字母，则读进它，并转换到状态1。 在状态1之下，若输入字符为字母或数字，则读进它，并 重新进入状态1。 一直重复这个过程直到发现输入字符不再是字母或数字时 （这个字符已经被读进）进入状态2； 状态2是终态，意味着到此已识别出一个标识符； 终态上打个星号表示单词尾部多跟一个字符,应该去掉。 若在状态0时输入的字符不为“字母”，则意味着这个转 换图不工作。 012 2 (b) 字母 字母或数字 其它 * 37 (c) 012 2 数字 数字 其它 * 例3.8 P41 图3.2(c)表示：识别无符号整数的状态转 换图如下： 在状态转换图中, 到达单词符号的终态时即给出相应 的单词编码。若到达终态时多读入了一个符号,则识别出该 单词后再将多读入的那个符号退回。对此类情况的处理方 法是在终态上以*作为标识。 38 例3.9 P41 图3.2(d)表示：识别实数的状态转换 图如下： 01 数字 数字 其它 * 2345 6 数字数字 数字 E或e+或 -数字 E或e 其它 数字 7 (d) 初态0终态7之 间任意一个路径都 表示一个实数。 小数形式的实数： 指数形式的实数： 该转换图可以识别下面形式的一些实数: 123. , .123, 123E3 ,123.456,123.45e2 , .123E+10, 123.456E-3 等 39 状态转换图识别字符串: 综合例 v一个非常重要的事实是，大多数程序语言的单 词符号都可以用状态转换图予以识别。 v作为一个综合例子，教材P42-P46.构造了一个 识别某个简单语言的所有单词符号的状态转换图 ，并给出了对应的词法分析程序。 v希望同学们好好读一下。为完成的实验 - 设 计并实现一个小语言的词法分析程序, 可以以这 个例子做参考。 40 识别简单语言单词符号的转换图 v参见P43.图 3.3 7 非* + 3 12 字母 0 * 非字母与数字 字母或数字 = 数字 数字 空白 * 4 * 非数字 5 6 8 * 9 * 13 其它 2态：识别标识 符和关键字 4态：识别整常数 8态：识别* 9态：识别* 13态：识别错误 5态：识别= 6态：识别+ 41 v状态转换图容易用程序实现: 即容易由转换图编写词法分析程序。 v最简单的办法是让每个状态结点对应一小段程 序。 根据画出的识别单词的状态转换图构造词 法分析程序，每个状态对应一段程序，完成到达 此状态的工作；词法分析程序的控制程序模拟状 态转换图的状态转换。 3.2.4 状态转换图的实现 (自学) 42 v状态转换图实质上就是一个抽象的程序流程图 。 转换图忽略了程序的实现细节，着力刻画了单词符 号识别的本质。 v转换图与程序结构之间存在下述对应关系， 并可以据此构造相应的程序： 初态对应程序的开始； 终态对应程序的结束，一般是一条返回语句，且 不同的终态对应不同的返回语句； 状态转移分叉对应分情况或者条件语句； 转换图中的环对应程序中的循环语句； 3.2.4 状态转换图的实现 43 3.2.4 状态转换图的实现 v为便于程序实现,假设每个单词间都有界符或运 算符或空格隔开,并引入下面的全局变量及子程序 : 1) Ch 字符变量存放刚读入的源程序字符; 2) Token 单词字符串存放构成单词的字符串; 3) Getchar 读一个字符到 Ch中子程序; 4) GetBC 读一个非空白字符到Ch中子程序; 5) Concat 把Ch中字符连接到Token 之后子程 序; 6) isLetter 判断Ch中字符是否为字母子程序; 7) isDigit 判断Ch中字符是否为数字子程序; 8) Reserve 用Token中的字符串查找保留字表,并返回 保留字种别码,若返回零,则非保留字子程序; 9) Retract 把Ch中字符回送到缓冲区子程序; 44 状态结对应程序段的编写(1) v不含回路的分叉结对应条件语句或情形语句 j 数字 i / 字母 k l P45.图3.4(a) 的状态结 i n状态结 i 对应的程序段: Getchar(); If(IsLetter()状态j的对应程 序段; Else if(IsDigit() 状态k的对 应程序段; Else if(ch=/) 状态l的对应程 序段; Else 错误处理程序段 或接其他状态图的程序; 45 状态结对应程序段的编写(2) v含回路的状态结 对应循环语句 n状态结 i 对应的程序段: Getchar(); While(IsLetter() or IsDigit() Begin concat(); Getchar(); End; 状态j的对应程序段; 其它 ij 字母或 数字 P45.图3.4(b) 的状态结 i 46 状态结对应程序段的编写(3) v终态结(如图3.3中的状态5、6、9、10、11、 12、13)对应return(Code,Value)语句,返回单词 符号的内部表示二元式给语法分析器。 v带*号的终态结(如图3.3中的状态2、4、8)多 读进了一个不属于现行单词符号的字符,这个字 符应退回,即搜索指示器要回调一个字符位置,这 时除了Return外，还要调用Retract过程来完成 这项工作。 47 状态结对应程序段的编写(4) v多种单词出口的终态结，如图3.3中的状态2 ，既是标识符的出口又是关键字的出口，为了 确认到底是关键字还是用户自定义的标识符， 需要对strToken查询保留字表，这由整型函数 过程Reserve来完成。若函数值为0，则表示 strToken中的字符串是一个标识符；否则，表 示是关键字编码。 48 状态结对应程序段的编写(5) v初态结(如图3.3中的状态0)，要作一些初 始化的工作,比如：设置指示器的值，对ch ，strToken等进行初始化。 v对于某些状态(如图3.3中的状态1、3)， 需要将ch的内容送进strToken拼接单词，则 还要调用Concat过程。 49 本节内容及关系 正规表达 式E 用 正规集L(E) 表示,值集 正规文法G 正规语言 L(G) 用 产生 单词符号结 构的描述 词法分析器(扫描器) 用手工实现 有限自动机 FA M 状态转换图 单词符号集 L(M) 形式化 识别,接受 三者相同 等价 等价 等价 50 作业： P64 8 (1) (2) 9 (1) 51 (b) 0 12 2 0|1 0 其它 * 0|1 012 2 (a) 字母 字母 其它 * 数字 52 3.2.5 确定有限自动机 v确定有限自动机（DFA）(Deterministic FA) 一个确定有限自动机(DFA M)是一个五元式 : DFA M=(S, , , s0, F) 注：这里确定的含义，就是状态转换关系是一个函数，即对 于给定的当前状态s和当前读入的字符a有唯一确定的下一状 态s。 1. S 是有限状态集； 2. 是一个有穷字母表,每个元素为一字符； 3. s0S,是唯一的初态; 4. F S,是终态集（可空）。 5. 是一个单值映射函数, (s,a)=s，指明若当前的 状态为s，而输入字符为a时，则下一个状态是s； 53 3.2.5 确定有限自动机 vDFA表示 状态转换矩阵 状态转换图 DFA的映射关系可以用一个矩阵表示： 该矩阵的行表示状态 列表示输入字符，矩阵元素表示(s,a)的 值 该矩阵称为状态转换矩阵或状态转换表 54 例如3.10 P48 DFA M=( 0,1,2,3, a,b, , 0, 3) 其中为: (0,a)=1 (1,a)=3 (2,a)=1 (3,a)=3 (0,b)=2 (1,b)=2 (2,b)=3 (3,b)=3 状态转换矩阵可表示为: 状态图可表示为: ab 012 132 213 333 状 态 字 符a 0 1 2 a b b a a b b 3 55 DFA识别(读出,接受)字 vDFA识别字： 对于*中的任何一个字，若存在一条从 初态结点到某一终态结点的通路，且这条通路上 所有箭弧的标记符连接成的字等于，则称为 DFA M所识别。 例: P48 图3.5的DFA识别字abbab, 因为存 在路径 012333；但不接受字ababa, 因为不存在 识别路径。 a,b a 0 1 2 3 a b b ab 56 DFA识别字、语言L(M) vDFA识别空字 若M的初态结点同时又是终态 结点，则称空字可以为DFA M所识别。 例: 图3.5的DFA不识别空字。 vDFA M所能识别的字的全体记为L(M)。 例：P48 图3.5的DFA M识别的字的全体 L(M) =上所有含有相继两个a或相继两个b 的字 a,b a 0 1 2 3 a b b ab 57 DFA：练习1 设有 DFA M=(0,1,2,a,b,0,1,2) 其中： （0,a)=2; （0,b)=1 （1,a)=; （1,b)=2 （2,a)=2; （2,b)=2 问：该DFA有几个状态？几个输入字符？初态？终 态？画出其转换图。 n解：有0，1，2共三个状态。0为初态，1和2为终态 。输入字符为a,b两个。 其状态转换图如: a,b a 0 1 2 bb 58 3.2.6 非确定有限自动机 vS是一有限状态集; v是一个有穷字母表,每个元素为一字符; vF S ,是终态集。 vS0 S, 是初态集; v是一个多值映射函数, S * 2s 其含义为:在状态S,输入字时,将转换到下一状态集 2s。 一个非确定有限自动机(NFA M)是一个五元式: NFA M=(S, , , S0, F) 而DFA 是字符 注：非确定主要是指后继状态可有多个。 DFA是NFA的特例。 59 如: 一个NFAM也可用状态图表示。 3.2.6 非确定有限自动机 a 0 bb a,b a|b 1 2 3 a 60 假定DFA有m个状态、n个输入符, 则状态转换图含m个状 态, 每个状态最多有n条输出边与其它状态相连, 每条边 用中一个字符作标记，整个图含一个初态和若干个终态 。 假定NFA有m个状态、n个输入字, 则状态转换图含m个状 态, 每个状态最多有n条输出边与其它状态相连, 每条边 用*中一个字作标记，整个图含若干个初态和若干个终 态。 NFA的状态转换函数是一多值函数，即(si, )= 某些状态的集合，它表示由当前状态和当前输入字符不 能唯一确定下一状态，即允许同一状态对同一输入字可 有不同输出边；而DFA的状态转换函数是一个单值函数 。 NFA和DFA的主要区别 61 例3.11 DFA M=(s0,s1,s2, a,b, , s0,s2), 且 (s0,a)= s1, (s0,b)= s2, (s1,a)= s1 (s1,b)= s2, (s2,a)= s2, (s2,b)= s1 试给出M的状态转换图与状态转换矩阵。 解：状态转换图： 状态转换矩阵： 字符 状态 ab s0s1s2 s1s1s2 s2s2s1 a s 1 2 s 2 s0 ab b a b 62 例3.12 NFA M=(s0,s1,s2,a,b, ,s0,s2,s1), 且(s0,a)=s2, (s0, b)=s0,s1, (s1,a)= (s1,b)=s2, (s2,a)=, (s2,b)= s1 试给出Mn的状态转换图与状态转换矩阵。 解: 状态转换图: 状态转换矩阵： 字符 状态 ab s0s2 s0,s1 s1s2 s2s1 2 s1 s0 s2 b bbb a 63 NFA识别字、空字、L(M) v1. NFA识别字 对于*中的任何一个字，若 存在一条从初态结点到某一终态结点的通路，且 这条通路上所有箭弧的标记符连接成的字(忽略 那些标记为的弧)等于，则称为NFA M所识别( 读出或接受)。 v2. NFA识别空字 若M的初态结点同时又是终 态结点; 或者存在一条从某个初态结点到某个终 态结点的通路，则称空字可以为M所识别。 v3. NFA M识别的上字的全体记为L(M)。 64 例3.13 P49 图3.6的 NFA M： a 5Y 12 a 6 a a b X b 3 4b b 识别字 abbab，路径是X55142666Y X555555 X5555514 X555513 X55514 不接受字 ababa，不接受 L(M)=上所有含有相继两个a或相继两个b的字 n注意: 图3.5的DFA与图3.6的NFA识别的字集相同， 两个FA等价。 65 NFA：练习 练习1 如图的FA M 是NFA吗? L(M)=? n是NFA nL(M) =ambn|m0,n0 练习2 如图的FA M 是NFA吗? L(M)=? aa 0 a,b 1 a,b 2 bb a,b n是NFA nL(M)=所有含有相继两个a 或相继两个b的字 a b 01 b 2 a 66 3.3 正规式到有限自动机的构造 v由正规式与有限自动机的等价性: P53 (1)对任何FA M，都存在一个正规式r,使得L(r)=L(M) 。 (2)对任何正规式r，都存在一个FA M,使得L(M)=L(r) 。 67 3.3 正规式到有限自动机的构造 3.3.1 由正规式构造等价的NFAM 3.3.2 NFA M的确定化 3.3.3 具有动作NFA M的确定化 3.3.4 DFA M的化简(最小化) 68 3.3.1 由正规式构造等价的NFAM X2 Y R v由正规式构造等价的NFA M的方法：P50 (1) 将正规式R构造一个如下仅有两个结点X,Y 的拓广转换图。 69 (2) 采用下述三条转换规则构造NFA M。 s i s j r 1 | r2 1. r 1 r2s i s j 2.s j s i r 1 r2 s i r 1 r2 s j s k * 3.s j s i s i r 1 r 1 s j s k 3.3.1 由正规式构造等价的NFA M 70 例3.14 构造 b*(d|ad)(b|ab)+ 对应的NFA。 解: 首先用R+=RR*把正规式改造为 b*(d|ad)(b|ab)(b|ab)* 然后构造其NFA M，如下图所示： 3.3.1 由正规式构造等价的NFAM (3)重复步骤2不断加入新结点直到每个弧上的标记是 上的一个字符或为止。 71 b*(d|ad)(b|ab)(b|ab)* XY (b|ab)* d|ad b*b|ab X132Y abad b d b|ab b 41235XY b X41 d 2 6 b b 35 78 a dba a b Y 72 例3.15 P50 构造 (a|b)*(aa|bb)(a|b)*对应的NFA。 解: 构造其NFA M，如下图所示： (a|b)*(aa|bb)(a|b)* XY (a|b)*aa|bb(a|b)* X12Y bb a|b aa a|b 312X 4Y 5 6 123X4 a b a b a b a b 2 Y 73 3.3.2 NFA M的确定化 v定理：对于每一个NFAM存在DFAM，使得L(M)=L(M) 。 即设L是一NFA接受的正规集，则存在一个DNF接受 L。 v子集法：一种将NFA转换成接受同样的语言的DFA的算 法。 v基本思想：该DFA的每一个状态对应NFA的一组状态。 该DFA使用它的状态去记录在NFA读入一个输入符号后可能 达到的所有状态。 该状态表示这个NFA的状态的一个子 集T。 74 3.3.2 NFA M的确定化 v算法： 由NFA M=（S, , f, S0, Z)构造一 个等价的DFAM=(Q, , , I0, F) 取I0= S0； 若状态集Q中有状态Ii=s0,s1, ，sj，skS ，0kj，而且M机中有f(=s0,s1, ， sj,a)=f(s0,a) f(s1,a)f(s2,a)f(sj,a)=s0,s1, st= It 若It不在Q中，则It加入Q。 重复步骤2 ，直到Q中无新的状态加入为止。 取终态F=I|IQ且IZ 75 3.3.2 NFA M的确定化 v构造状态子集表 上述过程也可用表格法来描述。其中列是字 符集的字符，行是Q中的各状态，开始仅包含I0 状态，随着算法的执行，Q的状态逐渐增多直至不 再增多为止。表格的元素是映射函数。 76 3.3.2 NFA M的确定化 v由状态子集表构造DFA M的状态转换表 状态子集表的每个状态子集是DFA M的一 个状态 - 重新编号。 DFA M唯一的初态是I0对应的状态子集。 DFA M的终态是含有原来的终态Y的状态子 集。 77 例：设有NFA M=(X,Y,0,1, f,X,Y)且 f(X,0)=X, f(X,1)=Y, f(Y,0)=X,Y, f(Y,1)=X 把它确定化。 解：1.M的初态：I0=X则Q中就有了I0状态； 2.由Q中的状态I0=X，查看M机有 f(X,0)=X, f(X,1)=Y=I1, 此时Q里就有I0 ，I1 由Q中的状态I1=Y，查看M机有 f(Y,0)=X，Y =I2, f(Y,1)=X=I0, 此时Q里就有I0 ,I1,I2 由Q中的状态I2=X,Y，查看M机有 f(X,Y,0)=X，Y =I2,f(X,Y,1)=X,Y=I2, 此时Q里就 有I0 ,I1,I2 3.F=I1,I2 I2=X,YI2=X,Y I2=X,Y I1=YI2=X,Y I1=Y I1=YI0=X I0=X 1 0 字符 Q X Y 0 1 1 0 0 78 I2=X,YI2=X,YI2=X,Y I1=YI2=X,YI1=Y I1=YI0=X I0=X 1 0 字符 Q CCC BC B BAA 1 0 Q A B 1 1 1 00 C 0 解：1.构造状态子集表： 3.确定的DFA M： 2.重命名： 79 NFA确定化：练习1 设有NFA M=(x,y,a,b,x,y), 其中定义如 下: (x,a)=x,y (x,b)=y (y,a)= (y,b)=x,y 试构造相应的 DFAM。 解：1.构造状态子集表： a x b y a b b NFA xx,y y x,y x,y x,y y x,y a a 0 2 1 bb DFA b x 0 b a 字符 Q 1 2 11 1 210 b a Q 2.重命名： 3.确定的DFA M： 80 3.3.3 具有弧的NFA M确定化 v_闭包 可以从某状态或某些状态通过弧所能到达的 所有状态的集合。 假定I是NFA M的状态集的一个子集， v状态集合I的_闭包（_CLOSURE(I)形式定义 如下： (1)若siI, 则si_CLOSURE(I)； (2)若siI, 则从si出发经过任意段的弧所能到达的 任意 状态sj属于_CLOSURE(I)。 81 例3.16：若 I=X 则_CLOSUR(I)=X, 5, 1 I=5, 1 I=2 a 5Y 12 a 6 a a b X b 3 4b b _CLOSUR(I)=5, 1 _CLOSUR(I)=2, 6, Y 82 3.3.3 具有弧的NFA M确定化 v闭包间的转换： 设_CLOSURE(I)=s1 , s2 ,. ， sk 当读入字母表中的字母a时，它转换到另一闭包 _CLOSURE(J)。 对NFA M的任一状态子集I, 若a是中的 一个字符，则定义 Ia=_CLOSURE(J) 其中J= q|(q, a)=q 且 qI; a 表示: J是从I中某一状态出发经过a所能到达 的所有状态的集合。 83 例3.17 对下图,取I=_CLOSUREI=1,2, 求从状态I出发经一条有向边a所能 到达的状态集J和_CLOSURE(J)。 a 1 5 2 4 a 6 3 7 8 a J=5, 3 ,4 Ia=_CLOSURE(J)=5, 6, 2, 3, 8, 4, 7 84 设有NFA M=(S, , , S0 , Z)构造一个等价的 DFA M=(Q, , ,I , F) 设= a1,a2, , ak v构造一张状态转换子集表 第一行第一列为 I=_CLOSUR(S0)，以此I求 Ia1,Ia2,Iak 。 把没有在第一列出现过的Iai填入空行第一列，以此 Iai为 新的 I，再求Ia1,Ia2，Iak。 重复的过程，直到所有求出的Iai都在第一列出现为止。 I Ia1 Ia2 Iak _CLOSUR(S0) 3.3.3 具有弧的NFA M确定化 85 例3.17 正规式(a|b)*(aa|bb)(a|b)*的NFA M如下: 试将其确定化为DFA M。 3 4 251X6 a b a b a b a b 2 Y 86 解:构造一张状态子集表 = a, b IIaIb X,1,21,2,31,2,4 1,2,3 1,2,3,5,6,Y 1,2,4 1,2,41,2,31,2,4,5,6,Y 1,2,3,5,6,Y 1,2,4,5,6,Y 1,2,4,6,Y 1,2,4,5,6,Y 1,2,3,6,Y1,2,4,5,6,Y 1,2,4,6,Y1,2,3,6,Y1,2,4,5,6,Y 1,2,3,6,Y 1,2,3,5,6,Y 1,2,4,6,Y 3 4 251X6 a b a b a b a b 2 Y 87 3.3.3 具有弧的NFA M确定化 v由状态子集表构造DFA的状态转换表。 状态子集表的每个状态子集是DFA M的一个状 态 - 重新编号。 DFA M唯一的初态是_CLOSUR(S0)对应的状态 子集。 DFA M的终态是含有原来的终态Y的状态子集 。 88 由状态子集表构造DFA的状态转换矩阵: I Ia Ib X, 5, 1 初 0 5, 3, 1 1 5, 4, 1 2 5, 3, 1 1 5, 3, 1, 2, 6, Y 3 5, 4, 1 2 5, 4, 1 2 5, 3, 1 1 5, 4, 1, 2, 6, Y 5 5, 3, 1, 2, 6, Y 终3 5, 3, 1, 2, 6, Y 3 5, 4, 1, 6, Y 4 5, 4, 1, 6,Y 终 4 5, 3, 1, 6, Y 6 5, 4, 1, 2, 6, Y 5 5, 4, 1, 2, 6, Y 终5 5, 3, 1, 6, Y 6 5, 4, 1, 2, 6, Y 5 5, 3, 1, 6, Y 终6 5, 3, 1, 2, 6, Y 3 5, 4, 1, 6, Y 4 89 Qab 012 132 214 335 464 564 635 a 2 32 5 2 42 6 1 2 0 a b ba a ba b b a a b b 于是得到对应的DFAM如下：重命名： 90 NFA确定化的实质是以原有状态集上的 覆盖片作为DFA上的一个状态，将原状 态间的转换改为覆盖片间的转换，从而 把不确定问题确定化。通常经过确定化 之后，状态数增加，而且可能出现一些 等价状态，这时需要化简。 91 3.3.4 DFAM的化简 vNFA确定化所得的DFA可能含有多余的状态需化简。 v所谓一个DFA M=(S, , , s0, F) 的化简(最少化、最小 化), 是指寻找一个状态数比较少的DFA M, 使L(M)=L(M) 。 v化简的原则：受的语言是等价的。 v思想-划分法 1.把DFA M的状态集S分划成一些不相交的子集, 使属 于同一子集的状态都等价, 属于不同子集的状态可区别。 2.从每个子集选一个代表, 消去其他等价状态。 3.把那些原来导入子集各状态的弧都导入此代表状态 。 v化简后的DFA M 满足下述条件： (1)无多余状态； (2)状态集中无相互等价的状态。 92 状态的等价和可区别定义 v定义: 设s,tS是两个不同的状态, 若对任何 *, 从s(或t)出发能读出而停于某个终态 ，则称s和t是等价状态。否则，称s和t是可区别的 ，即不等价的。 v例如: 终态和非终态是可区别的，因为终态能读 出空字，而非终态不行。 v又如：P51.图3.8的DFA中的状态1和2是可区别的 ，因为状态1能读出a而停于终态，但状态2读出a后 不能停于终态。 v等价状态定义了状态集合上的等价关系。因此， 状态集合能被划分成等价类。 93 3.3.4 DFA M的化简 vDFA M的化简方法： (1)首先将DFA M的状态集S中的终态与非终态分 开,形成两个子集,得到基本划分。 (2)对当前已划分出的I(1),I(2),I(m)子集, 看 每个I是否能进一步划分。对某个I(i)= s1,s2,sk, 若存在输入字符a使得Ia(i) 不全包含在当前划分的某个子集I(j)中, 即跨越 两个子集, 则将I(i)一分为二。 (3)重复(2), 直到每个子集均不能再分。 不能再分是指子集要么仅有一个状态，要么 有多个状态但这些状态是等价的。 94 例3.15 化简由例3.14得到的DFA。 2 32 5 2 4