最新形式语言自动机——上下文无关文法与下推自动机(四)PPT课件.ppt
形式语言自动机形式语言自动机上下文上下文无关文法与下推自动机无关文法与下推自动机(四四)从上下文无关文法构造等价的下推自从上下文无关文法构造等价的下推自动机机n 定理定理4.5.1（由（由CFG可导出可导出PDA）：设上下文无关文法G（N，T，P，S），产生语言L（G），则存在PDA M，以空栈接受语言L(M),使L(M)=L(G)。n 证证明明：构造下推自动机M，使M按文法G的最左推导方式工作。2College of Computer Science&Technology,BUPT例例：构构造造一一个个PDA PDA M M，使使L(M)=(M)=L(G)L(G)。其其中中G G是是我我们们常常用用来来生生成算术表达式的文法：成算术表达式的文法：G G（N N，T T，P P，E E）N N E,T,F,T=+,*,(,),a,S=E E,T,F,T=+,*,(,),a,S=E P:EE+TT;TT*FF;F(E)a P:EE+TT;TT*FF;F(E)a解：构造解：构造M（q，T，q，E，）定义为：定义为：(q,E,E)(q,E+T),(q,T)(q,T,T)(q,T*F),(q,F)(q,F,F)(q,(E),(q,a)(q,b,bb,b)(q,)对所有对所有 b a,+,*,(,)a,+,*,(,)例例3:从文法构造等价的下推自从文法构造等价的下推自动机机9College of Computer Science&Technology,BUPT用格局用格局说明句子分析明句子分析过程程 例例如如 以以a+a*a*a作作为为输输入入，则则M M在在所所有有可可能能移移动动中中可可作作下下列列移移动动（用到文法（用到文法G G中从中从E E出发的最左派生的一系列规则）出发的最左派生的一系列规则）（q q，a aa*a,Ea*a,E）(q(q，a aa*a,E+T)a*a,E+T)(q (q，a aa*a,T+T)a*a,T+T)(q (q，a aa*a,F+T)a*a,F+T)(q (q，a aa*a,a+T)a*a,a+T)(q (q，a*a,+T)a*a,+T)(q (q，a*a,T)a*a,T)(q (q，a*a,T*F)a*a,T*F)(q (q，a*a,F*F)a*a,F*F)10College of Computer Science&Technology,BUPT从下推自动机构造等价的上下文无关文法从下推自动机构造等价的上下文无关文法 定理定理4.5.14.5.1是由是由G G导出导出PDAPDA，其逆定理也成立。其逆定理也成立。定理定理4.5.24.5.2（由（由PDAPDA导出文法导出文法G G）：）：设设下下推推自自动动机机M M，以以空空栈栈形形式式接接受受语语言言 L L(M(M），则则存存在在一一个上下文无关文法个上下文无关文法G G，产生语言产生语言L(G),L(G),使使L(G)=LL(G)=L(M(M）。证明：设证明：设M M（Q，T，q q0 0，z z0 0，）思路：构造文法思路：构造文法G G，使使串在串在G G中的一个最左推导直接对应于中的一个最左推导直接对应于PDA M PDA M 在处理在处理时所做的一系列移动时所做的一系列移动。11College of Computer Science&Technology,BUPT从下推自动机构造等价的上下文无关文法从下推自动机构造等价的上下文无关文法采用形如采用形如 q q，z,z,的非终结符的非终结符,q q，QQ，zz q q，z,z,的物理意义：的物理意义：在在q q状状态态，栈栈顶顶为为z z时时，接接受受某某个个字字符符(可可为为)后后将将变变换换到到状态，并保证状态，并保证 q q，z,z,当且仅当（当且仅当（q,zq,z）*（,）.12College of Computer Science&Technology,BUPT从下推自动机构造等价的上下文无关文法从下推自动机构造等价的上下文无关文法 构造方法构造方法 设设 PDA MPDA M（Q Q，T T，q q0 0，z z0 0，）,构造构造CFGG G（N,T,P,SN,T,P,S）其中其中 N N q,z,q,Q q,z,q,Q，zSzS 产生式集合产生式集合 P定义如下：定义如下：1)1)对于每个对于每个qQqQ，将将SSq q0 0，z z0 0,q,q 加入到加入到产生产生式中。式中。2)若若（q q，a a，z z）含有（含有（,），），则将则将 q,z,aq,z,a加入到加入到产生产生式中。式中。3)3)若若（q q，a a，z z）含有（含有（，B B1 1,B,B2 2,B,Bk k）k1k1，B Bi i，则对则对Q Q中的中的每一个状每一个状态态序列序列q q1 1,q,q2 2,q,qk k,(q,(qi iQ),Q),把形如把形如 q,z,qq,z,qk ka,Ba,B1 1,q,q1 1qq1 1,B,B2 2,q,q2 2 qqk-1k-1,B,Bk k,q,qk k 的的产产生式加入到生式加入到P P中。其中，中。其中，a a T T 或或 a a=13College of Computer Science&Technology,BUPT（书P169170）由PDA M构造文法G设PDA M（q0,q1,a,b,A,z0,q0,z0,）定义为：（q0,a,z0）=(q0,Az0)（q0,a,A）=(q0,AA)（q0,b,A）=(q1,)（q1,b,A）=(q1,)（q1,A）=(q1,)（q1,z0）=(q1,)例例1:从下推自动机构造等价的上下文无关文法从下推自动机构造等价的上下文无关文法14College of Computer Science&Technology,BUPT q0 b,A/q1 a,z0/Az0 b,A/a,A/AA ,A/,z0/解：（1）q0,q1Q，构造 Sq0,z0,q0;Sq0,z0,q1（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,q115College of Computer Science&Technology,BUPT q0 b,A/q1 a,z0/Az0 b,A/a,A/AA ,A/,z0/（3）对式（q0,a,z0）=(q0,A z0)，所有可能的状态序列为：q0q0，q1q0，q0q1，q1q1可构造出产生式：q0,z0,q0 a q0,A,q0 q0,z0,q0 q0,z0,q0 a q0,A,q1 q1,z0,q0 q0,z0,q1 a q0,A,q0 q0,z0,q1 q0,z0,q1 a q0,A,q1 q1,z0,q1 16College of Computer Science&Technology,BUPT q0 b,A/q1 a,z0/Az0 b,A/a,A/AA ,A/,z0/对式（q0,a,A）=(q0,AA)，所有可能的状态序列为：q0q0，q1q0，q0q1，q1q1可构造出产生式：q0,A,q0 a q0,A,q0 q0,A,q0 q0,A,q0 a q0,A,q1 q1,A,q0 q0,A,q1 a q0,A,q0 q0,A,q1 q0,A,q1 a q0,A,q1 q1,A,q1 17College of Computer Science&Technology,BUPT(4)删除无用符号 q0,A,q1 和 q1,z0,q0及相应产生式 重命名 q0,z0,q1为A SA q1,A,q1为B AaCD q0,A,q1为C 得 Bb q1,z0,q1为D CaCBb D注注:构构造造生生成成式式时时，可可从从S S生生成成式式出出发发，以以避避免免生生成成无无用用产生式。产生式。18College of Computer Science&Technology,BUPT定理的关键：定理的关键：当当存存在在(q，a，z)含含有有（，B1B2Bk）则则对对Q中中的每个可能的状态序列的每个可能的状态序列q1 q2 qk排成一条产生式排成一条产生式q,z,qka,B1,q1 q1,B2,q2qk-1,Bk,qk 这这是是一一个个猜猜测测过过程程，实实质质是是写写出出从从q出出发发，栈栈顶顶为为Z，经经过过一一系系列列推推导导走走到到qk的的所所有有可可能能的的状状态态序序列列，其中必有一条路径是正确的。其中必有一条路径是正确的。19College of Computer Science&Technology,BUPTM（q，T，q，E，）定义为：定义为：(q,E,E)(q,E+T),(q,T)(q,T,T)(q,T*F),(q,F)(q,F,F)(q,(E),(q,a)(q,b,bb,b)(q,)对所有对所有 b a,+,*,(,)a,+,*,(,)算术表达式的文法算术表达式的文法 G G（N N，T T，P P，E E）N N E,T,F,T=+,*,(,),a,S=E E,T,F,T=+,*,(,),a,S=E P:EE+TT;TT*FF;F(E)a P:EE+TT;TT*FF;F(E)a练习：针对算术表达式的练习：针对算术表达式的PDA反向构造其等价文法反向构造其等价文法20College of Computer Science&Technology,BUPT练习练习:从从PDA构造等价的上下文无关文法构造等价的上下文无关文法对于右下图的对于右下图的 PDA，构造构造CFG G=(N,0,1,P,S)，其中其中N=S p,Y,q p,q q0,q1,q2 Y Z0,X 产生式集合产生式集合 P定义如下：定义如下：(1)S q0,Z0,q0;S q0,Z0,q1;S q0,Z0,q2;(5)由由(q0,XZ0)(q0,0,Z0)得得q0Z0qj 0q0XqiqiZ0qj,i,j=0,1,2;(6)由由(q0,XX)(q0,0,X)得得 q0Xqj 0q0XqiqiXqj,i,j=0,1,2;(2)由由(q1,)(q0,1,X)得得q0Xq1 1;(3)由由(q1,)(q1,1,X)得得q1Xq1 1;(4)由由(q2,)(q1,Z0)得得q1Z0q2 ;21College of Computer Science&Technology,BUPT练习练习:从从PDA构造等价的上下文无关文法构造等价的上下文无关文法（续前页）（续前页）消去所有非消去所有非生成符号，得到的新文法包含如下产生式：生成符号，得到的新文法包含如下产生式：S q0Z0q2;q0Z0q2 0q0Xq1q1Z0q2q0Xq1 0q0Xq1q1Xq1 q0Xq1 1;q1Xq1 1;q1Z0q2 ;为简洁为简洁，记，记 q0Z0q2为为A，q0Xq1为为B，q1Xq1为为C，q1Z0q2为为D，上述文法的产生式改写如下：上述文法的产生式改写如下：S A;A 0BD;B 0BC;B 1;C 1;D ;22College of Computer Science&Technology,BUPT作业作业:Ch4 Ch4 习题习题 20 20，2121，222223College of Computer Science&Technology,BUPT
