编译原理-国防科技大学课件Chapt3.ppt

国防科技大学计算机系,602,教研室,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,复习：,程序语言的语法描述,几个概念:,考虑一个,有穷,字母表,字符集,其中每一个元素称为一个,字符,上的,字,(也叫,字符串,)是指由中的字符所构成的一个有穷序列,不包含任何字符的序列称为,空字,，记为,用,*,表示,上的所有字的全体,包含空字,国防科技大学计算机系,602,教研室,复习：,程序语言的语法描述,*,的子集,U,和,V,的,连接,（,积,）定义为,UV,|,U&,V,V,自身的,n,次积记为,V,n,=VVV,规定,V,0,=,，令,V,*,=V,0,V,1,V,2,V,3,称,V,*,是,V,的,闭包,;,记,V,VV,*,，称,V,+,是,V,的正规闭包。,国防科技大学计算机系,602,教研室,复习：,程序语言的语法描述,上下文无关文法的定义：,一个上下文无关文法,G,是一个四元式,G=(V,T,，,V,N,，,S,，,P),，其中,V,T,：终结符集合,(,非空,),V,N,：非终结符集合,(,非空,),，且,V,T,V,N,=,S,：文法的开始符号，,S,V,N,P,：产生式集合,(,有限,),，每个产生式形式为,P,，,P,V,N,，,(,V,T,V,N,),*,开始符,S,至少必须在某个产生式的左部出现一次。,国防科技大学计算机系,602,教研室,复习：,程序语言的语法描述,定义：称,A,直接推出,，即,A,仅当,A ,是一个产生式，,且,，,(,V,T,V,N,),*,。,如果,1,2,n,，,则我们称这个序列是从,1,到,n,的一个,推导,。若存在一个从,1,到,n,的推导，则称,1,可以,推导,出,n,。,国防科技大学计算机系,602,教研室,通常，用,表示：从,1,出发，经过一步或若干步，可以推出,n,。,用 表示：从,1,出发，经过,0,步或若干步，可以推出,n,。,所以：即 或,定义：假定,G,是一个文法，,S,是它的开始符号。如果 ，则,称是一个,句型,。仅含终结符号的句型是一个,句子,。文法,G,所产生的句子的全体是一个,语言,，将它记为,L(G),。,国防科技大学计算机系,602,教研室,复习：,程序语言的语法描述,最左推导,：任何一步,都是对,中的最左非终结符进行替换。,最右推导,：任何一步,都是对,中的最右非终结符进行替换。,国防科技大学计算机系,602,教研室,复习：,程序语言的语法描述,用一张图表示一个句型的推导,称为,语法树,。,E,(E),(,E+E,),(,E*E+E,),(i*,E+E,),(i*,i+E,),(i*,i+i,),E,(E),(,E+E,),(,E+i,),(E*,E+i,),(E*,i+i,),(i*,i+i,),国防科技大学计算机系,602,教研室,复习：,程序语言的语法描述,定义,：,如果一个文法存在某个句子对应两颗不同的语法树,，,则说这个,文法是二义的,。,语言的二义性：一个,语言是二义性的,，如果对它不存在无二义性的文法。,国防科技大学计算机系,602,教研室,复习：,程序语言的语法描述,形式语言鸟瞰,0,型,(,短语文法，图灵机,),：,产生式形如：,其中：,(,V,T,V,N,),*,且至少含有一个非终结符；,(,V,T,V,N,),*,1,型,(,上下文有关文法，线性界限自动机,),：,产生式形如：,其中：,|,|,，仅,S,例外。,国防科技大学计算机系,602,教研室,复习：,程序语言的语法描述,形式语言鸟瞰,2,型,(,上下文无关文法，非确定下推自动机,),：,产生式形如：,A ,其中：,A,V,N,；,(,V,T,V,N,),*,。,3,型,(,正规文法，有限自动机,),：,产生式形如：,A B,或,A ,其中：,V,T,*,；,A,，,B,V,N,产生式形如：,A B,或,A ,其中：,V,T,*,；,A,，,B,V,N,国防科技大学计算机系,602,教研室,第三章 词法分析,词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号。,词法分析器,(Lexical Analyzer),又称扫描器,(Scanner),：,执行词法分析的程序,国防科技大学计算机系,602,教研室,3.1,对于词法分析器的要求,一、词法分析器的功能和输出形式,功能,:,输入源程序、输出单词符号,单词符号的种类：,基本字,：如,begin,，,repeat,，,标识符,表示各种名字：如变量名、数组名和过程名,常数,：各种类型的常数,运算符,：,+,，,-,，*，,/,，,界符,：逗号、分号、括号和空白,国防科技大学计算机系,602,教研室,输出的单词符号的表示形式,:,(,单词种别,，,单词自身的值,),单词种别通常用整数编码表示。,若一个种别只有一个单词符号，则种别编码就代表该单词符号。假定基本字、运算符和界符都是一符一种。,若一个种别有多个单词符号，则对于每个单词符号，给出种别编码和自身的值。,标识符单列一种；标识符自身的值表示成按机器字节划分的内部码。,常数按类型分种；常数的值则表示成标准的二进制形式。,国防科技大学计算机系,602,教研室,例,C,程序,while(i=j)i-;,输出单词符号：,=,-,国防科技大学计算机系,602,教研室,例,FORTRAN,程序,IF(5.EQ.M)GOTO 100,输出单词符号：,逻辑,IF(34,，,-),左括号,(2,，,-),整常数,(20,，,5,的二进制,),等号,(6,，,-),标识符,(26,，,M),右括号,(16,，,-),GOTO(30,，,-),标号,(19,，,100,的二进制,),国防科技大学计算机系,602,教研室,二、词法分析器作为一个独立子程序,词法分析是作为一个独立的阶段，是否应当将其处理为一遍呢？,作为独立阶段的优点：结构简洁、清晰和条理化，有利于集中考虑词法分析一些枝节问题。,不作为一遍：将其处理为一个子程序。,国防科技大学计算机系,602,教研室,词法分析器,词法分,析器,语法分,析器,符号表,源程序,单词符号,取下一单词,.,国防科技大学计算机系,602,教研室,词法分析器的结构,预处理子程序,扫描器,输入缓冲区,扫描缓冲区,单词符号,输入,列表,3.2,词法分析器的设计,国防科技大学计算机系,602,教研室,输入串放在输入缓冲区中。,预处理子程序：剔除无用的空白、跳格、回车和换行等编辑性字符,;,区分标号区、捻接续行和给出句末符等,扫描缓冲区,起点 搜索,指示器 指示器,一、输入、预处理,国防科技大学计算机系,602,教研室,WhatALong,Wo,rd,WhatALong,Wo,rd,rd,WhatALong,Wo,rd,WhatALong,Wo,国防科技大学计算机系,602,教研室,二、单词符号的识别,:,超前搜索,1,基本字识别,:,例如,:,DO99K=1,，,10,DO 99 K=1,，,10,IF(5.EQ.M)GOTO55,IF(5.EQ.M)GOTO 55,DO99K=1.10,IF(5)=55,需要超前搜索才能确定哪些是基本字,国防科技大学计算机系,602,教研室,2,标识符识别,:,字母开头的字母数字串，后跟界符或算符,3,常数识别,:,识别出算术常数并将其转变为二进制内码表示。有些也要超前搜索。,5.EQ.M,5.E08,4,算符和界符的识别,把多个字符符合而成的算符和界符拼合成一个单一单词符号。,:=,，*，,.EQ.,，,+,，,-,，,=,国防科技大学计算机系,602,教研室,三,、,状态转换图,1 概念,状态转换图是一张有限方向图。,2,1,3,X,Y,结点代表状态，用圆圈表示,。,状态之间用箭弧连结，箭弧上的标记(字符)代表射出结状态下可能出现的输入字符或字符类。,一张转换图只包含有限个状态，其中有一个为初态，至少要有一个终态。,国防科技大学计算机系,602,教研室,识别标识符的状态转换图,1,2,3,字母,其他,字母或数字,*,识别,整常数,的状态转换图,1,2,3,数字,其他,数字,*,一个,状态转换图可用于识别,(,或接受,),一定的字符串。,国防科技大学计算机系,602,教研室,2 例子,助忆符,：直接用编码表示不便于记忆，因此用助忆符来表示编码。,国防科技大学计算机系,602,教研室,国防科技大学计算机系,602,教研室,1,2,3,4,5,6,7,8,9,10,11,12,13,0,空白,字母,字母或数字,非字母与数字,数字,非数字,数字,=,+,*,非*,(,),其它,*,*,*,*,国防科技大学计算机系,602,教研室,几点重要限制,不必使用超前搜索,所有基本字都是保留字,;,用户不能用它们作自己的标识符,基本字作为特殊的标识符来处理,;,不用特殊的状态图来识别，只要查保留字表。,如果基本字、标识符和常数,(,或标号,),之间没有确定的运算符或界符作间隔，则必须使用一个空白符作间隔。,DO99K=1,，,10,要写成,DO 99 K=1,，,10,国防科技大学计算机系,602,教研室,3,状态转换图的实现,思想：每个状态结对应一小段程序。,做法:,1)对不含回路的分叉结，可用一个,CASE,语句或一组,IF-THEN-ELSE,语句实现,GetChar,();,if(,IsLetter,(),状态,j,的对应程序段,;,else if(,IsDigit,(),状态,k,的对应程序段,;,else if(,ch,=/),状态,l,的对应程序段,;,else,错误处理,;,i,j,k,l,字母,数字,国防科技大学计算机系,602,教研室,3,状态转换图的实现,2)对含回路的状态结，可对应一段由,WHILE,结构和,IF,语句构成的程序.,i,字母或数字,其它,j,GetChar,();,while(,IsLetter,()or,IsDigit,(),GetChar,();,状态,j,的对应程序段,国防科技大学计算机系,602,教研室,3,状态转换图的实现,3)终态结表示识别出某种单词符号，因此，对应语句为,RETURN(C，VAL),其中，,C,为单词种别，,VAL,为单词自身值.,国防科技大学计算机系,602,教研室,全局变量与过程,1),ch,字符变量、存放最新读入的源程序字符,2),strToken,字符数组，存放构成单词符号的字符串,3),GetChar,子程序过程，把下一个字符读入到,ch,中,4),GetBC,子程序过程，跳过空白符，直至,ch,中读入一非空白符,5),C,oncat,子程序，把,ch,中的字符连接到,strToken,国防科技大学计算机系,602,教研室,6),IsLetter,和,IsDisgital,布尔函数，判断,ch,中字符是否为字母,和数字,7),R,eserve,整型函数，对于,strToken,中的字符串查找保留字表，若它实保留字则给出它的编码，否则回送0,8),R,etract,子程序，把搜索指针回调一个字符位置,9),InsertId,整,型函数，将,strToken,中的标识符插入符号表，返回符号表指针,10),InsertConst,整,型函数过程，将,strToken,中的常数插入常数表，返回常数表指针。,国防科技大学计算机系,602,教研室,int code,value;,strToken,:=“”;/*,置,strToken,为空串*,/,GetChar,();,GetBC,();,if(,IsLetter,(),begin,while(,IsLetter,()or,IsDigit,(),begin,Concat,();,GetChar,();,end,Retract();,code:=Reserve();,if(code=0),begin,value:=,InsertId(strToken,);,return($ID,value);,end,else,return(code,-);,end,国防科技大学计算机系,602,教研室,else if(,IsDigit,(),begin,while(,IsDigit,(),begin,Concat,();,GetChar,();,end,Retract();,value:=,InsertConst(strToken,);,return($INT,value);,end,else if(,ch,=)return($ASSIGN,-);,else if(,ch,=+)return($PLUS,-);,国防科技大学计算机系,602,教研室,else if(,ch,=*),begin,GetChar,();,if(,ch,=*)return($POWER,-);,Retract();return($STAR,-);,end,else if(,ch,=;)return($SEMICOLON,-);,else if(,ch,=()return($LPAR,-);,else if(,ch,=)return($RPAR,-);,else,ProcError,();/*,错误处理*,/,国防科技大学计算机系,602,教研室,3.3 正规表达式与有限自动机,几个概念:,考虑一个,有穷,字母表,字符集,其中每一个元素称为一个,字符,上的,字,(也叫,字符串,)是指由中的字符所构成的一个有穷序列,不包含任何字符的序列称为,空字,，记为,用,*,表示,上的所有字的全体,包含空字,例如,:,设,=a,，,b,，,则,*,=,a,b,aa,ab,ba,bb,aaa,.,国防科技大学计算机系,602,教研室,*,的子集,U,和,V,的,连接,（,积,）定义为,UV,|,U&,V,V,自身的,n,次积记为,V,n,=VVV,规定,V,0,=,，,令,V,*,=V,0,V,1,V,2,V,3,称,V,*,是,V,的,闭包,;,记,V,VV,*,，称,V,+,是,V,的正规闭包。,国防科技大学计算机系,602,教研室,3.3.1,正规式和正规集,正规集,可以用,正规表达式,（简称,正规式,）表示。,正规表达式,是表示,正规集,一种方法。一个字集合是,正规集,当且仅当它能用,正规式,表示。,国防科技大学计算机系,602,教研室,冯,-,诺伊曼构造自然数的方案,0,1,2,3,国防科技大学计算机系,602,教研室,正规式和正规集的递归定义：,对给定的字母表,1),和,都是,上的正规式，它们所表示的正规集为,和,;,2),任何,a,，,a,是,上的正规式，它所表示的正规集为,a,;,国防科技大学计算机系,602,教研室,3),假定,e,1,和,e,2,都是,上的正规式，它们所表示的正规集为,L(e,1,),和,L(e,2,),，,则,i),(e,1,|e,2,),为正规式，它所表示的正规集为,L(e,1,),L(e,2,),，,ii),(e,1,.e,2,),为正规式，它所表示的正规集为,L(e,1,)L(e,2,),，,iii),(e,1,),*,为正规式，它所表示的正规集为,(L(e,1,),*,，,仅由,有限次,使用上述三步骤而定义的表达式才是,上的正规式，仅由这些正规式表示的字集才是,上的正规集。,国防科技大学计算机系,602,教研室,所有词法结构一般都可以用正规式描述。,若两个正规式所表示的正规集相同，则称这两个正规式等价。如,b(ab,),*,=(,ba,),*,b(a,*,b,*,),*,=(,a|b,),*,L(,ba,)*b),=,L(ba,)*),L(b,),=(,L(ba,)*,L(b,),=(,L(b)L(a,)*,L(b,),=,ba,*b,=,ba,baba,bababa,b,=,b,bab,babab,bababab,L(b(ab,)*),=,L(b)L(ab,)*),=,L(b,)(,L(ab,)*,=,L(b,)(,L(a)L(b,)*,=b,ab,*,=b,ab,abab,ababab,=,b,bab,babab,bababab,L(b(ab,)*)=L(,ba,)*b),b(ab,)*=(,ba,)*b,国防科技大学计算机系,602,教研室,对正规式，下列等价成立：,e,1,|e,2,=e,2,|e,1,交换律,e,1,|(e,2,|e,3,)=(e,1,|e,2,)|e,3,结合律,e,1,(e,2,e,3,)=(e,1,e,2,)e,3,结合律,e,1,(e,2,|e,3,)=e,1,e,2,|e,1,e,3,分配律,(e,2,|e,3,)e,1,=e,2,e,1,|e,3,e,1,分配律,e,=,e,=e,e,1,e,2,e,2,e,1,L(,e,1,|e,2,),=L(,e,1,),L(,e,2,),=L(,e,2,),L(,e,1,),=L(,e,2,|e,1,),国防科技大学计算机系,602,教研室,正规集,正规式,3.3.1,国防科技大学计算机系,602,教研室,3.3.2,确定有限自动机,(DFA),对状态图进行形式化，则可以下定义：,自动机,M,是一个五元式,M=(S,f,S,0,F),其中：,1.S:,有穷状态集，,2.,：输入字母表,(,有穷,),，,3.f:,状态转换函数，为,S,S,的单值部分映射，,f(s,，,a)=s,表示：当现行状态为,s,，,输入字符为,a,时，将状态转换到下一状态,s,。,我们把,s,称为,s,的一个后继状态。,4.S,0,S,是唯一的一个初态；,5 F,S,：,终态集,(,可空,),。,国防科技大学计算机系,602,教研室,例如：,DFA M=(0,，,1,，,2,，,3,，,a,，,b,，,f,，,0,，,3),，,其中：,f,定义如下：,f(0,，,a)=1f(0,，,b)=2,f(1,，,a)=3 f(1,，,b)=2,f(2,，,a)=1f(2,，,b)=3,f(3,，,a)=3 f(3,，,b)=3,状态转换矩阵,0,3,1,2,a,a,a,a,状态转换图,b,b,b,b,国防科技大学计算机系,602,教研室,DFA,可以表示为状态转换图。假定,DFA M,含有,m,个状态和,n,个输入字符，那么，这个图含有,m,个状态结点，每个结点顶多含有,n,条箭弧射出，且每条箭弧用,上的不同的输入字符来作标记。,国防科技大学计算机系,602,教研室,对于,*,中的任何字,，若存在一条从初态到某一终态的道路，且这条路上所有弧上的标记符连接成的字等于,，则称,为,DFA M,所,识别,(,接收,),DFA M,所识别的字的全体记为,L(M),。,可以证明：,上的字集,V,*,是正规集，当且仅当存在上的,DFA M,，,使得,V,L(M),。,国防科技大学计算机系,602,教研室,3.3.3,非确定有限自动机,(NFA),定义：一个非确定有限自动机,(NFA)M,是一个五元式,M=(S,f,S,0,F),，,其中：,1 S:,有穷状态集；,2,：,输入字母表,(,有穷,),；,3 f:,状态转换函数，为,S,*,2,S,的部分映射,(,非单值,),；,4,S,0,S,是非空的初态集；,5 F,S,：,终态集,(,可空,),。,国防科技大学计算机系,602,教研室,从状态图中看,NFA,和,DFA,的区别：,1,弧上的标记可以是,*,中的一个字，而不一定是单个字符；,2,同一个字可能出现在同状态射出的多条弧上。,DFA,是,NFA,的特例。,国防科技大学计算机系,602,教研室,0,2,1,a，b,aa,a，b,bb,a，b,0,1,2,a,b,a,b,识别所有含相继两个,a,或相继两个,b,的字,a,m,b,n,|m,，,n,1,国防科技大学计算机系,602,教研室,定义：对于任何两个有限自动机,M,和,M,，,如果,L(M)=L(M),，,则称,M,与,M,等价。,自动机理论中一个重要的结论：判定两个自动机等价性的算法是存在的。,对于每个,NFA M,存在一个,DFA M,，,使得,L(M)=L(M),。,亦即,DFA,与,NFA,描述能力相同。,国防科技大学计算机系,602,教研室,1.,假定,NFA M=,，,我们对,M,的状态转换图进行以下改造：,1),引进新的初态结点,X,和终态结点,Y,，,X,Y,S,，,从,X,到,S,0,中任意状态结点连一条,箭弧，从,F,中任意状态结点连一条,箭弧到,Y,。,2),对,M,的状态转换图进一步施行替换，其中,k,是新引入的状态。,证明,:,国防科技大学计算机系,602,教研室,代之为,i,k,A,B,j,i,j,AB,代之为,i,j,A|B,i,j,B,A,代之为,i,j,A*,i,k,j,A,按下面的三条规则对,V,进行分裂,:,国防科技大学计算机系,602,教研室,逐步把这个图转变为每条弧只标记为,上的一个字符或,，最后得到一个,NFA M,，,显然,L(M)=L(M),国防科技大学计算机系,602,教研室,识别所有含相继两个,a,或相继两个,b,的字,X,Y,5,1,4,2,3,6,a,b,a,b,a,b,a,b,5,1,2,6,a,b,a,b,aa,bb,国防科技大学计算机系,602,教研室,2.,把上述,NFA,确定化,采用子集法,.,设,I,是的状态集的一个子集，定义,I,的,-,闭包,-closure(I),为,:,i),若,s,I,，则,s,-closure(I),；,ii),若,s,I,，,则从,s,出发经过任意条,弧而能到达的任何状态,s,都属于,-closure(I),即,-closure(I)=Is|,从某个,s,I,出发经过任意条,弧能到达,s,国防科技大学计算机系,602,教研室,设,a,是,中的一个字符，定义,I,a,=,-closure(J),其中，,J,为,I,中的某个状态出发经过一条,a,弧而到达的状态集合。,国防科技大学计算机系,602,教研室,-closure(1)=1,，,2=I,J=5,，,4,，,3,I,a,=,-,closure(J,)=-closure(5,，,4,，,3),=5,，,4,，,3,，,6,，,2,，,7,，,8,6,1,a,2,3,4,5,7,8,a,a,设,a,是,中的一个字符，定义,I,a,=,-closure(J),其中，,J,为,I,中的某个状态出发经过一条,a,弧而到达的状态集合。,国防科技大学计算机系,602,教研室,把确定化的过程,:,不失一般性，设字母表只包含两个,a,和,b,，,我们构造一张表,:,国防科技大学计算机系,602,教研室,首先，置第,1,行第,1,列为,-closure(X),求出这一列的,I,a,，,I,b,；,然后，检查这两个,I,a,，,I,b,，,看它们是否已在表中的第一列中出现，把未曾出现的填入后面的空行的第,1,列上，求出每行第,2,，,3,列上的集合,.,重复上述过程，知道所有第,2,，,3,列子集全部出现在第一列为止。,国防科技大学计算机系,602,教研室,I,I,a,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,5,2,3,1,6,Y,5,2,3,1,6,Y,5,4,6,1,Y,5,4,6,1,Y,5,3,6,1,Y,5,2,4,1,6,Y,5,2,4,1,6,Y,5,3,6,1,Y,5,2,4,1,6,Y,5,3,6,1,Y,5,2,3,1,6,Y,5,4,6,1,Y,X,Y,5,1,4,2,3,6,a,b,a,b,a,b,a,b,国防科技大学计算机系,602,教研室,现在把这张表看成一个状态转换矩阵，把其中的每个子集看成一个状态。,这张表唯一刻划了一个确定的有限自动机,M,，,它的初态是,-closure(X),，,它的终态是含有原终态,Y,的子集。,不难看出，这个,DFA M,与,M,等价。,国防科技大学计算机系,602,教研室,I,a,b,0,1,2,1,3,2,2,1,4,3,3,4,4,6,5,5,6,5,6,3,4,0,1,2,3,5,4,6,a,a,b,b,b,a,b,a,a,b,a,b,a,b,国防科技大学计算机系,602,教研室,FA,正规集,正规式,DFA,NFA,正规文法,3.3.1,3.3.2,3.3.3,3.3.4,国防科技大学计算机系,602,教研室,3.3.4,正规文法与有限自动机的等价性,对于正规文法,G,和有限自动机,M,，,如果,L(G),L(M),，,则称,G,和,M,是,等价,的。关于正规文法和有限自动机的等价性，有以下结论：,国防科技大学计算机系,602,教研室,3.3.4,正规文法与有限自动机的等价性,定理：,1.,对每一个右线性正规文法,G,或左线性正规文法,G,，,都存在一个有限自动机,(FA)M,，,使得,L(M),L(G),。,2.,对每一个,FA M,，,都存在一个右线性正规文法,G,R,和左线性正规文法,G,L,，,使得,L(M),L(G,R,),L(G,L,),。,国防科技大学计算机系,602,教研室,证明：,1.,对每一个右线性正规文法,G,或左线性正规文法,G,，,都构造一个有限自动机（,FA,）,M,，,使得,L(M),L(G),。,(1),设右线性正规文法,G=,。将,V,N,中的每一非终结符号视为状态符号，并增加一个新的终结状态符号,f,，,f,V,N,。,令,M=,，,其中状态转换函数,由以下规则定义：,国防科技大学计算机系,602,教研室,(a),若对某个,A,V,N,及,a,V,T,，,P,中有产生式,Aa,，,则令,(A,a)=f,(b),对任意的,A,V,N,及,a,V,T,，设,P,中左端为,A,，,右端第一符号为,a,的所有产生式为：,AaA,1,|,aA,k,（,不包括,Aa,），,则令,(A,a)=A,1,A,k,。,显然，上述,M,是一个,NFA,。,国防科技大学计算机系,602,教研室,对于右线性正规文法,G,，在,S w,的最左推导过程中,:,利用,A,aB,一次就相当于在,M,中从状态,A,经过标记为,a,的箭弧到达状态,B,（,包括,a=,的情形）,;,在推导的最后，利用,A,a,一次则相当于在,M,中从状态,A,经过标记为,a,的箭弧到达终结状态,f,（,包括,a=,的情形）。,综上，在正规文法,G,中，,S w,的充要条件是：在,M,中，从状态,S,到状态,f,有一条通路，其上所有箭弧的标记符号依次连接起来恰好等于,w,，,这就是说，,w,L(G),当且仅当,w,L(M),，故,L(G),L(M),。,国防科技大学计算机系,602,教研室,(2),设左线性正规文法,G=,。将,V,N,中的每一符号视为状态符号，并增加一个初始状态符号,q,0,，,q,0,V,N,。,令,M=,，,其中状态转换函数,由以下规则定义：,(a),若对某个,A,V,N,及,a,V,T,，若,P,中有产生式,A,a,，,则令,(q,0,a)=A,(b),对任意的,A,V,N,及,a,V,T,，若,P,中所有右端第一符号为,A,，,第二个符号为,a,的产生式为：,A,1,Aa,A,k,Aa,，,则令,(A,a)=A,1,A,k,。,与,(1),类似，可以证明,L(G),L(M),。,国防科技大学计算机系,602,教研室,G,R,(A),：,A0|0B|1D,B0D|1C,C0|0B|1D,D0D|1D,从,G,R,出发构造,NFA M=,，,M,的状态转换图如右图所示。,显然,L(M)=L(G,R,),。,例,:,A,B,C,D,1,0,0,1,1,1,0,f,0,0,0,国防科技大学计算机系,602,教研室,3.3.4,正规文法与有限自动机的等价性,定理：,1.,对每一个右线性正规文法,G,或左线性正规文法,G,，,都存在一个有限自动机,(FA)M,，,使得,L(M),L(G),。,2.,对每一个,FA M,，,都存在一个右线性正规文法,G,R,和左线性正规文法,G,L,，,使得,L(M),L(G,R,),L(G,L,),。,国防科技大学计算机系,602,教研室,证明,2,：对每一个,DFA M,，,都存在一个右线性正规文法,G,R,和左线性正规文法,G,L,，,使得,L(M),L(G,R,),L(G,L,),。,设,DFA M=,(1),若,s,0,F,，,我们令,G,R,=,，,其中,P,是由以下规则定义的产生式集合：,对任何,a,及,A,B,S,，,若有,(A,a)=B,，,则：,(a),当,B,F,时，令,AaB,，,(b),当,B,F,时，令,Aa|aB,。,国防科技大学计算机系,602,教研室,对任何,w,*,，,不妨设,w=a,1,a,k,，,其中,a,i,(i=1,k),。若,s,0,w,，,则存在一个最左推导：,s,0,a,1,A,1,a,1,a,2,A,2,a,1,a,i,A,i,a,1,a,i+1,A,i+1,a,1,a,k,因而，在,M,中有一条从,s,0,出发依次经过,A,1,，,，,A,k-1,到达终态的通路，该通路上所有箭弧的标记依次为,a,1,a,k,。,反之亦然。所以，,w,L(G,R,),当且仅当,w,L(M),。,国防科技大学计算机系,602,教研室,现在考虑,s,0,F,的情形：,因为,(s,0,)=s,0,，,所以,L(M),。,但,不属于上面构造的,G,R,所产生的语言,L(G,R,),。,不难发现，,L(G,R,)=L(M)-,。,所以，我们在上述,G,R,中添加新的非终结符号,s,0,，,(s,0,S),和产生式,s,0,s,0,|,，,并用,s,0,代替,s,0,作开始符号。这样修正,G,R,后得到的文法,G,R,仍是右线性正规文法，并且,L(G,R,)=L(M),。,(2),类似于,(1),，从,DFA M,出发可构造左线性正规文法,G,L,，,使得,L(G,L,)=L(M),。,最后，由,DFA,和,NFA,之间的等价性，结论,2,得证。,若有,(,A,a,)=B,：,(a),当,A,=,q,0,时，令,Ba,，,(b),当,A,q,0,时，令,BAa,国防科技大学计算机系,602,教研室,L(M)=0(10),*,G,R,=,，,其中,P,由下列产生式组成：,A0|0B|1D,B0D|1C,C0|0B|1D,D0D|1D,L(G,R,)=L(M)=0(10)*,例,3.4,设,DFA M=,。,M,的状态转换图如下图所示。,A,B,C,D,1,0,0,1,1,1,0,0,国防科技大学计算机系,602,教研室,从,NFA M,出发构造左线性正规文法,G,L,=,，,其中,P,由下列产生式组成：,f0|C0,CB1,B0|C0,D1|C1|D0|D1|B0,易证,L(G,L,)=L(M),。,例,3.4,设,DFA M=,。,M,的状态转换图如图,3.9(a),所示。,A,B,C,D,1,0,0,1,1,1,0,f,0,0,0,国防科技大学计算机系,602,教研室,FA,正规集,正规式,DFA,NFA,正规文法,3.3.1,3.3.2,3.3.3,3.3.4,3.3.5,国防科技大学计算机系,602,教研室,3.3.5,正规式与有限自动机的等价性,定理：,1.,对任何,FA M,，,都存在一个正规式,r,，,使得,L(r)=L(M),。,2.,对任何正规式,r,，,都存在一个,FA M,，,使得,L(M)=L(r),。,对转换图概念拓广，令每条弧可用一个正规式作标记。,(,对一类输入符号,),国防科技大学计算机系,602,教研室,证明：,1,对,上任一,NFA M,，,构造一个,上的正规式,r,，,使得,L(r)=L(M),。,首先，在,M,的转换图上加进两个状态,X,和,Y,，从,X,用,弧连接到,M,的所有初态结点，从,M,的所有终态结点用,弧连接到,Y,，,从而形成一个新的,NFA,，,记为,M,，,它只有一个初态,X,和一个终态,Y,，,显然,L(M)=L(M),。,然后，反复使用下面的一条规则，逐步消去的所有结点，直到只剩下,X,和,Y,为止；,国防科技大学计算机系,602,教研室,代之为,i,j,r,1,r,2,k,i,k,r,1,r,2,代之为,i,j,r,1,|r,2,i,j,r,2,r,1,代之为,i,k,r,1,r,2,*r,2,i,j,r,1,r,3,k,r,2,国防科技大学计算机系,602,教研室,1,2,3,5,4,U,1,V,1,U,2,V,2,W,2,W,1,1,2,5,4,V,1,(U,1,|U,2,)*W,1,V,1,(U,1,|U,2,)*W,2,V,2,(U,1,|U,2,)*W,2,V,2,(U,1,|U,2,)*W,1,国防科技大学计算机系,602,教研室,最后，,X,到,Y,的弧上标记的正规式即为所构造的正规式,r,显然,L(r)=L(M)=L(M),国防科技大学计算机系,602,教研室,证明,2:,对于,上的正规式,r,，,构造一个,NFA M,，使,L(M)=L(r),，,并且,M,只有一个终态，而且没有从该终态出发的箭弧,。,下面使用关于,r,中运算符数目的归纳法证明上述结论。,(1),若,r,具有零个运算符，则,r=,或,r=,或,r=a,，,其中,a,。,此时下图所示的三个有限自动机显然符合上述要求。,q,0,q,0,q,f,a,q,0,q,f,国防科技大学计算机系,602,教研室,(2),假设结论对于少于,k(k,1),个运算符的正规式成立。,当,r,中含有,k,个运算符时，,r,有三种情形：,情形,1,：,r=r,1,|r,2,，,r,1,r,2,中运算符个数少于,k,。,从而，由归纳假设，,对,r,i,存在,M,i,=,，,使得,L(M,i,)=,L(r,i,),，,并且,M,i,没有从终态出发的箭弧（,i=1,2,）。,不妨设,S,1,S,2,=,，在,S,1,S,2,中加入两个新状态,q,0,，,f,0,。,国防科技大学计算机系,602,教研室,令,M=,，,其中,定义如下：,(a),(q,0,)=q,1,q,2,(b),(q,a)=,1,(q,a),当,q,S,1,-f,1,a,1,(c),(q,a)=,2,(q,a),当,q,S,2,-f,2,a,2,(d),(f,1,)=,(f,2,)=f,0,。,M,的状态转换如右图所示。,L(M)=L(M,1,),L(M,2,),=L(r,1,),L(r,2,)=L(r),q,0,f,0,M,1,q,1,f,1,M,2,q,2,f,2,国防科技大学计算机系,602,教研室,情形,2,：,r=r1r2,设,M,i,同情形,1(i=1,2),。,令,M=,，,其中,定义如下：,(a),(q,a)=,1,(q,a),当,q,S,1,-f,1,a,1,(b),(q,a)=,2,(q,a),当,q,S,2,a,2,(c),(f,1,)=q,2,M,的状态转换如右图所示。,L(M)=L(M,1,)L(M,2,),=L(r,1,)L(r,2,)=L(r),。,M,1,q,1,f,1,M,2,q,2,f,2,国防科技大学计算机系,602,教研室,情形,3,：,r=r,1,*,。设,M,1,同情形,1,。,令,M=,，,其中,q,0,f,0,S,1,，,定义如下：,(a),(q,0,)=,(f,1,)=q,1,f,0,(b),(q,a)=,1,(q,a),当,q,S,1,-f,1,a,1,。,M,的状态转换如右图所示。,L(M)=L(M,1,),*,=L(r,1,),*,=L(r),至此，结论,2,获证。,M,1,q,1,f,1,q,0,f,0,国防科技大学计算机系,602,教研室,1),构造,上的,NFA M,使得,L(V)=L(M),首先，把,V,表示成,X,Y,V,上述证明过程实质上是一个将正规表达式转换为有限自动机的算法。,国防科技大学计算机系,602,教研室,代之为,i,j,V,1,V,2,k,i,k,V,1,V,2,代之为,i,j,V,1,|V,2,i,j,V,2,V,1,代之为,i,k,V,1,*,i,j,k,V,1,然后，按下面的三条规则对,