課件，編譯原理，編譯原理課件，屬性文法，語(yǔ)法制導(dǎo)，2005課件說(shuō)明，第四章(參考版)
2025-05-06 23:00本頁(yè)面
【正文】 要求： (1) 允許 0打頭 (2) 不允許 0打頭 G［ 〈 表達(dá)式 〉 ］是二義的。 57 上下文無(wú)關(guān)文法中的 ε規(guī)則 上下文無(wú)關(guān)文法中某些規(guī)則可具有形式 A→ ε，稱這種規(guī)則為 ε規(guī)則 因?yàn)?ε規(guī)則會(huì)使得有關(guān)文法的一些討論和證明變得復(fù)雜 ,有時(shí)會(huì)限制這種規(guī)則的出現(xiàn) 兩種定義的唯一差別是 ε句子在不在語(yǔ)言中 文法構(gòu)思的啟示是要找出語(yǔ)言的有窮描述，而如果語(yǔ)言 L有一個(gè)有窮的描述，則 L1=L∪ ｛ ε｝也同樣有一個(gè)有窮的描述，并且可以證明，若 L是上下文有關(guān)語(yǔ)言、上下文無(wú)關(guān)語(yǔ)言或正規(guī)語(yǔ)言，則L∪ ｛ ε｝和 L｛ ε｝分別是上下文有關(guān)語(yǔ)言、上下文無(wú)關(guān)語(yǔ)言和正規(guī)語(yǔ)言。 2）文法中某些 非終結(jié)符 ，由它 不能推出終結(jié)符號(hào)串 ，該非終結(jié)符稱 為 不可終止 。 S c A d a b 這時(shí)應(yīng)該 回朔 ，把 A為根的子樹(shù)剪掉，掃描過(guò)的輸入串中的 a吐出來(lái) ,再試探用產(chǎn)生式（ 3） 52 (1)S → cAd (2) A → ab (3)A → a 識(shí)別輸入串 w=cabd是否為該文法的 句子 自下而上的語(yǔ)法分析 對(duì)串 cabd的分析中，如果不是選擇 ab用產(chǎn)生式 (2),而是選擇 a用產(chǎn)生式 (3)將 a歸約到了 A，那么在 c A b d 中無(wú)法找到一個(gè)可歸約串了，最終就達(dá)不到歸約到 S的結(jié)果，因而也無(wú)從知道 cabd是一個(gè)句子 c a b d c A b d a 53 句型分析的有關(guān)問(wèn)題 1）在自上而下的分析方法中 如何 選擇 使用 哪個(gè) 產(chǎn)生式進(jìn)行推導(dǎo) ？ 假定要被代換的最左非終結(jié)符號(hào)是 B，且有 n條規(guī)則： B→ A1|A2|…|An ，那么如何確定用哪個(gè)右部去替代 B？ 2）在自下而上的分析方法中 如何 識(shí)別可歸約的串 ？ 在分析程序工作的每一步，都是從當(dāng)前串中 選擇一個(gè) 子串 ，將它 歸約 到 某個(gè)非終結(jié)符號(hào) ，該子串稱為“ 可歸約串 ” 54 文法實(shí)用中的一些說(shuō)明 限制 化簡(jiǎn)文法 文法中 不含有 有害規(guī)則 和 多余規(guī)則 有害規(guī)則 ：形如 U→ U的產(chǎn)生式。 自上而下方法 是從文法符號(hào)開(kāi)始，將它做為語(yǔ)法樹(shù)的根，向下逐步建立語(yǔ)法樹(shù)，使語(yǔ)法樹(shù)的結(jié)果正好是輸入符號(hào)串 自下而上方法 則是從輸入符號(hào)串開(kāi)始，以它做為語(yǔ)法樹(shù)的結(jié)果，自底向上的構(gòu)造語(yǔ)法樹(shù) 49 自上而下的語(yǔ)法分析 例：文法 G： S → cAd A → ab A → a 識(shí)別輸入串 w=cabd是否為該文法的 句子 S S S c A d c A d a b 推導(dǎo)過(guò)程： S ? cAd cAd ? cabd 50 自下而上的語(yǔ)法分析 例：文法 G： S → cAd A → ab A → a 識(shí)別輸入串 w=cabd是否該文法的 句子 S A A c a b d c a b d c a b d 規(guī)約 過(guò)程構(gòu)造的推導(dǎo)： cAd ? cabd S ? cAd 51 自上而下的語(yǔ)法分析 (1)S → cAd (2) A → ab (3) A → a 識(shí)別輸入串 w=cad是否為該文法的 句子 若 S ? cAd 后選擇 (2)擴(kuò)展 A，S ? cAd ? cabd 那將會(huì)？ w的第二個(gè)符號(hào)可以與葉子結(jié)點(diǎn) a得以匹配，但第三個(gè)符號(hào)卻不能與下一葉子結(jié)點(diǎn) d匹配 ？宣告分析失?。ㄆ湟馕吨R(shí)別程序不能為串 cad構(gòu)造語(yǔ)法樹(shù)，即 cad不是句子） 顯然是錯(cuò)誤的結(jié)論。 自下而上分析法 ： 從 輸入符號(hào)串 開(kāi)始 ， 逐步進(jìn)行 歸約 ，直至歸約 到 文法的 開(kāi)始符號(hào) 。 從左到右的分析算法 ，即 總是從 左 到 右 地 識(shí)別輸入符號(hào)串 ，首先識(shí)別符號(hào)串中的 最左符號(hào)，進(jìn)而 依次識(shí)別右邊 的一個(gè)符號(hào)， 直到分析結(jié)束 。 在語(yǔ)言的編譯實(shí)現(xiàn)中，把 完成句型分析 的 程序 稱為 分析程序 或 識(shí)別程序 。對(duì)于一個(gè)程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō)，常常希望它的文法是無(wú)二義的，因?yàn)橄Ｍ麑?duì)它的每個(gè)語(yǔ)句的分析是唯一的。因?yàn)榭赡苡袃蓚€(gè)不同的文法 G和 G′ ，其中 G是二義的，但是卻有 L(G)=L(G′) ，也就是說(shuō)，這兩個(gè)文法所產(chǎn)生的語(yǔ)言是相同的。 由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型 39 語(yǔ)法樹(shù) 設(shè) G=( VN,VT,P,S)為一 cfg，若一棵樹(shù)滿足下列 4個(gè)條件，則此樹(shù)稱作 G的語(yǔ)法樹(shù) (推導(dǎo)樹(shù) )(派生樹(shù)）： 1. 每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是 V的一個(gè)符號(hào) 2. 根的標(biāo)記是 S 3. 若一結(jié)點(diǎn) n至少有一個(gè)它自己除外的子孫，并且有標(biāo)記 A，則肯定 A∈V N 4. 如果結(jié)點(diǎn) n有標(biāo)記 A,其直接子孫結(jié)點(diǎn)從左到右的次序是 n1， n2， … ， nk，其標(biāo)記分別為 A1， A2， … ，Ak，那么 A→A 1A2， … ， Ak一定是 P中的一個(gè)產(chǎn)生式 語(yǔ)法樹(shù)的結(jié)果： 從左到右讀出葉子的標(biāo)記而構(gòu)成的行謂之 40 上下文無(wú)關(guān)文法的語(yǔ)法樹(shù) ?句型 aabbaa的可能 推導(dǎo) 序列和語(yǔ)法樹(shù) 例 : G[S]: S→ aA
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1