編譯原理第03章-文法和語(yǔ)言(編輯修改稿)
2025-09-01 15:47 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 例 ?設(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 文法的等價(jià) ?若 L（ G1） =L（ G2），則稱文法 G1和 G2是等價(jià)的。 ?示例：文法 G1[A]： A→0R A→01 R→A1 與G2[S]： S→0S1 S→01 等價(jià)。 30 文法的類型 ?喬姆斯基分類 ?示例： ? 例 ? 例 ?喬姆斯基分類文法之間關(guān)系 ?對(duì)應(yīng)于喬姆斯基分類文法的語(yǔ)言 ?文法和語(yǔ)言之間的關(guān)系 31 喬姆斯基對(duì)文法的分類 ?通過(guò)對(duì)產(chǎn)生式施加不同的限制， Chomsky（喬姆斯基）將文法分為四種類型： ? 0型文法：對(duì)文法 G=(VN， VT， P， S)的任一產(chǎn)生式 α → β ，都有α ∈(V N∪V T)*且至少含有一個(gè)非終結(jié)符， β ∈(V N∪V T)*。 ? 1型文法（ 上下文有關(guān)文法） ： 對(duì)文法 G=(VN， VT， P， S)的任一產(chǎn)生式 α → β ，都有 |β |≥| α |， 僅僅 S→ ε 除外。 ? 2型文法（ 上下文無(wú)關(guān)文法） ： 對(duì)文法 G=(VN， VT， P， S)的任一產(chǎn)生式 α → β ，都有 α ∈V N ， β ∈(V N∪V T)* 。 ? 3型文法（ 正規(guī)文法 ）：設(shè) G=(VN， VT， P， S)，若 P中的每一個(gè)產(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改寫(xiě)為： ? 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改寫(xiě)為： ? S→0A|1B|0 ? A→0S|1B|0A ? B→1B|1|0 ?則 G是正規(guī)文法或 3型文法。 34 喬姆斯基分類文法之間關(guān)系 2型文法 1型文法 0型文法 四種 文法 之間 的 逐級(jí) “ 包含 ” 關(guān)系 3型文法 35 對(duì)應(yīng)喬姆斯基分類文法的 語(yǔ)言 ?0型文法產(chǎn)生的語(yǔ)言稱為 0型語(yǔ)言。 ?1型文法或上下文有關(guān)文法（ CSG ） 產(chǎn)生的語(yǔ)言稱為 1型語(yǔ)言 或上下文有關(guān) 語(yǔ)言（ CSL）。 ?2型文法或上下文無(wú)關(guān)文法（ CFG ） 產(chǎn)生的語(yǔ)言稱為 2型語(yǔ)言 或上下文無(wú)關(guān) 語(yǔ)言（ CF L ）。 ?3型文法或正則（正規(guī)）文法（ RG ） 產(chǎn)生的語(yǔ)言稱為 3型語(yǔ)言 正則（正規(guī)） 語(yǔ)言（ RL ）。 36 文法和語(yǔ)言之間的關(guān)系 ?四種文法之間的關(guān)系是將產(chǎn)生式做進(jìn)一步限制而定義的。 ?語(yǔ)言之間的關(guān)系依次：有不是上下文有關(guān)語(yǔ)言的 0型語(yǔ)言，有不是上下文無(wú)關(guān)語(yǔ)言的 1型語(yǔ)言，有不是正則語(yǔ)言的上下文無(wú)關(guān)語(yǔ)言。 37 上下文無(wú)關(guān)文法及其語(yǔ)法樹(shù) ?語(yǔ)法樹(shù) ? 句型能夠構(gòu)造關(guān)聯(lián)語(yǔ)法樹(shù)的條件 ? 示例： 例 ?最左（右）推導(dǎo) ?二義性文法 ? 判斷依據(jù) ? 示例： 例 ? 二義性文法與二義性語(yǔ)言的區(qū)別 38 句型能夠構(gòu)造關(guān)聯(lián)語(yǔ)法樹(shù)的條件 ?給定文法 G=(VN， VT， P， S)，對(duì)于 G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹(shù) (推導(dǎo)樹(shù) )。這棵樹(shù)滿足下列 4個(gè)條件： ? ① 每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是 V的一個(gè)符號(hào)。 ? ② 根的標(biāo)記是 S。 ? ③ 若一結(jié)點(diǎn) n至少有一個(gè)它自己除外的子孫 （子結(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中的一個(gè)產(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)樹(shù)。 40 最左（右）推導(dǎo) ?如果在推導(dǎo)的任何一步 α?β，其中 α， β是句型，都是對(duì) α中的最左 (最右 )非終結(jié)符進(jìn)行替換，則稱這種推導(dǎo)為最左 (最右 )推導(dǎo)。 ?在形式語(yǔ)言中，最右推導(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ù) ?若一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱這個(gè)文法是二義的。 或者，若一個(gè)文法存在某個(gè)句子有兩個(gè)不同的最左（右）推導(dǎo)，則稱這個(gè)文法是二義的。 ?如果產(chǎn)生上下文無(wú)關(guān)語(yǔ)言的每一個(gè)文法都是二義的，則說(shuō)此語(yǔ)言是先天二義的。 ?判定任給的一個(gè)上下文無(wú)關(guān)文法是否二義，或它是否產(chǎn)生一個(gè)先天二義的上下文無(wú)關(guān)語(yǔ)言，這兩個(gè)問(wèn)題是遞歸不可解的，即，不存在一個(gè)算法，它能在有限步驟內(nèi)，確切判定任給的一個(gè)文法是否為二義的。我們所能做的事是為無(wú)二義性尋找一組充分條件 (當(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)造出一個(gè)無(wú)二義文法。 ?定義表達(dá)式的無(wú)二義文法 G[E]： E→T|E+T T→F|T*F F→(E)|i 它和上述文法產(chǎn)生的語(yǔ)言是相同的。即它們是等價(jià)的。 43 二義性文法與二義性語(yǔ)言的區(qū)別 ?文法的二義性和語(yǔ)言的二義性是兩個(gè)不同的概念。因?yàn)榭赡苡袃蓚€(gè)不同的文法 G和 G′ ，其中 G是二義的，但是卻有L(G)=L(G′) ，也就是說(shuō)，這兩個(gè)文法所產(chǎn)生的
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1