形式語言和自動機課件——上下文無關文法與下推自動機

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(xiàn)）其中其中 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出發(fā)的最左派生的一系列規(guī)則）出發(fā)的最左派生的一系列規(guī)則） （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狀態(tài)，棧頂為狀態(tài)，棧頂為z z

15、時，接受某個字符時，接受某個字符( (可為可為)后后PDAPDA將變換將變換到到狀態(tài)，并保證狀態(tài)，并保證 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中的中的每一個狀態(tài)序列每一個狀態(tài)序列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) ，所有可能的狀態(tài)序列為：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) ，所有可能的狀態(tài)序列為：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生成式出發(fā)，以避免生成無用生成式出發(fā)，以避免生成無用產生式。產生式。19College of Computer Science & Technology, BUPT定理的關鍵：定理的關鍵： 當存在當存在(q，a，z)含有（含有（，B1B2Bk）則對則對Q中中的每個可能的狀態(tài)序列的每個可能的狀態(tài)序列q1 q2 qk排成一條產生式排成一條產生式q, z, qka, B1, q1 q1, B2,q2qk-1,Bk,qk 這是一個猜測過程

22、，實質是寫出從這是一個猜測過程，實質是寫出從q出發(fā)，棧頂為出發(fā)，棧頂為Z，經過一系列推導走到經過一系列推導走到qk的所有可能的狀態(tài)序列，其的所有可能的狀態(tài)序列，其中必有一條路徑是正確的。中必有一條路徑是正確的。 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 ,