課件，編譯原理，編譯原理課件，屬性文法，語(yǔ)法制導(dǎo)，2005課件說(shuō)明，第四章-免費(fèi)閱讀
【正文】 55 對(duì)于文法 G[S]，為了保證任一非終結(jié)符 A在句子 推導(dǎo)中出現(xiàn)，必須滿足如下兩個(gè)條件： 1. A必須在某句型中出現(xiàn) 即有 S =* αAβ，其中 α， β屬于 V* 2. 必須能夠從 A推出終結(jié)符號(hào)串 t來(lái) 即 A =* t，其中 t∈ VT* 56 化簡(jiǎn)文法 ?例： G[S] ： 1) S→ Be 2) B→ Ce D為不可到達(dá) 3) B→ Af C為不可終止 4) A→ Ae 5) A→ e 6) C→ Cf 7) D→ f 產(chǎn)生式 2）， 6）， 7）為 多余規(guī)則 應(yīng)去 掉。 47 句型的 分析算法分類 分析算法可分為： 自上而下分析法 ： 從文法的開(kāi)始符號(hào)出發(fā) ，反復(fù)使用文法的產(chǎn)生式， 尋找 與 輸入符號(hào)串 匹配 的 推導(dǎo)，或者說(shuō)，為輸入串尋找一個(gè)最左推導(dǎo)。但是，一個(gè)句型是否只對(duì)應(yīng)唯一的一棵語(yǔ)法樹(shù)呢 ?一個(gè)句型是否只有唯一的一個(gè)最左 (最右 )推導(dǎo)呢 ? 43 例： G‘[E]: E → i E → E+E E → E*E E → (E) E E + E E * E i i i E E * E i E + E i i 句型 i*i+i 的兩個(gè)不同的最左推導(dǎo)： 推導(dǎo) 1： E ? E+E ? E*E+E ? i*E+E ? i*i+E ? i*i+i 推導(dǎo) 2： E ? E*E ? i*E ? i*E+E ? i*i+E ?i*i+i 44 二義文法 若一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱這個(gè)文法是 二義 的 或者，若一個(gè)文法存在某個(gè)句子有兩個(gè)不同的最左（右）推導(dǎo)，則稱這個(gè)文法是 二義 的 判定任給的一個(gè)上下文無(wú)關(guān)文法是否二義，或它是否產(chǎn)生一個(gè)先天二義的上下文無(wú)關(guān)語(yǔ)言，這兩個(gè)問(wèn)題是遞歸不可解的，但可以為無(wú)二義性尋找一組充分條件 45 文法的二義性和語(yǔ)言的二義性 文法的二義性和語(yǔ)言的二義性是兩個(gè)不同的概念。 Z={N} 25 根據(jù)形式語(yǔ)言理論 ,文法和識(shí)別系統(tǒng)間有這樣的關(guān)系 0型文法（短語(yǔ)結(jié)構(gòu)文法）的能力相當(dāng)于圖靈機(jī)，可以表征任何遞歸可枚舉集，而且任何 0型語(yǔ)言都是遞歸可枚舉的 1型文法（上下文有關(guān)文法）：產(chǎn)生式的形式為 α 1Aα 2→ α 1βα2，即只有 A出現(xiàn)在 α 1和 α 2的上下文中時(shí)，才允許 β 取代 A。BEGIN READ(標(biāo)識(shí)符 )END. ? VAR A。（嚴(yán)謹(jǐn)、簡(jiǎn)潔、易讀） 形式 工具 “形式”是指這樣的事實(shí)：語(yǔ)言的所有規(guī)則只以什麼符號(hào)串能出現(xiàn)的方式來(lái)陳述 2 本章內(nèi)容 文法和語(yǔ)言的形式定義 文法的類型 上下文無(wú)關(guān)文法及其語(yǔ)法樹(shù) 上下文無(wú)關(guān)文法 的句型分析 有關(guān)文法實(shí)用中的一些說(shuō)明 3 文法和語(yǔ)言的形式定義 如何來(lái)描述一種語(yǔ)言？ 如果語(yǔ)言是有窮的（只含有有窮多個(gè)句子），可以將句子逐一列出來(lái)表示 如果語(yǔ)言是無(wú)窮的，找出語(yǔ)言的有窮表示。 VN和 VT不含公共的元素，即 VN ∩ VT = φ 用 V表示 VN ∪ VT ，稱為文法 G的字母表或字匯表 規(guī)則 ，也稱 重寫(xiě)規(guī)則 、 產(chǎn)生式 或 生成式 ，是形如?→ ?或 ? ∷ =?的 (? ， ?)有序?qū)Γ渲??是字母表 V的正閉包 V+中的一個(gè)符號(hào)， ?是 V*中的一個(gè)符號(hào)。 例： G： S→ 0S1， S→ 01 S ?0S1 ?00S11 ?000S111 ?00001111 G的句型 S,0S1 ,00S11 ,000S111,00001111 G的句子 00001111, 01 14 句型、句子 例： G[E]： E→E+T|T T→T*F|F F→(E)|a E?E+T ?T+T ?F+T ?a+T ?a+T*F ?a+F*F ?a+a*F ?a+a*a 句子：用符號(hào) a， +， *， (和 )構(gòu)成的算術(shù)表達(dá)式 15 (文法生成的 )語(yǔ)言的定義 由文法 G生成的語(yǔ)言記為 L(G),它是文法 G的一切句子的集合 : L(G)={x|S =* x，其中 S為文法的開(kāi)始符號(hào)，且 x ∈V T*} 例： G： S→ 0S1， S→ 01 L(G)={0n1n|n≥ 1} 例 文法 G[S]： （ 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 } G生成的每個(gè)串都在 L(G)中 L(G)中的每個(gè)串確實(shí)能被 G生成 17 文法的等價(jià) ?若 L（ G1） =L（ G2），則稱文法 G1和 G2是等價(jià)的。 ∑= VT S = A 在語(yǔ)言的編譯實(shí)現(xiàn)中，把 完成句型分析 的 程序 稱為 分析程序 或 識(shí)別程序 。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1