编译原理习题课

1、3.5上下文无关文法及其语法树上下文无关文法及其语法树o上下文无关文法有足够的能力描述现今多数程上下文无关文法有足够的能力描述现今多数程序设计语言的语法结构。因此本书主要关心上序设计语言的语法结构。因此本书主要关心上下文无关文法的句子分析和分析方法的研究，下文无关文法的句子分析和分析方法的研究，本书中若无特别说明，均指该文法。本书中若无特别说明，均指该文法。o常用的描述上下文无关文法的句型推导的直观常用的描述上下文无关文法的句型推导的直观工具是语法工具是语法分析分析树，也称推导树。树，也称推导树。o语法分析树语法分析树：用一张图表示一个句型的推导，：用一张图表示一个句型的推导，这种表示称为语法

2、分析树，或简称为语法树。这种表示称为语法分析树，或简称为语法树。语法树需满足的语法树需满足的4 4个条件个条件o1)1)每个节点都有一个标记，此标记是每个节点都有一个标记，此标记是V V的一个的一个符号。符号。o2 2）根的标记是）根的标记是S S。o3 3）若一结点）若一结点n n至少有一个它自己除外的子孙，至少有一个它自己除外的子孙，并且有标记并且有标记A A，则，则A A肯定在肯定在V VN N中。中。o4 4）如果结点）如果结点n n的直接子孙，从左到右的次序的直接子孙，从左到右的次序是结点是结点n n1 1,n,n2 2,n,nk k，其标记分别是，其标记分别是A A1 1,A,A2

3、 2,A,Ak k ，那么那么A AA A1 1,A,A2 2,A,Ak k一定是一定是P P中的一个产生式。中的一个产生式。o有一句子：有一句子： He gave me a book He gave me a book 显然这是一个语法上正确的句子，它满足英语中的基本语显然这是一个语法上正确的句子，它满足英语中的基本语法规则，则可描述为：法规则，则可描述为： HeHe meme a a gavegave bookbook 举例举例说明语法树的构造过程说明语法树的构造过程o有了一组规则以后，按照如下方式用它们导出句子：开始去有了一组规则以后，按照如下方式用它们导出句子：开始去找找左端的带有左端

4、的带有 的规则并把它由的规则并把它由右端的符号串代替，右端的符号串代替，这个动作表示成：这个动作表示成： o然后选取然后选取 或或 ,再用相应规则的再用相应规则的右端代替之。右端代替之。这样重复做下去就可以得到最后的结果。这样重复做下去就可以得到最后的结果。 HeHe HeHe He gave He gave He gave me He gave me He gave me a He gave me a He gave me a bookHe gave me a booko可用一种图示化的方法来表示这种推导，其语法分可用一种图示化的方法来表示这种推导，其语法分析树如下：析树如下： He gav

5、e me a book1)1)上述定义英文句子的规则就是一个上下文无关文法。其上述定义英文句子的规则就是一个上下文无关文法。其中：中： 、 、 、 等，称为等，称为非终结符号非终结符号； 称为开始符号；称为开始符号； 称为称为产生式产生式。2 2）从上可知，一个上下文无关文法）从上可知，一个上下文无关文法G G包括包括四个组成部分四个组成部分： 一组终结符号，一组非终结符号，一个开始符号以及一组终结符号，一组非终结符号，一个开始符号以及一组产生式。一组产生式。 终结符号终结符号：组成语言的基本符号，就是单词符号如基本：组成语言的基本符号，就是单词符号如基本字，算符等。从语法分析的角度来看，终结

6、符号是一个字，算符等。从语法分析的角度来看，终结符号是一个语言的不可再分的基本符号。语言的不可再分的基本符号。非终结符号非终结符号：也称语法变量，用来代表语法范畴。例如，：也称语法变量，用来代表语法范畴。例如，“算术表达式算术表达式”、“分程序分程序”、“过程过程”等。也可等。也可以说，每个非终结符号表示一定符号串的集合以说，每个非终结符号表示一定符号串的集合开始符号开始符号：是一个特殊的非终结符号，它代表所定义的：是一个特殊的非终结符号，它代表所定义的语言中我们最终感兴趣的语法范畴，这个语法范畴，语言中我们最终感兴趣的语法范畴，这个语法范畴，通常称为通常称为“句子句子”。产生式产生式：是定义

7、语法范畴的一种书写规则。产生式的形：是定义语法范畴的一种书写规则。产生式的形式是：式是：A Aa a其中，箭头左边的其中，箭头左边的A A是一个非终结符，称是一个非终结符，称为产生式的左部符号；箭头右边的为产生式的左部符号；箭头右边的a a是由终结符或是由终结符或/ /与非终结符组成的一符号串，称为产生式的右部。与非终结符组成的一符号串，称为产生式的右部。o3 3）形式上说，一个上下文无关文法）形式上说，一个上下文无关文法G G是一个四元是一个四元式式G=G=（ V VT T , V , VN N , S, P , S, P），其中），其中: : V VT T是一个非空有限集，它的每个元素称为

