编译原理与技术讲义 第2章 词法分析

1、编译原理与技术第2章 词法分析青岛大学信息工程学院主要内容词法分析器的设计 词法分析器的一种手工实现 正规表达式 有限自动机词法分析的自动生成器Lex编译原理与技术2词法分析器在编译中的位置 词法分析器语法分析器符号表源程序单词取下一个单词单词记号编译原理与技术32.1 词法分析器的设计词法分析器的基本功能按照语言的定义规则，逐个地读入源程序的符号，识别出对语言有意义的符号串，即单词符号；分析单词记号的属性，并把单词记号及其属性填写在符号表中；同时把源程序改造成等价的计算机内部表示单词记号，以便编译的后续阶段使用。还要对源程序进行预处理工作，包括：删除源程序中的空格、制表符、换行、注释等不影响

2、程序语法、语义的结构。 编译原理与技术42.1 词法分析器的设计高级程序语言的五种单词记号：保留字 是程序语言定义的具有固定意义的英文单词，有时称为基本字或关键字。例如，在C+中， char、float、extern、friend、switch、new都是关键字。保留字一般不能另作它用。标识符 表示各种名字的字符串，如变量名、类型名、函数名、对象名等。运算符 如+、= =、=等。常量 常量的类型一般有整型、实型、布尔型、文字型等。分界符 如分号、括号、注释标记/*、*/等。编译原理与技术52.1 词法分析器的设计词法分析器的输出单词记号一般采用形式为 的二元式。单词的种别是语法分析需要的信息，

3、通常用整数表示；单词的属性值则是编译的语义分析和代码生成等阶段需要的信息。编译原理与技术62.1 词法分析器的设计例2.1：假如保留字的编码是1，标识符的为2，运算符为3，分界符为4，整型常量为10，实型常量为11。那么，对于源程序代码：for (i = 1, sum = 9.8; i = 100; i+) sum += i3.14;词法分析器产生的结果是单词记号序列3，编译原理与技术72.1 词法分析器的设计词法扫描器与符号表 对符号表的操作主要是填表、查询和更新。每当词法分析器识别了一个单词的时候，第一项工作就是查询符号表。对于不同的单词种别，查询的方式和随后的处理完全不同。例如，对于关键

4、字、分界符和运算符等，只需在各自的符号表中查询，获得并记录其它属性值，生成相应的单词记号。处理常量，特别是处理标识符要复杂的多，而且仅仅在词法分析阶段是无法获得一个标识符的所有信息。当词法扫描器识别了一个标识符的时候，首先查询关键字表，看它是否是关键字；如果不是，还要在标识符表中查询，看它是否已经存在，如果不存在就把它填入标识符表，并填入种别、类型等信息。 编译原理与技术82.1 词法分析器的设计词法分析器的两种实现模式 完全独立模式和相对独立模式在完全独立模式下，词法分析器作为编译的子系统单独地运行一趟，扫描整个源程序，把识别的单词序列以机器内码的形式输出在一个中间文件上，供为语法分析使用。

5、编译原理与技术92.1 词法分析器的设计完全独立模式的好处编译程序结构清晰、条理化而且便于高效地实现；在设计高级语言时能独立地研究词法与语法两个方面的特性；增强编译程序的可移植性：可以就同一个语言为不同的机器写不同的词法分析器，而只编写一个共同的语法分析，使用这些词法分析器相同的单词机内表示；把同一个词法由于单词记号的语法可以用较简单的文法描述，把词法和语法分开，就能为这种文法建立有效的特殊方法和自动构造技术。 编译原理与技术102.1 词法分析器的设计相对独立模式：词法分析器设计成一个子程序，每当语法分析需要一个单词的时候，就调用该子程序。 相对独立模式的好处：词法分析器和语法分析器被设计在

6、同一趟，省去了存放单词的终结文件。 编译原理与技术112.1 词法分析器的设计词法错误的处理 在词法分析阶段发现的错误统称为词法错误，它们大多是单词拼写错误，这或者是因为书写错误、或者因为键入错误，例如把关键字拼写错。 对词法错误校正的常用策略是修补尝试，一般包括：删除一个多余的字符；插入一个遗漏的字符；用一个正确的字符替换一个不正确的字符；交换两个相邻的字符。编译原理与技术122.2 词法分析器的一种手工实现 输入的预处理 对于许多程序语言来说，空格、制表符、换行符等编辑性字符除了出现在文字常量中，在其它任何地方的出现都没有意义，而注释作为程序的重要文档几乎可以出现在程序中的任何地方。它们的

