郑州大学编译原理课件第3章.ppt

Click to edit Master title style,Click to edit Master text styles,Second Level,Third Level,Fourth Level,Fifth Level,*,*,*,第三章 词法分析,词法分析的任务：,从左到右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成单词符号串的中间程序。,执行词法分析的程序称为,词法分析器,。,本章讨论词法分析器的构造。,3.1,对于词法分析器的要求,词法分析器的功能,输入源程序，输出单词符号。,单词符号是一个程序语言的基本语法符号。,程序语言的单词符号分类,关键字,(,for while,),标识符(,x1,xname,),运算符,(,+*,),界符 (,;,),常数 (,23,abcdf,),功能和输出形式,单词符号,一个程序语言的关键字、运算符和界符都是确定的。但对于标识符和常数的使用是灵活的。,词法分析器所输出的单词符号形式：,（单词种别，属性值）,单词种别通常用整数编码。,属性值是反映单词符号特性或特征的值。,本书假定,关键字、运算符和界符都是一符一种；,标识符为一种；,常数按类型分种。,例如：,C,的代码段,while (x=y)x-;,=,-,经词法分析器处理后，输出如下序列,：,词法分析器作为一个独立子程序,安排词法分析器为一个独立阶段的,好处,：,它可使整个编译程序的结构更简单、清晰和条理化。因为词法分析比语法分析要简单得多，可用更有效的特殊方法和工具进行处理。,是否也把词法分析器作为,独立一遍,呢？,不尽然。常常是作为一个子程序由语法分析器调用。,（,P38）,3.2,词法分析器的设计,常常按词法分析的任务和作为一个独立子程序来考虑它的设计。,3.2.1,输入、预处理,词法分析器的第一步工作是输入源程序文本到一个输入缓冲区中。这样，词法分析的工作可以直接在这个缓冲区中进行。,在许多情况下，常常把输入串,预处理,一下，目的是为了方便单词符号的识别。,预处理的工作是将源程序中多余的空白符、跳格符、回车符、换行符等编辑性字符以及注释部分剔除掉，并将结果存入,扫描缓冲区,中。,预处理子程序,预处理子程序就是完成上述任务的。每当词法分析器调用它时，它就处理一串确定长度的输入字符，并装入扫描缓冲区中。,预处理子程序,词法分析器,单词符号,输入缓冲区,扫描缓冲区,源程序,扫描缓冲区,词法分析器对扫描缓冲区进行扫描时，一般用两个指示器,(,P1,P2)：,一个指向当前正在识别的单词的开始位置，另一个用于向前搜索以寻找单词的终点。,P1 P2,120,个字符,120,个字符,假设,|,标识符,|,=,120,个字符,|,常数,|,=,120,个字符,while(x100),单词符号的识别,-,超前搜索,关键字的识别,例如：,(1),do99k=1,10,do 99 k=1,10,(2),do99k=1.10,do99k,是变量,标识符的识别,常数的识别,例如：,(1),5.,E-8 5,-8,(2),5.EQ.M 5=M,算符和界符的识别,例如：,+,+=,=,状态转换图,状态转换图是设计词法分析程序的一个好途径。转换图是一张有限的有向图。结点代表状态，用圆圈表示，状态之间用箭弧连接。箭弧上的标记,代表在射出结点状态下可能出现的输入字符或字符类。,一张转换图只能含有有限个状态，其中一个被认为是,初态,，可以有一个或多个,终态,（双圈）。,例如：,（,P41）,一个,状态转换图,可用于识别（或接受）一定的字符串。,例如,字母,字母,数字,数字,数字,其它,其它,（,a）,识别标识符的状态图,（,b）,识别整数的状态图,*,*,一个状态转换图可用于识别（或接受）一定的字符串。,3,3,大多数程序语言的单词符号都可以用转换图予以识别。,作为一个综合例子，我们来构造一个识别某个简单语言的所有单词符号的转换图。,下面列出了这个小语言所有单词以及它们的种别和内部值。,见,P42,词法分析的状态转换图,*,非字母或数字,字母,数字,非数字,空白,数字,*,非,*,*,其它,1,0,3,*,字母或数字,13,P43,7,*,3.2.4,状态转换图的实现,状态转换图很容易用程序实现。最简单的办法是让每个状态结点对应一小段程序。,假设已有一组全局变量和过程，将它们作为实现转换图的基本部分。这些变量和过程,见,P44,。,词法分析器（即：程序）算法,见,P45,。,例如,ch,=,GetChar,();,GetBC,();,if(,IsLetter,(,ch,),/*,进入关键字或标识符识别状态*,/,while(,IsLetter,(,ch,)|,IsDigit,(,ch,),Concat,();,ch,=,Getchar,();,Retract();,/*,回退一个字符位置*,/,code=Reserve();,/*,查找保留字表 *,/,if(!code),return(code,-);,else,value=,InsertId,(,strToken,);return($ID,value);,else,/*,进入其它单词符号的判断状态 *,/,思考题,1.,令,=,a,b,画出接受上含有偶数个,a,的字符串的状态转换图。,2.,画出状态转换图，它接受,=0,1,上所有满足如下条件的字符串：每个,1,都有,0,直接跟在右边。,解答,a,a,b,b,1,2,0,0,1,1.,令,=,a,b,画出接受上含有偶数个,a,的字符串的状态转换图。,2.,画出状态转换图，它接受,=0,1,上所有满足如下条件的字符串：每个,1,都有,0,直接跟在右边。,3.3,正规表达式与有限自动机,词法分析器的,自动生成,可依据正规表达式和有限自动机的理论。实际上，状态转换图与正规表达式和有限自动机在描述语言能力方面是等价的。,3.3.1,正规式与正规集,对于字母表，我们感兴趣的是它的一些特殊字集，即正规集。我们将使用正规式这个概念来表示正规集。下面是,正规式和正规集的递归定义,：,1）,和,都是,上的正规式，它们所表示的正规集分别为,和,；,2）,任何,a,a,是上的一个正规式，它所表示的正规集为,a；,正规式和正规集的递归定义（续）,3）,假定,U,和,V,都是,上的正规式，它们所表示的正规集分别记为,L(U),和,L(V),，,那么，,(,U,|,V)、(U,V),和(,U),*,也都是正规式。它们所表示的正规集分别为,L(U)L(V)、L(U),L(V),（,连接积）和,(,L(U),*,（,闭包）。,仅由有限次使用上述三步骤而得到的表达式才是上的正规式。仅由这些正规式所表示的字集才是上的正规集。,算符的优先顺序：先“,*,”，次“,”，,后“,|,”,。,例3.1,令,=,a,b，,下面是上的正规式和相应的正规集：,正规式,正规集,ba,*,上所有以,b,为首，后跟任,意多个,a,的字。,a(a|b),*,上所有以,a,为首的字。,(,a|b),*,(,aa,|bb)(a|b),*,上所有含有两个相继的,a,或两个相继的,b,的字。,例3.2,令,=,a，b，0，1，,则：,正规式,正规集,(,a|b)(a|b|0|1),*,上的“标识符”的全体,(0|1)(0|1),*,上的“数,”,的全体,正规式的等价性,若两个,正规式所表示的正规集相同，则称两者等价。,例如,b(,ab,)*=(,ba,)*b (a|b)*=(a*b*)*,令,U、V,和,W,均为正规式，则下列关系成立：,U,|,V=V,|,U,交换律,U,|,(V,|,W)=(U,|,V),|,W,结合律,U(VW)=(UV)W,结合律,U(V,|,W)=UV,|,UW,分配律,(,V,|,W)U=VU,|,WU,5)U=U=U,注意,:,UVVU,思考题,：,写出下面正规,式,1.,令,=,a,b,含有偶数个,a,的上的字符 串。,2.,每个,1,都有,0,直接跟在右边的二进制串。,(,b*|,ab,*a)*,(0|10)*,确定的有限自动机,一个确定有限自动机,(,DFA,),M,是一个五元式：,M=(S,s,0,F),其中：,S,是一个有限集，它的每个元素称为一个状态。,是一个有穷字母表，它的每个元素称为一个输入,字符。,是一个从,S,至,S,的单值部分映射。,(s,a)=s,意味着：当现行状态为,s、,输入字符为,a,时，将转换到,下一状态,s。,我们称,s,为,s,的一个后继。,s,0,S，,是,唯一,的初态。,F,S,是一个终态集（可空）,。,状态转换矩阵,一个,DFA,可用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示,(s,a),的值。这个矩阵称为,状态转换矩阵,。,例3.2,有,DFA M=(S,s,0,F),其中：,S=0,1,2,3,=a,b,s,0,=0,F=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,状态转换矩阵 状态转换图,字符,状态,a,b,0,1,2,1,3,2,2,1,3,3,3,3,0,a,a,a,b,b,b,a,b,DFA,M,接受的语言,对于,*,中的任何字,，,若存在一条从初态到某一终态结点的通路，且这条通路上的所有弧的标记符连接成的字等于,，,则称,可为,DFA M,所识别,(,或接受,),。,DFA M,所能识别的字的全体，称为,DFA M,所接受的语言，记为,L(M),。,注意,：若,M,的初态结点又是终态结点，则空字,可被,M,所识别。,例如：,有,DFA M,如下：,0,a,a,a,b,b,b,a,b,M,可接收的字：,aa,bb,aaa aab,babb abaa,baaa abbb,M,接收的语言为：,含有两个相继,a,或,b,的,a,b,字符串。,非确定的有限自动机,一个非确定有限自动机,(,NFA,)M,是一个五元式：,M=(S,S,0,F),其中,：,S,是一个有限集，它的每个元素称为一个状态。,是一个有穷字母表，它的每个元素称为一个输入,字符。,是一个从,S,*,至,S,的,子集,的映射,即:,:S,*2,S,4),S,0,S，,是一个非空初态集。,5),F,S,是一个终态集（可空）,。,同样,一个,NFA M,也可表示成状态转换图,。,NFA,状态转换图与,DFA,状态转换图的主要区别：,（,1）,箭弧上的标记可以不同。,DFA,的标记是,上,的单个字符，而,NFA,的标记是,*,上的字（,可以是,字,）；,（,2,）映射函数,的定义不同，,DFA,的,是,单值函数，而,NFA,的,是多值,函数。,0,DFA,0,0,NFA,NFA M,接受的语言,L(M),对于,*,中的任何字,，,若存在一条从某个初态到某一终态结点的通路，且这条通路上所有弧的标记字依序连接成的字（忽略,字）等于,，,则称,可为,NFA M,所识别,(,或接受,),。,NFA M,所能识别的字的全体，称为,NFA M,所接受的语言，记为,L(M),。,例如,：,下图就是一个,NFA M,它所能识别的是含有两个相继,a,或两个相继,b,的字符串。,x y,a,aa,a,b,bb,b,NFA,与,DFA,等价,显然，,DFA,是,NFA,的特例。但是可以证明对于每个,NFA M，,都存在一个,DFA M,”，,使,L(M)=L(M,”,),证明,：（构造性证明）,（,1,）假定,NFA M=，,对,M,的状态转换图进行以下改造：,引进新的初态结点,X,和终态结点,Y,，,并且,X、Y S，,从,X,到,S,0,的任意状态结点连一条,箭弧，从,F,中任意状 态结点连一条箭弧,到,Y,。,对,M,的状态转换图进行如下替换,：,AB,A/B,A,B,B,A,A*,A,代之以,k,代之以,代之以,k,重复这种分裂过程直至状态转换图中的每条箭弧上的标记或为,，,或为,中的单个字母。将最终得到的,NFA,记为,M。,显然,L(M)=L(M),（2,）将,NFA M,进一步变换成等价的,DFA M,”,方法如下：,假定,I,是,M,的状态集的子集，定义,I,的,闭包,_CLOSURE(I),为：,若,qI，,则,q_CLOSURE(I)；,若,qI，,那么从,q,出发经过任意条,弧而能达到的任何状态,q,都,_CLOSURE(I),假定,I,是,M,的状态子集，,a，,定义,Ia,=_CLOSURE(J),其中，,J,是那些可以从,I,中的某一状态结点出发经过一条,a,弧而到达的状态结点的全体。,假定,=,a,1,a,k,。,构造一张含有,k+1,列的表,置该表的首行首列为,_CLOSURE,(X)。,若某行第一列状态子集,I,已确定，求出其它列,Ia,i,(i=1,2,k)，,然后检查该行上的所有状态子集，将其未出现在第一列的状态子集填入后面空行的第一列。,重复上述过程，直至所有状态子集均在该表的第一列出现过。因为,M,的状态子集的个数是有限的，所以上述过程必定在有限步内终止。,（3,）将所构造出的表视为,状态转换矩阵,将其中每个状态子集视为一个新的状态。显然，该表唯一刻划了一个,DFA M,”,。,它的初态就是该表中的首行首列的那个状态子集，终态是那些含有原终态,Y,的状态子集对应的新状态。,显然,L(M)=L(M)=L(M”),。,上述把,NFA,确定化为,DFA,的方法称为子集法。,例如：,正规式,(,a|b),*,(,aa,|bb)(a|b),*,求对应的,NFA M，,并,转换出等价的,DFA M。,a,a,a,a,b,b,b,b,x,y,a|b,a|b,aa,|bb,NFA (2),NFA (1),解答：,利用子集法求状态转换表,：,a,a,a,a,b,b,b,b,x y,I,Ia,I,b,x,5,1 ,5,3,1,5,4,1,5,3,1,5,2,3,1,6,y,5,4,1,5,4,1,5,3,1,5,2,4,1,6,y,继续求新的子集：,I、,Ia,、,I,b,，,得出下表：,I,Ia,I,b,0,X,5,1,5,3,1,5,4,1,1,5,3,1,5,3,1,2,6,Y,5,4,1,2,5,4,1,5,3,1,5,4,1,2,6,Y,3,5,3,1,2,6,Y,5,3,1,2,6,Y,5,4,1,6,Y,4,5,4,1,6,Y,5,3,1,6,Y,5,4,1,2,6,Y,5,5,4,1,2,6,Y,5,3,1,6,Y,5,4,1,2,6,Y,6,5,3,1,6,Y,5,3,1,2,6,Y,5,4,1,6,Y,0 1 2,1 3 2,2 1 5,3 3 4,4 6 5,5 6 5,6 3 4,对所有的状态子集重新命名，由此而得：,0,a,a,a,a,a,a,a,b,b,b,b,b,b,等价的,DFA,（,未化简）如下：,例题,1,（1）画 NFA,（2）,加,X，Y,构造一个,DFA，,它接受,a,b,上含有偶数个,a,的字符串。,b,b,a,a,b,b,b,a,a,b,x,y,(3),用子集法求状态转换矩阵,I,Ia,I,b,0,X,1,2,1,1,1,2,1,2,2,3,1,y,2,3,3,1,Y,2,3,1,Y,b,b,a,a,b,x,y,(4),重新命名,得,DFA,I,Ia,I,b,0,X,1,2,1,1,1,2,1,2,2,3,1,y,2,3,3,1,Y,2,3,1,Y,0 2 1,1 2 1,2 3 2,3 2,3,b,b,a,a,b,0,a,b,a,作业（,3）,P64,7.,8.,9.,10,*,.,（选做）,例题,2,（1）DFA,（2）,正规文法,G(S):,构造一个,DFA，,它接受,a,b,上含有偶数个,a,的字符串。然后写出其等价的正规文法。,b,b,a,a,b,a,S,aA,|,bS,A,aB,|,bA,|a,B,aA,|,bB,|,b,正规文法与有限自动机的等价性,对于正规文法,G,和有限自动机,M,，,如果：,L(G)=L(M),则称,G,和,M,是等价的。,结论：,（,1,）对每一个右（或左）线性文法,G，,都存在一个有限自动机,(,FA)M，,使得：,L(M)=L(G),（2）,对于每一个,FA M，,都存在一个右线性文法,G,R,和左线性文法,G,L,，,使得：,L(M)=L(G,R,)=L(G,L,),证明,(1),对每一个右线性文法,G，,都存在一个,FA M，,使得,:,L(M)=L(G),证明：,(,构造性证明,),设右线性文法,G=,，,将,V,N,的,每个非终结符视为状态符号，并增加一个终态状态符,F,V,N,。,令：,FA,M,=,(,V,N,F,V,T,，S，,F,),其中,定义如下：,对,A,V,N,及,a,V,T,，,若有,A,a，,则令,(A,a)=,F,对,A,V,N,及,a,V,T,，,若有,A,aA,1,|aA,2,|,aA,k,，,则 令,(A,a)=,A,1,，A,2，,，,A,k,显然，上述构造的,M,是一个,NFA,。,可以证明：,L(G),当且仅当,L(M),显然,A,a,A F,A,aB,A B,a,a,证明：,令,=,a,1,a,2,a,k,其中,a,i,V,T,若,L(G),即,S,则,S,a,1,B,1,a,1,a,2,B,2,a,1,a,2,a,k-1,B,k-1,a,1,a,2,a,k,因此，存在一条从初态,S,到终态,F,的通路，其箭弧上的标记依次连接起来恰好为,a,1,a,2,a,k,，,故,L(M),反之亦然,。,+,a,1,a,2,a,k-1,a,k,S,B,1,B,2,B,k-1,F,例题,3,已知正规文法,G,如下，构造其等价的,FA M,。,G:S,aA,|,bS,A,bA,|,a,|,aB,B,aA,|,bB,|,b,NFA,解：,b,S A B,F,a,b,a,a,b,a,b,证明,(2),对于每一个,DFA M，,都存在一个右线性文法,G，,使得：,L(M)=L(G),证明：,设,DFA M,=,（,S，,，,，s,0,，F,）,(1),若,s,0,F，,令,G=（,，,S，,s,0,，P）,其中,P,定义如下：,对任意,a,及,A，BS，,若有,(A,a)=B，,则,若,BF,时，令,A,aB,若,BF,时，令,A,a|,aB,可以推出：,L(M),当且仅当,L(G),(2),若,S,0,F，,即,(,S,0,)=,S,0,，,L(G)。,此时增加一个,S,0,S，,且令,S,0,|,S,0,，,并令,S,0,为开始符号。,显然，对,G,修改后的,G，,有,L(G)=L(M),例题,4,设,DFA M,如下，构造其等价的正规文法。,解：,S,aA,|,bS,A a,|,aB,|,bA,B,aA,|,b,|,bB,a,b,a,b,S,aA,|,bS,|,b,A a,|,aS,|,bA,b,b,a,a,b,a,S,S,|,例题,5,b,b,a,a,解：,G(S):,S,aA,|,bS,A,bA,|,a,|,aB,注意,:,去掉多余的该非终结符,证明,(1),对每一个左线性文法,G，,都存在一个,FA M，,使得：,L(M)=L(G),证明,：,设左线性文法,G=,，,将,V,N,的,每个非终结符视为状态符号，并增加一个初态符,q,0,V,N,。,令：,FA M=,其中,定义如下：,对,A,V,N,及,aV,T,，,若有：,A,a，,则令,(,q,0,a)=A,对,A,V,N,及,aV,T,，,若有：,A,1,Aa，,A,2,Aa，,A,k,Aa,，,则令,(A,a)=,A,1,，A,2，,，,A,k,显然，上述构造的,M,是一个,NFA,。,可以证明：,L(G),当且仅当,L(M),显然,A,a,q,0,A,A,Ba,B A,a,a,证明,令,=,a,1,a,2,a,k,其中,a,i,V,T,若,L(G),即,S,则,S,B,k-1,a,k,B,k,-2,a,k-1,a,k,B,1,a,2,a,k,a,1,a,2,a,k,因此，存在一条从初态,q,0,到终态,S,的通路，其箭弧上的标记依次连接起来恰好为,a,1,a,2,a,k,，,故,L(M),+,a,k,a,k-1,a,2,a,1,S B,k-1,B,k-2,B,1,q,0,证明,(2),对于每一个,DFA M，,都存在一个左线性文法,G，,使得：,L(M)=L(G),证明：,设,FA,M,=,令,G=,其中,P,定义如下：,若,(,S,0,a)=A，,则,A,a,|,S,0,a,若,(A,a)=,B,，,则,B,Aa,（,其中,A,S,0,）,可以证明：,L(M),当且仅当,L(G),例3.4(1),p(53),1,）,已知,DFA M ,求,G,R,A,B,C,D,0,1,0,0,1,1,0,1,解：,右线性文法,G,R,(A):,A 0|0B|1D,B 0D|1C,C 0|0B|1D,D 0D|1D,例3.4,(2),p(53),2,）,已知,G,R,求,FA M,右线性文法,G,R,(A):,A 0,|,0B,|,1D,B 0D,|,1C,C 0,|,0B,|,1D,D 0D,|,1D,A,B,C,D,0,1,0,0,1,1,0,1,F,0,0,例3.4,(3),p(53),2,）,已知,FA M,求,G,L,A,B,C,D,0,1,0,0,1,1,0,1,F,0,0,解：左线性文法,G,L,(,F,):,F 0,|,A0,|,C0,D 1,|,A1,|,B,0|,C1,|,D0,|,D1,C B1,B0,|,A0,|,C0,正规式与有限自动机的等价性,可以证明：,（,1,）对任何,FA M,，,都存在一个正规式,r,使得：,L(,r,)=L(M),（2）,对,任何正规式,r,，,都存在一个,FA M,，,使得,L(M)=L(,r,),结论：,正规文法、正规式,、,NFA,、,DFA,在接受语言能力上是等价的。,证明,对任何,FA M,，,都存在一个正规式,r,使得：,L(,r,)=L(M),证明：,(1),引进新的初态结点,X,和终态结点,Y,，,并且,X、Y S，,从,X,到,S,0,的任意状态结点连一条,箭弧，从,F,中任意状态结点连一条箭弧,到,Y,。,（2）,逐步消除中间状态结点，使之只剩下,X，Y,为止。在消除结点的过程中，逐步用正规式来标记箭弧，方法如下：,代之为,V,1,V,2,V,1,V,2,代之为,V,1,|,V,2,V,1,V,2,代之为,V,1,V,2,V,1,V,2,*,V,3,V,3,r,最后得到,:,x y,证明,:,对任何正规式,r,，,都存在一个,FA M,，,使得,L(M)=L(,r,),证明,：,（采用归纳证明法,）,（1）,若,r,具有,0,个运算符，,则,r=,或,r=,或,r=a,此时，对应的,FA,分别为：,q,0,q,0,q,0,q,a,（2）,假设结论对少于,k(k0),个运算符的,r,成立。,（3,）当,r,具有,k,个运算符时，有三种情形：,r=r,1,|r,2,q,0,q,1,f,M,1,f1,q,2,M,2,f2,r=r,1,.r,2,r=r,1,*,q,1,M,1,f1,q,2,M,2,f2,q,q,1,M,1,f1,f,例题,6,1.,写出,a,b,上不以,a,开头，以,aa,结尾的正规式和,DFA。,解:,正规式：,b(a|b),*,aa,I,Ia,I,b,1,2,2,2,3,2,2,3,2,3,4,2,2,3,4,2,3,4,2,NFA：,a,b,a,b,a,DFA：,b,b,a,a,a,b,b,例题,7,写出下面,N,FA,对应的正规式,（1,）,b,a,a,b,解,：令,r=,ab,*,(a|b),正规式,:,R=r(,ar,),*,即：,ab,*,(a|b)(,aab,*,(a|b),*,解,：,ab,*,(a|b),a,（2,）,a,a,b,b,确定有限自动机的化简,一个确定有限机,M,的化简：,即寻找一个状态数比,M,少的,DFA M，,使得：,L(M)=L(M),什么是等价状态？,如果从状态,s,出发能读出某个字,而停止于终态，从状态,t,出发也能读出相同的字,而停止于终态；反之亦然，则称状态,s,和,t,是等价的。,两个状态是可区别的？,如果,DFA M,的两个状态,s,和,t,不等价；则称状态,s,和,t,是可区别的。,例题,8,状态,2 与3,是等价的。,状态,2 与1,是可区别的。,DFA：,b,b,b,a,a,a,b,DFA M,的,状态最少化过程,将,M,的状态集分割成一些不相交的子集，使得任何不同的两个子集中的状态都是可区别的，而同一子集中的任何两个状态都是等价的。最后，在每个子集中选出一个代表，同时消去其它等价状态。,I,1,1,9,7,3,5,2,8,4,6,I,4,I,3,I,2,将,DFA,最小化的方法,(1),先把,DFA M,的终态与非终态分开，分成两个不同的子集；,(2),对每个子集,I,中的状态分别考察它们是否是可区别的，,设,I=q,1,q,k,若,存在一个输入字符,a,使得,Ia,不全在现行划分的同一子集,I,中，就将,I,分为两个子集,I,1，,I,2,：,I,1,=,s|s,是,经,a,弧到达同一子集的状态,I,2,=I-I,1,(3),重复（,2,）过程，直到每个状态子集中的状态都是等价的。,设,I=,q,1,q,k,，,选,q,1,为代表，,在原来的,DFA,中，凡导入到,q,2,q,k,的,弧，都,改成,导入到,q,1,，,然后删除,q,2,q,k,。,若,I,中含有原来的初态，则,q,1,是新初态；若,I,中含有原来的终态，则,q,1,是新终态。,可以证明：,如此化简之后得到的,DFA M,和原来的,M,是等价的，,即：,L(M)=L(M),(5),若从,M,中再删除所有,无用状态,，则,M,就是含有最少状态的,DFA。,(4),在每个子集,I,中选取一个状态代表其它状态,例题,9,将,DFA,最小化,I,1,=1,2,3 I,2,=4,b,b,b,a,a,a,b,I,11,=1,I,12,=2,3,I,2,=4,最小化,DFA,b,a,a,b,b,例题,3.6,设,DFA M,如下，将其最少化。,0,a,a,a,a,a,a,a,b,b,b,b,b,b,(1),I,1,=0,1,2,I,2,=3,4,5,6,(2),0,1,2,分为,0,2 1,(3),0,2,分为：,0 1,(4),3,4,5,6,不可分,(5),故,0 1 2,3,4,5,6,b,例题,3.6,设,DFA M,如下，将其最少化。最少化的,DFA：,0,a,a,a,a,a,a,a,b,b,b,b,b,b,(5),故,0 1 2,3,4,5,6,0,a,a,b,b,a,b,a,b,3,b,3.4,词法分析器,L,的自动产生,LEX,编译程序,词法分析器,L,LEX,源程序,词法分析器,L,C,源程序,单词符号串,LEX,语言,：,是专门描述词法分析器的语言。,一个,LEX,源程序,主要包括两部分：正规定义式和识别规则。,（,1,）,上的正规定义式为：,d,1,r,1,d,i,r,i,其中,d,i,表示不同的名字，,r,i,是,d,1,d,i-1,上的正规式。,（2,）,识别规则是如下一串,LEX,语句,：,P,1,A,1,P,m,A,m,其中,P,i,是一个正规式，称为词形，,A,i,是一小段程序代码。,分析器,L,只能识别具有词形,P,1,P,m,的单词符号，它指明在识别出词型为,Pi,的单词后，词法分析器应采取动作,Ai。,分析器,L,一般是返回,Pi,的种别编码和属性值。,作业,P64,7.(1)8.9.10.(,选做,),12.14.15.20.,补充题,1.,构造,a,b,上的含有偶数个,a,的文法。,2.,构造,a,b,上的含有奇数个,a,的文法。,3.,构造,a,b,上的含有偶数个,a，,且偶数个,b,的文法。,4.,构造,a,b,上的含有奇数个,a，,且奇数个,b,的文法。,5.,构造,a,b,上的含有偶数个,a，,且奇数个,b,的文法。,