8、终结符号；是一个非空有限集，它的每个元素称为终结符号； V VN N是一个非空有限集，它的每个元素称为非终结符号是一个非空有限集，它的每个元素称为非终结符号 ，V VT TVVN N S S是一个非终结符号，称为开始符号；是一个非终结符号，称为开始符号； P P是一个产生式集合（有限），每个产生式的形式是是一个产生式集合（有限），每个产生式的形式是 A A a a，其中，其中A (VA (VT TVVN N ) )* *。开始符号。开始符号S S至至少必须在某个产生式的左部出现一次。少必须在某个产生式的左部出现一次。注意注意，为了书写方便，若干个左部相同的产生式，如，为了书写方便，若干个左部相

9、同的产生式，如P P a1, a1, P Pa2,Pa2,Panan可合并为一个，缩写成可合并为一个，缩写成P P a1| a2|an a1| a2|an 其中每个其中每个aiai有时也称为是有时也称为是P P的一个候选式的一个候选式 箭头箭头“”读为读为“定义为定义为”，直竖，直竖“|”|”读为读为“或或”，它们，它们是元语言符号。是元语言符号。说明：说明：1.1.一般用大写字母一般用大写字母A A、B B、CC或汉语词组代表非终结符号或汉语词组代表非终结符号 2.2.用小写字母用小写字母 a a、b b、cc代表终结符号；代表终结符号； 3.3.用用、 等代表由终结符和非终结符组成的符号串

10、；等代表由终结符和非终结符组成的符号串； 4.4.为简便起见，当引用具体的文法例子时，仅列出产生式为简便起见，当引用具体的文法例子时，仅列出产生式和指出开始符号。和指出开始符号。 例如例如：一个上下文无关文法：一个上下文无关文法： E E i|EAEi|EAE； A A +|+|* * E E、A A是非终结符号，是非终结符号，E E是开始符号，而是开始符号，而i,+,i,+,* *是终结符是终结符o4 4）一个上下文无关文法定义一个语言的中一个上下文无关文法定义一个语言的中心思想：从文法的开始符号出发，反复连心思想：从文法的开始符号出发，反复连续使用产生式，对非终结符施行替换和展续使用产生式

11、，对非终结符施行替换和展开，例如，我们考虑下面的文法开，例如，我们考虑下面的文法G(G(E E) ) E EE+E|EE+E|E* *E|(E)|iE|(E)|i则根据规则有则根据规则有E E （E E） （E+EE+E） （i+Ei+E） (i+i)(i+i)o5）最左推导：任何一步）最左推导：任何一步都是对都是对中的最左非终结符进行替换；中的最左非终结符进行替换； 最右推导：任何一步最右推导：任何一步都是对都是对中的最右非终结符进行替换；中的最右非终结符进行替换；例如：例如：E+E E+E i+Ei+Ei+i i+i 最左推导最左推导 E+E E+E E+iE+ii+i i+i 最右推导最

12、右推导例如：例如：文法为文法为EE+T|TTT*F|FF(E)|a，符号串符号串w=a+a*a，写出其最左推导和最右推导的过程写出其最左推导和最右推导的过程定义定义3.7 3.7 等价文法等价文法如果两个不同的文法能产生相同的语言如果两个不同的文法能产生相同的语言, ,则则称这两个文法是等价文法称这两个文法是等价文法. .即即: :文法文法G G1 1和文法和文法G G2 2等价等价, , 是指是指L(GL(G1 1)=L(G)=L(G2 2) )例如文法例如文法GAGA：A A0R , 0R , A A01, 01, R RA1A1 和例和例3.13.1中的文法是等价的有：中的文法是等价的有

13、： L(G1)=L(G2)=0L(G1)=L(G2)=0n n1 1n n|N=1|N=1o例如：例如：文法文法GS，P：SaAS|aASbA|SS|ba，对对字符串字符串aabbaa，根据推导过程得到的语法树如下：，根据推导过程得到的语法树如下：二义性二义性 3.6.3句型分析的有关问题句型分析的有关问题o1）自上而下会面临替代选择问题，常用）自上而下会面临替代选择问题，常用回回溯溯方法来解决。方法来解决。o2）自下而上会面临精确定义）自下而上会面临精确定义“可规约串可规约串”的问题，采用的问题，采用句柄句柄的方法。的方法。短语短语, ,直接短语与句柄直接短语与句柄定义定义3.83.8设设是

14、文法是文法G G的一个句型的一个句型, , 如果有：如果有：oS=S=* *AA且且= =+ +则称则称是句型是句型相对相对于非终结符号的于非终结符号的短语短语。o特别地特别地, ,如果有如果有 = = 则称则称是句型是句型相对于产生式相对于产生式AA的的直接短语直接短语. .o一个句型的最左直接短语称为该句型的一个句型的最左直接短语称为该句型的句柄句柄. . (P44)(P44)素短语素短语o素短语素短语是一个短语是一个短语, ,它至少含有一个终结它至少含有一个终结符符, ,除它本身外不再含有更小的素短语除它本身外不再含有更小的素短语. .o最左素短语最左素短语是指处于句型最左边的那个是指处

15、于句型最左边的那个素短语素短语. .说明说明o 关于短语关于短语, ,直接短语和句柄直接短语和句柄 在短语的定义中有在短语的定义中有三个条件三个条件: : 1.w=xuy 1.w=xuy 是文法的一个句型是文法的一个句型 2.Z=2.Z=* *xUy; 3.U=xUy; 3.U=+ +uu 这三个条件必须都满足这三个条件必须都满足. . 实际上实际上,1,2 ,1,2 说明说明xuy,xUy xuy,xUy 都必须是句型都必须是句型, ,即都能由识别符号推出即都能由识别符号推出.2,3.2,3则说明则说明, ,将将xuy xuy 中的中的 u u 归约成归约成 U U 后后, ,得到的得到的

