形式語言和自動機課件——上下文無關(guān)文法與下推自動機

1、1College of Computer Science & Technology, BUPT4.5 上下文無關(guān)文法與下推自動機上下文無關(guān)文法與下推自動機 上下文無關(guān)文法與下推自動機的等價性上下文無關(guān)文法與下推自動機的等價性:PDA與上下文無關(guān)文法之間存在著對應(yīng)關(guān)系。即：n PDA(M) CFGn CFG = PDA(M) PDA byfinal statePDA byemptystackGrammar2College of Computer Science & Technology, BUPT從上下文無關(guān)文法構(gòu)造等價的下推自動機從上下文無關(guān)文法構(gòu)造等價的下推自動機n 定理定理4.5.1（由（

2、由CFG可導(dǎo)出可導(dǎo)出PDA）： 設(shè)上下文無關(guān)文法G（N，T，P，S），產(chǎn)生語言L（G），則存在PDA M，以空棧接受語言L(M),使L(M)=L(G)。 n 證明：證明：構(gòu)造下推自動機M，使M按文法G的最左推導(dǎo)方式工作。 3College of Computer Science & Technology, BUPT 構(gòu)造方法構(gòu)造方法 設(shè)設(shè) CFG G = (N, T, P , S ) ，構(gòu)造一個空棧接受構(gòu)造一個空棧接受方式的方式的 PDA M（Q，T，q0，z0，F(xiàn)）其中其中 Qq, =NT, q0q，z0S, F (以空棧接受以空棧接受)即即 M = ( q , T, N T, , q, S

3、 , F) , 轉(zhuǎn)移函數(shù)轉(zhuǎn)移函數(shù) 定義如下：定義如下： (1) 對每一對每一 A N, (q, , A) = (q, ) A ” P ; （即將棧頂?shù)募磳ｍ數(shù)腁 A換為換為） (2) 對每一對每一 a T, (q, a, a) = (q, ) . （即若棧頂為終結(jié)符，則退棧）即若棧頂為終結(jié)符，則退棧） 從上下文無關(guān)文法構(gòu)造等價的下推自動機從上下文無關(guān)文法構(gòu)造等價的下推自動機4College of Computer Science & Technology, BUPTq，z0z0S/S/ 若若SPSP ，A/ A/ 若若APAP a,a/ a,a/ a T, 從上下文無關(guān)文法構(gòu)造等價的下推自動

4、機從上下文無關(guān)文法構(gòu)造等價的下推自動機用圖形表示：用圖形表示： 例例1 對右邊產(chǎn)生式所代表對右邊產(chǎn)生式所代表 CFG， 依上述方法構(gòu)造的依上述方法構(gòu)造的 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自頂向下的分析過程自頂向下的分析過程定理的物理意義：定理的物理意義：利用下推自動機進行自頂向下的分析，利用下推自動機進行自頂向下的分析， 檢查一個句子的最左推導(dǎo)過程。檢查一個句子的最左推導(dǎo)過程。 步驟如下：步驟如下： (1) 初始時，將文法開始符號壓入空棧初始時，將文法開始符號壓入空棧. (2) 如果棧為空，則分析完成如果棧為空，則分析完成. (3) 如果棧頂為一非終結(jié)符，先將其從棧中彈出如果棧頂為一非終結(jié)符，先將其從棧中彈出. 選擇下選擇下 一個相應(yīng)于該非終結(jié)符的產(chǎn)生式，并將其右部一個相應(yīng)于該非終結(jié)符的產(chǎn)生式，并

6、將其右部 符號從符號從 右至左地一一入棧右至左地一一入棧. 如果沒有可選的產(chǎn)生式，則轉(zhuǎn)出如果沒有可選的產(chǎn)生式，則轉(zhuǎn)出 錯處理錯處理. (4) 如果棧頂為一終結(jié)符，那么這個符號必須與當(dāng)前輸入如果棧頂為一終結(jié)符，那么這個符號必須與當(dāng)前輸入 符號相同，將其彈出棧，讀下一符號，轉(zhuǎn)第符號相同，將其彈出棧，讀下一符號，轉(zhuǎn)第(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). 先證明如下結(jié)論先證明如下結(jié)論, if A w, then (q,w,A)*(q, , ). 歸納于歸納于 A w 的步數(shù)的步數(shù) n. . 基礎(chǔ)基礎(chǔ) n=1，Aw 必為產(chǎn)生式，必為產(chǎn)生式，

8、 (q,w,A) (q,w,w) *(q, , ).歸納歸納 設(shè)第一步使用產(chǎn)生式設(shè)第一步使用產(chǎn)生式 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定理的證明定理的證明 先證明如下結(jié)論先證明如下結(jié)論, if (q, w,A)*(q, , ), the

9、n A w. 歸納于歸納于 (q, w,A)*(q, , ) 的步數(shù)的步數(shù) n. .歸納歸納 n1，設(shè)第一步使用產(chǎn)生式設(shè)第一步使用產(chǎn)生式 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 為終結(jié)符，還是非終結(jié)符，都有為終結(jié)符，還是非終結(jié)符，都有 Xi w i . 基礎(chǔ)基礎(chǔ) n=1，必有必有 w =

