wsx(编译原理第04章)词法分析.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,*,页，共152页,第4章 词 法 分 析,词法分析是编译的第一个阶段，它的,主要任务,是从左至右逐个字符地对源程序进行扫描，产生一个个单词序列，用以语法分析。执行词法分析的程序称为词法分析程序或扫描程序。,词法分析程序的设计,单词的描述工具,有限自动机,正规式和有穷自动机的等价性,正规文法和有穷自动机间的转换,词法分析程序的自动构造工具,本章目的：讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。,本章重点,单词的,描述,工具,单词的,识别,系统,设计和实现词法分析程序,首先需要描述和刻画程序设计语言中的原子单位单词，其次需要识别单词和执行某些相关的动作。,描述程序设计语言的词法的机制是,正则表达式,，识别机制是,有穷状态自动机,。,词 法 分 析 程 序 的 设 计,回顾,什麽是词法分析程序,词法分析（,lexical analysis）,逐个读入,源程序字符并按照构词规则切分成一系列单词。,单词,是语言中具有独立意义的,最小单位,，包括保留字、标识符、运算符、标点符号和常量等。,词法分析是编译过程中的一个阶段，在语法分析前进行。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。,词法分析程序,源程序,词法分析程序,语法分析程序,Token,get token,.,主要任务：,读源程序，产生单词符号,其他任务：,滤掉空格，跳过注释、换行符,追踪换行标志，复制出错源程序，,宏展开，,单词符号,单词符号一般可分为下列五种：,基本字,（,关键字,）：,begin,end,if,while,var,等,标识符,：各种名称，如常量名、变量名、过程名等,常数,（量）：25,3.1415,TRUE,“ABC”,等,运算符,：如+-*/=等,界符,：逗号，分号，括号等,输出表示,词法分析程序所输出的单词符号常常采用二元式表示：,（单词种别，单词自身的值）,。,单词种别是语法分析需要的信息；,单词自身的值则是编译其它阶段需要的信息。,例：,A:=B+2,(Id,指向,A,的符号表的入口指针）,(,Becomes,),(Id,指向,B,的符号表的入口指针),(,Num,2),词法分析工作独立的原因：,简化设计,改进编译效率,增加编译系统的可移植性,程序设计语言中的单词是基本语法符号。单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，可以建立词法分析技术，进而可以建立词法分析程序的自动构造方法。,正规文法：,多数程序设计语言的单词的语法都能用正规文法或3型文法来描述。,3型文法,G=（V,N,，V,T,，P，S），P,中每一产生式的,形式都为：,AaB,或,Aa,，,其中,AV,N,，BV,N,，,aV,T,。,单 词 的 描 述 工 具,几类单词的描述,标识符,：标识符,l|l,字母数字字母数字,l|d|l,字母数字|,d,字母数字,无符号整数,：无符号整数,d|d,无符号整数,运算符,：运算符+,|-|*|/|=|等号等号=,界符,：界符,|;|(|)|,无符号实数,：无符号实数,d,余留无符号数|.十进小数|,e,指数部分余留无符号数,d,余留无符号数|.十进小数|,e,指数部分|,十进小数,d,余留十进小数余留十进小数,e,指数部分|,d,余留十进小数|,指数部分,d,余留整指数|,s,整指数,整指数,d,余留整指数余留整指数,d,余留整指数|,其中,s,表示正或负号。,如 25.55,e+5,和 2.1,正规式(,regular expression),正规式也称正则表达式,正规表达式（,regular expression）,是说明单词的模式(,pattern),的一种重要的表示法（记号），是定义正规集的,数学工具。我们用以描述单词符号。下面是正规式和它所表示的正规集的递归定义。,定义（正规式和它所表示的正规集）：,设字母标为,，辅助字母表,=,，。,1。和都是上的正规式，它们所表示的正规集分别为和,；,2。任何,a,，,a,是上的一个正规式，它所表示的正规集为,a；,3。,假定,e,1,和,e,2,都是上的正规式，它们所表示的正规集分别为,L(e,1,),和,L(e,2,)，,那么，(,e,1,),e,1,e,2,e,1,e,2,e,1,也都是正规式,它们所表示的正规集分别为,L(e,1,),L(e,1,)L(e,2,),L(e,1,)L(e,2,),和(,L(e,1,),。,4。仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集。,(,e,1,),e,1,e,2,e,1,e,2,e,1,L(e,1,),L(e,1,)L(e,2,),L(e,1,)L(e,2,),和(,L(e,1,),。,其中的,“,”读为“或”,（,也有使用“+”代替,“,”,的）；,“,”,读为,“连接”,；,“,”读为“闭包”,（即，任意有限次的自重复连接）。在不致混淆时，括号可省去，但规定算符的优先顺序为,“,”,、,“,”,、,“,”,。连接符,“,”,一般可省略不写。,“,”,、,“,”,和,“,”,都是左结合的。,例4.2 令,=,a，b,，,上的正规式和相应的正规集的例子有：,正规式 正规集,a a,a,b,a,b,ab,ab,(a,b)(a,b),aa,ab,ba,bb,a,a,a,任意个,a,的串,(,a,b),a,b,aa,ab,所有由,a,和,b,组成的串,(,a,b),(aabb)(a,b),上所有含有两个相继 的,a,或两个相继的,b,组成 的串,例,=,l，d，r,=,l(l,d),定义的正规集:,l,ll,ld,ldd,（,标识符）,例4.3 ,=,d，.，e,，+，-,则上的正规式,d,(.dd,)(e(+,-,),dd,),表示的是无符号数的集合。其中,d,为09的数字。,程序设计语言的单词都能用正规式 来定义.,两个正规式,等价,若两个正规式,e,1,和,e,2,所表示的,正规集相同,则说,e,1,和,e,2,等价,写作,e,1,=,e,2,。,例如：,e,1,=(a,b)，e,2,=b,a,又如：,b(ab,),=(,ba),b,(a,b),=(a,b,),正规式的运算律,设,r,s,t,为正规式，正规式服从的代数规律有：,1。,r,s=s,r“,或”服从交换律,2。,r,(,s,t)=(,r,s,),t“,或”的可结合律,3。(,rs)t,=,r(st,)“,连接”的可结合律,4。,r(s,t)=,rs,rt,(s,t)r,=,sr,tr,分配律,5。,r=r,r=r,是“连接”的恒等元素,6。,r,r=r r,=,r,rr,“或”的抽取律,正规文法到正规式,对上的正规式,r,存在一个,G=(V,N,V,T,P,S),使得,L(G)=,L(r,)，,反之亦然。,1.将正规式转换成正规文法,V,T,=,S,V,N，,生成正规产生式 S,r (1),对形如,Axy,的,正规产生式：,AxB,By,B,V,N,(2),对形如,A,x,y,的,正规产生式：,AxB,Ay,BxB,By,B,V,N,(,3),对形如,A,xy,的,正规产生式:,A x,A y,不断应用上述规则做变换，直到每个产生式右端只含一个,V,N,例,r=,a(ad,),V,T,=,a,d,Sa(ad,),SaA,A(ad,),A,(ad)B,A,B(ad)B,B,Gs,:,SaA,A V,T,=,a,d,AaB,V,N,=S,A,B,AdB,BaB,BdB,B,2.将正规文法转换成正规式,文法产生式正规式,（1）,AxB,By,A=,xy,（2）AxAyA=,x,y,（3）AxyA=,xy,S,=,aAa,A,=,aAdA,a d,=,(,ad)A(ad,),=,(,ad),(ad,),S=,a,(ad),(ad)a,=,a(ad),(ad,)=,a(ad,),R=,a(ad,),Gs:,S,aA,AaA,AdA,Sa,Aa,Ad,正规定义的例子,PL/0,语言的标识符集合,letter,A,|,B,|,Z,|,a,|,b|,|,z,digit,0,|1|9,id,letter,(,letter,|,digit,),*,无符号数集合，例,1946,11.28,63.6,E8,1.99,E,6,digit,0,|1|9,digits,digit,digit,*,optional_fraction,.,digits,|,optional_exponent,(E(+|,|,)digits)|,num,digits,optional_fraction,optional_exponent,简化表示,num,digit,+,(,.,digit,+,)(E(+|,)digit,+,),while,while,do,do,relop,|=,id,letter(letter|digit),*,num,digit,+,(,.,digit,+,)(E(+|,)digit,+,),delim,blank,|,tab,|,newline,ws,delim,+,转换图,关系算符的转换图,relop,|=,0,5,1,6,2,4,8,3,7,return(relop,LE),return(relop,NE),return(relop,LT),return(relop,GE),return(relop,GT),return(relop,EQ),开始,=,=,*,*,other,other,标识符和保留字的转换图,id,letter(letter|digit),*,9,10,11,开始,letter,other,*,letter,或,digit,return(,install,_,id,(),无符号数的转换图,开始,19,12,13,14,15,16,17,18,digit,digit,digit,digit,digit,digit,other,.,E,+/,E,digit,other,other,return(,install,_,num,(),*,num,digit,+,(,.,digit,+,)(,E,(+|,),digit,+,),空白,的转换图,delim,blank,|,tab,|,newline,ws,delim,+,21,22,开始,delim,other,*,delim,20,有穷自动机,有穷自动机(也称有限自动机)作为一种,识别装置,，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。,有穷自动机分为两类：,确定的有穷自动机,(,Deterministic Finite,Automata),DFA,不确定的有穷自动机,(,Nondeterministic Finite Automata),NFA,有 穷 自 动 机,1,2,开始,a,0,a,b,b,a,b,识别语言,(,a,|,b,),*,ab,的,DFA,1,2,开始,a,0,a,b,b,识别语言,(,a,|,b,),*,ab,的,NFA,关于,有穷自动机,我们将讨论如下题目,确定的有穷自动机,DFA,不确定的有穷自动机,NFA,NFA,的确定化(,NFA,DFA,的转换),DFA,的最小化(,DFA,的化简),DFA,定义：,一个确定的有穷自动机（,DFA）M,是一个五元组：,M=（,K，f，S，Z,）,其中,1。,K,是一个有穷集，它,的每个元素,称,为,一个,状态,；,2。,是,一个有穷字母表，它的每个元素称为一个输入符号，所以也称,为,输入符号字母表,；,3。,f,是转换函数,，是在,K,K,上的映射，即，如,f（k,i,，a,）=,k,j,，（k,i,K，k,j,K）,就意味着，当前状态为,k,i,，,输入符为,a,时，将转换为下一个状态,k,j,，,我们把,k,j,称作,k,i,的一个后继状态；,4。,S,K,是唯一,的一个,初态,；,5。,Z,K,是,一个,终态集,，终态也称,可接受状态,或,结束状态,。,DFA,例：,DFA M=（S,U,V,Q,a,b,f,S,Q）,其中,f,定义为：,f（S，a,）=U,f（V，a,）=U,f（S，b,）=V,f（v，b,）=Q,f（U，a,）=Q,f（Q，a,）=Q,f（U，b,）=V,f（Q，b,）=Q,一个,DFA,可以表示成一个,状态图,(或称,状态转换图,)。,假定,DFA M,含有,m,个状态，,n,个输入字符，那么这个状态图含有,m,个结点，每个结点最多有,n,个弧射出，整个图含有唯一一个初态结点和若干个终态结点，初态结点冠以双箭头,“=”,或标以,“,-,”,，终态结点用双圈表示或标以,“,+,”,，若,f(k,i,a,)=,k,j,，,则从状态结点,k,i,到状态结点,k,j,画标记为,a,的弧；,DFA 的状态图表示,f（S，a,）=U,f（V，a,）=U,f（S，b,）=V,f（v，b,）=Q,f（U，a,）=Q,f（Q，a,）=Q,f（U，b,）=V,f（Q，b,）=Q,b,S,U,V,Q,a,a,a,b,a，b,b,一个,DFA,还可以用一个,矩阵表示,，该矩阵的,行表示状态,，,列表示输入字符,，矩阵元素表示相应状态行和输入字符列下的新状态，即,k,行,a,列为,f(k,a,),的值。用双箭头,“=”,标明初态；否则第一行即是初态，相应终态行在表的右端标以1，非终态标以0。,DFA,的矩阵表示,f（S，a,）=U,f（V，a,）=U,f（S，b,）=V,f（v，b,）=Q,f（U，a,）=Q,f（Q，a,）=Q,f（U，b,）=V,f（Q，b,）=Q,字符,状态,0,1,0,0,*,上的符,号,串,t,在,M,上运行,一个输入符,号,串,t，（,我们将它表示成,Tt1,的形式，其中,T，t1,*,）在,DFA M,上,运行,的定义为：,f（Q,，Tt1）=f（f（Q，T），t1）,其中,QK,扩充转换函数,f，,是,K,*,K,上的映射，且：,f（Q,，,）=Q,为了说明,DFA,如何作为一种识别机制,我们还要理解下面的定义,*,上的符,号,串,t,被,M,接受,对于*中的任何字符串,t，,若存在一条从初态结到某一终态结的道路，且这条路上所有弧的的标记符连接成的字符串等于,t，,则称,t,可为,DFA M,所接受，若,M,的初态结同时又是终态结，则空字可为,M,所,接受,（,识别,）。,若,t,*,，,f(S，t,)=P，,其中,S,为,DFA,M,的开始状态，,P,Z，Z,为终态集。则称,t,为,DFA M,所,接受,（,识别,）。,例：证明,t=,baab,被如下的,DFA,所接受。,DFA M=（S,U,V,Q,a,b,f,S,Q）,其中,f,定义为：,f（S，a,）=U,f（V，a,）=U,f（S，b,）=V,f（v，b,）=Q,f（U，a,）=Q,f（Q，a,）=Q,f（U，b,）=V,f（Q，b,）=Q,b,S,U,V,Q,a,a,a,b,a，b,b,证明：,f（S，baab,）,=,f（f（S，b），aab,）,=,f（V，aab,）,=,f（f（V，a），ab,）,=,f（U，ab,）,=,f（f（U，a），b,）,=,f（Q，b,）,=Q,Q,属于终态。得证。,DFA M,所能接受的符,号,串的全体记为,L(M),结论：,上一个字符串集,V,是正规的，当且仅当存在一个上的确定有穷自动机,M，,使得,V=L(M)。,DFA,的,确定性,表现在,转换函数,f,:K,K,是一个单值函数，也就是说，对任何状态,kK,，,和输入符号,a,，f(k,a,),唯一地确定了下一个状态。,从状态转换图来看，若字母表,含有,n,个输入字符，那末任何一个状态结点最多有,n,条弧射出，而且每条弧以一个不同的输入字符标记。,DFA,的行为很容易用程序来模拟.,DFA M=（,K，f，S，Z,）,的行为的模拟程序,K:=S；,c:=,getchar,;,while c,eof,do,K:=,f(K,c,);,c:=,getchar,;,;,if K is in Z then return(yes),else return(no),例：,DFA，,接受,0,和,1,的个数都是偶数的字符串,3,1,2,0,1,1,1,1,0,0,0,0,开始,偶0偶1,奇0奇1,奇0偶1,偶0奇1,不确定的有穷自动机,NFA,定义,N=,K，f，S，Z,，,其中,K,为状态,的有穷非空,集,，,为,有穷输入,字母表,，,f,为,K*,到,K,的子集的,映像,，,S,K,是初,始状,态集,，,Z,K,为终,止状,态集,。,例子,NFA N=（S，P，Z，0，1，f，S，P，Z）,其中,f（S，0）=P,f（S，1）=S，Z,f（P，1）=Z,f（Z，0）=P,f（Z，1）=P,S,P,Z,0,0,1,1,1,1,状态图表示,表格表示,简化为,NFA N=（S，P，Z，0，1，f，S，P，Z）,其中,f（S，0）=P,f（S，1）=S，Z,f（P，1）=Z,f（Z，0）=P,f（Z，1）=P,f,为,K*,到,K,的子集（2,K,）,的一种映射,具有,转移的不确定的有穷自动机,1,2,3,a,b,c,有如下定理：,对任何一个具有,转移的不确定的有穷自动机,NFA N，,一定存在一个,不具有,转移的不确定的有穷自动机,N,FA,，,使得,L(M)=L(N)。,与上例等价的一个,N,FA,.,2,a,c,b,b,3,1,a,c,a,c,b,b,1,2,3,a,b,c,类似,DFA,对,NFA M=,K，f，S，Z,也有如下定义,*上的符,号,串,t,在,NFA,M,上,运行,.,一个输入符,号,串,t，（,我们将它表示成,Tt,1,的形式，其中,T，t,1,*）在,NFA M,上,运行,的定义为：,f（Q,，Tt,1,）=f（f（Q，T），t,1,）,其中,QK,.,*上的符,号,串,t,被,NFA,M,接受,若,t,*，,f(S,0,，t)=P，,其中,S,0,S,，,P,Z，,则称,t,为,NFA M,所,接受,（,识别,）,*上的符号串,t,被,NFA,M,接受也可以这样理解,对于,中的任何一个串,t，,若存在一条从某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串(不理采那些标记为,的弧)等于,t，,则称,t,可为,NFA M,所识别(读出或接受)。若,M,的某些结既是初态结又是终态结，或者存在一条从某个初态结到某个终态结的道路,其上所有弧的标记均为,，那么空字可为,M,所接受。,000,111,1010001,110000001,00,01100,NFA M,所能接受的符,号,串的全体记为,L(M),结论：,上一个符,号,串集,V,是正规的，当且仅当存在一个上的不确定的有穷自动机,M，,使得,V=L(M)。,(0|1)*(000|111)(0|1),DFA,是,NFA,的特例.对每个,NFA N,一定存在一个,DFA,，,使得,L(M)=L(N)。,对每个,NFA N,存在着与之等价的,DFA M。,有,一种算法，将,NFA,转换成接受同样语言的,DFA.,这种算法称为,子集法.,与某一,NFA,等价的,DFA,不唯一,.,从,NFA,的矩阵表示中可以看出，表项通常是一,状态的集合,，而在,DFA,的矩阵表示中，表项是,一个状态,，,NFA,到相应的,DFA,的构造的,基本思路是：,DFA,的每一个状态对应,NFA,的一组状态.,DFA,使用它的状态去记录在,NFA,读入一个输入符号后可能达到的所有状态.,NFA,的确定化,(,NFA,DFA,的转换),DFA,是,NFA,的特例.对每个,NFA M,一定存在一个,DFA,，,使得,L(M)=L(M,)。,对每个,NFA M,存在着与之,等价,的,DFA M,。,与某一,NFA,等价的,DFA,不唯一。,定义对状态集合,I,的几个有关运算：,1,状态集合,I,的,-闭包，表示为,-,closure(I,),，,定义为一状态集，是状态集,I,中的任何状态,S,经任意条弧而能到达的状态的集合。,状态集合,I,的任何状态,S,都属于,-,closure(I,)。,2,状态集合,I,的,a,弧转换，表示为,move(I,a,),定义为状态集合,J，,其中,J,是所有那些可从,I,的某一状态经过一条,a,弧而到达的状态的全体。,定义,Ia,=,-,closure(J,),例,I=1,-,closure(I,)=1,2；,I=5,-,closure(I,)=5,6,2；,move(1,2,a)=5,3,4,-,closure(5,3,4)=2,3,4,5,6,7,8；,1,2,5,3,4,6,8,7,a,a,a,NFADFA,假设,NFA N=(K,f,K,0,K,t,),按如下办法构造一个,DFA M=(S,d,S,0,S,t,)，,使得,L(M)=L(N),：,1.,M,的状态集,S,由,K,的一些子集组成,。用,S,1,S,2,.,S,j,表示,S,的元素，其中,S,1,S,2,.,S,j,是,K,的状态。,并且约定，状态,S,1,S,2,.,S,j,是,按某种规则排列的,，即对于子集,S,1,S,2,=S,2,S,1,来说，,S,的状态就是,S,1,S,2,；,2.,M,和,N,的输入字母表是相同的，即是,；,3.转换函数是这样定义的：,D(,S,1,S,2,.,S,j,a)=,R,1,R,2,.,R,t,其中,R,1,R,2,.,R,t,=,-,closure(move,(,S,1,S,2,.,S,j,a),4.,S,0,=,-,closure(K,0,),为,M,的开始状态；,5.,S,t,=,S,i,S,k,.,S,e,，其中,S,i,S,k,.,S,e,S,且,S,i,S,k,.,S,e,K,t,构造,NFA N,的状态,K,的子集的算法：,假定所构造的子集族为,C，,即,C=(T,1,T,2,.,T,I,),其中,T,1,T,2,.,T,I,为状态,K,的子集。,1.开始，令,-,closure(K,0,),为,C,中唯一成员，并且它是未被标记的。,2.,while（C,中存在尚未被标记的子集,T）do,标记,T；for,每个输入字母,a do U:=,-,closure(move(T,a,)；if U,不在,C,中,then,将,U,作为未标记的子集加在,C,中,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,状态,例:将下图的,NFA N,转换成,DFA M,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,状态,A,=0,1,2,4,7,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,状态,A,=0,1,2,4,7,B,=1,2,3,4,6,7,8,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,B,状态,A,=0,1,2,4,7,B,=1,2,3,4,6,7,8,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,状态,A,=0,1,2,4,7,B,=1,2,3,4,6,7,8,C,=1,2,4,5,6,7,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,C,状态,A,=0,1,2,4,7,B,=1,2,3,4,6,7,8,C,=1,2,4,5,6,7,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,B,C,状态,A,=0,1,2,4,7,B,=1,2,3,4,6,7,8,C,=1,2,4,5,6,7,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,B,D,C,状态,A,=0,1,2,4,7,B,=1,2,3,4,6,7,8,C,=1,2,4,5,6,7,D,=1,2,4,5,6,7,9,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,B,D,C,D,状态,A,=0,1,2,4,7,B,=1,2,3,4,6,7,8,C,=1,2,4,5,6,7,D,=1,2,4,5,6,7,9,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,B,D,C,B,C,D,状态,A,=0,1,2,4,7,B,=1,2,3,4,6,7,8,C,=1,2,4,5,6,7,D,=1,2,4,5,6,7,9,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,B,D,C,B,C,D,B,C,状态,A,=0,1,2,4,7,B,=1,2,3,4,6,7,8,C,=1,2,4,5,6,7,D,=1,2,4,5,6,7,9,B,D,开始,a,A,a,b,b,a,b,C,b,a,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,B,D,C,B,C,D,B,C,状态,0,2,3,4,5,6,7,8,9,10,1,b,b,b,a,a,-,closure(move(T,i,a,),-,closure(move(T,i,b,),T,0,=,-,closure(0)=0,1,2,4,7,1,2,3,4,6,7,8加入为,T,1,1,2,4,5,6,7 加入为,T,2,T,1,=,1,2,3,4,6,7,8,1,2,3,4,6,7,8,已存在,T,1,1,2,4,5,6,7,9 加入为,T,3,T,2,=,1,2,4,5,6,7,1,2,3,4,6,7,8,已存在,T,1,1,2,4,5,6,7,已存在,T,2,T,3,=,1,2,4,5,6,7,9,1,2,3,4,6,7,8,已存在,T,1,1,2,4,5,7,10 加入为,T,4,T,4,=,1,2,4,5,7,10,1,2,3,4,6,7,8,已存在,T,1,1,2,4,5,6,7,已存在,T,2,-,closure(move(T,i,a,),-,closure(move(T,i,b,),T,0,=,-,closure(0)=0,1,2,4,7,1,2,3,4,6,7,8加入为,T,1,1,2,4,5,6,7 加入为,T,2,T,1,=,1,2,3,4,6,7,8,1,2,3,4,6,7,8,已存在,T,1,1,2,4,5,6,7,9 加入为,T,3,T,2,=,1,2,4,5,6,7,1,2,3,4,6,7,8,已存在,T,1,1,2,4,5,6,7,已存在,T,2,T,3,=,1,2,4,5,6,7,9,1,2,3,4,6,7,8,已存在,T,1,1,2,4,5,7,10 加入为,T,4,T,4,=,1,2,4,5,7,10,1,2,3,4,6,7,8,已存在,T,1,1,2,4,5,6,7,已存在,T,2,初态,终态,b,0,2,1,3,4,a,b,a,a,a,a,b,b,b,DFA M,温习一下：构造,NFA N,的状态,K,的子集的算法：,假定所构造的子集族为,C，,即,C=(T,1,T,2,.,T,I,),其中,T,1,T,2,.,T,I,为状态,K,的子集。,1.开始，令,-,closure(K,0,),为,C,中唯一成员，并且它是未被标记的。,2.,while（C,中存在尚未被标记的子集,T）do,标记,T；for,每个输入字母,a do U:=,-,closure(move(T,a,)；if U,不在,C,中,then,将,U,作为未标记的子集加在,C,中,说一个有穷自动机是化简了的，即是说，它,没有多余状态,并且它的状态中,没有两个是互相等价的,。一个有穷自动机可以通过,消除,多余状态和,合并,等价状态而转换成一个最小的与之等价的有穷自动机。,最小状态,DFA,没有多余状态(,死状态),没有两个状态是互相等价（不可区别）,DFA,的最小化（,DFA,的化简,）,所谓,有穷自动机的多余状态,，是指这样的状态：,从,自动机的开始状态出发，任何输入串也不能到达的那个状态；,或者从这个状态没有通路到达终态,。,两个状态,s,和,t,等价（即它们不可区别）：满足,一致性（兼容性）同是终态或同是非终态,蔓延性（传播性）从,s,出发读入某个,a,a,和从,t,出发,读入某个,a,到达的状态等价。,消除多余状态,s1 s5s2 s7s2 s5,s5,s7s5 s6s3 s1s8 s0,s0,s1s3 s6,0 1,011000110,s0s1s2s3s4s5s6s7s8,s1 s5s2 s7s2 s5,s5,s7,s5 s6,s3 s1,s8 s0,s0,s1,s3 s6,0 1,0110,0,0,1,1,0,s0s1s2s3,s4,s5,s6,s7,s8,s1 s5s2 s7s2 s5,s5,s7s3 s1s0 s1,0 1,011001,s0s1s2s3s5s7,如图，状态0和4是可区别的。,状态2和3是可区别的，因为读入,b,后分别到达2和4，而2和4不是等价的。,b,0,2,1,3,4,a,b,a,a,a,a,b,b,b,DFA M,“,分割法,”,我们这里介绍一个方法，叫做“分割法”，来把一个,DFA（,不含多余状态）的状态分成一些不相交的子集。,“,分割法”是,DFA,的最小化算法的核心,把一个,DFA,的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的.,举例：将图中的,DFA M,最小化。,1,2,3,4,5,6,7,Ia,:6,7,1,4,7,4,4,Ib,:3,3,5,6,3,1,2,1,2,3,4 5,6,7,1,2 3,4 5 6,7,1,2 3 4 5 6,7,1,3,5,2,7,4,6,a,a,a,a,a,a,a,b,b,b,b,b,b,b,1,3,5,4,6,a,a,a,a,a,b,b,b,b,b,首先将,M,的状态分成,两个子集,：一个由终态（可接受态）组成，一个由非终态组成。,比起原来的有穷自动机，化简了的有穷自动机具有较少的状态，因而在计算机上实现起来将简洁些。,1.,对于,上的NFA M，可以构造一个,上的正规式R,使得,L(R)=L(M)。,2,.对于,上的一个正规式R，可以构造一个,上的NFA M，使得L,(,M)=L(R)。,正 规 式 和 有 穷 自 动 机 的 等 价 性,1.,对于,上的NFA M，可以构造一个,上的正规式R,使得,L(R)=L(M)。,步骤如下,：,第一步：,在,M,的状态转换图上,加进两个结,，一个为,x,结点，一个为,y,结点。从,x,结点用,弧连接到,M,的,所有初态结点,，从,M,的,所有终态结点,用,弧连接到,y,结点。形成一个与,M,等价的,M,M,只有,一个初态,x,和,一个终态,y,。,第二步：,逐步消去,M,中的所有结点，直至只剩下,x,和,y。（,消去规则见下页）,最后,x,和,y,结点间的弧上的标记则为所求的正规式,R。,1,2,3,R,1,R,2,1,3,R,1,R,2,1,3,R,1,R,2,1,3,R,1,|,R,2,1,2,3,R,1,R,3,R,2,1,3,R,1,R,2,*,R,3,例：,0,3,1,2,4,a,b,a,a,a,b,a,b,b,b,求正规式,R,0,3,1,2,4,a,b,a,a,a,b,a,b,b,b,x,y,0,2,4,a|b,aa,a|b,a|b,bb,x,y,0,2,4,a|b,aa,a|b,a|b,bb,x,y,0,a|b,aa(a|b,)*,bb(a|b,)*,x,y,0,a|b,aa(a|b,)*,bb(a|b,)*,x,y,0,a|b,x,y,aa(a|b,)*|,bb(a|b,)*,x,y,(,a|b,)*(,aa,|,bb)(a|b,)*,(,aa,|,bb)(a|b,)*,R=(,a|b,)*(,aa,|,bb)(a|b,)*,2,.对于,上的一个正规式R，可以构造一个,上的NFA M，使得L,(,M)=L(R)。,(1),R=,任一具有空终态集的,NFA M,(2,),R=,，,NFA M=(k,0,f,k,0,.k,0,):,f（,k,0,a),对于,所有,a,都没定义。,(,3,),R=,a,NFA,M=,(k,0,k,1,f,k,0,.k,1,):f(,k,0,a)=k,1,i,开始,识别正规式,的,NFA,a,f,i,f,开始,识别正规式,a,的,NFA,(4),若,s,t,为,上的正规式,，相应的,NFA,分别为,N(s,),和,N(t,)，,则（,a),对正规式,R=,s|t,，,所构造的,NFA（R）,如下：,其中,i,是,NFA(R),的初态，,f,是,NFA（R）,的终态，,i,到,N(s,),和,N(t,),的初态各有一,弧，从,N(s,),和,N(t,),的终态各有一弧到,f，,现在,N(s,),和,N(t,),的初态或终态已不作为,N（R）,的初态和终态了。,构造识别主算符为或者（选择）的正规式的,NFA,f,i,开始,识别正规式,s,|,t,的,NFA,N,(,s,),N,(,t,),(4),若,s,t,为,上的正规式,，相应的,NFA,分别为,N(s,),和,N(t,)，,则（,a),对正规式,R=,st,，,所构造的,NFA（R）,如下：,其中,N(s,),的初态成了,N（R）,的初态，,N(t,),的终态成了,N（R）,的终态。,N(s,),的终态与,N(t,),的初态合并为,N（R）,的一个既不是初态也不是终态的状态。,构造识别主算符为连接的正规式的,NFA,i,N,(,s,),f,开始,识别正规式,st,的,NFA,N,(,t,),(4),若,s,t,为,上的正规式,，相应的,NFA,分别为,N(s,),和,N(t,)，,则（,a),对正规式,R=s,*,，,所构造的,NFA（R）,如下：,这里,i,和,f,分别是,NFA（R）,的初态和终态，从,i,引,弧到,N(s,),的初态，从,N(s,),的终态引,弧到,f，,从,i,到,f,引弧，同样,N(s,),的终态可沿弧的边直接回到,N(s,),的初态。,N(s,),的初态或终态不再是,N(s,),的初态和终态。,构造识别主算符为闭包的正规式的,NFA,N,(,s,),f,开始,识别正规式,s,*,的,NFA,i,例：,为,R=(,a|b,)*,abb,构造,NFA N，,使得,L(N)=L(R)。,2,3,5,4,a,b,R=(,a,|b,)*,abb,R=(,a|,b,)*,abb,2,3,5,4,a,b,1,6,R=(,a|b,)*,abb,2,3,5,4,a,b,1,6,R=(,a|b,)*,abb,2,3,5,4,a,b,1,6,R=,(,a|b,)*,abb,0,7,继续加上,abb,即可得到结果。,x,i,y,(,a|b,)*,abb,R=,(,a|b,)*,abb,x,j,y,abb,i,a|b,x,j,y,abb,i,a,b,继续对,abb,进行分解。,x,y,(,a|b,)*,abb,采用下面的规则从正规文法,G,直接构造一个有穷自动机,NFA M，,使得,L(M)=L(G)：,字母表与,G,的终结符集相同；,为,G,中的每个非终结符生成,M,的一个状态，（不妨取称相同的名字）,G,的开始符号是开始状态,S；,增加一个新状态,Z，,作为,NFA,的终态；,对,G,中的形如,AtB,的产生式（其中,t,为终结符或,，A,和,B,为非终结符），构造,M,的一个转换函数,f(A,t,)=B,；,对,G,中形如,At,的产生式，构造,M,的一个转换函数,f(A,t,)=Z,。,正 规 文 法 和 有 穷 自 动 机 间 的 转 换,例：与文法,GS,等价