16、xUy xUy 一定要是一定要是句型句型. .假如一个符号串中有假如一个符号串中有 u, u, 但将其归约成但将其归约成 U U 后后得到的符号串不能由识别符号推出得到的符号串不能由识别符号推出, ,则则 u u 不是短语不是短语. .例例. .定义文法定义文法GE=(+,GE=(+,* *,(,),i,E,T,F,E,P),(,),i,E,T,F,E,P) 其中其中P P为：为：ET|E+TET|E+T TF|T TF|T* *F F Fi|(E) Fi|(E) 对于文法对于文法GEGE的句型的句型i i* *i+i. i+i. 找出该句型的所有找出该句型的所有的短语，直接短语和句柄。的短语

17、，直接短语和句柄。解：解：考虑文法考虑文法GEGE的句型的句型i i* *i+i. i+i. 为叙述方便，将为叙述方便，将句型写作句型写作 i i1 1* *i i2 2+i+i3 3. .因为有因为有: : 1.E = 1.E =* *FF* *i i2 2+i+i3 3, ,且且 F= iF= i1 1 , , 则称则称i i1 1是句型是句型i i1 1* *i i2 2+i+i3 3的相对于非终结符的相对于非终结符F F的短语，也是直接的短语，也是直接短语。短语。 2.E =2.E =* *ii1 1* *F+iF+i3 3, ,且且F=iF=i2 2 , , 则称则称i i2 2是句

18、型是句型i i1 1* *i i2 2+i+i3 3的相对于非终结符的相对于非终结符F F的短语，也是直接短语的短语，也是直接短语. . 3.E = 3.E =* *ii1 1* *i i2 2+F,+F,且且F=iF=i3 3 , ,则称则称i i3 3是句型是句型i i1 1* *i i2 2+i+i3 3的的相对于非终结符相对于非终结符F F的短语，也是直接短语。的短语，也是直接短语。E E T|E+TT|E+T， T T F|TF|T* *F F，F F i|(E)i|(E)4.E=4.E=* *TT* *i i2 2+i+i3 3, ,且且T=T=+ +ii1 1 , ,则称则称i

19、i1 1是句型是句型i i1 1* *i i2 2+i+i3 3的的相对于相对于T T的短语；的短语；5.E=5.E=* *T+iT+i3 3, ,且且T=T=+ +ii1 1 * *i i2 2 , ,则称则称i i1 1 * *i i2 2是句型是句型i i1 1* *i i2 2+i+i3 3的相对于的相对于T T的短语；的短语；6.E=6.E=* *ii1 1* *i i2 2+T,+T,且且T=T=+ +ii3 3 , ,则称则称i i3 3是句型是句型i i1 1* *i i2 2+i+i3 3的的相对于相对于T T的短语；的短语；7.E=7.E=* *E+iE+i3 3, ,且且

20、E=E=+ +ii1 1 * *i i2 2 , ,则称则称i i1 1* *i i2 2是句型是句型i i1 1* *i i2 2+i+i3 3的相对于的相对于E E的短语；的短语；8.E=8.E=* *E,E,且且E=E=+ +ii1 1 * *i i2 2 +i+i3 3 , ,则称则称i i1 1 * *i i2 2 +i+i3 3是句型是句型i i1 1* *i i2 2+i+i3 3的相对于的相对于E E的短语的短语. .E E T|E+TT|E+T， T T F|TF|T* *F F，F F i|(E)i|(E) 即即i i1 1,i,i2 2,i,i3 3, i, i1 1*

21、*i i2 2 ,i ,i1 1* *i i2 2+i+i3 3都是都是i i1 1 * *i i2 2 +i+i3 3的的短短语语, ,而且而且i i1 1,i,i2 2,i,i3 3 均是均是直接短语直接短语，其中，其中i i1 1是最左是最左直接短语直接短语, , 即即句柄句柄。 虽然虽然i i2 2+i+i3 3是句型是句型i i1 1* *i i2 2+i+i3 3的一部分，并不是它的一部分，并不是它的短语，因为尽管有的短语，因为尽管有E =E =+ +ii2 2+i+i3 3, ,但不存在从文但不存在从文法开始符号法开始符号E E到到i i1 1* *E E的推导。的推导。 又如上

22、述文法又如上述文法GEGE的一个句型的一个句型F F* *F+i,F+i, F F* *F,F,i F,F,i 和和F F* *F+iF+i都是它的短语都是它的短语, , 而而F F* *F F和和i i是它是它的素短语，的素短语， F F* *F F也是它的最左素短语也是它的最左素短语. .语法树对应的短语语法树对应的短语, ,直接短语和句柄直接短语和句柄o由由可以看出可以看出,是语法树生长过程中由是语法树生长过程中由A A结点结点开始向下生长出来的开始向下生长出来的全部树叶全部树叶，缺少一片树叶都不，缺少一片树叶都不满足满足.也即，这些树叶由左至右排列可以向也即，这些树叶由左至右排列可以向

