编译原理词法2(NFA、DFA的确定化和化简)

,第二级,第三级,第四级,第五级,第,3,讲,编译原理,西北农林科技大学本科教程,主讲教师：赵建邦,第二章,词法分析,节,2.3,正规表达式与有限自动机简介,2.4,正规表达式到优先自动机的构造,2.5,词法分析器的自动生成,重点掌握,有限自动机理论,有限自动机的,构造、确定化和化简,本讲目标,第二章 词法分析,2.1,词法分析的设计方法,2.2,一个简单的词法分析器,2.3,正规表达式与有限自动机简介,2.4,正规表达式到有限自动机的构造,2.5,词法分析器的自动生成,：有限自动机：可以自动识别单词的机器,有限自动机（,F,inite,A,utomation,）：,FA,是一个状态转换图，“有限”指的是状态有限。当前状态读入一个字符后，和后继状态的转换有以下三种情形：,(1),后继状态为自身,(2),后继状态只有一个,(3),后继状态有多个,如果每次转换的后继状态是唯一的，则称它为,确定有限自动机,（,D,eterministic,FA,）,如果每次转换的后继状态不是唯一的，则称它为,非确定有限自动机,（,N,ondeterministic,FA,）,2.3,正规表达式与优先自动机简介,：有限自动机,1,、确定有限自动机（,DFA,）：,DFA,是一个五元组，,M,d,(S,f,s,0,Z),，其中：,(1),S,是一个有限状态集合，它的每个元素称为一个,状态,(2),是一个有穷,字母表,，它的每个元素称为一个,输入字符,f,是一个从,S,至,S,的单值映射，也叫状态转移函数,s,0,S,是唯一的,初态,是一个,终态集,2.3,正规表达式与优先自动机简介,：有限自动机,1,、确定有限自动机（例,2.4,）：,假定,DFA,M,d,=(,s,0,s,1,s,2,，,a,b,f,s,0,s,2,),，,状态转移函数：,f(,s,0,a,)=,s,1,f(,s,0,b,)=,s,2,f(,s,1,a,)=,s,1,f(,s,1,b,)=,s,2,f(,s,2,a,)=,s,2,f(,s,2,b,)=,s,1,2.3,正规表达式与优先自动机简介,状态转换图：,s,2,s,0,s,1,a,b,a,b,a,b,状态转换矩阵,：,f,a,b,S,s,0,s,1,s,2,s,1,s,1,s,2,s,2,s,2,s,1,：有限自动机,2,、非确定有限自动机（,NFA,）：,NFA,是一个五元组，,M,d,(S,f,Q,Z),，其中：,(1),S,是一个有限状态集合，它的每个元素称为一个,状态,(2),是一个有穷,字母表,，它的每个元素称为一个,输入字符,(3),f,是一个从,S,*至,S,的多值映射，也叫状态转移函数,(4),Q,S,是非空,初态集,(5),是一个,终态集,NFA,相比于,DFA,的特征：,若干个初始状态,(2)f,多值映射,(3),允许接收字和空字符,2.3,正规表达式与优先自动机简介,：有限自动机,2,、非确定有限自动机（例,2.5,）：,假定,NFA,M,n,=(,s,0,s,1,s,2,a,b,f,s,0,s,2,s,2,),，,状态转移函数：,f(,s,0,a,)=,s,2,f(,s,0,b,)=,s,0,s,2,f(,s,1,a,)=,f(,s,1,b,)=,s,2,f(,s,2,a,)=,f(,s,2,b,)=,s,1,2.3,正规表达式与优先自动机简介,状态转换矩阵,：,f,a,b,S,s,0,s,2,s,0,s,2,s,1,s,2,s,2,s,1,状态转换图：,s,1,s,0,s,2,b,a,b,b,b,：有限自动机（识别的语言）,对于一个自动机,FA,而言，如果存在一条从初始状态到终止状态的通路，通路上有向边所识别的字符依次连接所得到的字符串为,则称,可以为,FA,所接受或者,为,FA,所识别,FA,所能识别的字符串集为,FA,所识别的语言，记为,L(M),FA,的,等价,：对于任意两个,FA M,和,FA M,如果,L(M)=L(M),则称,M,和,M,等价,对于任意一个,NFA M,，一定存在一个,DFA M,与其等价,2.3,正规表达式与优先自动机简介,2.3,课堂例题,例,2.5,接受与正规式,(a|b),*,abb,相同的语言的,DFA,与,NFA,:,DFA,：,s,3,s,0,s,2,a,a,b,b,b,a,a,b,s,1,NFA,：,s,3,s,0,s,2,a,a,b,a,b,s,1,DFA,识别,abb aabb abab,无论成功或者失败只需要,运行一次,NFA,识别,abb aabb abab,无论成功或者失败可能需要,运行若干次,第二章 词法分析,2.1,词法分析的设计方法,2.2,一个简单的词法分析器,2.3,正规表达式与有限自动机简介,2.4,正规表达式到有限自动机的构造,2.5,词法分析器的自动生成,需要了解的等价性：,1.,如果,R,是字母表,上的一个正规式，则必然存在一个,NFA M,，使得,L(M)=L(R),;,2.,对于任意一个,NFA M,，一定存在一个,DFA M,与其等价,即,L(M)=,L(,M,),;,从正规式开始构造,DFA,的过程有以下几个步骤：,1.,由正规式构造,NFA;,2.,由,NFA,构造与之等价的,DFA,（确定化）,3.DFA,的化简,2.4,正规表达式到有限自动机的构造（重点）,：由正规式构造等价的,NFA,1,、对于给定的正规式,R,，将其表示成,称为“,拓广转换图,”其中,X,为初始状态，,Y,为终止状态,2,、对正规式中的三种运算，分别采用如下的对应转换规则,2.4,正规表达式到有限自动机的构造,Y,X,R,s,i,r,1|,r,2,s,j,s,i,r,1,s,j,r,2,s,i,r,1,r,2,s,j,s,i,r,1,s,k,r,2,s,j,s,i,s,j,r,1,*,s,i,s,k,s,j,r,1,2.4,正规表达式到有限自动机的构造,例,2.6,对给定正规表达式,b*(d|ad)(b|ab),+,构造其,NFA M,X,按照正规式从左到右构造,NFA,：,解答,先用,R,+,=RR,*,改造正规表达式,b*(d|ad)(b|ab),+,=,b*(d|ad)(b|ab)(b|ab)*,b,a,d,d,a,b,b,Y,b,a,b,1,3,4,2,6,5,8,7,：,NFA,的确定化（相关概念）,NFA,的确定化,：构造一个和,NFA,等价的,DFA,状态集合,I,的,_,闭包,设,I,是,FA M,的状态子集，则以下状态属于,_CLOSURE(I),：,(1),若,s,i,I,，则,s,i,_CLOSURE(I),；,(2),若,s,i,I,，则对从,s,i,出发经过任意条通路所能到达的,状态,s,j,，都有,s,j,_CLOSURE(I),。,定义,I,a,=,_CLOSURE(J),，其中：,I=,s,1,s,2,s,n,，,J=f(I,a)=f(,s,1,a),f(,s,2,a),f(,s,n,a),2.4,正规表达式到有限自动机的构造,1,5,2,4,2.4,正规表达式到有限自动机的构造,例,2.7,已知一状态转换图如下图所示，且假定,I=,_CLOSURE(1)=1,2,，试求从状态集,I,出发经过一条有向边,a,能到达的状态集,J,和,_CLOSURE(J),6,3,7,8,a,a,a,解答,状态集,I,经过一条,a,弧得到,J,，,J=5,3,4,J,中的每一个状态经过任意条通路得到,_CLOSURE(J)=,I,a,=5,6,2,3,8,4,7,：,NFA,的确定化（子集法）,(1),构造一张转换表，第一列记为状态子集,I,，对于不同的符号,(a,),，在表中单设一列,I,a,；,(2),表的首行首列置为,_CLOSURE(,s,0,),，,其中,s,0,为初始状态；,(3),根据首行首列的,I,，为每个,a,求其,I,a,并记入对应的,I,a,列中，,如果此,I,a,不同于第一列中已存在的所有状态子集,I,，则将其,顺序列入空行中的第一列；,(4),重复,(3),直至对每个,I,及,a,均已求得,I,a,，并且无新的状态子集,I,a,加入第一列时为止；,(5),重新命名第一列的每一个状态子集，形成新的状态转换矩阵，,即为与,NFA,等价的,DFA,2.4,正规表达式到有限自动机的构造,2.4,正规表达式到有限自动机的构造,例,2.8,求正规表达式,(a|b),*,(aa|bb)(a|b),*对应的,DFA M,解答,首先根据正规式构造,NFA M:,X,b,a,1,2,3,4,5,b,a,6,Y,a,b,a,b,1.,构造状态转换表,:,I,I,a,I,b,X,1,2,1,2,3,1,2,4,1,2,3,1,2,4,2.,确定首行首列,:,_CLOSURE(,s,0,),3.,依次计算,I,a,和,I,b,并更新首列,2.4,正规表达式到有限自动机的构造,X,b,a,1,2,3,4,5,b,a,6,Y,a,b,a,b,I,I,a,I,b,X,1,2,1,2,3,1,2,4,1,2,3,1,2,4,1,2,3,5,6,Y,1,2,4,1,2,3,5,6,Y,1,2,3,1,2,4,5,6,Y,1,2,4,5,6,Y,1,2,3,5,6,Y,1,2,4,6,Y,1,2,4,6,Y,1,2,3,6,Y,1,2,3,6,Y,1,2,4,5,6,Y,1,2,3,6,Y,1,2,4,5,6,Y,1,2,3,5,6,Y,1,2,4,6,Y,4.,重复,(3),直至无新状态加入首列为止,5.,新的状态转换矩阵,S,a,b,0,1,2,3,4,5,6,1,3,1,3,6,6,3,2,2,4,5,4,4,5,X,b,a,1,2,3,4,5,b,a,6,Y,a,b,a,b,S,a,b,0,1,2,3,4,5,6,1,3,1,3,6,6,3,2,2,4,5,4,4,5,a,0,a,1,2,3,b,a,b,a,b,4,5,b,a,6,b,a,b,b,a,得到新的状态转换图,DFA:,2.4,正规表达式到有限自动机的构造,：,DFA,的化简,状态的,等价,：,假设,s,1,和,s,2,是,M,的两个不同的状态，如果从,s,1,出发能识别字符串,而停于终态，从,s,2,出发也能识别,而停于终态。反之也是成立的。称,s,1,和,s,2,等价,，否则称它们,可区分,一个确定有限自动机,M,的,化简,是指：,寻找一个状态数比,M,少的,DFA M,，使得,L(M)=L(M),化简后的,DFA,满足两个条件：,(1),没有多余状态,(2),状态集中不存在等价状态,2.4,正规表达式到有限自动机的构造,：,DFA,的化简（方法）,(1),首先将,DFA,的状态集按照终态与非终态分为两个子集，形成,初始划分,H,(2),对每个子集,G,进行如下变换：,把,G,划分为新的子集，使得,G,的两个状态,s,1,和,s,2,属于同一子集,当且仅当对任何输入符号,a,状态,s,1,和,s,2,的后继状态都属于同一子集；,用,G,划分出的所有子集替换,G,，形成,新的划分,H,new,(3),如果,H,new,=H,，执行,(4);,否则令,H=,H,new,，重复执行,(2),(4),划分结束后，一个子集只对应一个状态，作为代表状态，删去,其它一切等价状态，并将对应的弧射向这个代表状态,2.4,正规表达式到有限自动机的构造,2.4,正规表达式到有限自动机的构造,例,2.8,求正规表达式,(a|b),*,(aa|bb)(a|b),*对应的,DFA M,解答,画出例,2.8,未化简的,DFA:,a,0,a,1,2,3,b,a,b,a,b,4,5,b,a,6,b,a,b,b,a,(1),初始划分集合,1=0,1,2,，集合,2=3,4,5,6,(2),考察,0,1,2,：,0,a,0,b,1,b,2,a,在集合,1,；,1,a,2,b,在集合,2,；,因此划分为,012,；,考察,3,4,5,6,：,3,a,4,a,5,a,6,a,在集合,2,；,3,