形式語言自動機-上下文無關(guān)文法與下推自動機(一)

1、第四章 上下文無關(guān)文法與下推自動機 推導樹和文法的 二義性上下文無關(guān)文法的變換 ChomskyGreibach 下推自動機上下文無關(guān)語言的性質(zhì)1本章要點上下文無關(guān)文法（即2型文法）： 產(chǎn)生式形如 A, A, )* 所描述的語言稱為上下文無關(guān)語言。用途：可定義程序設(shè)計語言、進行語法分析、簡化語言翻譯 2型文法對應的識別器下推自動機 PDA（Push Down Automata)由輸入帶、有限控制器和下推棧構(gòu)成（書P152 圖）2 回顧：在第一講中介紹過如下內(nèi)容 設(shè) T= 0, 1 ， L = 0n1n n 1，如 0011, 000111, 01 L, 而10, 1001 , , 010 L .

2、 如下是一個可接受該語言的上下文無關(guān)文法 S 01 S 0S1 但沒有任何有限自動機能夠接受語言L.3歸約與推導的概念: 推理字符串是否屬于文法所定義的語言 一種是自下而上的方法，稱為遞歸推理(recursive inference），遞歸推理的過程習稱為歸約； 一種是自上而下的方法，稱為推導（derivation）.歸約過程 將產(chǎn)生式的右部（body）替換為產(chǎn)生式的左部（ head ）. 推導過程 將產(chǎn)生式的左部（ head ）替換為產(chǎn)生式的右部（ body ）.4.1 推導樹和二義性 4歸約與推導 歸約過程舉例 對于CFG Gexp = (E,O, (, ), , v, d , P , E

3、 ) ，P 為 （1）E EOE （2） E (E) （3） E v （4） E d （5） O （6） O 遞歸推理出字符串 v (vd) 的一個歸約過程為v (vd)（4）v (vE)（6）vO(vE)（3）vO(EE)（5）vO(EOE)（1）vO(E)（2）vOE（3）EOE（1）E5歸約與推導 推導過程舉例 對于CFG Gexp = (E,O, (, ), , v, d , P , E ) ，P 為 （1）E EOE （2） E (E) （3） E v （4） E d （5） O （6） O 從開始符號到字符串 v (vd) 的一個推導過程為v (vd)（4）v (vE)（6）E (

4、E)（3）（1）v (EOE)（5）（3）EOE（1）EE E（2）v (E)v (EE)6歸約與推導E EOEE (E)E vE dO O 最左推導(leftmost derivations) 若推導過程的每一步總是替換出現(xiàn)在最左邊的非終結(jié)符， 則這樣的推導稱為最左推導. 為方便，最左推導關(guān)系用 表示，其傳遞閉包用表示. 如對于文法Gexp ，下面是關(guān)于 v (vd) 的一個最左推導：lmlmv (vd)v (vE)v (EOE)EOEEv (E)vOEv Ev (vOE)lmlmlmlmlmlmlmlm7歸約與推導E EOEE (E)E vE dO O 最右推導(rightmost der

5、ivations) 若推導過程的每一步總是替換出現(xiàn)在最右邊的非終結(jié)符， 則這樣的推導稱為最右推導. 為方便，最右推導關(guān)系用 表示，其傳遞閉包用表示. 如對于文法Gexp ，下面是關(guān)于 v (vd) 的一個最右推導：rmrmv (vd)E (vd)EO(Ed)EOEEEO(EOd)EO(E)EO(EOE)EO(vd)rmrmrmrmrmrmrmrm8推導樹用圖的方法表示一個句型的推導，這種圖稱為推導樹（也稱語法樹或語法分析樹）。有助于理解語法結(jié)構(gòu)的層次。定義方法：文法的起始符為根，樹的枝結(jié)點標記是非終結(jié)符，葉結(jié)點標記為終結(jié)符或。若枝結(jié)點有直接子孫x1, x2, xk，則文法中有生成式Ax1 x2

6、xk9 推導樹舉例例：（書P124 例1）文法SS+S | S*S |(S)| a ，對句子 (a*a+a) 可有推導樹即：推導樹是對文法G中一個特定句子形式的派生過程所做的一種自然描述。 10邊緣葉子從左向右組成的字符串稱為推導樹的邊緣。如圖x1 y1 y2 x3 xm xm+1 xn-1 y3 y4 y5是樹的邊緣11(1) E EOE(2) E (E)(3) E v(4) E d(5) O (6) O 歸約過程自下而上構(gòu)造了一棵樹 如對于文法Gexp ，關(guān)于 v (vd) 的一個歸約過程可以認為是構(gòu)造了如下一棵樹：v (vd)（4）v (vE)（6）vO(vE)（3）vO(EE)（5）v

7、O(EOE)（1）vO(E)（2）vOE（3）EOE（1）EEEOEEOEEdv()v12(1) E EOE(2) E (E)(3) E v(4) E d(5) O (6) O 推導過程自上而下構(gòu)造了一棵樹 如對于文法Gexp ，關(guān)于 v (vd) 的一個推導過程可以認為是構(gòu)造了如下一棵樹：EdvvOEEE()EEOv (vd)（4）v (vE)（6）E (E)（3）（1）v (EOE)（5）（3）EOE（1）EE E（2）v (E)v (EE)13歸約、推導與分析樹之間關(guān)系 三者之間的關(guān)系 設(shè) CFG G = (V, T, P , S ). 以下命題是相互等價的： (1) 字符串 wT* 可

8、以歸約（遞歸推理）到非終結(jié)符A； (2) A w； (3) A w； (4) A w； (5) 存在一棵根結(jié)點為 A 的分析樹，其邊緣為 w.lmrm14定理：設(shè)2型文法G=（N，T，P，S），如果存在S=+ ，當且僅當文法G中有一棵邊緣為的推導樹。證明：需證明對任意枝結(jié)點BN，有B=* 當且僅當存在邊緣為的B樹（根為B的樹）子樹概念：一棵派生樹的子樹，是樹中的某個頂點連同它的全部后裔，以及連接這些后裔的邊。歸約、推導與分析樹之間關(guān)系15證明步驟：1. 證當是B樹邊緣時，有B =* 設(shè)B樹邊緣為，對樹中枝結(jié)點數(shù)目m作歸納證明。2. 設(shè)有B =* ，證明存在一棵邊緣為的B樹。對推導步數(shù)作歸納 1

9、61. 證當是B樹邊緣時，有B =* 設(shè)B樹邊緣為，對樹中枝結(jié)點數(shù)目m作歸納證明。wAX1X2X3w1w2w3A基礎(chǔ) m為 1. 分析樹一定如 右圖所示，必定有產(chǎn)生 式A w. 因此， A w.歸納 m大于 1 的分析樹一定 如右圖所示，必定有產(chǎn) 生式 A X1X2Xk . 存在 w1,w2,wk，wi 是Xi子樹 的邊緣（1i k），且 w = w1w2wk， 由歸納 假設(shè)， Xi wi（1i k）. 在此基礎(chǔ)上易證得A w.172. 設(shè)有B =* ，證明存在一棵邊緣為的B樹。對推導步數(shù)作歸納 基礎(chǔ) 步數(shù)為 1. 一定有產(chǎn)生式 A w . w 可以歸約到 A.歸納 設(shè)步數(shù)大于 1，第一步使用

10、了產(chǎn)生式A X1X2Xk . 該推導如 A X1X2Xk w . 可以將 w 分成 w = w1w2wk，其中 (a) 若 Xi 為終結(jié)符，則 wi = Xi. (b) 若 Xi 為非終結(jié)符，則 Xi wi. 由歸納假設(shè)， wi 可以歸約到 Xi . 這樣，wi 或者為Xi，或者可以歸約到 Xi ，使用產(chǎn)生 式A X1X2Xk ，得出w 可以歸約到 A. 18定義: 2型文法是二義的,當且僅當對于句子L(G),存在兩棵不同的具有邊緣為的推導樹。 (即：如果文法是二義的, 那么它所產(chǎn)生的某個句子必然能從不同的最左(右)推導推出)。例: (書P124 例1)句子(a*a+a)有二棵不同的推導樹. (相當于一