23、上归结到某个结点上归结到某个结点( (比如说比如说A)A)，并且由该结点向下，并且由该结点向下生长出来的全部树叶也恰好是刚归结的这些树叶生长出来的全部树叶也恰好是刚归结的这些树叶, ,则这个树叶序列就是该结点的则这个树叶序列就是该结点的短语短语。o如果这种向上归结只需一层如果这种向上归结只需一层( (即树叶与该结点为父即树叶与该结点为父子关系），则为子关系），则为直接短语直接短语。o句柄句柄是语法树中最左那棵子树的树叶的自左至右排是语法树中最左那棵子树的树叶的自左至右排列，且这棵子树只有父子两代。列，且这棵子树只有父子两代。+例例: :设文法设文法G G 为为: :EE+T|TEE+T|TTT

24、+P|PTT+P|PP(E)|iP(E)|i试找出句型试找出句型P+T+(E+i)P+T+(E+i)的全部短语和直接短语的全部短语和直接短语, ,并找出句柄和最左素短语并找出句柄和最左素短语. . 解解: :设文法设文法G G 为为: :EE+T|TEE+T|TTT+P|PTT+P|PP(E)|iP(E)|i语法分析树语法分析树E ET TE EP PT T( () )E EP PE EP Pi i解解: :n 如果一个树叶序列由左至右排列最终能够到达某一结如果一个树叶序列由左至右排列最终能够到达某一结点上点上, ,并且包含由该结点推导出的全部树叶并且包含由该结点推导出的全部树叶, ,不多也不

25、不多也不少少, ,则这一树叶序列即为则这一树叶序列即为短语短语. .n 如果树叶序列与该结点仅差一层如果树叶序列与该结点仅差一层, ,即能够一步直接归结即能够一步直接归结到该结点到该结点, ,则为则为直接短语直接短语. .n 而位置在最左边的直接短语为而位置在最左边的直接短语为句柄句柄. .由语法树可以看出由语法树可以看出,P,P可以归结到可以归结到T,P+TT,P+T可以归结到可以归结到E,iE,i可以可以归结到归结到P,E+iP,E+i可以归结到可以归结到E, (E+i)E, (E+i)可以归结到可以归结到P,P+T+(E+i)P,P+T+(E+i)可以归结到可以归结到E.E.其中能够一步

26、归结到某一结其中能够一步归结到某一结点的只有点的只有P P和和i,i,所以得出所以得出: :短语短语: P, P+T, i,E+i, (E+i): P, P+T, i,E+i, (E+i)和和P+T+(E+i);P+T+(E+i);直接短语直接短语: P, i: P, i句柄句柄: P: P解解: :n 从语法树上寻找最左素短语应遵从语法树上寻找最左素短语应遵循这样一个原则循这样一个原则: :u 同层的相邻终结符优先关系同层的相邻终结符优先关系为为”u 不同层相邻的终结符不同层相邻的终结符, ,层次在下的层次在下的优先级高优先级高, ,层次在上的优先级低层次在上的优先级低. .从左至右扫描语法

27、分析树的终结符序从左至右扫描语法分析树的终结符序列可以得到：列可以得到：#+ + (+i)#+ + (+i)#由由+ + 和和i i 可知素短语为可知素短语为P+TP+T和和i,i,最左素短语为最左素短语为P+T.P+T.E ET TE EP PT T( () )E EP PE EP Pi i例：例：T * F E + TiET* * + i + i 4.34.3有穷自动机有穷自动机o有穷自动机（也称有限自动机）作为一种识有穷自动机（也称有限自动机）作为一种识别装置，它能准确地识别正规集。别装置，它能准确地识别正规集。o引入的目的，是为词法分析程序的自动构造引入的目的，是为词法分析程序的自动构

28、造寻找特殊的方法和工具。寻找特殊的方法和工具。o有限自动机分为两类：确定的有限自动机和有限自动机分为两类：确定的有限自动机和非确定的有限自动机。非确定的有限自动机。4.3.1 4.3.1 确定有限自动机（确定有限自动机（DFADFA）o(1)(1)确定的有限自动机确定的有限自动机 (DFA) (DFA) M M （五元式）（五元式） M = M = （S, S, , , , s , s0 0, F, F） S S：有限状态集合，每个元素称为一个状态：有限状态集合，每个元素称为一个状态 ：是一个有穷字母表：是一个有穷字母表, , 每个元素称为一个输入字符每个元素称为一个输入字符：S S S S

29、的单值部分映射。的单值部分映射。(s,a)=s(s,a)=s意味意味着：当现行状态为着：当现行状态为s s、输入字符为、输入字符为a a时，将转换到下一状时，将转换到下一状态态ss。我们称。我们称s s 为为s s的一个后继状态。的一个后继状态。s s0 0：s s0 0 S S，是唯一的初态，是唯一的初态F F S S：终态集合终态集合o确定的含义确定的含义：下一个输入字符唯一地确定了下一个当前：下一个输入字符唯一地确定了下一个当前状态。状态。(2)(2)状态转换矩阵状态转换矩阵o一个一个 DFA DFA 可用一个矩阵表示可用一个矩阵表示, , 该矩阵的行表该矩阵的行表示状态，列表示输入字符

30、，矩阵元素表示示状态，列表示输入字符，矩阵元素表示(s,a) (s,a) 的值。这个矩阵称为状态转换矩阵。的值。这个矩阵称为状态转换矩阵。 例如，有例如，有 DFADFAM=(0,1,2,3,a,b, ,0,3), M=(0,1,2,3,a,b, ,0,3), 为：为：(0,a)=1 (0,b)=2 (1,a)=3 (1,b)=2 (0,a)=1 (0,b)=2 (1,a)=3 (1,b)=2 (2,a)=1 (2,b)=3 (3,a)=3 (3,b)=3 (2,a)=1 (2,b)=3 (3,a)=3 (3,b)=3 画出它的状态转化矩阵画出它的状态转化矩阵表表4.2 状态转换矩阵状态转换矩

31、阵状态状态ab012132213333状态转换图状态转换图o一个一个DFADFA也可表示成一张（确定的）状态转换图。假定也可表示成一张（确定的）状态转换图。假定DFA DFA M M含有含有m m个状态和个状态和n n个输入字符，则有如下特点：个输入字符，则有如下特点：1 1）这个图含有）这个图含有m m个状态结点，每个结点顶多有个状态结点，每个结点顶多有n n条箭弧射条箭弧射出和别的结点相连接；出和别的结点相连接；2 2）每条箭弧用）每条箭弧用中的一个不同输入字符做标记；中的一个不同输入字符做标记；3 3）整张图含有唯一的一个初态结点和若干个（可以是）整张图含有唯一的一个初态结点和若干个（可

32、以是 0 0个）终态结点。个）终态结点。对于对于* *中的任何字中的任何字a a，若存在一条从初态结点到某一终态，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字等结点的通路，且这条通路上所有弧的标记符连接成的字等于于a a，则称，则称a a可为可为DFA MDFA M所识别（读出或接受）。若所识别（读出或接受）。若M M的初态的初态结点同时又是终态结点，则空字结点同时又是终态结点，则空字 可为可为M M所识别。所识别。DFA MDFA M所能识别的字符全体记为所能识别的字符全体记为L L（M M）。）。状态转换图状态转换图o上例所定义的上例所定义的DFA M相应

33、的状态转换图如下图所相应的状态转换图如下图所示。它能识别示。它能识别上所有含有相继两个上所有含有相继两个a a或相继两个或相继两个b b的字。的字。 0123abbaaa,bb非确定有限自动机非确定有限自动机(NFA)(NFA)o非确定的有限自动机非确定的有限自动机 NFA NFA M M （五元组）（五元组） M = M = （S, S, , , , S , S0 0, F, F） S S：有限状态集合，每个元素称为一个状态：有限状态集合，每个元素称为一个状态 ：字母表：字母表, , 每个元素称为一个输入字符每个元素称为一个输入字符 ：S S * *S S的子集的映像，即：的子集的映像，即：

34、S S * *2 2S S， 其中其中2 2S S表示表示S S的幂集；的幂集；S S0 0 S S ：非空初态集非空初态集F F S S：终态集合（可空）终态集合（可空）oDFA DFA 是是NFA NFA 的特例的特例o一个一个NFANFA也可表示成一张状态转换图。假定也可表示成一张状态转换图。假定NFA MNFA M含有含有m m个状态个状态和和n n个输入字符，则有如下特点：个输入字符，则有如下特点：1 1）这个图含有）这个图含有m m个状态结点，每个结点可射出若干条箭弧和别个状态结点，每个结点可射出若干条箭弧和别的结点相连接；的结点相连接；2 2）每条弧用）每条弧用* *中的一个字（

35、不一定要不同的字而且可以是空中的一个字（不一定要不同的字而且可以是空字字）作标记；）作标记；3 3）整张图至少含有一个初态结点以及若干个（可以是）整张图至少含有一个初态结点以及若干个（可以是 0 0个）个）终态结点。某些结点既可以是初态结点也可以是终态结点。终态结点。某些结点既可以是初态结点也可以是终态结点。对于对于* *中的任何字中的任何字a a，若存在一条从初态结点到某一终态结点，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字（忽略那些的通路，且这条通路上所有弧的标记符连接成的字（忽略那些标记为标记为的弧）等于的弧）等于a a，则称，则称a a可为可为NFA

36、 MNFA M所识别（读出或接所识别（读出或接受）。若受）。若M M的某些结点既是初态结点又是终态结点，或者存在的某些结点既是初态结点又是终态结点，或者存在一条从某个初态结点到某个终态结点的一条从某个初态结点到某个终态结点的通路，则空字通路，则空字 可可为为M M所识别。所识别。NFA NFA 的例子的例子X531426Ya aa ab bb ba aa ab bb b该该NFA所能识别的也是所有含有相继两个所能识别的也是所有含有相继两个a或相继两个或相继两个b的字。的字。图图4.3 非确定有限自动机非确定有限自动机关于关于DFA DFA 与与 NFANFAoDFA DFA 与与 NFA NF

37、A 的区别在两方面：的区别在两方面：n一是一是NFA NFA 可有若干个开始状态，而可有若干个开始状态，而DFADFA仅一个。仅一个。n另一方面，另一方面，DFA DFA 的映象的映象 是从是从S S 到到 S S 的映象的映象, , 而而NFA NFA 的映象的映象 是从是从S S * *到到 S S 的的幂集的映象幂集的映象, , 即映象即映象M M 将产生一个状态集合将产生一个状态集合（可能为空集），（可能为空集）， 而不是单个状态。而不是单个状态。 关于状态集合关于状态集合I I的几个有关运算的几个有关运算o状态集合状态集合I I的的- - 闭包闭包, ,表示为表示为-CLOSURE(

38、I),-CLOSURE(I), 定义为一状态集定义为一状态集, , 是状态集中是状态集中I I的任何状态的任何状态S S经任意条经任意条弧而能到达的状态的集合。弧而能到达的状态的集合。n状态集合状态集合I I的任何状态的任何状态S S都属于都属于-CLOSURE(I).-CLOSURE(I).o状态集合状态集合I I的的a a弧转换，表示为弧转换，表示为move(I,a)move(I,a)定义为状态定义为状态集合集合J, J, 其中其中J J是所有那些可以从是所有那些可以从I I中的某一状态经过中的某一状态经过一条一条a a弧而到达的状态的全体。弧而到达的状态的全体。 例例:o- CLOSUR

39、E(0)=0,1,2,4,7 ,- CLOSURE(0)=0,1,2,4,7 ,即即0,1,2,4,70,1,2,4,7中的任一状态中的任一状态都是从都是从0 0经任意条经任意条弧可到达的状态弧可到达的状态, , 令令0,1,2,4,7=A, 0,1,2,4,7=A, 则则move(A,a)=3,8,move(A,a)=3,8,因为在状态因为在状态 0,1,2,4,70,1,2,4,7中中, ,只有只有2 2和和7 7 有有a a弧弧射出射出, ,分别到达状态分别到达状态3 3和和8.8.o而而 - CLOSURE(3,8)=1,2,3,4,6,7,8 - CLOSURE(3,8)=1,2,3

40、,4,6,7,8 012345678910图图4.4 NFA N4.4 NFA N证明证明 子集法子集法o显然，显然，DFADFA是是NFANFA的特例。但是，对于每个的特例。但是，对于每个NFA MNFA M存在一存在一个个DFA M”DFA M”，使，使L L（M M）=L=L（M”M”）。证明过程如下：）。证明过程如下：1 1）假定）假定NFA NFA M = M = （S, S, , , , S , S0 0, F, F） ，我们对，我们对M M的的状态转换图进行如下改造：状态转换图进行如下改造：引进新的初态结点引进新的初态结点X X和终态和终态Y Y，X X，Y Y S S，从，从X

41、 X到到S S0 0中中任意状态结点连一条任意状态结点连一条箭弧，从箭弧，从F F中任意状态结点连一中任意状态结点连一条条箭弧到箭弧到Y Y。 对对M M的状态转换图进一步施行图的状态转换图进一步施行图4.54.5所示的替换，其所示的替换，其中中K K是新引入的状态。是新引入的状态。 重复这种分裂过程直至状态转换图中的每条箭弧重复这种分裂过程直至状态转换图中的每条箭弧上的标记或为上的标记或为，或为，或为中的单个字母。将最终得到的中的单个字母。将最终得到的NFANFA记为记为MM，显然，显然L L（MM）=L=L（M M）。）。2 2）将）将MM进一步变换为进一步变换为DFADFA，方法如下：，

42、方法如下： 假定假定I I是是MM的状态集的子集，定义的状态集的子集，定义I I的的闭闭_CLOSURE(I)_CLOSURE(I)为：为： a)a)若若q I q I ，则，则q_CLOSURE(I)q_CLOSURE(I)； b)b)若若q I q I ，那么从，那么从q q出发经任意条出发经任意条弧而能到达的任何状弧而能到达的任何状态态 qq都属于都属于_CLOSURE(I)_CLOSURE(I)；iijkjijijijikj代之以代之以代之以代之以代之以代之以图补图补4.1 替换规则替换规则假定假定I I是是MM的状态集的子集，的状态集的子集，aa，定义，定义I Ia a=_CLOSU