10、 ，且且 A 為為 G 的產(chǎn)生式，所以的產(chǎn)生式，所以 A w. 9College of Computer Science & Technology, BUPT例：構(gòu)造一個例：構(gòu)造一個PDA MPDA M，使使L(M)= L(G)(M)= L(G)。其中其中G G是我們常用來生是我們常用來生成算術(shù)表達式的文法：成算術(shù)表達式的文法：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解：構(gòu)造解：構(gòu)造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: 從文法構(gòu)造等價的下推自動機從文法構(gòu)造等價的下推自動機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從下推自動機構(gòu)造等價的上下文無關(guān)文法從下推自動機構(gòu)造等價的上下文無關(guān)文法 定理定理4.5.14.5.1是由是由G G導(dǎo)出導(dǎo)出PDAPDA，其逆定理也成立。其逆定理也成立。 定理定理4.5.24.5.2（由（由PDAPDA導(dǎo)出文法導(dǎo)出文法G G）：）：設(shè)下推自動機設(shè)下推自動機M M，以空棧形式接受語言以空棧形式接受語言 L L(M(M），），則存在一則存在一個上下文無關(guān)文法個上下文無關(guān)文法G G，產(chǎn)生語言產(chǎn)生語言L(G), L(G), 使使L(G)= LL(G

14、)= L(M(M） 。證明：設(shè)證明：設(shè)M M（ Q，T，q q0 0，z z0 0，） 思路：構(gòu)造文法思路：構(gòu)造文法G G，使使串在串在G G中的一個最左推導(dǎo)直接對應(yīng)于中的一個最左推導(dǎo)直接對應(yīng)于PDA M PDA M 在處理在處理時所做的一系列移動時所做的一系列移動 。12College of Computer Science & Technology, BUPT從下推自動機構(gòu)造等價的上下文無關(guān)文法從下推自動機構(gòu)造等價的上下文無關(guān)文法采用形如采用形如 q q，z,z,的非終結(jié)符的非終結(jié)符, , 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, 當(dāng)且僅當(dāng)（當(dāng)且僅當(dāng)（q,zq,z）* *（,）. .13College of Computer Science & Technology, BUPT從下推自動機構(gòu)造等價的上下文無關(guān)文法從下推自動機構(gòu)造等價的上下文無關(guān)文法 構(gòu)造方法構(gòu)造方法 設(shè)設(shè) PDA MPDA M（ Q Q，T T，q q0 0，z z0 0，） , , 構(gòu)造構(gòu)造CFG G G（N,T,P,SN,T,P,S） 其中其中 N N q,z,q,Q q,z,q,Q，zSzS 產(chǎn)生式集合產(chǎn)生式集合 P 定義如

16、下：定義如下： 對于每個對于每個qQqQ，將將SSq q0 0，z z0 0, q , q 加入到加入到產(chǎn)生產(chǎn)生式中。式中。 若若（q q，a a，z z）含有（含有（,），），則將則將 q,z,aq,z,a加入加入到到產(chǎn)生產(chǎn)生式中。式中。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 的產(chǎn)生式加入到的產(chǎn)生式加入到P P中。其中，中。其中，a a T T 或或 a a = = 14College of Computer Science & Technology, BUPT（書P169170）由PDA M構(gòu)造文法G設(shè)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: 從下推自動機構(gòu)造等價的上下文無關(guān)文法從下推自動機構(gòu)造等價

18、的上下文無關(guān)文法15College of Computer Science & Technology, BUPT q0 b, A/ q1 a, z0/Az0 b, A/ a, A/AA , A/ , z0/解：（1） q0,q1Q， 構(gòu)造 Sq0,z0,q0; Sq0,z0,q1 （2）對式，可構(gòu)造由（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可構(gòu)造出產(chǎn)生式： 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可構(gòu)造出產(chǎn)生式： 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及相應(yīng)產(chǎn)生式 重命名 q0,z0,

21、q1為A SA q1,A,q1為B AaCD q0,A,q1為C 得 Bb q1,z0,q1為D CaCBb D注注: : 構(gòu)造生成式時，可從構(gòu)造生成式時，可從S S生成式出發(fā)，以避免生成無用生成式出發(fā)，以避免生成無用產(chǎn)生式。產(chǎn)生式。19College of Computer Science & Technology, BUPT定理的關(guān)鍵：定理的關(guān)鍵： 當(dāng)存在當(dāng)存在(q，a，z)含有（含有（，B1B2Bk）則對則對Q中中的每個可能的狀態(tài)序列的每個可能的狀態(tài)序列q1 q2 qk排成一條產(chǎn)生式排成一條產(chǎn)生式q, z, qka, B1, q1 q1, B2,q2qk-1,Bk,qk 這是一個猜測過程

22、，實質(zhì)是寫出從這是一個猜測過程，實質(zhì)是寫出從q出發(fā)，棧頂為出發(fā)，棧頂為Z，經(jīng)過一系列推導(dǎo)走到經(jīng)過一系列推導(dǎo)走到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、,(,) 算術(shù)表達式的文法算術(shù)表達式的文法 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練習(xí)：針對算術(shù)表達式的練習(xí)：針對算術(shù)表達式的PDA反向構(gòu)造其等價文法反向構(gòu)造其等價文法21College of Computer Science & Technology, BUPT練習(xí)練習(xí): 從從PDA構(gòu)造等價的上下文無關(guān)文法構(gòu)造等價的上下文無關(guān)文法對于右下圖的對于右下圖的 PDA，構(gòu)造構(gòu)造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 / 產(chǎn)生式集合產(chǎn)生式集合 P 定義如下：定義如下： (1) S q0 , Z0 ,