【文章內(nèi)容簡介】 G產(chǎn)生。 證明 ：由定理 ，對一個不含有 ε 的 CFL L都可由 一個不含無用符號、無 ε 產(chǎn)生式、無單一產(chǎn)生式的 CFG G 產(chǎn)生。 不妨設(shè) CFG G =(Ｖ Ｎ ,Ｖ Ｔ ,Ｐ ,S)是一個不含無用符號、 無 ε 產(chǎn)生式、無單一產(chǎn)生式的 CFG, 且 L(G)=L。 P中產(chǎn)生式做如下處理： ⑴ 保留右側(cè)只有一個符號的產(chǎn)生式， (此符號是終極符， ) ⑵ 處理產(chǎn)生式 A?X1X2…Xn (n≥2)： 如果其中 Xi是終極符 a， 則引入新的變元 Ca， 用 Ca代替 a， 同時添加新的產(chǎn)生式 Ca?a 。 經(jīng)過此步處理后，使得產(chǎn)生式的形式只有兩種：一種是 A?a， a是終極符；另一種是 A?B1B2…Bn， 其中每個 Bi都 是變 元 (包括新引入的變元 )。 ⑶ 處理產(chǎn)生式 A?B1B2…Bn (n≥3) (因為 n=2時符合要求 )， 引進新的變元 D1D2…Dn2， 此產(chǎn)生式用下面產(chǎn)生式替換： A?B1D1 , D1? B2D2 , D2?B3D3 ,…, Dn3?Bn2Dn2 , Dn2?Bn1Bn 。 顯然用這 n－ 1個產(chǎn)生式代替 A?B1B2…Bn， 這是個等價變 換。經(jīng)過此步處理后，所有產(chǎn)生式的形式就具有 CNF形式 了 : A?BC,D?a,其中 A,B,C,D是變元， a是終極符。 CFG G’=(Ｖ Ｎ ’ ,Ｖ Ｔ ,Ｐ ’ ,S)， 其中Ｖ Ｎ ’ 中除 了原來Ｖ Ｎ 中的變元外，還含有新增加的所有變元。Ｐ ’ 就是由經(jīng)過上述處理后得到的具有 CNF形式的產(chǎn)生式構(gòu)成。 L(G’)=L(G), 這里證明從略。 【例 】 G是個定義算術(shù)表達式的 CFG G=({E,T,F},{a,b,+,*,(,)},P,E),其中 E表示算術(shù)表達式； T表 示項； F表示因子。 P含有下面這些產(chǎn)生式： E?E+T|T T?T*F|F F?(E)|a|b 求一個具有 CNF 形式的 CFG G’,使得 L(G’)=L(G)。 解 ： 1．先簡化 G， 因為 G中不含無用符號，也無 ε產(chǎn)生式， 所以只去掉單一產(chǎn)生式。 1） 去掉 T?F， 添加如下產(chǎn)生式： T?(E)|a|b 2） 去掉 E?T， 添加如下產(chǎn)生式： E?T*F|(E)|a|b 2． 保留符合要求的產(chǎn)生式 ： E?a|b, T?a|b, F?a|b 3．處理產(chǎn)生式 A?X1X2…Xn (n≥2)： 終極符 Xi變成變元。 E?E+T 變成 E?EC+T C+?+ E?T*F 變成 E?TC*F C*?* E?(E) 變成 E?C(EC) C(?( C) ?) T?T*F 變成 T?TC*F T?(E) 變成 T?C(EC) F?(E) 變成 F?C(EC) 4． 處理產(chǎn)生式 A?B1B2…Bn (Bi都是變元 ,n≥3)： 引進新 的變元 D1,D2, …,Dn2。 E?EC+T 變成 E?ED1 D1?C+T E?TC*F 變成 E?TD2 D2?C*F E?C(EC) 變成 E?C(D3 D3?EC) T?TC*F 變成 T?TD2 T?C(EC) 變成 T?C(D3 F?C(EC) 變成 F?C(D3 5．最后得具有 CNF形式的 CFG G’=(Ｖ Ｎ ’ ,Ｖ Ｔ ,P’,E), 其中Ｖ Ｎ ’ ＝ {E,T,F,C+,C*,C(,C),D1,D2,D3} Ｖ Ｔ ＝ {a,b,+,*,(,)} P’: E?ED1|TD2|C(D3|a|b T?TD2|C(D3|a|b F?C(D3|a|b D1?C+T D2?C*F D3?EC) C+?+ C*?* C(?( C)?) CFG 的 Greibach范式 (GNF) 下面我們討論 CFG的另外一種范式 ―― Greibach范式 (GNF)。 定義 ： CFG G=(Ｖ Ｎ ,Ｖ Ｔ ,Ｐ ,S)， P中產(chǎn)生式形式都是： A?aα， 其中 a是一個終極符， a∈ Ｖ Ｔ ， α是變元符號 串， α∈ Ｖ Ｎ *，則稱此文法具有 GNF形式。 任何一個不含有 ε 的 CFL， 都可以由一個具有 GNF形 式的 CFG產(chǎn)生。那么如何將一個 CFG變成具有 GNF形式 的 CFG， 應(yīng)用下面兩個引理 可以實現(xiàn)。 引理 34 .1 設(shè) G =(Ｖ Ｎ ,Ｖ Ｔ ,Ｐ ,S) 是個 CFG， A?α1Bα2 是 P中一個產(chǎn)生式，又 B?β1|β2|β3…|βm是 P中變元 B的 所有產(chǎn)生式。又令 G’ =(Ｖ Ｎ ,Ｖ Ｔ ,Ｐ ’ ,S)， 其中 P’構(gòu)成如 下：從 P中刪除 A?α1Bα2， 再添加產(chǎn)生式 A?α1β1α2|α1β2α2|α1β3α2|…|α1βmα2， 則 L(G’)=L(G)。 證明 ：顯然有 L(G’)?L(G)。 因為如果 A?α1βiα2(1≤i≤m)用在 G’的一個派生中，雖然在 G 中沒有此產(chǎn)生式，但是在 G中有如下派生： A?α1Bα2?α1βiα2(1≤i≤m)。 所以 G’中的任何派生 在 G中也可以實現(xiàn)。所以 L(G’)?L(G)。 再證明 L(G)?L(G’) 這里只需注意到 G與 G’的差別是：只有 A?α1Bα2是在 G中而不在 G’中的產(chǎn)生式，而 G中其余的產(chǎn)生式 G’中也 有。所以只要 A?α1Bα2用于 G的一個派生中，在其后 的某一步推導(dǎo)肯定用到產(chǎn)生式 B?βi， 用以改變變元 B， 而這二步推導(dǎo)在 G’中用一步派生 A?α1βiα2(1≤i≤m) 以代之。所以 L(G)?L(G’)。 最后得 L(G’)＝ L(G)。 下面介紹的引理是處理帶有左遞歸的產(chǎn)生式 。 這里所謂左遞歸的產(chǎn)生式形式： A?Aα, 顯然左遞歸不去掉，就無法變成 GNF形式。因為要求 產(chǎn)生式的右側(cè)第一個符號是終極符。當(dāng)然這不像上面引 理那么簡單。 應(yīng)用下面引理解決這個問題。 引理 設(shè) G =(Ｖ Ｎ ,Ｖ Ｔ ,Ｐ ,S) 是個 CFG， A?Aα1| Aα2|… |Aαm是 P中變元 A的所有帶有左遞歸的產(chǎn)生式。 又 A?β1|β2|β3|…|βn是 P中變元 A的其余的產(chǎn)生式。構(gòu) 造 CFG G’=(Ｖ Ｎ ∪ {Z},Ｖ Ｔ ,Ｐ ’ ,S)， 其中 P’構(gòu)成如下： 將 P中變元 A的產(chǎn)生式用下面產(chǎn)生式替換： A?βi|βi Z (1≤i≤n) Z?αj|αj Z (1≤j≤m) 則 L(G’)＝ L(G)。 證明 ：此引理的 處理思路 ， 就是用變元 Z的右遞歸代替變 元 A的左遞歸 。 任取 x∈ L(G),考慮 x的最左派生 ， A?βi型的產(chǎn)生式 ， 則 G’中也有這 種產(chǎn)生式 ， 所以 x的派生在 G’中也可以實現(xiàn) 。 A?Aαj ， 最后必用 A?βi， 才可以 消去變元 A， 例如有如下派生： A? Aαj1?Aαj2αj1 ? … ? Aαjkαjk1…αj2αj1 ?βiαjkαjk1…αj2αj1 A A A A A αj1 αj2 αjk βi A Z Z Z Z αj1 αj2 αjk βi 這個派生在 G’中也可以實現(xiàn)，如下所示： A?βi Z?βiαjk Z ? … ?βiαjkαjk1…αj 2 Z ?βiαjkαjk1…αj2αj1 所以 x∈ L(G’)。 反之 x∈ L(G’)， x在 G’中的派生 ， 類似可證在 G中也可 以實現(xiàn) ， 所以 x∈ L(G)。 最后得 L(G’)=L(G)。 定理 (Greibach定理 ) 每個不含有 ε的 CFL L， 都可 以由一個具有 GNF形式的 CFG產(chǎn)生。 證明 ：令 G =(Ｖ Ｎ ,Ｖ Ｔ ,Ｐ , A1) 是個 CFG， L(G)=L， ε?L(G)， 假設(shè) G已經(jīng)具有 CNF形式。不妨設(shè) Ｖ Ｎ ＝ {A1,A2,A3, …,An}， 按照如下方法處理 P中產(chǎn)生式： 1． 先暫時保留形如 Ai?AjAk的產(chǎn)生式，其中 ij 。 2． 用引理 Ai?AjAk的產(chǎn)生式，其中 ij， 即用所有 Aj產(chǎn)生式的右側(cè)符號串代替該產(chǎn)生式中的 Aj 。 3． 用引理 Ak?Akαj |βi ， (1≤j≤m) (1≤i≤n)， 用下面產(chǎn)生式替換： A?βi|βi Zk , Zk?αj|αj Zk 。 4． 經(jīng)過上述處理后， 再依次將 An,An1,…,A 2,A1產(chǎn)生式以 及所有新增加的變元 Zk (1≤ k≤ n)的產(chǎn)生式用引理 法處理，使之都變成 GNF形式。 由于我們對 G的產(chǎn)生式的處理都是使用上面兩個引理， 所以最后得到的具有 GNF形式的文法 G’必與 G等價，即 L(G’)=L(G)。 下面我們通過一個例子說明如何將 G變成具有 GNF形式 的文法 G’的過程。 【例 】 . 令 G=({A1,A2,A3},{a,b},P,A1)， 其中 P： ⑴ A1?A2A3, ⑵ A2?A3A1, ⑶ A2 ?b, ⑷ A3 ?A1A2, ⑸ A3 ?a, 將 G寫成 GNF形式。 解： 1. 先暫時保留產(chǎn)生式 ⑴ 、 ⑵ 。 2． 處理產(chǎn)生式 ⑷ A3 ?A1A2： 用 ⑴ 的 A1產(chǎn)生式右側(cè)的 A2A3替換 ⑷ 中 A1， 得新產(chǎn)生式 ⑹ A3 ?A2A3A2。 ⑹ 仍然不 滿足要求，再次對 ⑹ 處理：用 ⑵⑶ 的 A2產(chǎn)生式右側(cè)符號 串分別替換 A2， 得 ⑺ A3 ?A3A1A3A2, ⑻ A3 ?bA3A2。 這 兩個產(chǎn)生式符合要求。 ⑺ A3 ?A3A1A3A2, ⑻ A3 ?bA3A2， ⑸ A3 ?a。 用引理 ： A3 ?bA3A2|a|bA3A2Z3|aZ3 , Z3?A1A3A2| A1A3A2Z3 。 可以看出，到此所有 A3的產(chǎn)生式都已經(jīng)符合 GNF形式了。 4． 用引理 將 A A1產(chǎn)生式變成 GNF 形式。 對 ⑵ A2?A3A1, ⑶ A2 ?b, 應(yīng)用所有 A3產(chǎn)生式的右側(cè)符號串 替換 A3得： A2?bA3A2A1|aA1|bA3A2Z3A1|aZ3A1|b, 到此 A2已經(jīng)滿足 GNF形式了。 對 ⑴ A1?A2A3, 應(yīng)用所有 A2產(chǎn)生式的右側(cè)符號串替換 A2得： A1?bA3A2A1A3|aA1A3|bA3A2Z3A1A3|aZ3A1A3|bA3 到此 A1已經(jīng)滿足 GNF形式了。 5． 將所有 Z3產(chǎn)生式變成 GNF形式，用所有 A1產(chǎn)生式得： Z3?A1A3A2 變成 Z3?bA3A2A1A3A3A2|aA1A3A3A2|bA3A2Z3A1A3A3A2 |aZ3A1A3A3A2|bA3A3A2 Z3?A1A3A2Z3 變成 Z3?bA3A2A1A3A3A2Z3|aA1A3A3A2Z3 |bA3A2Z3A1A3A3A2Z3|aZ3A1A3A3A2 Z3|bA3A3A2Z3 最后得文法 G’=({A1,A2,A3,Z3},{a,b},P’,A1)， 其中 P’： A1?bA3A2A1A3|aA1A3|bA3A2Z3A1A3|aZ3A1A3|bA3 A2?bA3A2A1|aA1|bA3A2Z3A1|aZ3A1|b A3 ?bA3A2|a|bA3A2Z3|aZ3 Z3?bA3A2A1A3A3A2|aA1A3A3A2|bA3A2Z3A1A3A3A2 |aZ3A1A3A3A2|bA3A3A2 Z3?bA3A2A1A3A3A2Z3|aA1A3A3A2Z3 |bA3A2Z3A1A3A3A2Z3|aZ3A1A3A3A2 Z3|bA3A3A2Z3 可見 G’具有 GNF形式。 隨便說明一下，上邊定理中介紹的方法是個將具有 CNF 形式的文法變成 GNF形式的一般的方法，有時不一定嚴 格按照此法去做，即不一定都得先將給定 CFG G變成 CNF形式后，再寫成 GNF形式。 【 例 】 將下面 CFG G寫成 GNF形式。 G=({S},{0,1},P,S)， 其中 P： S?0S0|1S1|00|11。 解： 因為此文法所有產(chǎn)生式的右側(cè)的第一個符號已經(jīng)是 終極符，所以問題就簡單了，就不必先將 G變成 CNF形 式，可以直接寫成 GNF形式。令 G’=({S,A,B},{0,1},P’,S)， P’： S?0SA|1SB|0A