43、RE(J)=_CLOSURE(J)其中，其中，J J是那些可从是那些可从I I中的某一状态结点出中的某一状态结点出发经过一条发经过一条a a弧而到达的状态结点的全体。弧而到达的状态结点的全体。J=move(I,a)J=move(I,a) 假定假定=a1,a2,ak=a1,a2,ak。我们构造一张表，此表的每一行。我们构造一张表，此表的每一行含含K+1K+1列。置该表的首行首列为列。置该表的首行首列为_CLOSURE(X)_CLOSURE(X)。一般而言，。一般而言，如果某一行的第一列的状态子集已经确定，例如记为如果某一行的第一列的状态子集已经确定，例如记为I I，那么，置该行的那么，置该行的i

44、+1i+1列为列为I Iaiai(i=1,k)(i=1,k)。然后，检查该行上。然后，检查该行上的所有状态子集，看它们是否已在表的第一列中出现，将的所有状态子集，看它们是否已在表的第一列中出现，将未曾出现者填入到后面空行的第一列。重复上述过程，直未曾出现者填入到后面空行的第一列。重复上述过程，直至出现在第至出现在第i+1i+1列（列（i=1,ki=1,k）上的所有状态子集均已在第）上的所有状态子集均已在第一列上出现。因为一列上出现。因为MM的状态子集的个数是有限的，所以的状态子集的个数是有限的，所以上述过程必定在有限步内终止。上述过程必定在有限步内终止。X531426Ya aa ab bb b

