编译原理与实现03第3章 词法分析1.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,3.5 正则表达式,由于各种高级程序设计语言的单词形式基本上差不多，人们就希望能否构造一个自动生成系统，只要给出程序设计语言的各类单词描述以及识别出各类单词后应输出的结果，这种自动系统便能自动产生此程序设计语言的词法分析程序。词法分析程序自动生成系统的实现涉及正则表达式和有限自动机理论,假设有字母表=0，1，那么，字母表上的每个元素都是正则表达式，这样的正则表达式表示的语言只有一个句子。例如，0是一个正则表达式，表示的语言为0，该语言只有一个句子0。如果想表示更加复杂的语言，就必须使用运算符组成复杂的正则表达式，这一点很像用加减乘除运算符构造算术表达式。在正则表达式中，可使用的运算符有连接、选择和重复。,例3.4，有正则表达式,R1=1,R2=1,R3=0，,所描述的语言分别为,L,1,=1,L,2,=1,L,3,=0，,求正则表达式,R1,.,R2,.,R3、R1|R3R1,描述的语言。,解：根据正则表达式运算符的操作定义，可得如下结果：,R1,.,R2,.,R3,是一个正则表达式，描述的语言为110，该语言有一个句子110。,R1|R3,是一个正则表达式，描述的语言为1,0，该语言有两个句子1和0。,R1,是一个正则表达式，描述的语言为1,n,|n=0,1,2,.，,该语言有无穷的句子，如1、11、11111等等。,标识符的正则表达式为：标识符=字母字母|数字,而带有符号的实数的正则表达式为：数=（,|+|-）（,数字.数字数字）,3.5.1 正则表达式定义,设有两个正则表达式,R1,和,R2，,它们分别产生语言,L,1,和,L,2,，,则正则表达式运算符的操作定义如下：连接：,R1,.,R2=,xy,|xL,1,，yL,2,选择：,R1|R2=x|xL,1,或,xL,2,重复：,R1=x|x L,1,*,，L1,*,=L,1,0,L,1,1,L,1,2,3.5.1 正则表达式定义,定义了运算符后，下面我们给出正则表达式的形式定义。,设是有穷字母表，在上的正则表达式及所描述的语言可递归定义如下：,1.,是一个表示空集的正则表达式。,2.,是一个正则表达式，它所表示的语言仅含一个空符号串，即,3.a,是一个正则表达式，,a，,它所表示的语言由符号,a,所组成,a,4.,如果,R,1,和,R2,是正则表达式，其表示的语言分别为,L1,和,L2，,则,1),R,1,|R,2,或,R,1,+R,2,是一个表示语言,L1L2,的正则表达式,2),R,1,.,R,2,或,R,1,R,2,是一个表示语言,L1L2,的正则表达式,3),R,1,或,R,1,*,是一个表示语言,L1,*,的正则表达式,4)(,R),表示的语言仍是,L1,的正则表达式，但调整优先权，使括号内的运算符优先权高于括号外的。,5.所有上的正则表达式可由上述4条规则构造出来。,注意：不要混淆,和,，,正则表达式,描述的语言只含一个空字符串,，,而,表示的语言不含有任何字符串。,3.5.1 正则表达式定义,在正则表达式的运算符中，重复优先级高于连接，而连接高于选择，因此，(,p)|(p),.,(q),可写成,p|,pq,但表达式(,p|q),.,r,中的括号则不能去掉。,例3.5，设字母表=,a,b，,则,a,b,和,都是上的正则表达式，所描述的语言为,a、b、，,求表达式,ab、a|b,和,aa,|,ab,|,ba,|bb,定义的语言。,解：根据正则表达式的形式定义，可得如下结果：,表达式,ab,定义的语言为：,a,m,b,n,|m0,n0，,表达式,a|b,定义的语言为：,x|x a,b*，,即字母,a,或,b,组成的任意长度字符串。,而表达式,aa,|,ab,|,ba,|bb,表示的语言由字母,a,或,b,组成的所有偶长度字符串。,3.5.1 正则表达式定义,例3.6，设字母表=0，求表达式00与000|0定义的语言。,解：表达式00定义的语言是0,i,|i1,表达式000|0定义的语言是0,i,|i1,例3.6给出了两个不同的正则表达式，但描述的语言却相同，这说明不同的正则表达式可描述相同的语言。如果两个正则表达式表示相同的语言，则称这两个表达式等价或相等。显然，例3.6的表达式00和000|0是等价的。,正则表达式的部分操作符满足结合律、交换律和分配律:,即 (,ab,)c=a(,bc,),(a|b)|c=a(b|c),a|b=b|a,a(b|c)=,ab,|ac,注意：连接不满足交换律，即,ab,ba,3.5.2 正则文法与正则表达式的等价性,正则文法与正则表达式有等价性，即可以将正则文法转换成正则表达式。,例如，用正则文法表示标识符的文法规则如下：,标识符=,a|b|z,|,标识符,a|,标识符,b|,标识符,z,|,标识符0|标识符1|标识符9,而采用正则表达式则为：,标识符=(,a|b|c|z)a|b|z|0|1|9,或简写成 标识符=字母字母|数字,由此可见，正则表达式在描述语言时比正则文法更为简洁,。,3.5.2 正则文法与正则表达式的等价性,例3.7，有正则文法如下，将其换成等价的正则表达式。,S,aS,S,aB,B,bC,C,aC,C,a,解：,先用元符号“”和“”将文法改写成如下：,S=a,aB,B=,bC,C=aa,然后按解方程组的方法可得：,C=aa,B=baa,S=a,ab,aa,最终转成正则表达式,S=a,ab,aa,可以验证，它表示的语言与原来的正则文法描述的语言相同。,3.6 有穷自动机（,FA）,有穷自动机不是一台具体的机器，而是一种具有离散输入与输出系统的数学模型。在这种数学模型中有有限个状态，状态间存在着转换关系。系统可以处于有限个状态中的任意一个之中，系统的当前状态概括了有关过去输入的信息，这些信息对于确定系统在以后的输入上的行为是必需的。当系统处在某个状态之下读入一个字符时，会使系统所处的状态发生变化，从而形成状态转换。改变后的状态称为后继状态。在状态转换中，后继状态可能为一个，也可能为多个。有穷自动机分确定的和不确定的，所谓“,确定的有穷自动机,”是指在当前的状态下，输入一个符号，有穷自动机将转换到唯一的后继状态；而“,不确定的有穷自动机,”在当前状态下输入一个符号，可能有两种或两种以上可选择的后继状态。,3.6.1 确定的有穷自动机,状态图就是一个确定的有穷自动机。,1,、确定的有穷自动机定义,一个确定的有穷自动机,M（,记作,DFA M）,是一个五元组：,M=（Q，q,0,，F，）,其中：,：,是一个字母表，它的每个元素称为一个输入符号,Q,：,是一个有穷的状态集合。,q,0,：q,0,Q，,是唯一的初始状态。,F,：FQ，,称为终结状态集合。,：,状态转换函数，是一个,QQ,的单值映射。,在确定的有穷自动机中，状态转换函数的具体形式如下：,（q，a）=q,其中,qQ，qQ，a,这是一个单值函数，表示在当前状态为,q,下，输入符号为,a,时，自动机将从状态,q,转换到下一个状态,q，q,称为,q,的后继状态。,3.6.1 确定的有穷自动机,2、确定的有穷自动机状态图,确定的有穷自动机,M=（Q，q0，F，）,可以用状态图来表示。状态图中的结点代表状态，用圆圈表示，它与自动机,M,中的状态集合,Q,相对应，其中包括初始状态,q,0,和终结状态集合,F，,结束状态用双圈表示。状态间用有向弧线连接，连接弧上标记有符号，每条弧线对应一个状态转换函数，弧线上标记的符号集合就是字母表。,例3.8 设有穷自动机,DFA M=（0，1，2，3，a,b,0,3,）,(0,a)=1 (0,b)=2,(1,a)=3 (1,b)=2,(2,a)=1 (2,b)=3,(3,a)=3 (3,b)=3,画出该自动机对应的状态图。,解：该自动机对应的状态图如图3.9所示。,a,b,0,1,2,3,b,a,a,a,b,b,3.6.1 确定的有穷自动机,3,、确定的有穷自动机状态转换矩阵,图3.10 状态转换矩阵,确定的有穷自动机,M=（,Q，,q,0,，F，）,还可以用关系矩阵即状态转换矩阵来表示。矩阵中的第一列元素与自动机,M,中的状态集合,Q,一一对应，且初始状态,q,0,是第一列的第一个元素，右上角标记*的元素对应终结状态。状态转换矩阵的第一行元素与子目标中的每个符号相对应。矩阵中的元素对应每个状态转换函数。如果有状态转换函数,（q，a）=q，,其中,qQ，qQ，a，,那么，就在矩阵中状态,q,对应的行和符号,a,对应的列单元中填入,q。,例3.5中的状态转换矩阵如图3.10所示。,S,a b,0,1,2,3,*,1,2,3 2,1 3,3 3,3.6.1 确定的有穷自动机,4、确定的有穷自动机接受的语言,为了讲解确定的有穷自动机如何接受或识别字符串，首先，我们对状态转换函数作补充定义：,（q，at）=（q，a），t）,其中,a ，t ,*,，,即,t,是上的字符串,例如,有,(0,a)=1,且,(1,b)=2，,则,(0,ab,)=（0，a），b）=(1,b)=2,对一个确定的有穷自动机,M=（Q，q,0,，F，）,以及某个字符串,x（x,*,），,如果有,(q,0,x)=p，,且,pF，,则字符串,x,就被该自动机,M,所接受。也就是从自动机开始状态开始，在读完全部输入串以后，自动机刚好到达终止状态，那么该输入串为该自动机所接受。从状态图上看，如果一个字符串能被自动机接受，那么从初始状态出发，则存在一条到达某一终结状态的路径，且组成这条路径的弧线上标记的符号连接起来正好就是字符串,x。,一个确定的有穷自动机,M,所接受的语言就是所能接受的输入串构成的集合，用,L（M）,表示，可定义为：,L（M）=t|(q,0,t)F，t,*,3.6.1 确定的有穷自动机,例3.9，设计能接受偶数个0和偶数个1组成的串的有穷自动机，画出其状态图及状态转换矩阵并判别110101、11101能否被该自动机接受。,解：首先设计能接受偶数个0和偶数个1组成的数字串的有穷自动机如下：,M1=,（S，A，B，C，0，1，S，S，）,（S，0）=B （S，1）=A,（A，0）=C （A，1）=S,（B，0）=S （B，1）=C,（C，0）=A （C，1）=B,其状态图及状态转换矩阵分别如图3.11(,a)(b),所示。,S,0 1,S,*,A,B,C,B,A,C S,S C,A B,S,A,B,C,1,1,0,1,0,0,1,0,图3.11(,a),图3.11(,a),下面判别110101、11101能否被该自动机接受：,(,S,，,110101,),=,(,A,，,10101,),=,(,S,，,101,),=,(,B,，,101,),=,(,C,，,01,),=,(,A,，,1,),=S(,接受),(,S,，,11101,),=,(,A,，,1101,),=,(,S,，,101,),=,(,A,，,01,)=(C，1)=B(,拒绝),3.6.2 不确定的有穷自动机,不确定的有穷自动机与确定的有穷自动机的区别主要有两点：一是状态转换函数,为多值函数，二是输入符号可允许为,。,1,、,不确定的有穷自动机定义,一个不确定的有穷自动机,NFA M,是一个五元式,M=,（Q，q,0,，F，）,其中：,Q,：,有穷状态集,：,输入字母表与空串组成的集合，输入可以是字母表中的字符，也可以是空串,q,0,：,开始状态,q0Q,F,：,终止状态集,FQ,：,状态转换函数，为,Q*,到,Q,的子集的映射。,不确定的有穷自动机同样可以用状态图和状态转换矩阵来表示，表示方法与确定的相同。,3.6.2 不确定的有穷自动机,2,、不确定的有穷自动机接受的语言,与确定的有穷自动机一样，为了判别一个字符串,x,能否被,NFA,接受，我们还需要对状态转换函数做补充定义：,设,(q,a)=p,1,p,2,p,n,，,其中,a ，q,p,1,p,2,p,n,Q,1),(q,)=-closure(q),其中,-closure(q),表示从状态,q,出发，沿着,弧到达的后继状态集合以及再从这些后继状态沿着,弧所能到达的所有状态集合。,2),(q,at)=(p,1,t)(p,2,t)(,p,n,t),其中,a,Vt,t ,*,3),(q,1,q,2,q,n,x)=(q,1,x)(q,2,x)(,q,i,x),其中,x ,*,，,表示从不确定自动机的状态集出发，扫描字符串,x,后，所到达的状态集等于从当前状态集的每一个状态集出发，扫描字符串,x,后所到达的状态集之和。,3.6.2 不确定的有穷自动机,对某台不确定的有穷自动机,NFA M=（Q，q,0,，F，）,及某个字符串,x（x,*,），,若有,(q,x)=Q，,且,Q F,，,则,x,为,M,所接受。,也就是从自动机开始状态开始，在读完全部输入串以后，自动机能够到达某个终止状态，那么该输入串为该自动机所接受。从状态图上看，如果一个字符串能被自动机接受，那么从初始状态出发，则存在一条到达某一终结状态的路径，且组成这条路径的弧线上标记的符号连接起来正好就是字符串,x。,如果初始状态也是终结状态，或是存在一条从初始状态到达某个终结状态的路径，路径上的所有标记都是,，,则,可被,NFA,接受。,M,所接受的语言为,L（M）=x|x,*,，(q,0,x)=Q，QF,3.6.2 不确定的有穷自动机,例3.10，有,NFA M=（0,1，2，a,b,0,2,）,其中：,（0，a）=2,（0，）=1,（1，b）=1,2,（2，a）=2,（2，b）=2,画出其状态图及状态转换矩阵，确定该自动机接收的语言。,解：不确定的有穷自动机用状态图和状态转换矩阵来表示，如图3.12(,a),和3.12(,b),所示。,该自动机接受的语言为,L(M)=(a|,b,m,)(a|b),n,|m1,n0,0,2,1,b,a,b,a,b,S,a,b,0,2,1,1,(,1,2),2,*,2,2,图3.12(,a),图3.12(,b),3.6.3,NFA,到,DFA,的转化,不确定的有穷自动机与确定的有穷自动机从功能上来说是等价的，它们所接受的语言类相同，给定任一不确定的有穷自动机,NFA M，,就能构造一个确定的有穷自动机,DFA M，,使得,L（M）=L（M）。,为了实现,NFA,到,DFA,的转化，首先要介绍两个状态子集的计算方法，它们是从,NFA,到,DFA,的转化过程中需要计算的状态子集。,1、状态集,P,的,闭包,设,p,是一,NFA M,的状态集,Q,的一个子集，则,-closure(p),称为状态集,p,的,闭包，,闭包也是状态集,Q,的一个子集，其计算方法如下：,1,）若,q p，,则,q-closure(p)，,即,P,的所有成员都是,p,的,闭包的成员,2,）若,q p，,那么从,q,出发经过任意条,弧而能到达的任何状态都属于,-closure(p)。,3.6.3,NFA,到,DFA,的转化,例3.11，对图3.13所示的,NFA M，,求,P=1、P=2、P=1，2,的,闭包。,解：当,P=1,时，,有,(1,)=3，,(3,)=6，,(3,)=4，,所以,-closure(1)=1,3,4,6,当,P=2,有,(2,)=6，,所以,-closure(2)=2,6,当,P=1,2,则,-closure(1,2),=,-closure(1)-closure(2),=1,3,4,6,2,6,=1,2,3,4,6,1,4,3,2,6,5,a,a,a,图3.13,例3.11的,NFA M,状态图,3.6.3,NFA,到,DFA,的转化,2,、状态集,P,的,a,弧转换集,设,p,仍是一自动机,M,的状态集的子集，,p=p1,p2,pn,a，,即,a,是字母表的一个输入符号，则,Pa,弧转换集为：,p,a,=-closure(J)，,其中,J=(p,1,a)(p,2,a)(,p,n,a),即,J,是从状态子集,p,中的每一个状态出发，沿着标记为,a,的弧而到达的状态所组成的集合。,从定义可知，状态集,P,的,a,弧转换集,Pa,也是状态子集，其集合元素为从,P,的每个状态出发，沿着标记为,a,的弧所到达的后继状态集合，再加上这些后继状态集合中的每个状态的,闭包，即从这些后继状态集合中的每个状态出发，沿着,弧所能到达的状态的集合。,例3.12，对图3.13所示的,NFA M，,若,p=1，,求,p,a,。,解：因为,(1,a)=2，(1,a)=4,所以,pa=-closure(J),=,-closure(1,a),=-closure(2,4)=2,4,6,1,4,3,2,6,5,a,a,a,图3.13,例3.11的,NFA M,状态图,3.6.3,NFA,到,DFA,的转化,3、,根据,NFA M,构造,DFA M,下面我们通过一个例子来介绍根据,NFA M,构造,DFA M,的方法。,假设有一个不确定的有穷自动机,NFA M=,（Q，q,0,，F），,其中,Q=1,2,3,4，=a,b,c，q,0,=1，F=4，,状态图如图3.14所示。,接受的语言：,L(M)=,a,m,b,|m1,ac,n,|n1，,构造一个,DFA M=（Q，q,0,，F），,使,L(M)=L(M),1,2,3,4,a,a,a,c,c,b,图3.14,NFA M,的状态图,3.6.3,NFA,到,DFA,的转化,构造确定的有穷自动机过程如下：,1,）首先根据,闭包的计算方法求,NFA M,的开始状态,q,0,的,闭包，从而确定,DNFA M,的开始状态,q,0,。,q,0,=-closure(q,0,)=-closure(1)=1，4,2,）,根据弧转换集的计算方法求开始状态,q0,对每个输入符号的弧转换集,q0a、q,0b,和,q,0c,从而确定与开始状态,q,0,有关的状态转换函数。,(q,0,a)=q,0a,=-closure(1,a)(4,a),=-closure(2,3,)=2,3,将2,3作为新状态,并令,q,1,=2,3，,即得到,(q,0,a)=q,1,(q,0,b)=q,0b,=-closure(1,b)(4,b)=-closure(,)=,(q,0,c)=q,0c,=-closure(1,c)(4,c)=-closure(,)=,由于,(q,0,b)=,，(q,0,c)=,，,说明没有新状态产生。至此，我们得到有关开始状态,q,0,的全部状态转换函数只有一个，即,(q,0,a)=q,1,。,1,2,3,4,a,a,a,c,c,b,3.6.3,NFA,到,DFA,的转化,3,）按步骤2的方法，对每个新状态计算相关的状态转换函数。,计算状态,q,1,的状态转换函数：,(q,1,a)=q,1a,=2，,将2作为新状态,并令,q,2,=2,(q,1,b)=q,1b,=4，,将4作为新状态,并令,q,3,=4,(q,1,c)=q,1c,c=3,4，,将3，4作为新状态,并令,q,4,=3，4,至此，得到有关开始状态,q1,的全部状态转换函数。,接下来，计算状态,q,2,、q3、q4,的有关状态转换函数如下：,(q,2,a)=2=q,2,(q,2,b)=4=q,3,(q,2,c)=,(q,3,a)=,(q,3,b)=,(q,3,c)=,(q,4,a)=,，,(q,4,b)=,，,(q,4,c)=3,4=q,4,计算到此，不再有新状态出现。,1,2,3,4,a,a,a,c,c,b,3.6.3,NFA,到,DFA,的转化,4）根据上面求出的各个状态确定终结状态集,F=p|p F,，,其中,p,为,M,的每个状态子集：,因为,q,0,=1，4、q,1,=2,3、q,2,=2、q,3,=4、q,4,=3,4，,而,F=4，,q,0,、q,3,、q,4,与,F,相交不为空，所以确定终结状态集,F=q,0,q,3,q,4,最后,我们得到确定的有穷自动机如下：,DFA M=(q,0,q,1,q,2,q,3,q,4,a,b,c,q,0,q,0,q,3,q,4,),其中状态转换函数为：,(q,0,a)=q,1,(q,1,a)=q,2,，(q,1,b)=q,3,，(q,1,c)=q,4,(q,2,a)=q2，(q,2,b)=q,3,(q,4,c)=q,4,该转换后的动机的状态图及状态转换矩阵如图3.16(,a)、(b),所示。,3.6.3,NFA,到,DFA,的转化,q,0,q,1,q,2,q,3,q,4,a,a,a,b,b,c,c,图3.15(,a),转换后的,DFA M,的状态图,状态,a,b c,q,0,*,q,1,q,1,q,2,q,3,q,4,q,2,q,2,q,3,q,3,*,q,4,*,q,4,图3.15(,b),转换后的,DFA M,的状态转换矩阵,得到的确定的自动机接收的语言为:,L(M)=,a,m,b,|m1,ac,n,|n1,与原来不确定的有穷自动机接收的语言,L(M),一样。,3.6.4 正则表达式与有穷自动机的等价性,正则表达式与有穷自动机等价性由以下两点说明：,1,）若给定一个正则表达式,R，,那么,就可构造一个,DFA M，,并有,L(M)=L(R)；,2）,若给定一个,DFA M，M,接受的语言为,L(M)，,则必然存在一正则表达式,R，,且,L(R)=L(M)。,1,、根据正则表达式构造有穷自动机,根据正则表达式的组成规则，可采用下列构造分解规则来构造,NFA M：,1),基本正则表达式,、,和,a（a）：,描述的语言为空集，,和,a,所定义的语言分别为,和,a，,可构造的,NFA,分别是：,S,0,S,1,S,0,S,1,S,0,S,1,a,图3.16,、,和,a,的状态转换图,3.6.4 正则表达式与有穷自动机的等价性,2)连接：设,R1,和,R2,都是基本正则表达式，则构造与正则表达式,R1.R2,等价的,NFA,如图3.17：,S,0,S,1,R1.R2,S,0,S,2,S,1,R1,R2,图3.17,R1.R2,的状态转换图,3)选择：设,R1,和,R2,都是正则表达式，则构造与正则表达式,R1|R2,等价的,NFA,如图3.18：,S,0,S,1,R1|R2,S,0,S,1,R1,R2,图3.18,R1|R2,的状态转换图,4)重复：设,R,是正则表达式，则构造与正则表达式,R,等价的,NFA,如图3.19：,S,0,S,1,R,S,0,S,2,S,1,R,图3.19,R,的状态转换图,对于任何正则表达式，我们都可根据上述,NFA,构造规则构造出等价的,NFA。,3.6.4 正则表达式与有穷自动机的等价性,例,3.13,有正则表达式,R=(a)*(,|b)(a|b)*,，,构造出等价的,NFA，,然后转化成,DFA。,解：构造过程如下：,设初始状态为0，目标状态为1，将整个正则表达式,(,a)*(,|bb)(a|b)*,看成一个整体,则状态转换图如图3.20所示：,0,1,(a)*(|bb)(a|b)*,图3.20,正则表达式到,NFA,转换图1,因,(,a)*(|bb)(a|b)*,由(,a)*、(|bb),和(,a|b)*,连接而成，所以展开连接后如图3.21：,0,2,(a)*,3,1,|bb,(a|b)*,图3.21,正则表达式到,NFA,转换图2,将重复展开后如图3.22所示：,0,2,3,1,|bb,a|b,4,5,a,图3.22,正则表达式到,NFA,转换图3,3.6.4 正则表达式与有穷自动机的等价性,将选择展开后，最终得到的,NFA,状态图如图3.23所示：,图3.23,正则表达式到,NFA,转换图4,0,2,3,1,a,4,5,a,6,b,b,b,3.6.4 正则表达式与有穷自动机的等价性,构造出,NFA,后，接下来，我们可按3.6.3小节介绍的方法将其转化成,DFA，,其过程如下：,设,DFA M=（Q，q,0,，F）,q,0,=-closure(0)=0，4，2，3，5，1,q,0a,=,-closure(4,5)=4，2，3，5，1q,1,q,0b,=,-closure(6,5)=6,5，1 q,2,q,1,a,=,-closure(4,5)=4，2，3，5，1q,1,q,1,b,=,-closure(6,5)=6,5，1 q,2,q,2,a,=,-closure(5)=5，1q,3,q,2,b,=,-closure(3,5)=3,5,1q,4,q,3,a,=,-closure(5)=5,1q,3,q,3,b,=-closure(5)=5,1q,3,q,4,a,=,-closure(5)=5,1q,3,q,4,b,=-closure(5)=5,1q,3,至此，不在有新状态产生。由于,q,0,、q,1,、q,2,、q,3,、q,4,都含有状态1，所以都是目标状态。转化后的,DFA,如图3.24所示,q,0,q,1,q,2,q,3,q,4,a,a,a,a,a,b,b,b,b,b,图3.24,DFA,状态图,3.6.4 正则表达式与有穷自动机的等价性,2,、将,DFA M,转换成正则表达式,若给定一个,DFA M，,构造正则表达式,R,相比之下更加容易，处理方法与上面的由正则表达式构造,NFA M,的方法是互逆的。其具体方法如下：,1),填加两个新的结点,S,和,T，,将结点,S,与,DFA M,上的初态结点连接，将每个终态结点与,T,结点用弧线连接，所有连接弧线上均标记为,，,从而，使,NFA M,只有一个初态,S,和一个终态,T。,2),逐步去掉,NFA M,中的结点，直到只剩下结点,S,和,T。,在去掉结点的过程中，逐步用正则表达式来标记弧线。去掉结点的规则如下。,连接：设,R1,和,R2,都是基本正则表达式，去掉结点，用弧线直接连接结点1和3，弧线上标记,R1.R2，,如图3.25所示：,1,3,R1.R2,1,2,3,R1,R2,图3.25 由,NFA,构造正则表达式,R1R2,3.6.4 正则表达式与有穷自动机的等价性,选择：设,R1,和,R2,都是正则表达式，去掉标记为,R1,和,R2,弧线，用一根弧线直接连接结点1和2，弧线上标记,R1|R2：,重复：设,R,是正则表达式，则构造与正则表达式,R,等价的,NFA,如图3.27所示：,1,2,R1|R2,1,2,R1,R2,图3.26由,NFA,构造正则表达式,R1|R2,1,3,R,1,2,3,R,图3.27由,NFA,构造正则表达式,R,例如，从例3.13中得到的,NFA M（,图3.23,）反向看，图3.23、图3.22、图3.21以及图3.20就是构造正则表达式的过程。,3.6.5 确定的有穷自动机的化简,如果有两个确定的有穷自动机,DFA M1,和,DFA M2,所接受的语言完全一样，我们说这两个自动机是等价的。但如果,DFA M1,的状态个数比,DFA M2,的状态个数少，那么，我们说,DFA M1,更加简洁。在设计词法分析程序时，效率是很重要的一个因数。如果可能的话，我们应该构造尽可能小的,DFA。,上一小节我们介绍了将正则表达式分解派生出,DFA,的方法，但这一方法有个缺点：就是生成的,DFA,可能比较复杂。自动机理论中有一个很重要的结论：对于任何给定的,DFA，,都有一个含有最少状态的等价的,DFA，,而且这个最少状态的,DFA,是唯一的。从任何,DFA,中都可以得到这个最少状态的,DFA。,1、,等价状态与不等价状态,在一个确定的有穷自动机里，如果从,S1,状态出发接受的所有符号串集合与从,S2,状态出发接受的所有符号串集合一样，那么称状态,S1,和,S2,是等价的；否则是不等价的。,例3.14，观察图3.27所示的状态图，判断状态1和状态2是否等价。,解：因为有,(1,a)=3，(2,a)=3，,因此，状态1和状态2是等价的。,0,2,1,3,4,a,b,a,a,b,图3.28有等价状态的状态图,3.6.4 正则表达式与有穷自动机的等价性,2.,多余状态,多余状态有两种。一是指从初始状态出发，输入任何输入串也无法到达的状态，即从初始状态到该状态之间没有通路。二是指从初始状态出发能够到达的状态，但从它出发却无法到达终止状态的状态，即从该状态到终止状态之间没有通路。多余状态是无用的，应该删除。删除多余状态的方法很简单，从状态图上看，就是直接将多余状态结点以及相关的弧线删除，即可得到等价的自动机。,例3.15，在图3.28(,a),所示的的状态图中，判断那些状态是多余状态。,解：根据多余状态的定义，可发现，从初始状态0出发，无法到达状态1，所以状态1是多余状态。而从状态5无法到达终止状态4，所以，状态5也是多余状态。删除多余状态后的状态图入3.28(,b),所示。,0,1,2,3,4,5,b,b,b,a,a,0,2,3,4,b,b,a,图3.29(,a),有多余状态的状态图,图3.29(,b),删除多余状态的状态图,3.6.4 正则表达式与有穷自动机的等价性,3.,DFA,化简算法,设,DFA M=（Q，q,0,，F），,化简算法如下：,1,）先将自动机的状态划分成终止状态集合,S1,和非终止状态集合,S2：,Q=S1S2,2,）,对各状态集合按下面方法划分，直到所有状态集合不再产生新的划分为止。设第,m,次划分将,Q,分成,N,个状态集合，即,Q=S1S2,Sn,。,对状态集合,Si,（i=1，2，n）,中的各个状态逐一检查，设状态,q,1,和,q,2,是状态集合,Si,中的两个状态，对于输入符号,a（a），,有,(q,1,a)=S、(q,2,a)=S”,若状态,S,和,S”,属于同一状态集合，则将状态,q,1,和,q,2,放在同一状态集合中；否则，将状态,q,1,和,q,2,分为两个集合。,3,）重复第2步，直到所有状态集合都不能划分。此时，每个状态集合中的状态都是等价的。,4,）将每个状态集合中的等价状态合并成一个等价代表状态。将状态函数中的所有状态用相应的等价代表状态表示。从状态图上看，要将一个状态集合中的等价状态结点合并成一个结点。,5）删除多余状态。,3.6.4 正则表达式与有穷自动机的等价性,例3.16 对图3.30所示的有穷自动机化简。状态函数如下,：,a,(0,a)=1，(1,a)=3，(2,a)=1，(3,a)=3，(4,a)=3,(0,b)=2，(1,b)=2，(2,b)=4，(3,b)=4，(4,b)=4,解：首先将状态集合分成终止状态集合,S1,和非终止状态集合,S2。,S1=0,，1，2，S2=3，4,对,S1=0，1，2,化分:,因为,(0,a)=1，(1,a)=3，(2,a)=1,1、3,不属于同一状态集，,所以将,S1,分成,S3=0，2，S4=1,对,S2=3，4,化分:,(3,a)=3，(4,a)=3,(3,b)=4，(4,b)=4,因为,3、4,属于同一状态集，,所以,S2,不能划分，说明状态3和4等价。,0,1,2,3,4,b,b,b,a,a,a,b,a,a,b,图3.30 等待化简的有穷自动机,3.6.4 正则表达式与有穷自动机的等价性,对,S3=0，2,化分:,因为,(0,a)=1，(2,a)=1,(0,b)=2，(2,b)=4,所以将,S3,分成,S5=0，S6=2,至此，不再能继续划分，,最终得到不能划分的状态集有,S2=3,，4，S4=1，S5=0，S6=2,每个状态集留一个状态得：,S2=3，S4=1，S5=0，S6=2,将原来的转换函数中的状态4改成状态3，得到,(0,a)=1，(1,a)=3，(2,a)=1，(3,a)=3，(3,a)=3,(0,b)=2，(1,b)=2，(2,b)=3，(3,b)=3，(3,b)=3,去掉重复的，最终得到化简后的状态函数如下，对应的状态图如图3.31所示。,(0,a)=1，(1,a)=3，(2,a)=1，(3,a)=3,(0,b)=2，(1,b)=2，(2,b)=3，(3,b)=3,0,1,2,3,b,b,b,a,a,a,a,b,图3.31 化简后的有穷自动机,3.6.6 根据,DFA,构造词法分析程序,根据,DFA,来构造词法分析程序有两种方法。,1.,直接编程的词法分析器,所谓直接编程的词法分析器，是将,DFA,识别过程转化为程序，即用程序来模拟,DFA,的行为。在这种方法里，首先将,DFA,用状态图表示，然后按下列步骤根据状态图画出词法分析程序流程图：,1),初始状态对用程序的开始；,2),终止状态对应程序的结束,3),状态转移对应条件语句或多分支选择语句；,4),状态图的环对应程序中循环语句；,5),终态返回时，隐瞒组应满足最长匹配原则。,其中最长匹配原则指识别出的单词有混淆时，按长度最长的来确定。例如符号串“=”认为是一个单词，而不是”,LEXYY.EXE AAA.TEST BBB.TXT,7、,打开“,BBB.TXT”，,看词法分析的结果。,习题,3.3,构造下列正则表达式相应的,NFA,：,1(1|0)*|0,1(1010*|1(010)*1)*0,3.4,将图3.36的,NFA M,确定化,3.5 将图3.37的,DFA,化简。,3.6修改3.3.2小节的词法分析程序，添加保留字“,do”,以及双分界符“&”和“|”的处理。,0,1,a,b,a,a,图3.36 状态图,0,1,4,2,5,3,a,a,a,a,a,a,b,b,b,b,b,b,图3.37,DFA,状态图,