編譯原理：第二章形式語言基礎(chǔ)(3)

1、編譯程序的設(shè)計(jì)原理與實(shí)現(xiàn)如何讓計(jì)算機(jī)認(rèn)識(shí)、理解 和 執(zhí)行 高級(jí)程序設(shè)計(jì)語言 ？【內(nèi)容提要】第 2 章 形式語言基礎(chǔ) (3) 2.1 形式語言是字符串集合 2.2 形式語言是由文法定義的 2.3 主要語法成分的定義 2.4 兩類特性文法 2.5 文法變換方法 2.6 關(guān)于形式語言的分類問題 上節(jié)課主要內(nèi)容回顧： 文法的運(yùn)算：推導(dǎo)和歸約(二者互為逆運(yùn)算) 推導(dǎo) ： 歸約 ： 文法的運(yùn)算與主要語法成分的定義！ 主要語法成分的定義 = + =+ = . = .+ =.+ 句型，句子，語法樹，短語，簡(jiǎn)單短語，句柄從語法樹上看 句型(句子)、短語、簡(jiǎn)單短語和句柄： 直接推導(dǎo)( = ),加推導(dǎo)( ), 最左

2、推導(dǎo)( );直接歸約( ),加歸約( ), 最左歸約( ); 語法樹的樹葉全體-句型(句子)； 語法樹的子樹樹葉全體短語(簡(jiǎn)單短語)； 語法樹的最左簡(jiǎn)單子樹樹葉全體 句柄！G2(S): S - b S | a - 直接右遞歸文法。3 兩種特性文法1 遞歸文法 設(shè)有文法：G(Z)=(VN,VT,Z,P)【定義】 設(shè) AVN，x, y(VN+VT)*，則; 若 A xAy，：稱文法具有遞歸性; = +特別： 若 A - A ，稱文法具有直接左遞歸性； A - A ，稱文法具有直接右遞歸性。 遞歸文法是定義無限語言的工具（遞歸文法定義的語言有無限個(gè)句子）！如：G1(S): S - S b | a -

3、 直接左遞歸文法； 4 兩種特性文法2 二義性文法【定義】 若文法中存在這樣的句型，它具有兩棵不同的語法樹，則稱該文法是二義性文法?！纠?.14】 算術(shù)表達(dá)式的另一種文法： 句型 i+i*i 有兩棵不同的語法樹(右圖)： G(E) 是二義性文法。G(E)：E - E+E|E-E|E*E|E/E|(E)|i ;其中：i(變量或常數(shù)) E E E + E E * E i E * E E + E i i i i i 二義性文法會(huì)引起歧義，應(yīng)盡量避免之！2.5.1 文法的等價(jià)性 2.5 文法的等價(jià)變換即：文法的等價(jià)性是指他們所定義的語言是一樣的。【定義】 設(shè)G1、G2是兩個(gè)文法，若L(G1)=L(G2

4、)，則稱G1與G2等價(jià)，記作G1G2?！纠?.15】：G1：S - aS|a； G2：S - Sa|a L(G1)=a, aa, aaa, =an | n1 L(G2)=a, aa, aaa, =an | n1 L(G1)=L(G2) 即 G1G2 【注】一個(gè)語言，其描述文法并不唯一。2.5.2 文法變換方法 在實(shí)際工作中，人們總是希望定義一種語言的文法盡可能地簡(jiǎn)單。另外，某些常用的語法分析技術(shù)也會(huì)對(duì)文法提出一定的要求或限制；為了適應(yīng)上述要求，有時(shí)需要對(duì)文法進(jìn)行必要的改寫。當(dāng)然改寫后的文法要與原文法等價(jià)通常稱為文法變換。 這里重點(diǎn)介紹三類變換： 常用的三種文法變換方法： 刪除產(chǎn)生式；必選項(xiàng)法；

5、 可選項(xiàng)法； 重復(fù)可選項(xiàng)法。 刪除無用的產(chǎn)生式（文法的化簡(jiǎn)）； 文法化簡(jiǎn)是指消除如下無用產(chǎn)生式： 刪除 A-A 形式的產(chǎn)生式(自定己)； 刪除不能從其推導(dǎo)出終結(jié)符串的產(chǎn)生式(不終結(jié))； 刪除在推導(dǎo)中永不使用的產(chǎn)生式(不可用)。 2.5.2 文法變換方法1. 文法的化簡(jiǎn) 第步算法(刪除不終結(jié)產(chǎn)生式)： 構(gòu)造能推導(dǎo)出終結(jié)符串的非終結(jié)符集 VVT: 若有 A- 且 VT* ;則令 AVVT ； 若有 B- 且 (VT+ VVT)* ;則令 BVVT ; 重復(fù)步驟，直到VVT不再擴(kuò)大為止。 刪除不在VVT中的所有非終結(jié)符(連同其產(chǎn)生式)。2.5.2 文法變換方法1(續(xù)1) 第步算法(刪除不可用產(chǎn)生式)