45、a aa ab bb b图补图补4.2非确定有限自动机非确定有限自动机对图对图补补4.1的非确定有限自动机用子集法对其进行构造可有下面的表结构，的非确定有限自动机用子集法对其进行构造可有下面的表结构，其中它的初态是该表首行首列的那个状态，终态是那些含有原终态的其中它的初态是该表首行首列的那个状态，终态是那些含有原终态的状态子集。状态子集。I II Ia aI Ib bX,5,1X,5,15,3,15,3,15,4,15,4,15,3,15,3,15,3,1,2,6,Y5,3,1,2,6,Y5,4,15,4,15,4,15,4,15,3,15,3,15,4,1,2,6,Y5,4,1,2,6,Y5

46、,3,1,2,6,Y5,3,1,2,6,Y5,3,1,2,6,Y5,3,1,2,6,Y5,4,1,6,Y5,4,1,6,Y5,4,1,6,Y5,4,1,6,Y5,3,1,6,Y5,3,1,6,Y5,4,1,2,6,Y5,4,1,2,6,Y5,4,1,2,6,Y5,4,1,2,6,Y5,3,1,6,Y5,3,1,6,Y5,4,1,2,6,Y5,4,1,2,6,Y5,3,1,6,Y5,3,1,6,Y5,3,1,2,6,Y5,3,1,2,6,Y5,4,1,6,Y5,4,1,6,Y表表补补4.1 对应与正规式对应与正规式(a|b)(a|b)* *(aa|bb)(a|b)(aa|bb)(a|b)* *的