7、存在可以改善程序的可读性和易理解性，却不影响程序的语法结构和执行语义。通常在编译的词法分析阶段被预处理过程删除掉。 编译原理与技术132.2 词法分析器的一种手工实现输入的预处理扫描器对缓冲区进行扫描时一般使用两个指针：一个指向当前正在识别的单词的起始位置，另一个用于向前搜索以寻找该单词的终点，两个指针之间的符号串就是要识别的单词符号。无论扫描缓冲区设计的多大都不能保证单词符号不会超过其边界。扫描缓冲区一分为二的两段置.f o r ( s u m = 0 , i = 1 .搜索指针起点指针.C a r.e e l . 2 .编译原理与技术142.2 词法分析器的一种手工实现超前搜索和最长匹配

8、为了识别一个更有意义的单词符号，在找到了可能是单词符号的起点或者构成了单词部分时，扫描器并不满足，还要继续读入输入串，看是否能找到由更多符号所组成的单词（即最长匹配），有时可能要扫描到一个可以“断句”的符号（超前搜索），才能决定最后一个扫描的符号不属于之前的符号串所构成的单词。超前搜索符号通常是最长匹配单词的结束标志，可以是空格符、回车符、制表符等可以被预处理掉的符号；也可能是下一个单词记号的起始符。编译原理与技术152.2 词法分析器的一种手工实现超前搜索和最长匹配的例子在识别“for”的时候，要扫描到左括弧(时才知道，它不属于标识符的符号；当读到了，以便构造出小于等于“=”或不等于“”的比

9、较运算符，否则，就构造小于运算符。 编译原理与技术162.2 词法分析器的一种手工实现状态转换图 状态转换图是构造词法分析器的一个良好工具，它描绘了为得到一个单词记号，词法分析器应该执行的动作。状态转换图是一个有向图，结点代表状态，用圆圈表示，内部用数字表示状态名称；状态之间由箭弧连接，箭弧上有符号作为标记，称为从箭弧尾的离开状态读入标记符号以后转换到箭弧头的进入状态。若离开状态s的某个标记为other，则表示离开s的其它箭弧标记以外的任意符号。每个状态转换图中的状态数量有限，都有唯一的一个起始状态（本书用一个进入的箭头表示）和至少一个终结状态（用双圈表示）。 编译原理与技术172.2 词法分

10、析器的一种手工实现状态转换图识别或接受一定的输入符号串从起始状态开始，读进输入符号串的一个符号a，沿着状态转换标记为a进入下一个状态，重复执行直到进入终结状态。即，如果存在一个从起始状态到终结状态的路径，路径上的标记用连接运算连接在一起形成一个符号串，它和输入符号串相同，则称该输入符号串可以接受。如果不能进入任何一个终结状态，则称该状态转换图不能识别或接受这个输入符号串 编译原理与技术182.2 词法分析器的一种手工实现digit01letterletter对于符号串var1，有状态序列， 例2.2： 标识符一般定义为字母打头的字母数字序列.编译原理与技术192.2 词法分析器的一种手工实现5

11、other=1=032例2.3：类似语言中的关系符的状态转换图 。在终结状态加了星号*，表示在状态1、2和3都还不能确定它们是否是符合最长匹配准则的单词记号，还需要在读入一个字符才能确定。而为实现最长匹配的一个超前搜索符号“其它”则不属于这个单词，应该推给扫描缓冲区。 编译原理与技术202.2 词法分析器的一种手工实现例2.4：Pascal语言中数的状态转换图 。在这个复杂的例子中，状态3、5和8分别表示识别是整数、不带指数部分的实数以及带有指数部分的实数，但是，只能在超前搜索一个其它符号以后，才能在状态9确定识别了一个Pascal的数。读者可以自己验证例子数2005，+1998，81.07，

12、2.0036，看它们是否能被这个转换图所接受。3digitdigitotherdigitdigitdigit9814562+, E7+,digitEdigitotherother*编译原理与技术212.2 词法分析器的一种手工实现基于状态转换图的词法分析器的实现code表示单词记号的种别；value存放标识符或数在符号表的入口地址；过程getghar(ch)从扫描缓冲区得到一个搜索符号，存储在变量ch中；函数isLetter(ch)和isDigit(ch)分别检查ch是否是字母/数字；函数lookup(token, table) 在符号表table中查询是否包含单词token；insert (

13、token, table)在则把单词token插入符号表table中并返回在符号表的地址；函数reporterror()报告并简单处理词法错误。 编译原理与技术222.2 词法分析器的一种手工实现根据状态栈图编写词法扫描器的方法一让状态转移对应一个读入字符的语句或函数，然后与转移上的标记比较，如果相等就进入转移对应的程序段或子程序；否则，调用错误处理程序。多个转移就对应分支语句；如果转移返回自身，形成一个圈，对应程序段的就是循环语句。 编译原理与技术232.2 词法分析器的一种手工实现标识符状态转换图的一个实现int code, value;char token =”;/ 在开始状态0do t

14、oken = token+ch;/ 不断读入字母或数字，合并成一个标识符 getchar(ch);/ 保持在状态1 while (!isLetter(ch) | !isDigit(ch)； / isLetter(ch)和isDigit(ch)分别检查ch是否是字母/数字/ 进入结束开始状态2code = lookup(token, keywordsTable);/ 在关键字表中查询token，若它是关键字就返回1if (code= =1) return(1, token);/ 返回关键字的单词记号，假如关键字种别是1else value=insert(token, identifierTabl

15、e); / 把token插入标识符表，返回入口地址return (2, value)/ 返回标识符的单词记号，假如标识符种别是2编译原理与技术242.2 词法分析器的一种手工实现根据状态栈图编写词法扫描器的方法二采用一个变量来记录当前的状态，把状态转换嵌入到一个循环体内的分支语句中，其中的第一个分支测试当前状态，而嵌入内层的第一个分支语句则对给定的状态测试输入符号，以决定转移进入的状态。 编译原理与技术252.2 词法分析器的一种手工实现例2.5：下图示意的是识别C风格注释，即形式/*.*/，的状态转换图。状态2中的标记other是除*之外的其它符号，而从状态3到状态2的标记other是除*和

16、/之外的其它符号。 413 2other*0/other*编译原理与技术262.2 词法分析器的一种手工实现int state = 0;while (state = 0, 1, 2, 3 ) switch state case 0: getchar(ch);if (ch = = /) state = 1; getchar(ch) ;else reporterror();case 1: getchar(ch);if (ch = = *) state = 2; getchar(ch) ;else reporterror();case 2: getchar(ch);if (ch = = *) sta

17、te = 3; getchar(ch) ;else getcharch(ch); / 还是在状态2case 3: getchar(ch);switch ch case /: state = 4; getchar(ch) ; case *: state =3; getchar(ch) ; default: state = 2if (state = = 4 ) return; else reporterror();编译原理与技术27Id-keywordsnumberotherotherotherEAotherotherotherdigitotherinIDstartLNE=*= =other*le

18、tter, digitletter23inNum*digitdigit*commentGE=*+*/=+*/digit课本图2.6:int code, value,;char state = “start”;char token =”;state_sets表示所有状态名的集合编译原理与技术282.2 词法分析器的一种手工实现while (state属于state_sets) switch state case “comment”: getchar(ch); if (ch = = ) state = “start”; getchar(ch) ; case “start”: getchar(ch)

19、;switch ch case isletter(ch): state = “inID”; token = ch; getchar(ch) ; case isdigit(ch): state = “inNum”; token = ch; getchar(ch) ; case ch = = : state = “comment”; getchar(ch) ; case ch = = : state = “GE”; token = ch; getchar(ch) ; case ch = =+ : state = “+” ; token = ch; case ch = = : state = “”

20、; token = ch; case ch = =* : state = “*” ; token = ch; case ch = =/ : state = “/” ; token = ch; default:getchar(ch);/ 过滤掉无用的符号 编译原理与技术292.2 词法分析器的一种手工实现case “inNum”: while (state属于inNumber, 2, 3) / 处理数 switch state case “inNum”: switch ch / 处理整数 case isdigit(ch): token = token+ch; getchar(ch) ; case

21、 ch = = . : state = “2”; token = token+ch; getchar(ch);default: state = “number”; code=10; / 处理实数case “2”: if (isdigit(ch) state = “3”; token = token+ch; getchar(ch); else reporterror (); case “3”: if (isdigit(ch) state = “3”; token = token+ch; getchar(ch); else code = 11; state = “number”; case “nu

22、mber”: value = insert (token, identifierTable); return(code, value); 编译原理与技术302.2 词法分析器的一种手工实现case “inID”: while (isletter(ch) | isdigit(ch) token = token+ch; getchar(ch) ; code = lookup(token, keywordsTable); / 在关键字表中查询token if (code= =1) return(1, token); / 返回关键字的单词记号 else value=insert(token, iden

23、tifierTable); / 把token插入标识符表 return (2, value); / 返回标识符的单词记号 case “LNE”: getchar(ch); if (ch = = ) getchar(ch); return(3, “”); if (ch = = =) getchar(ch); return(3, “=”); else return(3, “=”); else return(3, “”); case “+”: getchar(ch); return(3, “+”);case “”: getchar(ch); return(3, “”);case “”: getcha

24、r(ch); return(3, “”);case “/”: getchar(ch); return(3, “/”);编译原理与技术312.3 正规表达式 符号、符号串与符号集合 定义2.1：字母表是有限的非空的符号集合，字母表中的元素称作符号。例如，二进制数语言的字母表是0, 1；Java语言的字母表可以说是一切可以打印字符组成的集合。 编译原理与技术322.3 正规表达式定义2.2：由字母表中的符号所组成的任何有限序列称为符号串。一个符号串所包含符号的个数称为该符号串的长度。例如，对于字母表a, b，a、b、aa、ab、ba和abba都是上的符号串。符号串b、ab和abba的长度分别是1、

25、2和4。符号串中符号的排列顺序十分重要，上面的ab和ba表示不同的符号串。通常用小写的希腊字母、等表示符号串。符号的长度表示成|，例如|abba|=4。允许空符号串，即不包含任何符号的符号串，用希腊字母表示，|=0。 编译原理与技术332.3 正规表达式如果x=uv是一个符号串，则称u是x的头，称v是x的尾。当我们堆一个符号串的某些部分感兴趣、堆其它部分不感兴趣时，通常忽略调不感兴趣的部分，而只保留感兴趣的部分。例如，若我们只关心符号串x=t中的符号t，也可以用x=.t.表示；同样，x=t和x=t.这两种表示都只关注符号的头时符号t。 编译原理与技术342.3 正规表达式定义2.3：设和是同一

26、字母表上的符号串，把的各个符号相继地写在之后所的到的符号串称为和的连接（并置），记做。显然，|=|+|。例如，字母表a, b, 0, 1上的符号串=bb11、=a00，是bb11a00，而是a00bb11，而且| = | = 7 =| + | = | +| = 4+3 = 7。显然，对于任何符号串，都有。 定义2.4：设u是某一字母表上的符号串，把u自身连接n次，即=u.u(n个u)，称作符号串u的n次方幂，记做=un。例如，u1=u，u2=uu，u4=uuuu。特别地，当n=0时，u0=。显然，uun-1 = un-1u= un。编译原理与技术352.3 正规表达式定义2.5：若集合A中的所

27、有元素都是某字母表上的符号串，则称集合A是该字母表上的符号集合。字母表上的符号集合通常用大写字母A、B、C等表示。例如，字母表a, b, 0, 1上长度为2的符号串集合A= | =xy，并且x和y是中的一个符号；字母表上单词B= | 是a, b中的符号串。定义2.6：两个符号串集合A和B的乘积AB定义为：AB=uv | uA并且vB。例如，设A=a, b，B=0, 1，那么AB=a0, a1, b0, b1，BA=0a, 1a, 0b, 1b，AA=aa, ab, ba, bb。由于对于任何符号串x都有xxx，所以A=A=A，但是，对于空集，却有等式A=A=。类似于符号串的方幂，可以定义符号串

28、集合的方幂，特别地，定义字母表A的方幂为A0= ，A1=A，An= An-1 A ( n 0 )， 显然，若u An，则| u | = n。编译原理与技术362.3 正规表达式定义2.7：字母表的闭包*01.n.，正闭包+12.n. 。例如，对于字母表a, b，+= a, b, aa, bb, ab, ba, aaa, bbb, aab, bba, aba, bab, abb, baa, .。显然，*0+，+= * = *。*表示字母表上所有长度的符号串的集合，包括空符号串；+表示长度至少为1的符号串的集合。+实际上就表示了该字母表所构成的语言，句子就是其中的符号串。对于C语言，可以说，C语言

29、是其字母表，也即基本符号正闭包的真子集。编译原理与技术372.3 正规表达式例2.6：令字母表L=A, B, ., Z, a, b, ., z，D=0, 1, ., 9，那么LD是字母和数字的集合；LD4表示以字母开头、跟随4个数字的串的集合；L(LD)15表示长度为16的标识符，即以字母开始的16位的字母和数字串的集合；D*表示不含空的数字串的集合。编译原理与技术382.3 正规表达式正规式与正规集 字母表上的正规表达式用来描述一种称为正规集的语言。定义2.8：字母表上的正规表达式（简称正规式）按照下列规则递归地定义：（1）是上的正规式，它表示的正规集是；（2）是上的正规式，它表示的正规集是

30、；（3）中的任意符号a都是上的正规式，它表示的正规集是a（4）若r和t都是正规式，它们所表示的正规集分别是L(r)和L(t)，那么(r)、r|t 、rt和 r*都是正规式，表示的正规集分别是L(r)、L(r)L(t)、L(r)L(t)、( L(r) *。根据显然定义有下列等式： L(a)=a，L()=，L()=，L(r)= L(r)，L(rt)= L(r)L(t)，L(r|t)= L(r)L(t)，L(r*)= ( L(r) *。 编译原理与技术392.3 正规表达式例2.7：令字母表=a, b, c，那么(a|b)(a|b)aa, ab, ba, bb；(a|c)*表示所有a和c组成的符号串

31、，其中包含空串；(a|c)*b(a|c)*表示只包含一个b的字母表上的所有符号串，例如b，abc，baaac，caccb，ccbaaa。最多包含一个b的字母表上的符号串的集合可以表示成(a|c)*| (a|c)*b(a|c)*)，或者(a|c)*(b|)(a|c)*。(a|c)*b(a|c)* b表示的集合是什么呢？它表示只含两个b的符号串的集合。编译原理与技术402.3 正规表达式定义2.9：如果两个正规式r与t表示的正规集相同，则称它们的等价的，记做r=t。正规式等价的例子如a|(ba)*= (ba)*|a，(a|b)=(b|a)。 定理解释r|t = t|r| 的交换律r|(s|t) =

32、 (r|s)|tr(st) = (rs)t结合律r(s|t) = rs | rt(r|s)t = rt | st分配律r = r = rr = r = rr | = r吸收律r* = (r | )*闭包运算和之间的关系编译原理与技术412.3 正规表达式扩展的正规式 （1）一个或多次重复：一元后缀算符“+”表示一个或多次重复，即正规式r+表示一个或多个r的串的集合。这样，(0|1)+表示所有二进制数字的集合，而(0|1)*同时还包含了可串。（2）字符集的范围：对于字母或数字的集合，可以使用a|b|.|z或0|1|.|9。更简洁的方式是用方括弧，用连接线表示范围，这样，上面的字母或数字就可以分别

33、表示成a-z和0-9。类似的，a|b|c|d可以写成a-d或者abcd。标识符是字母打头的字母数字串，可以表示成A-Za-z A-Za-z0-9*。（3）零个或一个：一元后缀算符“?”表示零个或一个，r?是r|的缩写。带符号的整数可以写成(+|)?1-90-9*编译原理与技术422.3 正规表达式如果正规式很长，可以给它命名，使它们可以像普通的符号一样，在随后的正规式中使用这些名字来引用相应的正规式，以便得到简洁的正规式。如果r如是字母表上的正规式，那么正规定义的形式是：name r。这样，正规式r的名字name就可以像中的符号一样，在以后构造上正规式的时候使用。编译原理与技术432.3 正规

34、表达式例2.8：Pascal语言的标识符集合是字母开头的字母数字串，下面就是这个集合的正规定义：letter A-Za-zdigit 0-9identifier letter( letter| digit )*编译原理与技术442.3 正规表达式例2.9：Pascal语言的数是2005，+1998，81.07，2.0036这样的串，即由整数、小数和指数三个部分组成。小数和指数部分是可选的，其中指数标记E后面可以有+或，再跟上一个或多个数字，而小数点之后必须至少有一个数字。下面就是Pascal语言的数的集合的正规定义：digit 0-9digits digit digit*signed + |

35、fraction (.digits)?exponent (E(signed)?digits)?number signed? digits fraction exponent编译原理与技术452.3 正规表达式正规表达式的实现和应用正规表达式实际上是描述和识别一组字符串的模板（模式），它包含字符、元符号（如表示重复的*和选择符|）和一些具有特殊意义的符号。这个模板决定什么样的字符串属于某一个集合。正规表达式在处理文本方面具有强大的能力，它在计算机领域的应用不仅仅局限于构造编译器的词法扫描器，其它著名的应用还包括UNIX操作系统的命令工具如grep，处理复杂文本分析与操作的脚本语言Perl，Tcl

36、，Python，PHP和awk以及通用程序开发编辑器emacs。由于正规表达式的重要而广泛的应用，Java语言通过包java.util.regex还对正规表达式的处理提供了直接支持。 编译原理与技术462.4 有限自动机 为什么引入有限自动机确定的有限自动机和不确定的有限自动机都能识别正规集，即它们识别的语言正好就是正规式所能表达的语言，而且在识别语言的能力上，它们完全等价。但是，实现这两类有限状态机的效率不同，用它们构造的词法分析器在识别语言中单词记号的效率方面也有显著的差别。 正规式不确定的有限自动机确定的有限自动机词法分析器编译原理与技术472.4 有限自动机确定的有限自动机 DFA定义

37、2.10：一个确定的有限自动机DFA M是五元组，其中：（1）S是非空的有限的状态集合；（2）是非空的输入字母表；（3）T是部分单值映射S S，又称转移函数；T(s1, a)= s2表示输入符号a时，把状态s1转换到s2，成为当前状态；（4）s0S，是唯一的起始状态；（5）FS，是非空的终结状态。被M接受或识别的语言，记做L(M)，定义为字符串的集合，其中每个ci，并且存在状态序列s1=T(s0, c1), s2=T(s1, c2), . , sn=T(sn-1, cn)，sn F。 编译原理与技术482.4 有限自动机例2.10：一个有限自动机DFA N= ，其中T的定义如下:T(A, +)

38、=BT(A, )=BT(A, )=CT(A, d)=DT(B, )=DT(B, d)=CT(C, )ET(C, d)=CT(D, d)E T(E, d)E状态A是起始状态，E是终结状态。 编译原理与技术492.4 有限自动机转换函数可以用状态转换矩阵或状态转换表来表示，该表的行表示状态，列对应输入的符号，表元素表示状态转移的状态，空白元素对应的二元组没有定义。 +dABBCDBDCCECDEEE例2.10有限自动机的状态转换矩阵 编译原理与技术502.4 有限自动机一个DFA也可以表示成一个确定的状态转换图，状态转换函数T(s1, a)=s2对应了连接两个结点s1和 s2，标记为a的有向弧。

39、+, CEdADBdddd例2.10有限自动机的状态转换图 从状态A到B的转换上的标记“+, ”表示两条从A到B的弧的标记+和 ，这是常用的简化方式。 编译原理与技术512.4 有限自动机定义2.11：对于有限自动机M的*中的任何一个符号串，若存在一条从起始状态到某一终结状态的通路，且这条通路上所有弧的标记符连成的串等于，则称被M识别（读出或接受）。若起始状态也是一个终结状态，则空串可以为M接受。DFA M所能识别的所有字的集合称为M识别的语言，记做L(M)。编译原理与技术522.4 有限自动机例如，考虑上述的有限自动机，如果d代表任意一个数字0，1，.，9，它能否接受符号串30.、+.28和

40、813.19？对于它们，可以分别给出从状态A到终结状态E的路径：因而它们都是这个DFA N可以接受的数。编译原理与技术532.4 有限自动机定义2.12(a)：两个有限自动机M1和M2是等价的，当且仅当它们识别相同的语言，即L(M1)=L(M2)。定义2.12(b)：两个有限自动机M1和M2是等价的，当且仅当对于每个M1接受的符号串，M2接受。编译原理与技术542.4 有限自动机不确定的有限自动机NFA 定义：一个不确定的有限自动机NFA M是五元组，其中：（1）S是非空的有限的状态集合；（2）是非空的输入字母表；（3）T是S() 2S（S的幂集），它可以把一个状态映射到一组状态 ；T(s1,

41、 a)= s2表示输入符号a时，把状态s1转换到s2，成为当前状态；（4）s0S，是唯一的起始状态；（5）FS，是非空的终结状态。被M接受或识别的语言，记做L(M)，定义为字符串的集合，其中每个ci，并且存在状态序列s1=T(s0, c1), s2=T(s1, c2), . , sn=T(sn-1, cn)，sn F。编译原理与技术552.4 有限自动机例2.11：识别语言(a|b)nabb | n0的一个NFA M = ，ab01,2111,212334aa24a031bbbba这个NFA识别aabbabb，即存在一个状态序列，从状态0到状态4，路经上的标记连接是aabbabb：编译原理与技

42、术562.4 有限自动机两个NFA N1和N2称为等价的，当且仅当它们识别同一个语言，即L(N1)=L(N2)。为什么要引入NFA？首先，需要有限自动机的主要目的是用来识别正规式所描述语言的单词记号，直接从正规式构造出DFA的算法比较复杂，而从正规式构造NFA的算法则相对简单；然后，再从NFA构造等价的DFA作为记号的识别分析器。其次，我们有时需要多值映射以及所谓的空转移，即形式为N的产生式，以便简洁地表达多种可能的选择。而且，使用空转移描述对空串的匹配，更加直观和自然。 编译原理与技术572.4 有限自动机从NFA到DFA的等价变换定理2.1：对于任意一个NFA N都存在一个等价的DFA M

43、，即L(N) = L(M)。为了从NFA构造出等价的DFA，需要消除N形式的产生式，即消除空转移；确定化每个多重转移，即拆分多值函数为单值函数。一个常用的方法是子集法。编译原理与技术582.4 有限自动机定义2.13：设I是NFA N=中一个状态子集，对I的闭包运算-closure(I)的结果是一个状态子集，定义为-closure(I) = s | s I s | s -closure(I)并且存在T(s, )=s。直观地说，状态子集I的闭包就是从I中的任何一个状态经过任意个连线所能达到的所有状态。 编译原理与技术592.4 有限自动机例2.12：下图是接受连续a或b的语言的一个NFA，尽管在

44、每个状态，对应字母表上符号的转移是唯一的，但是，由于增加了所谓的空转移转移，所以，它不是DFA。abE5132B6baaa4bb例如，一个子集I=B，按照定义，计算-closure(B)的序列如下： -closure(B) B B, 5 B, 5, 1 编译原理与技术602.4 有限自动机定义2.14：设I是NFA N=中一个状态子集，a，对I移动的闭包运算Ia的结果是一个状态子集，定义为Ia=-closure(J)，其中J = s | s I并且存在T(s, a)=s。直观上，状态子集Ia是从I中的任何一个状态经过标记为a的一次转移之后所能到达的所有状态的闭包。计算Ia的两个步骤：（1）计算

45、从I读入符号a所达到的状态集合J；（2）求J的闭包，即-closure(J)。 编译原理与技术61算法2.1 从NFA到DFA的等价构造算法输入： NFA N=)输出： 等价的DFA假设 =a1,a2,., an（1）首先构造DFA的状态转换表MATRIX：这是一个n+1列、行动态增长的表格；第零列的每个元素对应DFA的状态，随着算法的执行，递增地产生新的状态，即增加新行；初始化：row = 1; / MATRIX的行sn = row; / DFA的状态个数MATRIXrow, 0 = -closure(q0)；S= MATRIXrow, 0 ；/ 加入DFA状态集合的第一个状态，它本身是一个

46、集合do / 逐行地填表for i = 1 to n do MATRIXrow, i = Iai；/ 在每行逐列地填表 if Iai S thenS = S Iai； / 把Iai加入Ssn = sn + 1;MATRIXsn, 0 = Iai； / 状态转换表增加一行，即增加一个新的状态 end if;end for；row = row + 1;/ 计算下一个状态的Iai while sn = = row / 直到没有新的状态为止（2）矩阵中第一行第零列所表示的状态就是DFA的起始状态；（3）包含了NFA终结状态的新状态就是DFA的终结状态。（4）可选：重新命名DFA的状态，相应地改变状态转

47、换函数中状态名字。编译原理与技术622.4 有限自动机例2.13：对例2.12表示的NFA构造等价的DFA。 首先，把-closure(q0)=-closure(B)=B, 5, 1填入转换矩阵表的第一行第一列。然后对每个a计算Ia并填入表中，如果Ia是新的状态集合，则在状态转换矩阵表中新增一行，把它加入其中。对于a，计算Ia=-closure(B, 5, 1) =5, 1, 3，是个新的状态集合，加入表的第二行；对于对于b，计算Ib=-closure(B, 5, 1) =5, 1, 4，也是个新的状态集合，加入表的第三行。然后，把5, 1, 3看作I，对每个a计算Ia并填入表中。Ia= 5,

48、 1, 3, 2, 6, E是个新的状态集合，加入表中的下一行，而Ib= 5, 1, 4已经出现过，什么也不做。编译原理与技术632.4 有限自动机这样继续下去，最后得到的状态转换矩阵如表2.5(a)所示。IaIbB, 5, 15, 1, 35, 1, 45, 1, 35, 1, 3, 2, 6, E5, 1, 45, 1, 45, 1, 35, 1, 4, 2, 6, E5, 1, 3, 2, 6, E5, 1, 3, 2, 6, E5, 1, 4, 6, E5, 1, 4, 2, 6, E5, 1, 3, 6, E5, 1, 4, 2, 6, E5, 1, 4, 6, E5, 1, 3,

49、6, E5, 1, 4, 2, 6, E5, 1, 3, 6, E5, 1, 3, 2, 6, E5, 1, 4, 6, E编译原理与技术642.4 有限自动机状态子集重新命名，并将Ia和Ib分别视为a与b后得表2.5(b)，对应的状态转换图如图2.13所示。 ab01213221435646435ab34a01bbba256baabbaa编译原理与技术652.4 有限自动机例2.14：对例子2.11表示的NFA（如下图）构造等价的DFA。ab43 ab01bbba2baaa IaIb01, 211, 21, 21, 311, 211, 31, 21, 41, 41, 21编译原理与技术662

50、.4 有限自动机DFA的最小化 定理2.2：对任意一个DFA N都存在一个等价的DFA M，它包含最少的状态数，而且这个最小状态的DFA M是唯一的（状态名不同的同构情况除外）。关键在于把DFA的状态划分成一些不相交的等价子集，使得任何两个不同子集中的状态都可以区别，而每个子集内的状态都是等价的。这样，每个子集用一个状态代表，删除子集中的其它状态，就得到了状态个数最少的DFA。 编译原理与技术672.4 有限自动机定义2.15：设q1和q2是DFA N中的两个不同的状态，如果从状态q1出发能扫描任意串而停于终结状态，当且仅当从q2出发也能扫描任意串而停于终结状态，称状态q1和q2是等价的。定义

51、2.16：若两个状态q1和q2不是等价的，则称这两个状态是可区分的。例如，例2.14中状态1和3是可区别的，因为从状态1读入一个b而停在终结状态3 ，但是，从状态3读入一个b而没有达到终结状态4。又如空串把一切终结状态与任何非终结状态区别开。 编译原理与技术682.4 有限自动机DFA最小化的方法对一个DFA M=的状态划分，不断地尝试对其中的状态子集寻找可区别的状态，进行分裂，直到没有状态子集可以分裂为止，直至每个子集内的状态是等价的，而每个状态子集是可区分的。假如在某个时刻，划分=I1,I2,.,Im，其中的任何一个都是状态子集。对于任意一个状态子集Ijq1,q2,.,qk，若存在一个输入

52、符号a，对于任意两个不等的qi和qj使得（1）T(qi ,a)=s和T(qj ,a)=t不在当前划分的任何一个状态子集中，（2）或者其中T(qi ,a)和T(qj ,a)的任何一个没有定义则可以据此把Ij一分为二：其中的一部分Ij1是从Ij的状态读入a之后进入包含s状态子集的状态，Ij2=Ij Ij1。这样，在划分中用Ij1和Ij2取代Ij，就形成一个新的划分。编译原理与技术692.4 有限自动机可以根据Ij中每个qi的T(qi ,a)来执行K分裂：若T(qi ,a)落在划分的K个不同的状态子集中，则可以把Ij划分成K个不相交的组，使得每组的状态都落入的同一子集中。重复这个划分，直到没有可以分

53、裂的状态子集为止，得到最终的划分。选择每组中的一个状态作为代表，删除其它一切等价的状态，所有这些状态代表就构成了化简了的DFA状态集合。每个状态组之间的连线转移就是每个状态代表之间的转移，同时去掉不可达状态和无用状态。含有原来初态的等价状态组就是化简了的DFA的起始状态。包含了原来终结状态的等价状态组就是化简了的DFA的终结状态。 编译原理与技术702.4 有限自动机算法2.2DFA最小化算法输入： DFA N=输出： 等价的具有最少状态的DFA M假设 =a1,a2,., an初始化： = F, SF; 标记F和SF没有访问过 finished = false; 编译原理与技术712.4 有

54、限自动机（1）完成划分；while not finished do if 中不存在未访问的子集J then finished = true else 把J标记“访问过”；/ Ijq1,q2,.,qk distinguished = false; i = 1; while i n AND not distinguished do if J使得Jai J可区分的 then distinguished = true;把J 从 中删除；设T(qi ,a)落在划分的K个不同Ji1,., Jik； 把J划分成K个不相交的组并加入到中； else i = i+1; end if; end while; en

55、d if;/ 试算中的下一个状态子集end while;/ 直到的每个状态子集不可划分为止编译原理与技术722.4 有限自动机（2）取的每组中的一个状态作为代表，删除其它一切等价的状态，所有这些状态代表就构成了化简了的DFA状态集合；（3）每个状态组之间的连线变成每个状态代表之间的连线，去掉不可达状态和无用状态；（4）含有原来初态的等价状态组就是化简了的DFA的起始状态；（5）包含了原来终结状态的等价状态组就是化简了的DFA的终结状态；编译原理与技术732.4 有限自动机例2.15：图2.13所示的DFA的最小化过程如下:初始划分 = 0,1,2, 3,4,5,6，计算0,1,2a1,3，它不

56、包含在的任何一个子集当中，所以，可以把0,1,2分解.根据T(1,a)=3，T(0,a)=T(2,a)=1，把0,1,2分解成两个状态子集1和0, 2。这时的 = 1, 0, 2,3,4,5,6。继续划分：由于0, 2b=2,5未包含在当前划分的任何一个子集中，所以0, 2一分为二，得到新的划分 = 0, 1,2,3,4,5,6。由于3,4,5,6a=3,4,6，3,4,5,6b=4,5,6都包含在3,4,5,6内，不可再划分。至此，整个划分结束。令状态3代表3,4,5,6，把原来进入状态4、5和6的弧都导入3，删除状态4、5和6，得到最小化的DFA如图2.15。 编译原理与技术742.4 有

57、限自动机例2.15ab34a01bbba256baabbaaab3b01bba2baa最小化图2.13所示的DFA最小化的DFA编译原理与技术752.4 有限自动机例2.16：下图所示的DFA的最小化过程 ab43 b01bbba2baaa32b1bb0baaaa（1）因为状态仅状态4是终结状态，首先得划分4和0,1,2,3。（2）只需对0,1,2,3继续划分：0,1,2,3在面临字符a时，每个状态都转换到状态1，无法区分；而在面临符号b时，状态3进入状态4，状态0、1和2都转换到0,1,2,3内得状态，所以，可以把0,1,2,3分解成3和0,1,2，从而得到新的划分包括4、3和0,1,2。（

58、3）可能再分解的是0,1,2：在输入b时，T(0, b)2，T(1, b)=3, T(2, b)=2，据此可以把0,1,2分解成1和0, 2（4）继续尝试分解0, 2：这时的0, 2a1，0, 2b2，无法区分，划分完毕。（5）最小化的状态包括0, 2、1、3和4，重新命名、整理后得到右上图。编译原理与技术762.4 有限自动机从正规式到有限自动机 基于转换规则的算法，利用转移把单个的正规式粘接起来，形成更复杂的 、识别正规式表示语言的NFA。 定理2.3：(1) 对字母表上的任何一个正规表达式e都存在一个接受L(e)的有限自动机M，即L(e)L(M)。(2) 对字母表上的任何一个有限自动机M

59、都存在一个接受L(M)正规表达式e，即L(M)L(e) 。编译原理与技术772.4 有限自动机（1）对应于基本正规式a、的NFAa对应于基本正规式a的NFA是对应于基本正规式的NFA是对应于基本正规式的NFA是编译原理与技术782.4 有限自动机（2）选择替换规则：e1|e2表示成e2e1构造的有限自动机新增加了两个状态，分别表示开始状态和终结状态，然后把新增的起始状态与N(e1)和N(e2)的起始状态用转移连接起来，把N(e1)和N(e2)的终结状态与新增的终结状态用转移连接来，并且更改N(e1)和N(e2)起始状态和终结状态的性质。N(e1)接受的任何串s，等价于s，而它可以被N(e1|e

60、2)接受，即L(e1)L(e1|e2)。同样，L(e2)L(e1|e2)。反之，所有从N(e1|e2)的开始状态，经过N(e1)部分到达终结状态，所接受的语言是 L(e1) L(e1)，或者经过N(e2)部分到达终结状态，所接受的语言是 L(e2) L(e2)，即L(e1|e2) L(e1) L(e2)。所以L(e1|e2) L(e1) L(e2)。 编译原理与技术792.4 有限自动机（3）连接替换规则：e1e2表示成e2e1e1和e2连接成e1e2时，把N(e1)的终结状态改为非终结状态，然后通过转移与N(e2)的起始状态连接起来，N(e1)的起始状态成为N(e1e2)的起始状态，N(e2