《形式语言与自动机》课件ch4.5.ppt

1、1School of Computer Science,BUPT4.5 上下文无关文法与下推自动机上下文无关文法与下推自动机 上下文无关文法与下推自动机的等价性上下文无关文法与下推自动机的等价性:PDA与上下文无关文法之间存在着对应关系。即：n PDA(M)CFGn CFG =PDA(M)PDA byfinal statePDA byemptystackGrammar2School of Computer Science,BUPT从上下文无关文法构造等价的下推自动机从上下文无关文法构造等价的下推自动机n 定理定理4.5.1（由（由CFG可导出可导出PDA）：设上下文无关文法G（N，T，P，S）

2、，产生语言L（G），则存在PDA M，以空栈接受语言L(M),使L(M)=L(G)。n 证明：证明：构造下推自动机M，使M按文法G的最左推导方式工作。3School of Computer Science,BUPT 构造方法构造方法 设设 CFG G=(N,T,P,S)，构造一个空栈接受构造一个空栈接受方式的方式的 PDA M（Q，T，q0，z0，F）其中其中 Qq,=NT,q0q，z0S,F(以空栈接受以空栈接受)即即 M=(q,T,N T,q,S,F),转移函数转移函数 定义如下：定义如下：(1)对每一对每一 A N,(q,A)=(q,)A”P;（即将栈顶的即将栈顶的A A换为换为）(2)

3、对每一对每一 a T,(q,a,a)=(q,).（即若栈顶为终结符，则退栈）即若栈顶为终结符，则退栈）从上下文无关文法构造等价的下推自动机从上下文无关文法构造等价的下推自动机4School of Computer Science,BUPTq，z z0 0S/S/若若SPSP，A/A/若若APAP a,a/a,a/a T,从上下文无关文法构造等价的下推自动机从上下文无关文法构造等价的下推自动机用图形表示：用图形表示：例例1 对右边产生式所代表对右边产生式所代表 CFG，依上述方法构造的依上述方法构造的 PDA 为为E EOE (E)v dO (q,v,d,+,(,),E,O,v,d,+,q,E,

4、),其中其中 定义为定义为 (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,),)=5School of Computer Science,BUPT自顶向下的分析过程自顶向下的分析过程定理的物理意义：定理的物理意义：利用下推自动机进行自顶向下的分析，利用下推自动机进行自顶向下的分析，检查一个句子的最左推导过程。检查一个句子的最左推导过程。步骤如下：步骤如下：(1)初始时，将文法开始符号压入空栈初始时，将文法开始符号压入空栈.(2)如果栈为空，则分析完成如

5、果栈为空，则分析完成.(3)如果栈顶为一非终结符，先将其从栈中弹出如果栈顶为一非终结符，先将其从栈中弹出.选择下选择下 一个相应于该非终结符的产生式，并将其右部一个相应于该非终结符的产生式，并将其右部 符号从符号从 右至左地一一入栈右至左地一一入栈.如果没有可选的产生式，则转出如果没有可选的产生式，则转出 错处理错处理.(4)如果栈顶为一终结符，那么这个符号必须与当前输入如果栈顶为一终结符，那么这个符号必须与当前输入 符号相同，将其弹出栈，读下一符号，转第符号相同，将其弹出栈，读下一符号，转第(2)步；否步；否 则，回溯到第则，回溯到第(3)步步.6School of Computer Sci