47、状态转换矩阵的状态转换矩阵对表补对表补4.14.1中所有状态子集重新命名，得到状态转换矩阵为：中所有状态子集重新命名，得到状态转换矩阵为：Sab012132215334465565634表表补补4.2 对表对表4.3中状态子集重新命名后的状态转换矩阵中状态子集重新命名后的状态转换矩阵对应的状态转换图对应的状态转换图0531426a aa ab bb ba ab bb bb ba ab ba ab b图图补补4.3 未简化的未简化的DFA其中其中0为初态为初态，3、4、5和和6为终态。为终态。o对于一个对于一个NFA N=(K,NFA N=(K,f,K,f,K0 0,K,Kt t) )来说，若来

48、说，若I I是是K K的的一个子集，不妨设一个子集，不妨设I=sI=s1 1,s,s2 2,s,sj j, a, a是是中的中的一个元素，则一个元素，则Move(I,a)=f(sMove(I,a)=f(s1 1,a)f(s,a)f(s2 2,a) ,a) f(sf(sj j,a).,a).o假设假设NFA N=(K,NFA N=(K,f,K,f,K0 0,K,Kt t) )按如下办法构造一个按如下办法构造一个DFA M=(S,DFA M=(S,D,S,D,S0 0,S,St t), ), 使得使得L(M)=L(N):L(M)=L(N):o1.M 1.M 的状态集的状态集S S由由K K的一些子

49、集组成。用的一些子集组成。用SS1 1,S,S2 2,S,Sj j 表示表示S S的元素，其中的元素，其中S S1 1,S,S2 2,S,Sj j是是K K的状态的状态. .o2.M2.M和和N N的输入字母是相同的，即是的输入字母是相同的，即是利用子集法由利用子集法由NFANFA构造构造DFADFAo3.3.转换函数转换函数 D D 是这样定义的：是这样定义的： D(SD(S1 1,S,S2 2,S,Sj j,a)=R,a)=R1 1,R,R2 2,R,Rj j 其中其中-CLOSURE(MoveS-CLOSURE(MoveS1 1,S,S2 2,S,Sj j,a),a) =R =R1 1,

50、R,R2 2,R,Rj j o4.S4.S0 0=-CLOSURE(K=-CLOSURE(K0 0) )为为M M的开始状态。的开始状态。o5. S5. St t=S=Sj j,S,Sk k,S,Se e,其中其中SSj j,S,Sk k,S,Se eSS且且 SSj j,S,Sk k,S,Se e K Kt t S St t和和K Kt t为各自的终态为各自的终态. .利用子集法由利用子集法由NFANFA构造构造DFADFAo假定所构造的子集族为假定所构造的子集族为C,C,即即C=(TC=(T1 1,T,T2 2,T,Ti i),),其中其中T T1 1,T,T2 2,T,Ti i为状态为状

