【文章內(nèi)容簡介】 例 ?設(shè) G=(VN， VT， P， S)， VN={S,B,E}，VT={a,b,e}， P由下列產(chǎn)生式組成： ? (1) S→aSBE (2) S→aBE (3) EB→BE ? (4) aB→ab (5) bB→bb (6) bE→be ? (7) eE→ee ?則 L（ G） ={ anbnen | n≥ 1 } 29 文法的等價 ?若 L（ G1） =L（ G2），則稱文法 G1和 G2是等價的。 ?示例：文法 G1[A]： A→0R A→01 R→A1 與G2[S]： S→0S1 S→01 等價。 30 文法的類型 ?喬姆斯基分類 ?示例： ? 例 ? 例 ?喬姆斯基分類文法之間關(guān)系 ?對應(yīng)于喬姆斯基分類文法的語言 ?文法和語言之間的關(guān)系 31 喬姆斯基對文法的分類 ?通過對產(chǎn)生式施加不同的限制， Chomsky（喬姆斯基）將文法分為四種類型： ? 0型文法：對文法 G=(VN， VT， P， S)的任一產(chǎn)生式 α → β ，都有α ∈(V N∪V T)*且至少含有一個非終結(jié)符， β ∈(V N∪V T)*。 ? 1型文法（ 上下文有關(guān)文法） ： 對文法 G=(VN， VT， P， S)的任一產(chǎn)生式 α → β ，都有 |β |≥| α |， 僅僅 S→ ε 除外。 ? 2型文法（ 上下文無關(guān)文法） ： 對文法 G=(VN， VT， P， S)的任一產(chǎn)生式 α → β ，都有 α ∈V N ， β ∈(V N∪V T)* 。 ? 3型文法（ 正規(guī)文法 ）：設(shè) G=(VN， VT， P， S)，若 P中的每一個產(chǎn)生式的形式都是 A→aB 或 A→a ，其中 A和 B都是非終結(jié)符， a是終結(jié)符。 ? 3型文法 G=(VN， VT， P， S)的 P中的規(guī)則有兩種形式：一種是前面定義的形式，即： A→aB 或 A→a 其中 A， B∈V N ， a∈V T*，另一種形式是： A→Ba或 A→a ，前者稱為右線性文法，后者稱為左線性文法。正規(guī)文法所描述的是 VT*上的正規(guī)集。 32 例 ?G=({S,A,B},{a,b},P,S)，其中 P由下列產(chǎn)生式組成： ? S→aB A→bAA S→bA B→b ? A→a B→bS A→aS B→aBB ? 或?qū)?P改寫為： ? S→aB|bA A→bA|a A→a|A→aS ? B→bS|B→aB|b ?則 G是正規(guī)文法或 3型文法。 33 例 ?文法 G=({S,A,B},{0,1},P,S)，其中 P由下列產(chǎn)生式組成： ? S→0A A→1B S→1B B→1B ? S→0 B→1 A→0A B→0 A→0S ? 或?qū)?P改寫為： ? S→0A|1B|0 ? A→0S|1B|0A ? B→1B|1|0 ?則 G是正規(guī)文法或 3型文法。 34 喬姆斯基分類文法之間關(guān)系 2型文法 1型文法 0型文法 四種 文法 之間 的 逐級 “ 包含 ” 關(guān)系 3型文法 35 對應(yīng)喬姆斯基分類文法的 語言 ?0型文法產(chǎn)生的語言稱為 0型語言。 ?1型文法或上下文有關(guān)文法（ CSG ） 產(chǎn)生的語言稱為 1型語言 或上下文有關(guān) 語言（ CSL）。 ?2型文法或上下文無關(guān)文法（ CFG ） 產(chǎn)生的語言稱為 2型語言 或上下文無關(guān) 語言（ CF L ）。 ?3型文法或正則（正規(guī)）文法（ RG ） 產(chǎn)生的語言稱為 3型語言 正則（正規(guī)） 語言（ RL ）。 36 文法和語言之間的關(guān)系 ?四種文法之間的關(guān)系是將產(chǎn)生式做進(jìn)一步限制而定義的。 ?語言之間的關(guān)系依次：有不是上下文有關(guān)語言的 0型語言，有不是上下文無關(guān)語言的 1型語言，有不是正則語言的上下文無關(guān)語言。 37 上下文無關(guān)文法及其語法樹 ?語法樹 ? 句型能夠構(gòu)造關(guān)聯(lián)語法樹的條件 ? 示例： 例 ?最左（右）推導(dǎo) ?二義性文法 ? 判斷依據(jù) ? 示例： 例 ? 二義性文法與二義性語言的區(qū)別 38 句型能夠構(gòu)造關(guān)聯(lián)語法樹的條件 ?給定文法 G=(VN， VT， P， S)，對于 G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹 (推導(dǎo)樹 )。這棵樹滿足下列 4個條件： ? ① 每個結(jié)點(diǎn)都有一個標(biāo)記，此標(biāo)記是 V的一個符號。 ? ② 根的標(biāo)記是 S。 ? ③ 若一結(jié)點(diǎn) n至少有一個它自己除外的子孫 （子結(jié)點(diǎn)） ，并且有標(biāo)記 A，則 A肯定在 VN中。 ? ④ 如果結(jié)點(diǎn) n的直接子孫，從左到右的次序是結(jié)點(diǎn) n1，n2， … ， nk，其標(biāo)記分別為 A1， A2， … ， Ak，那么A→A 1A2…A k一定是 P中的一個產(chǎn)生式。 39 例 G=(｛ S,A｝ ,｛ a,b｝ ,P,S)，其中 P為： ① S→aAS ② A→SbA ③ A→SS ④ S→a ⑤ A→ba 右圖是 G（ aabbaa）的一棵推導(dǎo)樹。 40 最左（右）推導(dǎo) ?如果在推導(dǎo)的任何一步 α?β，其中 α， β是句型，都是對 α中的最左 (最右 )非終結(jié)符進(jìn)行替換，則稱這種推導(dǎo)為最左 (最右 )推導(dǎo)。 ?在形式語言中，最右推導(dǎo)常被稱為規(guī)范推導(dǎo)。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。 ?最左推導(dǎo)示例 ? S?aAS?aSbAS?aabAS?aabbaS?aabbaa ?最右推導(dǎo)示例 ? S?aAS?aAa?aSbAa?aSbbaa?aabbaa 41 二義文法的 判斷依據(jù) ?若一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法是二義的。 或者，若一個文法存在某個句子有兩個不同的最左（右）推導(dǎo)，則稱這個文法是二義的。 ?如果產(chǎn)生上下文無關(guān)語言的每一個文法都是二義的，則說此語言是先天二義的。 ?判定任給的一個上下文無關(guān)文法是否二義，或它是否產(chǎn)生一個先天二義的上下文無關(guān)語言，這兩個問題是遞歸不可解的，即，不存在一個算法，它能在有限步驟內(nèi)，確切判定任給的一個文法是否為二義的。我們所能做的事是為無二義性尋找一組充分條件 (當(dāng)然它們未必都是必要的 )。 42 例 ?文法 G=(｛ E｝ ,｛ +,*,i,(,)｝ ,P,E)其中 P={ E→i E→E+E E→E*E E→(E)} 是二義性的，假若規(guī)定了運(yùn)算符“ +”與“ *”的優(yōu)先順序和結(jié)合規(guī)則，即按慣例，讓“ *”的優(yōu)先性高于“ +”，且它們都服從左結(jié)合，那么就可以構(gòu)造出一個無二義文法。 ?定義表達(dá)式的無二義文法 G[E]： E→T|E+T T→F|T*F F→(E)|i 它和上述文法產(chǎn)生的語言是相同的。即它們是等價的。 43 二義性文法與二義性語言的區(qū)別 ?文法的二義性和語言的二義性是兩個不同的概念。因?yàn)榭赡苡袃蓚€不同的文法 G和 G′ ，其中 G是二義的，但是卻有L(G)=L(G′) ，也就是說，這兩個文法所產(chǎn)生的