6、ence,BUPT例例2：利用下推自动机进行自顶向下的分析过程：利用下推自动机进行自顶向下的分析过程E EOE (E)v dO EEOEEOvEOE EE)(E)E)OEE)OvE)OE)E)d)v (v d )q，z z0 0E E/若若EPEP，O/O/*a,a/a a,a/a (,),v,d,+,(,),v,d,+,*，O/+O/+7School of Computer Science,BUPT定理的证明定理的证明 证明思路证明思路 欲证，对任何欲证，对任何 w T*,w L(G)w L(M).先证明如下结论先证明如下结论,if A w,then(q,w,A)*(q,).归纳于归纳于 A

7、 w 的步数的步数 n.基础基础 n=1，Aw 必为产生式，必为产生式，(q,w,A)(q,w,w)*(q,).归纳归纳 设第一步使用产生式设第一步使用产生式 AX1X2Xm，必有必有 w=w1w2wm，(q,w,A)(q,w,X1X2Xm)*(q,w2wm,X2Xm)*(q,w3wm,X3Xm)*(q,).所以所以:if S w,then(q,w,S)*(q,).即即,w L(G)w L(M).8School of Computer Science,BUPT定理的证明定理的证明 先证明如下结论先证明如下结论,if(q,w,A)*(q,),then A w.归纳于归纳于(q,w,A)*(q,)

8、的步数的步数 n.归纳归纳 n1，设第一步使用产生式设第一步使用产生式 AX1X2Xm，可以将可以将w 分为分为 w=w 1 w 2 w m，满足满足(q,wi ,Xi)*(q,)，所以所以:对任何对任何 w T*,if(q,w,S)*(q,),then S w.即即,w L(M)w L(G).因此因此，A X1X2Xm，w 1 w 2 w m=w 无论无论 Xi 为终结符，还是非终结符，都有为终结符，还是非终结符，都有 Xi w i.基础基础 n=1，必有必有 w=，且且 A 为为 G 的产生式，所以的产生式，所以 A w.9School of Computer Science,BUPT例：

9、构造一个例：构造一个PDA MPDA M，使使L(M)=L(G)(M)=L(G)。其中其中G G是我们常用来生是我们常用来生成算术表达式的文法：成算术表达式的文法：G G（N N，T T，P P，E E）N N E,T,F,T=+,E,T,F,T=+,*,(,),a,S=E,(,),a,S=E P:EE+TT;TT P:EE+TT;TT*FF;F(E)aFF;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

10、,+,*,(,),(,)例例3:从文法构造等价的下推自动机从文法构造等价的下推自动机10School of Computer Science,BUPT用格局说明句子分析过程用格局说明句子分析过程 例如例如 以以a+a*a a作为输入，则作为输入，则M M在所有可能移动中可作下列移在所有可能移动中可作下列移动（用到文法动（用到文法G G中从中从E E出发的最左派生的一系列规则）出发的最左派生的一系列规则）（q q，a aa a*a,Ea,E）(q(q，a aa a*a,E+T)a,E+T)(q (q，a aa a*a,T+T)a,T+T)(q (q，a aa a*a,F+T)a,F+T)(q (

11、q，a aa a*a,a+T)a,a+T)(q (q，a a*a,+T)a,+T)(q (q，a a*a,T)a,T)(q (q，a a*a,Ta,T*F)F)(q (q，a aa a*a,Fa,F*F)F)11School of Computer Science,BUPT从下推自动机构造等价的上下文无关文法从下推自动机构造等价的上下文无关文法 定理定理4.5.14.5.1是由是由G G导出导出PDAPDA，其逆定理也成立。其逆定理也成立。定理定理4.5.24.5.2（由（由PDAPDA导出文法导出文法G G）：）：设下推自动机设下推自动机M M，以空栈形式接受语言以空栈形式接受语言 L L(

12、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 在处理在处理时所做的一系列移动时所做的一系列移动。12School of Computer Science,BUPT从下推自动机构造等价的上下文无关文法从下推自动机构造等价的上下文无关文法采用形如采用形如 q q，z,z,的非终结符的非终结符,q q，QQ，zz

13、 q q，z,z,的物理意义：的物理意义：在在q q状态，栈顶为状态，栈顶为z z时，接受某个字符时，接受某个字符(可为可为)后将变换到后将变换到状态，并保证状态，并保证 q q，z,z,当且仅当（当且仅当（q,zq,z）*（,）.13School of Computer Science,BUPT从下推自动机构造等价的上下文无关文法从下推自动机构造等价的上下文无关文法 构造方法构造方法 设设 PDA MPDA M（Q Q，T T，q q0 0，z z0 0，）,构造构造CFG G G（N,T,P,SN,T,P,S）其中其中 N N q,z,q,Q q,z,q,Q，zSzS 产生式集合产生式集合

14、 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

15、2 qqk-1k-1,B,Bk k,q,qk k 的产生式加入到的产生式加入到P P中。其中，中。其中，a a T T 或或 a a=14School of Computer Science,BUPT由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,)例例:从下推自动机构造等价的上下文无关文法从下推自动机构造等价的上下文无关文法15School of Computer Science,B

16、UPT 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,q116School of Computer Science,BUPT q0 b,A/q1 a,z0/Az0 b,A/a,A/AA ,A/,z0/（3）对式（q0,a,z0）=(q0,Az0)，所有可能的状态序列为：q0q0，q1q0，q0q1

17、，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 17School of Computer Science,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,

18、A,q0 q0,A,q1 a q0,A,q0 q0,A,q1 q0,A,q1 a q0,A,q1 q1,A,q1 18School of Computer Science,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生成式出发，以避免生成无用生成式出发，以避免生成无用产生式。产生式。19School of Computer Science,BUPT定理的关键：定理的关键：当存在当存在

19、(q，a，z)含有（含有（，B1B2Bk）则对则对Q中中的每个可能的状态序列的每个可能的状态序列q1 q2 qk排成一条产生式排成一条产生式q,z,qka,B1,q1 q1,B2,q2qk-1,Bk,qk 这是一个猜测过程，实质是写出从这是一个猜测过程，实质是写出从q出发，栈顶为出发，栈顶为Z，经过一系列推导走到经过一系列推导走到qk的所有可能的状态序列，其的所有可能的状态序列，其中必有一条路径是正确的。中必有一条路径是正确的。20School of Computer Science,BUPTM（q，T，q，E，）定义为：定义为：(q,E,E)(q,E+T),(q,T)(q,T,T)(q,T*

20、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=+,E,T,F,T=+,*,(,),a,S=E,(,),a,S=E P:EE+TT;TT P:EE+TT;TT*FF;F(E)aFF;F(E)a练习：针对算术表达式的练习：针对算术表达式的PDA反向构造其等价文法反向构造其等价文法21School of Computer Science,BUPT练习练习:从从PDA构造等价的上下文无关文法构造等价的上下文无关文法对于

21、右下图的对于右下图的 PDA，构造构造CFG G=(N,0,1,P,S)，其中其中 N=S p,Y,q p,q q0,q1,q2 Y Z0,X Start0,Z0/XZ00,X/XXq2 q1 q0 Z0 ,/1,X/1,X/产生式集合产生式集合 P 定义如下：定义如下：(1)S q0,Z0,q0;S q0,Z0,q1;S q0,Z0,q2;(5)由由(q0,XZ0)(q0,0,Z0)得得 q0Z0qj 0q0Xqi qiZ0qj,i,j=0,1,2;(6)由由(q0,XX)(q0,0,X)得得 q0Xqj 0q0Xqi qiXqj,i,j=0,1,2;(2)由由(q1,)(q0,1,X)得得

22、 q0Xq1 1;(3)由由(q1,)(q1,1,X)得得 q1Xq1 1;(4)由由(q2,)(q1,Z0)得得 q1Z0q2 ;22School of Computer Science,BUPT练习练习:从从PDA构造等价的上下文无关文法构造等价的上下文无关文法（续前页）（续前页）消去所有非消去所有非生成符号，得到的新文法包含如下产生式：生成符号，得到的新文法包含如下产生式：S q0Z0q2;q0Z0q2 0q0Xq1 q1Z0q2 q0Xq1 0q0Xq1 q1Xq1 q0Xq1 1;q1Xq1 1;q1Z0q2 ;为简洁为简洁，记，记 q0Z0q2 为为A，q0Xq1 为为B，q1Xq1 为为C，q1Z0q2 为为D，上述文法的产生式改写如下：上述文法的产生式改写如下：S A;A 0BD;B 0BC;B 1;C 1;D ;