51、态K K的子集的子集. .o1.1.开始，令开始，令-CLOSURE(K-CLOSURE(K0 0) )为为C C中唯一成员，并且它是未中唯一成员，并且它是未被标记的。被标记的。o2.While(C 2.While(C 中存在尚未被标记的子集中存在尚未被标记的子集T) doT) do 标记标记T;T; for for 每个输入字母每个输入字母a doa do U:= -CLOSURE(Move(T,a); U:= -CLOSURE(Move(T,a); if U if U 不在不在C C中，中，thenthen 将将U U作为未被标记的子集加在作为未被标记的子集加在C C中中 子集构造法子集构

52、造法o1.1.首先计算首先计算-CLOSURE(0),-CLOSURE(0),令令T T0 0 =-CLOSURE(0) =0,1,2,4,7, T=-CLOSURE(0) =0,1,2,4,7, T0 0未被未被标记标记, ,它现在是子集族它现在是子集族C C的唯一成员。的唯一成员。o2.2.标记标记T T0 0 ; ;令令T T1 1 = -CLOSURE(Move(T= -CLOSURE(Move(T0 0,a) ,a) =-CLOSURE(3,8) =1,2,3,4,6,7,8, =-CLOSURE(3,8) =1,2,3,4,6,7,8,将将T T1 1加入加入C C中，中， T T

53、1 1未被标记未被标记. .o令令T T2 2 = -CLOSURE(Move(T= -CLOSURE(Move(T0 0,b) ,b) =-CLOSURE(5)=1,2,4,5,6,7, =-CLOSURE(5)=1,2,4,5,6,7,将将T T2 2加入加入C C中，中，T T2 2未被标记未被标记. .o3.3.标记标记T T1 1 ; ;计算计算-CLOSURE(Move(T-CLOSURE(Move(T1 1,a)=-CLOSURE(3,8) ,a)=-CLOSURE(3,8) 结果为结果为 1,2,3,4,6,7,8,1,2,3,4,6,7,8,即即T T1 1， T T1 1已

54、在已在C C中中. .o计算计算-CLOSURE(Move(T-CLOSURE(Move(T1 1,b)=-CLOSURE(5,9), ,b)=-CLOSURE(5,9), 结果为结果为 1,2,4,5,6,7,9,1,2,4,5,6,7,9,令其为令其为T T3 3， T T3 3加至加至C C中中, , 它未被标记它未被标记解：解： 对上述的对上述的NFA NNFA N构造子集：构造子集：012345678910a ab ba ab bb bo4.4.标记标记T T2 2 ; ;计算计算-CLOSURE(Move(T-CLOSURE(Move(T2 2,a),a) =-CLOSURE(3,

55、8), =-CLOSURE(3,8), 结果为结果为 1,2,3,4,6,7,8,1,2,3,4,6,7,8,即即T T1 1， T T1 1已在已在C C中中. .o计算计算-CLOSURE(Move(T-CLOSURE(Move(T2 2,b)=-CLOSURE(5), ,b)=-CLOSURE(5), 结果为结果为 1,2,4,5,6,7,1,2,4,5,6,7,即即T T2 2， T T2 2已在已在C C中中. . o5.5.标记标记T T3 3 ; ;计算计算-CLOSURE(Move(T-CLOSURE(Move(T3 3,a),a) =-CLOSURE(3,8), =-CLOS

56、URE(3,8),结果为结果为 1,2,3,4,6,7,8,1,2,3,4,6,7,8,即即T T1 1. .o计算计算-CLOSURE(Move(T-CLOSURE(Move(T3 3,b)=-CLOSURE(5,10),b)=-CLOSURE(5,10),结果为结果为1,2,4,5,6,7,10,1,2,4,5,6,7,10,另其为另其为T T4,4,加入加入C C中，中，T T4 4未被标记未被标记. .o6.6.标记标记T T4 4 ; ;计算计算-CLOSURE(Move(T-CLOSURE(Move(T4 4,a)=-CLOSURE(3,8), ,a)=-CLOSURE(3,8),

57、 结果为结果为 1,2,3,4,6,7,8,1,2,3,4,6,7,8,即即T T1 1. .o计算计算-CLOSURE(Move(T-CLOSURE(Move(T4 4,b)= -CLOSURE(5), ,b)= -CLOSURE(5), 结果为结果为 1,2,4,5,6,7,1,2,4,5,6,7,即即T T2.2.解：解： 对上述的对上述的NFA NNFA N构造子集：构造子集：o至此，算法终止共构造了五个子集：至此，算法终止共构造了五个子集： T T0 0 = 0,1,2,4,7 T= 0,1,2,4,7 T1 1 = 1,2,3,4,6,7,8= 1,2,3,4,6,7,8 T T2

58、 2 = 1,2,4,5,6,7 T= 1,2,4,5,6,7 T3 3 = 1,2,4,5,6,7,9= 1,2,4,5,6,7,9 T T4 4 = 1,2,4,5,6,7,10= 1,2,4,5,6,7,10o则则NFA N NFA N 构造的构造的 DFA M DFA M 为：为：1.S=T1.S=T0 0, T, T1 1, T, T2 2, T, T3 3, T, T4 42.2. =a,b =a,b3. D(3. D(TT0 0,a)= T,a)= T1 1 D(D(TT0 0,b)= T,b)= T2 2 D(D(TT1 1,a)= T,a)= T1 1 D(D(TT1 1,b

59、)= T,b)= T3 3 D(D(TT2 2,a)= T,a)= T1 1 D(D(TT2 2,b)= T,b)= T2 2 D(D(TT3 3,a)= T,a)= T1 1 D(D(TT3 3,b)= T,b)= T4 4 D(D(TT4 4,a)= T,a)= T1 1 D( D(TT4 4,b)= T,b)= T2 2 4. S4. S0 0 = T= T0 0 5. S5. St t = T= T4 4 解：解： 对上述的对上述的NFA NNFA N构造子集：构造子集：解：解： 对上述的对上述的NFA N构造子集：构造子集：o将将TT0 0,T,T1 1,T,T2 2,T,T3 3,

60、T,T4 4 重新命重新命名，以利于重写，如用名，以利于重写，如用0,1,2,3,40,1,2,3,4分分别表示，该别表示，该 DFA DFA 图为：图为：01234b ba aa aa aa aa ab bb bb b图图4.6 DFA Msab012113212314412b b4.3.44.3.4确定有限自动机的化简确定有限自动机的化简o一个确定有限自动机的化简是指：寻找一个状态一个确定有限自动机的化简是指：寻找一个状态数比数比M M少的少的DFA M,DFA M,使得使得L(M)=L(M)L(M)=L(M)oDFADFA最小化的最小化的关键关键在于把它的状态集分成一些两在于把它的状态集