6、： 構(gòu)造可用的非終結(jié)符集 VUS: 首先令 ZVUS ; (Z 為文法開始符號(hào)) = + 刪除不在VUS中的所有非終結(jié)符(連同其產(chǎn)生式)?！纠?.16】化簡(jiǎn)下述文法： G(S): S - Be | Ec A - Ae | e | A B - C e | AfC - Cf ; D - f ; G - b 若有 Z A ，則 令 AVUS ; 重復(fù)步驟，直到VUS不再擴(kuò)大為止。 = + 文法化簡(jiǎn)示例：化簡(jiǎn)步驟：G(S): S - Be | Ec A - Ae | e | A B - C e | AfC - Cf ; D - f ; G - b 刪除 A - A ; 刪除不終結(jié)產(chǎn)生式: VVT= A

7、,D,G,B,S ; 應(yīng)刪除 C,E(連同其產(chǎn)生式)得：G(S): S - Be ; A - Ae | e ; B - Af ;D - f ; G - b ; 刪除不可用產(chǎn)生式: VUS= S,B,A ; 應(yīng)刪除 D,G(連同其產(chǎn)生式) 整理后得：G(S):A - Ae | eB - AfS - Be2.5.2 文法變換方法2 刪除 產(chǎn)生式【算法】 首先構(gòu)造可以推出空串的非終結(jié)符集：V 若有 A-; 則 令 AV ; 若有 B-A1 An 且全部 AiV ;則令 BV ; 重復(fù)步驟，直到V不再擴(kuò)大為止。 刪除 G(Z)中的 A - 形式的產(chǎn)生式；假定 文法 G(Z) ; L(G) 依次改寫G(

8、Z)中的產(chǎn)生式 A - X1 X2 Xn :若有 Xi V 則用 (Xi|) 替換之(一個(gè)分裂為兩個(gè))； 若有 j 個(gè) Xi V ，則一個(gè)產(chǎn)生式將分裂為2j個(gè)!【例2.17】G(S): S-aAbc|bS A-dABe| ; B-A|b 刪除 產(chǎn)生式示例： 求解 V = A,B 刪除 產(chǎn)生式 得：S-aAbc|bS ；A-dABe ； B-A|b 改寫 含有 V 中元素的產(chǎn)生式： S-a(A|)bc S-aAbc|abc A-d(A|)(B|)e A-dABe|dBe|dAe|de B-(A|) B-A含有V元素的產(chǎn)生式 綜合 G(S) ：S-aAbc|abc|bSA-dABe|dBe|dAe

9、|deB-A|b令 （|）= 或者 可變換成: A - a(|) 2.5.2 文法變換方法3 必選項(xiàng)法（園括號(hào)法） 常用的三種文法變換方法： 基本思想：擴(kuò)展文法，引進(jìn)新的描述符號(hào)： （）圓括號(hào)； 方括號(hào)；花括號(hào)。必選其中之一！例如：有 A - a|a 也可： A - aA ； A - |【注】此法有稱提公因子法，利用此法可以使文法： 具有相同左部的各產(chǎn)生式首符號(hào)不同！ 也可： S - S ; S - |令 = 或者 2.5.2 文法變換方法3(續(xù)1) 可選項(xiàng)法（方括號(hào)法） 常用的三種文法變換方法： 例如： S - | 可選也可不選！例如 條件語句文法： S - if (B) S 可變換成： S

10、 - S - if (B) S else S可變換成：S - if (B) S else SS(語句)，B(布爾表達(dá)式)或：S - if (B) S S ; S- else S|2.5.2 文法變換方法3(續(xù)2) 重復(fù)可選項(xiàng)法（花括號(hào)法） 常用的三種文法變換方法： 例如： A - A| 令 = 或 或 或 可變換為： A - 通過遞推方法，可得： A= A= A= A= * 有 A - ；或 A A ; A -A| ； 也可： A A ; A -A| 驗(yàn)證：【注】此方法常用來消除文法的直接左遞歸！ 產(chǎn)生式形式為：xAy -xy 產(chǎn)生式形式為：A-aB , A-a , A- 產(chǎn)生式形式為：A -

11、 2.6 形式語言的分類 chomsky 把形式語言分為四類，分別由四類文法定義；四類文法的區(qū)別在于產(chǎn)生式的形式不同： 2 型語言 由 2型文法定義 1 型語言 由 1型文法定義 0 型語言 由 0型文法定義 產(chǎn)生式形式為： - 3 型語言 由 3型文法定義又稱 無限制文法！又稱 上下文有關(guān)文法！又稱 上下文無關(guān)文法！又稱 正規(guī)文法！【注】 四類語言為 包含關(guān)系，且有 L0 L1 L2 L3；編譯處理中，主要應(yīng)用后兩種文法！ 練習(xí)題：【習(xí)題2.8】 解釋下列詞語： 遞歸文法， 二義性文法， 等價(jià)文法 ；【習(xí)題2.9】 指出下述文法的文法類屬： G1(S): S-aAbB | Bc | G2(S): S-aS|bA|c| 【習(xí)題2.10】 化簡(jiǎn)下述文法： G(S): S-aSab|bAB ; A-bB|a ; B-aA|b C-abB|baA ; D-Cbc|abc ;【習(xí)題2.11】刪除下述文法的 產(chǎn)生式： G(S): S-aBS|b ; B-cS| 【習(xí)題2.12】消除下述文法的直接左遞歸： G(S): E-E+T|E-T|T ET | E + T | E - TTF | T * F | T / FFi | ( E )P:基本圖形庫 =.+ =+A = .+ = +=*, =+ , =.*