形式语言自动机——上下文无关文法与下推自动机(四).ppt

*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,College of Computer Science&Technology,BUPT,1,College of Computer Science&Technology,BUPT,4.5 上下文无关文法与下推自动机,上下文无关文法与下推自动机的等价性:,PDA,与上下文无关文法 之间存在着对应关系。即：,PDA(M)CFG,CFG =PDA(M),2,College of Computer Science&Technology,BUPT,从上下文无关文法构造等价的下推自动机,定理4.5.1（由,CFG,可导出,PDA）,：,设上下文无关文法,G,（,N,，,T,，,P,，,S,），,产生语言,L,（,G,），,则存在,PDA M,，,以空栈接受语言,L,(M),使,L,(M)=L(G)。,证明：,构造下推自动机,M,，,使,M,按文法,G,的最左推导方式工作。,3,College of Computer Science&Technology,BUPT,构造方法,设,CFG,G,=(,N,T,P,S,),，,构造一个空栈接受,方式的,PDA,M（Q，T，q,0,，z,0,，F）,其中,Qq,=NT,q,0,q，z,0,S,F(,以空栈接受),即,M=(q,T,N,T,q,S,F),转移函数,定义如下：,(1),对每一,A,N,(q,A)=(q,),A,”,P;,（,即将栈顶的,A,换为,）,(2),对每一,a,T,(q,a,a)=(q,).,（,即若栈顶为终结符，则退栈）,从上下文无关文法构造等价的下推自动机,4,College of Computer Science&Technology,BUPT,q,，,z0S/,若,SP,，A/,若,AP,a,a/,a,T,从上下文无关文法构造等价的下推自动机,用图形表示：,例1,对右边产生式所代表,CFG,，,依上述方法构造的,PDA,为,E,EOE,(E),v,d,O,(,q,v,d,+,(,),E,O,v,d,+,q,E,),其中,定义为,(,q,E)=,(,q,EOE),(q,(E),(q,v),(q,d),(,q,),(q,),(,q,O)=,(,q,),(,q,v,v)=,(,q,d,d)=,(,q,),(q,)=(q,)=,(q,(,()=(q,),)=,5,College of Computer Science&Technology,BUPT,自顶向下的分析过程,定理的物理意义：,利用下推自动机进行自顶向下的分析，,检查一个句子的最左推导过程。,步骤如下：,(1),初始时，将文法开始符号压入空栈.,(2),如果栈为空，则分析完成.,(3),如果栈顶为一非终结符，先将其从栈中弹出.选择下,一个相应于该非终结符的产生式，并将其右部 符号从,右至左地一一入栈.如果没有可选的产生式，则转出,错处理.,(4),如果栈顶为一终结符，那么这个符号必须与当前输入,符号相同，将其弹出栈，读下一符号，转第,(2),步；否,则，回溯到第,(3),步.,6,College of Computer Science&Technology,BUPT,例2：利用下推自动机进行自顶向下的分析过程,E,EOE,(E),v,d,O,E,E,O,E,E,O,v,E,O,E,E,E,),(,E,),E,),O,E,E,),O,v,E,),O,E,),E,),),d,),v,(v,d ),q,，,z,0,E,/,若,EP,，O/*,a,a/a (,),v,d,+,*,，O/+,7,College of Computer Science&Technology,BUPT,定理的证明,证明思路,欲证，对任何,w,T*,w,L(G),w,L,(M).,先证明如下结论,if,A,w,then,(q,w,A),*,(q,).,归纳于,A,w,的步数,n,.,基础,n=1,，,A,w,必为产生式，,(,q,w,A),(q,w,w),*,(q,).,归纳,设第一步使用产生式,A,X,1,X,2,X,m,，,必有,w=,w,1,w,2,w,m,，,(q,w,A),(q,w,X,1,X,2,X,m,),*,(q,w,2,w,m,X,2,X,m,),*,(q,w,3,w,m,X,3,X,m,),*,(q,).,所以:,if,S,w,then,(q,w,S),*,(q,).,即,w,L(G),w,L(M).,8,College of Computer Science&Technology,BUPT,定理的证明,先证明如下结论,if,(q,w,A),*,(q,),then,A,w.,归纳于,(,q,w,A),*,(q,),的步数,n,.,归纳,n1,，,设第一步使用产生式,A,X,1,X,2,X,m,，,可以将,w,分为,w,=,w,1,w,2,w,m,，,满足,(,q,w,i,X,i,),*,(q,),，,所以:对任何,w,T*,if,(q,w,S),*,(q,),then,S,w.,即,w,L(M),w,L(G).,因此，,A,X,1,X,2,X,m,，,w,1,w,2,w,m,=,w,无论,X,i,为终结符，还是非终结符，都有,X,i,w,i,.,基础,n=1,，,必有,w,=,，,且,A,为,G,的产生式，所以,A,w,.,9,College of Computer Science&Technology,BUPT,例：构造一个,PDA M，,使,L,(M)=L(G)。,其中,G,是我们常用来生成算术表达式的文法：,G（N，T，P，E）,N E,T,F,T=+,*,(,),a,S=E,P:EE+TT;TT*FF;F(E)a,解：构造,M,（,q,，,T,，,q,，,E,，）,定义为：,(q,E,),(q,E+T),(q,T),(q,T,),(q,T,*,F),(q,F),(q,F,),(q,(E),(q,a),(q,b,b,),(q,),对所有,b,a,+,*,(,),例3,:,从文法构造等价的下推自动机,10,College of Computer Science&Technology,BUPT,用格局说明句子分析过程,例如 以,a+a,*a,作为输入，则,M,在所有可能移动中可作下列移动（用到文法,G,中从,E,出发的最左派生的一系列规则）,（,q，aa*a,E）(q，aa*a,E+T),(q，aa*a,T+T),(q，aa*a,F+T),(q，aa*a,a+T),(q，a*a,+T),(q，a*a,T),(q，a*a,T*F),(q,，,a*a,F*F),11,College of Computer Science&Technology,BUPT,从下推自动机构造等价的上下文无关文法,定理4.5.1是由,G,导出,PDA，,其逆定理也成立。,定理4.5.2（由,PDA,导出文法,G）：,设下推自动机,M，,以空栈形式接受语言,L,(M），,则存在一个上下文无关文法,G，,产生语言,L(G),使,L(G)=L,(M）。,证明：设,M（,Q,，,T,，,，q,0,，z,0,，）,思路：构造文法,G，,使,串在,G,中的一个最左推导直接对应于,PDA M,在处理,时所做的一系列移动,。,12,College of Computer Science&Technology,BUPT,从下推自动机构造等价的上下文无关文法,采用形如,q，z,的非终结符,q，Q，z,q，z,的物理意义：,在,q,状态，栈顶为,z,时，接受某个字符(可为,),后将变换到,状态，并保证,q，z,当且仅当（,q,z）,*,（,）.,13,College of Computer Science&Technology,BUPT,从下推自动机构造等价的上下文无关文法,构造方法,设,PDA M（Q，T，q,0,，z,0,，）,构造,CFG,G（N,T,P,S）,其中,N q,z,q,Q，zS,产生式集合,P,定义如下：,对于每个,qQ，,将,S,q,0,，,z,0,q,加入到,产生,式中。,若,（q，a，z）,含有（,），,则将,q,z,a,加入到,产生,式中。,若,（q，a，z）,含有（,，B,1,B,2,B,k,）k1，B,i,，,则对,Q,中的,每一个状态序列,q,1,q,2,q,k,(q,i,Q),把形如,q,z,q,k,a,B,1,q,1,q,1,B,2,q,2,q,k-1,B,k,q,k,的产生式加入到,P,中。其中，,a,T,或,a,=,14,College of Computer Science&Technology,BUPT,（书,P169170）,由,PDA M,构造文法,G,设,PDA M（,q0,q1,a,b,A,z0,q0,z0,）,定义为：,（,q,0,a,z,0,）=(,q,0,A,z,0,),（,q,0,a,A,）=(,q,0,A,A),（,q,0,b,A,）=(,q,1,),（,q,1,b,A,）=(,q,1,),（,q,1,A,）=(,q,1,),（,q,1,z0,）=(,q,1,),例1:,从下推自动机构造等价的上下文无关文法,15,College of Computer Science&Technology,BUPT,q,0,b,A/,q,1,a,z,0,/Az,0,b,A/,a,A/AA,A/,z,0,/,解：（1）,q,0,q,1,Q，,构造,Sq,0,z,0,q,0,;,Sq,0,z,0,q,1,（2）,对,式，可构造,由,（q0,b,A,）=(q1,),得,q0,A,q1b,由,（q1,b,A,）=(q1,),得,q1,A,q1b,由,（q1,A,）=(q1,),得,q1,A,q1,由,（q1,z0,）=(q1,),得,q1,z0,q1,16,College of Computer Science&Technology,BUPT,q,0,b,A/,q,1,a,z,0,/Az,0,b,A/,a,A/AA,A/,z,0,/,（3）,对,式,（q,0,a,z,0,）=(q,0,A,z,0,),，,所有可能的状态序列为：,q,0,q,0,，q,1,q,0,，q,0,q,1,，q,1,q,1,可构造出产生式：,q,0,z,0,q,0,a q,0,A,q,0,q,0,z,0,q,0,q,0,z,0,q,0,a q,0,A,q,1,q,1,z,0,q,0,q0,z0,q1 a q0,A,q0 q0,z0,q1 ,q0,z0,q1 a q0,A,q1 q1,z0,q1 ,17,College of Computer Science&Technology,BUPT,q,0,b,A/,q,1,a,z,0,/Az,0,b,A/,a,A/AA,A/,z,0,/,对,式,（q,0,a,A,）=(,q,0,AA,),，,所有可能的状态序列为：,q,0,q,0,，q,1,q,0,，q,0,q,1,，q,1,q,1,可构造出产生式：,q,0,A,q,0,a q,0,A,q,0,q,0,A,q,0,q,0,A,q,0,a q,0,A,q,1,q,1,A,q,0,q,0,A,q1 a q,0,A,q,0,q,0,A,q,1,q,0,A,q1 a q,0,A,q,1,q,1,A,q,1,18,College of Computer Science&Technology,BUPT,(4)删除无用符号,q,0,A,q,1,和,q,1,z,0,q,0,及相应产生式,重命名,q0,z0,q1,为,A SA,q1,A,q1,为,B AaCD,q0,A,q1,为,C,得,Bb,q1,z0,q1,为,D CaCBb,D,注:构造生成式时，可从,S,生成式出发，以避免生成无用产生式。,19,College of Computer Science&Technology,BUPT,定理的关键：,当存在,(q，a，z),含有（,，B,1,B,2,B,k,）,则对,Q,中的每个可能的状态序列,q,1,q,2,q,k,排成一条产生式,q,z,q,k,a,B,1,q,1,q,1,B,2,q,2,q,k-1,B,k,q,k,这是一个猜测过程，实质是写出从,q,出发，栈顶为,Z,，,经过一系列推导走到,q,k,的所有可能的状态序列，其中必有一条路径是正确的。,20,College of Computer Science&Technology,BUPT,M,（,q,，,T,，,q,，,E,，）,定义为：,(q,E,),(q,E+T),(q,T),(q,T,),(q,T,*,F),(q,F),(q,F,),(q,(E),(q,a),(q,b,b,),(q,),对所有,b,a,+,*,(,),算术表达式的文法,G（N，T，P，E）,N E,T,F,T=+,*,(,),a,S=E,P:EE+TT;TT*FF;F(E)a,练习：针对算术表达式的,PDA,反向构造其等价文法,21,College of Computer Science&Technology,BUPT,练习:,从,PDA,构造等价的上下文无关文法,对于右下图的,PDA,，,构造,CFG,G,=(,N,0,1,P,S,),，,其中,N=S,p,Y,q,p,q,q,0,q,1,q,2,Y,Z,0,X,产生式集合,P,定义如下：,(1),S,q,0,Z,0,q,0,;,S,q,0,Z,0,q,1,;,S,q,0,Z,0,q,2,;,(5),由,(q,0,XZ,0,),(,q,0,0,Z,0,),得,q,0,Z,0,q,j,0,q,0,Xq,i,q,i,Z,0,q,j,i,j,=0,1,2;,(6),由,(q,0,XX),(,q,0,0,X,),得,q,0,Xq,j,0,q,0,Xq,i,q,i,Xq,j,i,j,=0,1,2;,(2),由(,q,1,),(,q,0,1,X,),得,q,0,Xq,1,1,;,(3),由,(q,1,),(,q,1,1,X,),得,q,1,Xq,1,1,;,(4),由,(,q,2,),(,q,1,Z,0,),得,q,1,Z,0,q,2,;,22,College of Computer Science&Technology,BUPT,练习:,从,PDA,构造等价的上下文无关文法,（续前页）,消去所有非,生成符号，得到的新文法包含如下产生式：,S,q,0,Z,0,q,2,;,q,0,Z,0,q,2,0,q,0,Xq,1,q,1,Z,0,q,2,q,0,Xq,1,0,q,0,Xq,1,q,1,Xq,1,q,0,Xq,1,1,;,q,1,Xq,1,1,;,q,1,Z,0,q,2,;,为简洁,，记,q,0,Z,0,q,2,为,A,，,q,0,Xq,1,为,B,，,q,1,Xq,1,为,C,，,q,1,Z,0,q,2,为,D,，,上述文法的产生式改写如下：,S,A,;,A,0,BD;B,0,BC;,B,1,;C,1,;D,;,23,College of Computer Science&Technology,BUPT,作业:,Ch4,习题 20，21，22,