形式语言和自动机课件——上下文无关文法与下推自动机

1、1College of Computer Science & Technology, BUPT4.5 上下文无关文法与下推自动机上下文无关文法与下推自动机 上下文无关文法与下推自动机的等价性上下文无关文法与下推自动机的等价性:PDA与上下文无关文法之间存在着对应关系。即：n PDA(M) CFGn CFG = PDA(M) PDA byfinal statePDA byemptystackGrammar2College of Computer Science & Technology, BUPT从上下文无关文法构造等价的下推自动机从上下文无关文法构造等价的下推自动机n 定理定理4.5.1（由（

2、由CFG可导出可导出PDA）： 设上下文无关文法G（N，T，P，S），产生语言L（G），则存在PDA M，以空栈接受语言L(M),使L(M)=L(G)。 n 证明：证明：构造下推自动机M，使M按文法G的最左推导方式工作。 3College of Computer Science & Technology, 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

3、 , F) , 转移函数转移函数 定义如下：定义如下： (1) 对每一对每一 A N, (q, , A) = (q, ) A ” P ; （即将栈顶的即将栈顶的A A换为换为） (2) 对每一对每一 a T, (q, a, a) = (q, ) . （即若栈顶为终结符，则退栈）即若栈顶为终结符，则退栈） 从上下文无关文法构造等价的下推自动机从上下文无关文法构造等价的下推自动机4College of Computer Science & Technology, BUPTq，z0z0S/S/ 若若SPSP ，A/ A/ 若若APAP a,a/ a,a/ a T, 从上下文无关文法构造等价的下推自动

4、机从上下文无关文法构造等价的下推自动机用图形表示：用图形表示： 例例1 对右边产生式所代表对右边产生式所代表 CFG， 依上述方法构造的依上述方法构造的 PDA 为为E EOE (E) v dO ( 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,),) )= 5Colleg

5、e of Computer Science & Technology, BUPT自顶向下的分析过程自顶向下的分析过程定理的物理意义：定理的物理意义：利用下推自动机进行自顶向下的分析，利用下推自动机进行自顶向下的分析， 检查一个句子的最左推导过程。检查一个句子的最左推导过程。 步骤如下：步骤如下： (1) 初始时，将文法开始符号压入空栈初始时，将文法开始符号压入空栈. (2) 如果栈为空，则分析完成如果栈为空，则分析完成. (3) 如果栈顶为一非终结符，先将其从栈中弹出如果栈顶为一非终结符，先将其从栈中弹出. 选择下选择下 一个相应于该非终结符的产生式，并将其右部一个相应于该非终结符的产生式，并

6、将其右部 符号从符号从 右至左地一一入栈右至左地一一入栈. 如果没有可选的产生式，则转出如果没有可选的产生式，则转出 错处理错处理. (4) 如果栈顶为一终结符，那么这个符号必须与当前输入如果栈顶为一终结符，那么这个符号必须与当前输入 符号相同，将其弹出栈，读下一符号，转第符号相同，将其弹出栈，读下一符号，转第(2)步；否步；否 则，回溯到第则，回溯到第(3)步步.6College of Computer Science & Technology, BUPT例例2：利用下推自动机进行自顶向下的分析过程：利用下推自动机进行自顶向下的分析过程E EOE (E) v dO EEOEEOvEOE EE

7、)(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/+7College 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，Aw 必为产生式，必为产生式，

8、 (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). 8College of Computer Science & Technology, BUPT定理的证明定理的证明 先证明如下结论先证明如下结论, if (q, w,A)*(q, , ), the

9、n A w. 归纳于归纳于 (q, w,A)*(q, , ) 的步数的步数 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 =

10、 ，且且 A 为为 G 的产生式，所以的产生式，所以 A w. 9College of Computer Science & Technology, BUPT例：构造一个例：构造一个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(

11、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: 从文法构造等价的下推自动机从文法构造等价的下推自动机10College of Computer Science & Technology, BUPT用格局说明句子分析过程用格局说明句子分析过程 例如例如 以以a+a* *a a作为输入，则作为输入，则M M在所有可

12、能移动中可作下列移在所有可能移动中可作下列移动（用到文法动（用到文法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 (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

13、 a* *a, Fa, F* *F)F) 11College 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

14、)= L(M(M） 。证明：设证明：设M M（ Q，T，q q0 0，z z0 0，） 思路：构造文法思路：构造文法G G，使使串在串在G G中的一个最左推导直接对应于中的一个最左推导直接对应于PDA M PDA M 在处理在处理时所做的一系列移动时所做的一系列移动 。12College of Computer Science & Technology, BUPT从下推自动机构造等价的上下文无关文法从下推自动机构造等价的上下文无关文法采用形如采用形如 q q，z,z,的非终结符的非终结符, , q q，QQ，zz q q，z,z,的物理意义：的物理意义：在在q q状态，栈顶为状态，栈顶为z z

15、时，接受某个字符时，接受某个字符( (可为可为)后后PDAPDA将变换将变换到到状态，并保证状态，并保证 q q，z, z, 当且仅当（当且仅当（q,zq,z）* *（,）. .13College of Computer Science & Technology, 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 产生式集合产生式集合 P 定义如

16、下：定义如下： 对于每个对于每个qQqQ，将将SSq q0 0，z z0 0, q , q 加入到加入到产生产生式中。式中。 若若（q q，a a，z z）含有（含有（,），），则将则将 q,z,aq,z,a加入加入到到产生产生式中。式中。1)1) 若若（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 2qqk

17、-1k-1,B,Bk k,q,qk k 的产生式加入到的产生式加入到P P中。其中，中。其中，a a T T 或或 a a = = 14College 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: 从下推自动机构造等价的上下文无关文法从下推自动机构造等价

18、的上下文无关文法15College 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,q116College of Computer Science & Technology, BUPT

19、 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 17College of Computer Science & Technology, BUPT q0 b, A/ q1 a,

20、 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 18College of Computer Science & Technology, BUPT(4)删除无用符号 q0,A,q1 和 q1,z0,q0及相应产生式 重命名 q0,z0,

21、q1为A SA q1,A,q1为B AaCD q0,A,q1为C 得 Bb q1,z0,q1为D CaCBb D注注: : 构造生成式时，可从构造生成式时，可从S S生成式出发，以避免生成无用生成式出发，以避免生成无用产生式。产生式。19College of Computer Science & Technology, BUPT定理的关键：定理的关键： 当存在当存在(q，a，z)含有（含有（，B1B2Bk）则对则对Q中中的每个可能的状态序列的每个可能的状态序列q1 q2 qk排成一条产生式排成一条产生式q, z, qka, B1, q1 q1, B2,q2qk-1,Bk,qk 这是一个猜测过程

22、，实质是写出从这是一个猜测过程，实质是写出从q出发，栈顶为出发，栈顶为Z，经过一系列推导走到经过一系列推导走到qk的所有可能的状态序列，其的所有可能的状态序列，其中必有一条路径是正确的。中必有一条路径是正确的。 20College 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,+,* *,(,)

23、,(,) 算术表达式的文法算术表达式的文法 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反向构造其等价文法反向构造其等价文法21College 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 Start0, Z0 / XZ00, X / XXq2 q1 q0 Z0 , /1, X / 1, X / 产生式集合产生式集合 P 定义如下：定义如下： (1) S q0 , Z0 ,