《Ch3词法分析》PPT课件.pptVIP

编译原理教程,第二章 词法分析,2,本章在编译程序中的地位,表 格 管 理,词法分析器,语法分析器,语义分析与中间代码产生,优化器,目标代码生成器,源程序,单词符号,语法单位,中间代码,中间代码,目标代码,出 错 处 理,3,P8. 词法分析概述,任务：从左到右逐个字符地对源程序扫描，产生出一个个单词符号。 输入：源程序。 输出：单词符号。 单词符号：保留字、标识符、常数、算符、界符。 词法分析依循的是语言的构词规则。 描述词法规则的工具是正规表达式和有限自动机。 词法分析器(扫描器)可以采用两种处理结构： P8.图2-1(a) 作为独立的主程序； P8.图2-1(b) 作为语法分析程序调用的子程序。,教学内容,2.1 词法分析器设计方法 P8.11. 单词符号的分类、词法分析器的输出形式 状态转换图 2.2 一个简单的词法分析器示例 P11.15. C语言子集的单词符号、状态转换图及其实现 2.3 正规表达式与有限状态自动机 P15.19. 正规表达式 、正规集、 NFA、 DFA 2.4 正规式到有限自动机的构造 P19.27. 正规式 NFA DFA 最简DFA 2.5 词法分析器的自动生成工具LEX P27.29.,重点难点掌握,重点掌握,重点掌握,词法分析涉及的概念及关系,词法分析程序(扫描器),输入,输出,自动生成工具LEX，用正规式描述单词, 扫描器象有限自动机一样工作(2.5),2.1 词法分析器的设计方法-输入、预处理,词法分析器工作的第一步是输入源程序。 输入串一般放在一个输入缓冲区中。词法分析器的工作可以直接在输入缓冲区中进行。但在许多情况下，可以先预处理输入串，识别工作将更方便。 预处理工作包括对空白符、跳格符、回车符和换行符等编辑性字符的处理，及删除注解等。 可以构造一个预处理子程序完成上面的工作。每当词法分析器调用它时就处理出一串确定长度的输入字符，并将其装入指定的缓冲区 - 扫描缓冲区中。 这样分析器就可以在扫描缓冲区中直接进行单词符号的识别工作。,7,输入、预处理：词法分析第一步,词法分析程序,扫描缓冲区的结构,词法分析器对扫描缓冲区进行扫描时一般使用两个指示器，一个指向当前正在识别的单词的开始位置 (首字符)，另一个用于向前搜索以寻找单词的终点。,扫描缓冲区使用互补的两个半区，每个半区假设120个字符。 如果搜索指示器从单词起点出发搜索到一个半区的边缘但尚未达到单词的终点，那么就调用预处理子程序，令其把后续的120个字符装入另一个半区，搜索指示器在另半区继续搜索。认定在另一半区一定可以达到单词的终点，即对单词限定了长度。,9,2.1.1 单词符号的分类和输出形式,P8. 词法分析程序的功能： 输入源程序，扫描识别分解，输出单词符号 程序语言的单词符号一般分为5类： (1) 保留字 (也称关键字、基本字)： 如C语言中的 int，if，while，for 等。这些字保留了语言所规定的语义，是编译程序识别各类语法成分的依据 (2) 标识符：用来标记各种名字：常量、数组、类型、变量、过程、函数等，如变量名 abc12 等,问题：标识符和名字的区别？,10,1. 单词符号的分类,P9.程序语言的单词符号一般分为5类： (3) 常数：包括各种类型的常数，如 256，3.14，true,abc 等 (4) 运算符：如 、*、/ 、= 等 (5) 分界符：在语言中作为语法上的分界符使用，如 逗号，分号，冒号，圆括号，空白符号等,注意：一个程序语言的保留字、运算符和界符的个数是确定的；而标识符和常数的使用则不限定个数。,11,P9. 单词符号的内部表示是二元式： 单词种别通常用整数编码 单词种别码提供给语法分析程序使用。 一个语言的单词符号如何分种，分成几种，怎样编码，取决于处理上的方便。 单词符号自身的属性值也称内码值 指单词符号的特征值，是编译中其他阶段如语义分析阶段所需要的信息。,2. 单词符号的输出形式,12,P9.单词种别如何编码？ 标识符一般统归为一种。 常数则宜按类型（整、实、布尔等）分种。 保留字可视其全体为一种，也可以一字一种。采用一字一种的分法实际处理起来较为方便。 运算符可采用一符一种的分法，但也可以把具有一定共性的运算符视为一种。 界符一般采用一符一种的分法。 例: P11.表2.1 C语言子集的单词种别编码,单词符号的种别编码,单词符号自身的属性值,P9.单词符号自身的属性值规定： 如果一个种别只含一个单词符号，那么种别编码就完全代表了这个单词符号，因而不需要属性值。 如果一个种别含有多个单词符号，那么对于它的每个单词符号，除了给出种别编码之外，还应给出有关单词符号的属性值，以便把同一种别的单词区分开来。 注意：标识符的属性值可以是标识符自身的字符串，也可以是指向符号表入口的指针；常数的属性值可以是常数本身的二进制数值，也可以是指向常数表入口的指针。 例: P11.表2.1 C语言子集的单词内码值,单词符号的分类和输出形式：例子,C代码段： while (i=10) i- -; 经词法分析器处理后，它将转换为如下的单词符号二元式序列：,如标识符单词 i 对应的二元组 , = , _ ,见P11.表2.1，使用了助记符,15,2.1.2 状态转换图(P9.),在词法分析中，状态转换图用来： 描述单词符号的结构 识别单词符号 是设计词法分析器的重要工具 手工生成词法分析程序的方法:,得到：词法分析程序,先构造：识别单词符号的状态转换图,16,状态转换图,P9.状态转换图是一张有限方向图，只包含有限个状态，即有限个结点。 结点代表状态，用圆圈表示 终止状态用双圈表示 初始状态前标记符号“ ”来表示 状态之间用箭弧连结 箭弧上的标记代表在射出结点即箭弧始结点状态下可能出现的输入字符或字符类，箭弧标记可看成状态转换的条件。,17,状态转换图例： P9.图2-2,该状态转换图表示, 在状态1下: 若输入字符为x，则读进x，并转换到状态2。 若输入字符为y，则读进y，并转换到状态3。 若输入字符非x和非y，则此转换图不工作。,状态转换图的作用：描述单词符号的结构，识别单词符号。,状态转换图识别标识符：P10.图2-3(a),该状态转换图描述了单词符号“标识符”的结构。标识符是字母打头的字母数字串。 该转换图识别标识符的过程是: 从初态0开始，若在状态0下输入字符是字母，则读进它，并转入状态1。在状态1之下，若输入字符为字母或数字，则读进它，并重新进入状态1。一直重复这个过程直到发现输入字符不再是字母或数字时(该字符已被读进)就进入终态2，识别结束。,19,状态转换图识别标识符: 续,识别标识符的状态转换图2-3(a)中，状态2是终态，它意味着到此已经识别出一个标识符。 终态上打个*号，表示多读进了一个不属于标识符部分的其他字符，应把它退还给输入串。 如果在状态0时输入字符不为“字母”，则意味着这个转换图不工作。,考虑，如何识别 abc123x:=10 中的标识符abc123x,20,状态转换图识别无符号整数：P10.图2-3(b),该状态转换图描述了单词符号“无符号整数”的结构。无符号整数是不带+、-符号的由09数字构成的数字串，如 123456 等。 识别无符号整数的转换图中，0为初态，2为终态，打了*号。 识别的过程类似于识别标识符。,状态转换图识别无符号数：P10.图2-3(c),该状态转换图可以识别下面形式的一些无符号数: 123.，.123， 123.456， 123.E3，123.456E-3 等等 识别的过程类似于识别标识符。,22,状态转换图的实现,P10. 状态转换图容易用程序实现。 办法是让每个状态结点对应一段程序。 转换图与程序结构之间存在下述对应关系： 初态对应程序的开始； 终态对应程序的结束，一般是一条返回语句，不同的终态对应不同的返回语句； 分叉状态对应情形或者条件语句； 转换图中的环对应程序中的循环语句； 状态转换图可看成一个抽象的程序流程图。,状态结对应程序段的编写(1),P10.不含回路的分叉结对应条件或情形语句,状态结 i 对应的程序段: s=getchar( ); 读当前字符到变量s if( IsLetter(s) 状态j对应的程序段 else if(IsDigit(s) 状态k对应的 程序段 else 错误处理程序段 或接其他状态图的程序 参见P10. Switch语句的程序段,状态结对应程序段的编写(2),P10.含回路的状态结 对应循环语句,状态结 i 对应的程序段: s=getchar( ); 读当前字符到变量s while(IsLetter(s) | IsDigit(s) concatenation(s); 拼接单词 s=getchar( ); ; 状态 j 对应的程序段; 参见P11. while语句的程序段,25,状态结对应程序段的编写(3),初态结(如P12.图2-5中的状态0)，要作一些初始化的工作，比如：设置指示器的值，对变量进行初始化等。 P11. 终态结对应return(Code,Value)语句，返回单词符号的内部表示二元式给语法分析器。 带*号的终态结多读进了一个不属于现行单词符号的字符，这个字符应退回输入串，即搜索指示器要回调一个字符位置，这时除了Return外，还要将搜索指示器回调一个字符位置，这可以由一个过程来完成。,26,状态结对应程序段的编写(4),多种单词出口的终态结，如P12.图2-5中的状态2，既是标识符的出口又是保留字的出口，为了确认到底是保留字还是用户自定义的标识符，需要对识别出的单词符号查询保留字表，这可以由一个整型函数过程来完成。若函数值为0，则表示是一个标识符；否则，表示是保留字的种别编码。 在识别标识符的过程中，要把标识符拼写出来，并和保留字区别开来；在识别常数的过程中，要把它转换成机器表示以作为属性值。,27,2.2 一个简单的词法分析器示例,P11. 一个非常重要的事实是，大多数程序语言的单词符号都可以用状态转换图予以识别。 作为一个综合例子，教材P11.15.构造了一个识别简单语言(是C语言子集)的所有单词符号的状态转换图，并给出了对应的词法分析程序。 希望同学们好好读一下这个例子。要求完成的第一个实验 - 设计并实现一个小语言的词法分析程序，就可以以这个例子作参考。,2.2.1 C语言子集的单词符号表示,P11.表2.1 C语言子集的单词符号及内部表示,注意：定义有哪些单词符号及怎么编码的？,为了简化问题，对C语言子集作几点限制: 保留字不能作标识符。 保留字视为特殊的标识符，不专设状态转换图来识别；但要设保留字表(表2.1中的前5项)，当识别出一个标识符以后要进一步确认是保留字还是用户定义的标识符。 保留字、标识符、常数之间必须有间隔，用运算符、界符、空白符等分隔。,2.2.2 C语言子集对应的状态转换图,P12.图2-5,问题：各个终态识别什么单词符号？ 终态2识别 终态4识别 终态5识别 终态9识别 终态10识别 终态15识别,30,2.2.3 状态转换图的实现,P13. 容易由状态转换图编写词法分析程序，办法是让每个状态结点对应一段程序。 P13. 在编制程序的过程中需要引进了一组全局变量和过程，将它们作为实现转换图即词法分析程序的基本成分。 1. character 字符变量, 存放最新读入的源程序字符。 2. token 字符数组，存放构成单词符号的字符串。 3. Getbe( ) 过程，若character中的字符为空白，则调用getchar，直到character为非空白字符。,4. Concatenation( ) 过程，将token中的字符串与character中的字符连接并作为token中新的字符串。,P13. 设定一组全局变量和过程(1),5. Letter( ) 和 Digit( ) 布尔函数，分别判断character中的字符是否为字母或数字，是则返回True, 否则返回False。 6. Reserve( ) 整型函数, 对Token中的字符串查保留字表, 若它是保留字则返回其编码, 否则返回0值(假定0不是保留字的编码), 表示是标识符。,思考：怎么连接？,思考：怎么设计保留字表的结构？,32,7. Retract( ) 过程，将搜索指示器回调一个字符位置，同时将character置为空白字符。 8. Buildlist( ) 整型函数，将Token中的标识符或常数登录到符号表或常数表，返回符号表或常数表指针。,P13. 设定一组全局变量和过程(2),思考：符号表或常数表的结构？,9. Error( ) 整型函数，出现非法字符，显示出错信息。 10. Getchar( ) 过程，将下一个输入字符读到character中，搜索指示器前移一个字符位置。,构造图2-5对应的词法分析程序(P13.),0状态对应的程序段：整个程序从开始到结束 是初态：作初始化工作 token=; s=getchar( ); 有分叉：对应整个程序的分支结构 switchcasecasedefault 含回路：有循环，用过程Getbe( )实现 1状态含回路，对应P13.的case a: case z: 分支中的循环语句 While(Letter( ) | Digit( ) ,图2-5对应的词法分析程序(P13.),2状态 对应P13.语句Retract( )开始到P14. 语句case 0:之前的部分 是带*号的终态: 调用了Retract( )过程回调指针 是标识符和保留字的识别态: 调用了Reserve( )函数并且作判断 if (c = = 0) buildlist( ); 是终态: 用Return( id, 指向id的符号表入口指针)返回标识符的内部表示，用Return(保留字码, null)返回保留字的内部表示 3状态 含回路，对应P14.的case 0: case 9：分支中的循环语句 While(Digit( ) ,35,构造图2-5对应的词法分析器(P14.),4状态 带*号的终态，整常数的识别态，对应P14. case 0: case 9：分支中的语句 Retract( )；buildlist( ); Return(num,num的常数表入口指针)； 15状态 识别错误, 对应P15. default: 分支中的语句error( ),说明: 这段程序执行一次, 只能识别出一个单词符号, 它作为语法分析器调用的一个子程序。 思考：如果作为一个独立执行的程序，要求把源程序的单词符号都输出来，该怎么办？,36,2.3 正规表达式与有限自动机简介,为了更好地使用状态转换图构造词法分析器，为了讨论词法分析器的自动生成，还需要将状态转换图的概念形式化。 2.3节主要讨论词法分析器自动产生所需要的工具, 将引入：正规表达式，正规集，有限自动机等概念。 2.4节讨论正规表达式与有限自动机的等价性。 2.3节及 2.4节是本章的重点和难点。,2.3节与2.4节的主要概念及关系,两者相同,等价 (2.4.1，2.4.4),38,字母表与符号（参见P16.）,在引入正规表达式之前先介绍几个关于字母表、符号、符号串、符号串集合、符号串集合的运算等概念。 字母表 是元素的非空有穷集合。 字母表记为。 例如，由26个英文字母组成的集合是一个字母表。 字母表的每个元素称为一个符号。 例如，26个英文字母中的a、b、c等都称为符号。,39,符号串及其集合, 上的一个符号串(也称字)是指由中的符号所构成的有穷序列。 例如，字母表中的符号组成的序列compiler、string、symbol等都是符号串。 不包含任何符号的符号串称为空符号串(也称空字)，记为 。 用 *表示上的所有符号串的全体(符号串集合， 的闭包)，空字 也包括在其中。 用 +表示上的所有符号串的全体(符号串集合，的正闭包)，空字 不包括在其中。,40,用表示不含任何元素的空集合 。 注意 、 和的区别。 例1：令=a,b, 则 *=, a, b, aa, ab, ba, bb, aaa, +=a, b, aa, ab, ba, bb, aaa, aab, 例2: 令=0,1,2,3,4,5,6,7,8,9, 则 * = 0 9 构成的所有数字串 + = 0 9 构成的所有数字串 ,符号串集合：例,41, 符号串集合的乘积 *的子集R和S的(连接)乘积定义为: RS=R & S 即集合RS中的符号串是由R和S的符号串连接而成，号可以省略。 一般 RSSR，但(RS)W=R(SW)。 符号串集合的方幂 R自身的n次连接积( n次方幂)记为： Rn = R R R (n个R的积) 规定 R0 = 。,符号串集的运算（1）,42, 符号串集合的自反闭包(闭包)R* R* = R0R1R2 符号串集合的正则闭包(正闭包)R+ R+ = R1R2R3 显然：R+ = RR* = R*R R* = R+ = R+ R*、R+中的每个符号串都是由R中的符号串经有限次连接而成的。,符号串集的运算（2）,设字母表=a,b,0,1 令 *的子集 R=10,ab, S=001 计算 RS，SR，RS，R2，R0，S * ，S + 。,符号串集运算：例及练习,解：RS=10001, ab001 SR=00110, 001ab RS=10, ab, 001 R2 =1010, 10ab, ab10, abab R0 = S * =, 001, 001001, 001001001, S + = 001, 001001, 001001001, ,44,2.3.1 正规表达式与正规集,P15.正规表达式，简称正规式。 它是状态转换图的一种形式化表示方法 它可以描述单词符号的结构 它能精确地定义单词符号集 - 称正规集 本小节主要内容 正规式与正规集的定义 正规式的等价及判断 由正规式写正规集 由正规集写正规式,45,P15. 正规式与正规集的递归定义,. 正规表达式 正规式表示的正规集 . (1). ， ， (2). a a (3). 若 R, S L( R ) , L(S) 则 选择 RS L( R ) L( S ) 连接 R.S L( R ) . L( S ) 闭包 R * ( L( R ) )* 括号 ( R ) L( R ) (4).,46,正规式运算符的优先级,P16.正规式运算符优先级由高到低依次是: 括号最优先 闭包 * R*表示R作任意有限次(包括0次)的连接 连接 选择 | 注：还可以引入正则闭包+，R+表示R作任意有限次(至少一次)的连接。 R+= R R* R*= R+,47,正规式等价的定义和性质,P16. 若两个正规式R和S所表示的正规集相同，即L(R) =L(S) ，则认为二者等价，记为R=S。 正规式的性质：,48,由正规式写正规集: 例2.1,P16. 令=a，b，设R=a(a|b)*是上的正规式，试求其表示的正规集。,解： L(R) = L(a(a|b)*) = L(a)(L(a|b)* = L(a)(L(a) L(b)*=a(a b)* = aa,b* = a, a, b, aa, ab, ba, bb, aaa, = a, aa, ab, aaa, aab, aba, abb, aaaa, ,注意：符是些集合的运算和变换！,由正规式写正规集例：设=a,b,正规式 正规集 . ab a, b (ab)(ab) aa, ab, ba, bb a* , a, aa, aaa, aaaa, = an | n0 (ab)* , a, b, aa, ab, ba, bb, aaa,. = a, b* ba* 上所有以b为首后跟着任意多个a的字 (a|b)*a 上所有以a为尾的字 (a|b)*(aa|bb)(a|b)* 上所有含有两个相继的a 或两个相继的b 的字,由正规式写正规集: 练习,令=A, B, 0, 1 , 问: 正规式 , , 0 , 110 , 0|1 , 1*，(A|B)(A|B|0|1)* 和 (0|1)(0|1)*表示的正规集分别是什么?,解答: 正规式 , , 0 , 110 , 0|1 , 1* 表示的正规集分别是 , , 0, 110, 0,1, , 1, 11, 111, =1* =1n | n0。 正规式 (0|1)(0|1)*表示的正规集是上“数”的全体 =0, 1.0, 1* 正规式 (A|B)(A|B|0|1)*表示的正规集是上的“标识符”的全体 =A, B.A, B, 0, 1*,51,正规式等价的判断和证明：例2.2,P16. 判断下述正规式之间是否等价 (1) (a|b)*与a*|b* 不等价 因为 (a|b)*对应的正规集为 a, b*； 而 a*|b*对应的正规集为 a* b*。 (2) (ab)*与a*b* 不等价 因为 (ab)*对应的正规集为 ab*； 而 a*b*对应的正规集为 a* b*。 (3) (a|b)*与(a*b*)* 等价 因为 (a|b)*对应的正规集为 a, b*； 而 (a*b*)*对应的正规集也为 a, b*。,52,正规式等价的证明：例2.3,P17. 设L(a+)=a*-，则有a+=aa*。,证明： 要证明a+=aa*，只要证明L(a+)=L(aa*) L(a+) = a*- = , a, a2, a3, - = a, a2 ,a3 , = a , a, a2 , = a a* = L(a) L(a*) = L(aa*),证明两个正规式等价的方法：用定义：正规集相等； 正规式对应的有限自动机相同。,写正规表达式: 例,1. 给出下列在字母表0, 1上的正规式： 所有以00结束的串的集合。,由正规集写正规式的方法：分析正规集中符号串的结构特点, 试着写出正规式； 验证是否能表示符号串, 不断调整正规式直到正确。,2. 写字母表a, b上的正规式：每个a都至少有一个b直接跟在其右边。,所有具有三个0的串的集合。,解: (0|1)*00,解: 1*01*01*01*,解: b*(abb*)* 或 b*(ab+)*,54,写正规表达式: 练习,1.给出下列在字母表a,b上的正规式：以b开头，后跟若干个(至少1个)ab的符号串的集合。,解: bab(ab)* 或 b(ab)+,解: a(aa)*bb(bb)*a(aa)*,2. P29.题2.5(1).写出描述语言 L(G)= a2n+1b2ma2p+1|n0, p0, m1 的正规式。,55,2.3.2 有限自动机(FA),有限自动机是描述符号串处理的强有力工具，是研究词法分析器的重要基础。 有限自动机(FA)分为确定有限自动机(DFA) 和不确定有限自动机(NFA) 。 本小节主要内容 DFA、NFA的定义及区别 FA M 表示为状态转换图和状态转换矩阵 FA M 识别字、空字、识别的语言 L(M),1. 确定有限自动机(DFA Md),P17. 一个确定有限自动机 DFA Md是一个五元组： Md= (S, , f, s0 , Z) (1) S 有限状态集。 (2) 有穷字母表，输入字符集。 (3) f 状态转换函数；从 S 至 S 的单值映射。 f (si, a)= sj 表示：当现行状态为 si, 输入字符为 a时，将转换到下一个状态 sj 。称 sj为 si的后继状态。DFA的后继状态是唯一确定的, 故称为确定有限自动机。 (4) s0 S，唯一的初态。 (5) Z S，终态集(可空)。 例：P17. 图2-6，DFA Md的的状态转换函数。,2. 非确定有限自动机(NFA),P17.一个非确定有限自动机NFA Mn是一个五元组： Mn= ( S，f，Q，Z ) (1) S 同 DFA ，有限状态集。 (2) 同 DFA，有穷字母表，输入字符集。 (3) f 状态转换函数：从 S* 到 S 的子集的映射 即 f：S*2s 意味着 f (si,)= s1, s2, , sm ，可以是空字。 (4) Q S，非空的初态集。 (5) Z S，终态集(可空)。 例：P18. 图2-7，NFA Mn的状态转换函数。,P17. DFA与NFA的联系与区别,DFA是NFA的特例。 DFA与NFA的区别: 初态数目，是否是集合 状态转换函数f： DFA： S S f (si, a)= sj a是一个符号 NFA： S*2s f (si,)=s1, s2, , sm * 是一个字(符号串) P19.对于任何一个NFA Mn，一定存在一个DFA Md ，使得L(Md)=L(Mn )。 NFA与DFA等价，说明两者描述能力相同。,59,P18. DFA可以用一个状态转换矩阵(表)表示 该矩阵的行表示状态 s 列表示输入符号 a，矩阵元素表示 f(s, a)的值 例2.4的DFA M所对应的状态转换矩阵：P18.表2.2,3. FA表示为 - 状态转换矩阵,NFA也可以用一个状态转换矩阵表示 P18. 例2.5 P19. 表2.3,P18. DFA可以表示成一张状态转换图。 假定DFA M含有m个状态n个输入字符，那末这张图： 含有m个状态结点； 每个状态结点顶多有n条箭弧射出和别的状态结点相连接； 每条箭弧用上的一个不同字符作标记； 整张图含有唯一的初态结点和若干个(可以是0个)终态结点； 某个结点可以既是初态同时又是终态。,3. DFA表示为 - 状态转换图,61,P18. 例2.4 DFA Md=( s0, s1, s2 , a,b, f, s0 , s2) 其中 f 为: f (s0 , a)= s1 f (s0 , b)= s2 f (s1 , a)= s1 f (s1 , b)= s2 f (s2 , a)= s2 f (s2 , b)= s1 对应的状态转换图： P18.图2-8.,DFA表示为状态转换图：例2.4,以后，将不加区别的使用DFA和状态转换图。,3. NFA表示成-状态转换图,P18. NFA也可以表示成一张状态转换图。假定NFA含有m个状态n个输入字符，则这张图： 含有m个状态结点； 每个结点可射出若干条箭弧和别的结点相连接； 每条箭弧用 *上的一个字（不一定要不同的字而且可以是空字 ）作标记（称为输入字）； 整张图至少含有一个初态，若干个(可以是0个)终态结点； 某些结点可以既是初态同时又是终态。,63,P18. NFA Mn=( s0, s1, s2 , a,b, f, s0, s2 , s1) 其中 f 为: f (s0 , a)= s2 f (s0 , b)= s0, s1 f (s1 , a)= f (s1 , b)= s2 f (s2 , a)= f (s2 , b)= s1 对应的状态转换图： P19. 图2-9.,NFA表示为状态转换图：例2.5,以后，将不加区别的使用NFA和状态转换图。,64,4. DFA识别(读出,接受)字,P18. DFA识别字 对于*中的任何一个字，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有箭弧的标记符连接成的字等于，则称为DFA M所识别。 DFA识别空字 若DFA M的初态结点同时又是终态结点，则称空字可以为DFA M所识别。 DFA M所能识别的字的全体记为L(M)。,65,DFA识别字：例,如图的DFA识别字abbab，因为存在路径 012333；但不接受字ababa，因为不存在识别路径。 如图的DFA不识别空字。 如图的DFA M识别的字的全体(语言): L(M)=上所有含有相继两个a 或相继两个 b的字,4. NFA识别字、语言L(M),P18. NFA识别字 对于*中的任何一个字，若存在一条从某一初态结点到某一终态结点的通路，且这条通路上所有箭弧的标记符连接成的字(忽略那些标记为的弧)等于，则称为NFA M所识别(读出或接受)。 NFA识别空字 若M的初态结点同时又是终态结点；或者存在一条从某个初态结点到某个终态结点的通路，则称空字可以为M所识别。 NFA M识别的上字的全体记为L(M)。,67,NFA识别字：例,P21.图2-14的 NFA M：,识别字 abbab，路径是X11245666Y 不接受字 ababa，不接受空字 该NFA M识别的字的全体（语言）为 ： L(M)=上所有含有相继两个a 或相继两个b的字,68,FA：练习1,设有 DFA M=(0, 1, 2, a, b, f, 0, 1, 2) 其中： f（0, a )= 2; f（0, b)= 1 f（1, a)= ; f（1, b)= 2 f（2, a)= 2; f（2, b)= 2 问：该DFA有几个状态？几个输入字符？初态？终态？画出其状态转换图。,解：有0，1，2共三个状态。0为初态，1和2为终态。输入字符为a, b两个。 其状态转换图为:,69,解释下面每个FA识别的语言是什么？,FA：练习2,含偶数个 0的二进制数串的集合,含(1+5*n)个a的符号串组成的集合, n0,70,给出接受下列在字母表0,1上的符号串的FA: ( a ) 所有以00结束的串的集合； （b) 所有具有三个0的串的集合。,FA：练习3,2.4 正规表达式到有限自动机的构造,本节讨论正规式与FA的等价性，DFA与NFA的等价性，NFA确定化为DFA的方法，DFA化简的方法。要求掌握这些方法。本节是重点和难点。 2.4.1 由正规表达式构造等价的NFA M 正规表达式R NFA M 2.4.2 NFA M的确定化 NFA DFA 2.4.3 DFA M的化简 DFA 最小化的DFA 2.4.4 正规表达式到有限自动机的构造示例,P19. 拓广状态转换图的概念，每条弧上可以用一个正规式作标记。 (1) 把正规式R表示成拓广的状态转换图。 如P19.图2-10所示,2.4.1 正规表达式与NFA的等价性 正规表达式R NFA M（1）,(2) 利用P19.图2-11的替换规则，对R进行分裂，加进新结，逐步把状态转换图变成每条弧上的标记为的一个符号或为止。,73,P19.图2-11的替换规则：,正规式R NFA M (2),P20.例2.6构造正规式b*(d|ad)(b|ab)+的NFA。 b*(d|ad)(b|ab)+ =b*(d|ad) (b|ab)(b|ab)*,连接,选择,闭包,参见P20.图2-12,正规式R NFA M：另例,正规式转有限自动机：练习,画出与正规式 r =01*|1 等价的有限自动机。,另外的练习： P23.例2.10 P24.例2.11 P26.例2.13 正规式转NFA的部分,76,(1) 在M的转换图上加进新的初态结X和新的终态结Y。从X用弧连接到M的所有原初态结点，从M的所有原终态结点用弧连接到Y，构成一个新的只有唯一初态和唯一终态的NFA M，显然，L(M)=L(M)。 (2) 逐步消去NFA M中的状态结点，直至只剩下X和Y为止。在消结的过程中，逐步用正规式来标记弧。消结的过程只需反复使用P27.图2-28的替换规则。,补充：NFA M 正规式R,77,P27.图2-28. 转换规则：,NFA M 正规式R,连接,选择,闭包,NFA M 正规式R： 例,NFA M 正规式R ：练习,80,基于DFA与NFA的等价性 对任何一个给定的NFA M，都能相应地构造出一个DFA M，使它们能够识别相同的语言，即L(M)=L(M)。 构造的思想：用DFA的一个状态对应NFA的一个状态子集，称作子集构造法。 要求掌握NFA确定化为DFA的方法。 本小节主要内容 状态子集 I 的闭包_CLOSURE(I) 状态子集 Ia =_CLOSURE(J) 确定化的方法、步骤,2.4.2 NFA M的确定化 (P20.),NFA的确定化: 状态子集的闭包,P20. 状态子集 I 的闭包_CLOSUR(I) (1) 若 qI , 则 q_CLOSUR(I); (2) 若 qI , 则从 q 出发经任意条弧而能到达的任何状态 q_CLOSUR(I)。,P20.例2.7,图2-13.,练习：若 I=1, 5， 则 _CLOSUR(I)= ,1, 2, 5, 6,_CLOSUR(1)=1, 2,NFA M的确定化: 状态子集Ia,P20. 状态子集 Ia = _CLOSUR(J) 其中, J = q | f (q, a) = q且 qI, a; 表示: J 是从 I 中的状态结点出发经过一条 a 弧而到达的状态结点的集合。,P20.例2.7 计算 Ia I=1, 2 , J = 5, 3, 4 Ia = 5, 6, 2, 3, 8, 4, 7 ,练习：I=1，计算 Ia = ?,NFA的确定化: 构造状态转换子集表,P21. 设= a1,a2, , ak ，构造状态转换子集表：, 第一行第一列为 I=_CLOSUR(X)，X是唯一的初态；以此 I 求 Ia1，Ia2，Iak。 把没有在第一列出现过的Iai填入空行第一列，以此 Iai为新的 I，再求 Ia1，Ia2，Iak。 重复的过程，直到所有求出的 Iai 都在第一列出现为止。,这个表是确定化方法的关键,构造状态子集表：P21.例2.8,对图2-14的NFA构造一张状态子集表。P21.表2.4, X, 1, 2, 1, 2, 3, 1, 2, 4, 1, 2, 3, 1, 2, 3, 5, 6, Y, 1, 2, 4 , 1, 2, 4, 1, 2, 3, 1, 2, 4, 5, 6, Y, 1, 2, 3, 5, 6, Y, 1, 2, 3, 5, 6, Y, 1, 2, 4, 6, Y, 1, 2, 4, 5, 6,Y, 1, 2, 3, 6, Y, 1, 2, 4, 5, 6, Y, 1, 2, 4, 6, Y, 1, 2, 3, 6, Y, 1, 2, 4, 5, 6, Y, 1, 2, 3, 6, Y, 1, 2, 3, 5, 6, Y, 1, 2, 4, 6, Y,NFA的确定化: 构造DFA状态转换表,P21.由NFA状态子集表构造DFA状态转换表： NFA的每个状态子集重新编号为DFA的一个状态 。 确定DFA唯一的初态是_CLOSUR(X) 对应的状态子集 - 第一行第一列的状态。 确定DFA的终态是所有含有原来NFA的终态Y的状态子集对应的状态。 如此, 构造出了DFA的状态转换表, 从而就构造出了与NFA等价的DFA。,86,构造DFA状态转换表：例2.8,对P21.表2.4中的所有子集重新命名，得到表2.5的DFA状态转换表，由此可以得到图2-15的DFA M。,NFA的确定化(子集法)：例2.8,正规表达式 (a|b)*(aa|bb)(a|b)*，对应的NFA见P21.图2-14，确定化得到等价的DFA见P21.图2-15。,注1：子集法进行确定化的关键在于构造状态转换子集表，即正确求出各个Ia。 注2：子集法要求NFA只有一个初态，必要时可以引入一个新的初态结X，用弧与原来的初态结连接。,NFA确定化：练习1,设有NFA M=(x, y, a, b, f, x, y), 其中 f 定义如下: f (x, a)=x, y f (x, b)=y f (y, a)= f (y, b)=x, y 试构造相应的 DFA M。,给出接受在字母表0,1上所有以00结束的符号串的DFA:,NFA确定化：练习2,另外的练习： P23.例2.10 P24.例2.11 P26.例2.13 NFA确定化的部分,90,2.4.3 DFA M的化简,P22. DFA M的化简(最少化、最小化), 是指寻找一个状态数比M少的DFA M, 使得 L(M)=L(M)。 化简了的DFA M满足下述两个条件： 没有多余状态； 在其状态集中没有两个相互等价的状态存在。 下面先引入状态的等价和可区别(不等价)的概念。能把DFA中等价的状态合并在一起, 就能减少DFA的状态数, 达到DFA化简的目的。 本小节要掌握DFA化简的方法。,91,状态的等价和可区别定义,P22. 设 s1, s2 S 是两个不同的状态, 若对任何 *, 从s1 (或 s2 )出发能读出而停于某个终态，则称 s1和 s2是等价状态。否则，称 s1和 s2是可区别的，即不等价的。 例如: 终态和非终态是可区别的，因为终态能读出空字，而非终态不能读出空字 。 又如：P21.图2-15的DFA中，状态1和2是可区别的，因为状态1能读出a而停于终态3，而状态2读出a后不能停于终态。,92,DFA最小化方法： 1. 把DFA M的状态集S分划成一些不相交的子集, 使属于同一子集的状态都等价, 属于不同子集的状态可区别(不等价)。 2. 从每个子集选一个代表, 消去其他等价状态，把原来导入子集各状态的弧都导入此代表结。 DFA最小化步骤： 1. 首先把状态集S分成终态集和非终态集两个子集，形成基本划分I(1), I(2)，显然属于这两个子集的状态是可区别的。,DFA M化简的方法(P22.),93,2. 假定到某时，划分为 I(1), I(2), I(m), 分成了m个子集, 且属于不同子集的状态是可区别的。检查每个I(i), 看能否进一步分裂, 方法: 对所有的a , 计算I(i)a 判断是否分裂I(i)。若 I(i)a 不全包含于现行划分的某一子集I(j )中, 即I(i)a跨越到两个子集，就将I(i) 一分为二。 参见图2-16 (a)和(b)：,DFA M化简的步骤(续1 P22.),94, 分裂 I(i) 的方法, 假定 I(i) 的状态 s1和 s2经 a弧分别到达 t1和 t2 , 而 t1和 t2属于现行划分的两个不同的子集，则分裂为：含有 s1的子集 I(i1) 和含有 s2的子集 I(i2) 。 含有s1 的子集 I(i1) = s | s I(i) 且 s经 a弧到达 t1所在子集 含有 s2 的子集：I(i2) = I(i) I(i1) 显然，I(i1)中的状态和 I(i2)中的状态是可区别的。 于是，I(i) 分裂为两个子集 I(i1)和 I(i2) 后形成了新的划分。,DFA M化简的步骤(续2 P22.),95,3. 重复第2步，直到子集个数不再增长为止，这时的划分为I(1), I(2), I(n), 满足每个子集不可再分, 每个子集的状态等价，不同子集的状态可区别。 4. 对最后的划分，从每个子集中选一个代表， 消去子集中其他的等价状态， 把原来导入子集各状态的弧都导入此代表状态结。再确定： 新的初态 含原初态的子集对应的代表状态 新的终态 含原终态的子集对应的代表状态,DFA M化简的步骤(续3 P22.),96,确定有限自动机的化简：例2.9,P23.例2.9 正规表达式(a|b)*(aa|bb)(a|b)* P21.图2-14 正规表达式对应的NFA P21.图2-15 NFA确定化得到未化简的DFA,现在进行DFA化简，化简过程参见P23.,DFA的化简：例2.9（1）P23.,(1) 首先把M的状态分为 终态集 3, 4, 5, 6和非终态集 0, 1, 2 (2) 结合图2-15 考察各集是否再分裂 考察终态集，需计算3, 4, 5, 6a 和 3, 4, 5, 6b 由于 3a = 6a = 3 3, 4, 5, 6 4a = 5a = 6 3, 4, 5, 6 所以 3, 4, 5, 6a = 3, 6 3, 4, 5, 6 由于 3b = 6b = 5 3, 4, 5, 6 4b = 5b = 4 3, 4, 5, 6 所以 3, 4, 5, 6b = 4, 5 3, 4, 5, 6 于是终态集3, 4, 5, 6不再分裂。,98,DFA的化简：例2.9（2） P23., 考察非终态集，需计算0, 1, 2a 和 0, 1, 2b 由于 0a = 2a = 1 0, 1, 2 1a = 3 3, 4, 5, 6 所以 0, 1, 2a = 1, 3 分属非终态集和终态集 于是0, 1, 2需要分裂，分裂为1和0, 2 。 现在划分为3个子集 3, 4, 5, 6、 1 和 0, 2。 继续考察 0, 2b ，由于0b = 2， 2b =4 所以 0, 2b = 2, 4 分属两个不同的子集 故 0, 2 也应一分为二：0 和 2。,99,DFA的化简：例2.9 （3）P23.,(3) 到此有了4个子集：3, 4, 5, 6、0、1和2。每个子集都不可再分了。 (4) 按顺序重新命名状态子集0、 1、 2 和3, 4, 5, 6 为0、1、2、3。其中3状态代表状态子集3,