課件，編譯原理，編譯原理課件，屬性文法，語(yǔ)法制導(dǎo)，2005課件說(shuō)明，第四章-資料下載頁(yè)
2025-05-01 23:00本頁(yè)面
【導(dǎo)讀】如果語(yǔ)言是無(wú)窮的，找出語(yǔ)言的有窮表示。格定義的規(guī)則來(lái)構(gòu)造。是”，要么永遠(yuǎn)繼續(xù)下去。VN，VT和P是非空有窮集。少要在一條產(chǎn)生式中作為左部出現(xiàn)。)有序?qū)?，其?稱作規(guī)則的右部。則稱v直接推導(dǎo)到w,記作v?<變量說(shuō)明部分><語(yǔ)句>). 若L=L，則稱文法G1和G2是。1型文法：對(duì)任一產(chǎn)生式α→β，都有|β|≥|α|，
【正文】 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匹配 ？宣告分析失?。ㄆ湟馕吨?，識(shí)別程序不能為串 cad構(gòu)造語(yǔ)法樹(shù)，即 cad不是句子） 顯然是錯(cuò)誤的結(jié)論。 導(dǎo)致失敗的原因是在分析中對(duì)A的選擇不是正確的。 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)生式。會(huì) 引起 文法的 二義性 多余規(guī)則 ：指文法中 任何句子的推導(dǎo) 都 不會(huì)用到的規(guī)則 文法中 不含有 不可到達(dá)和不可終止的 非終結(jié)符 1）文法中某些 非終結(jié)符不在任何規(guī)則的右部出現(xiàn) ，該非終結(jié)符稱為 不可到達(dá) 。 2）文法中某些 非終結(jié)符 ，由它 不能推出終結(jié)符號(hào)串 ，該非終結(jié)符稱 為 不可終止 。 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)去 掉。 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ǔ)言。 58 練習(xí) 1. 寫一文法，使其語(yǔ)言是偶正整數(shù)的集合。 要求： (1) 允許 0打頭 (2) 不允許 0打頭 G［ 〈 表達(dá)式 〉 ］是二義的。 〈 表達(dá)式 〉 ∷ =a|(〈 表達(dá)式 〉 )|〈 表達(dá)式 〉〈 運(yùn)算符 〉〈 表達(dá)式 〉 〈 運(yùn)算符 〉 ∷ =+||*|/ 3. 令文法 G［ E］為： E→T|E+T|E T T→F|T*F|T/F F→(E)|i 證明 E+T*F是它的一個(gè)句型 59 練習(xí) 4. 給出生成下述語(yǔ)言的上下文無(wú)關(guān)文法： （ 1） { anbnambm| n， m=0} (2) { 1n0m 1m0n| n， m=0} 5. 給出生成下述語(yǔ)言的三型文法： (1) { anbm|n,m=1 } (2){anbmck|n,m,k=0 } 6. 給出下述文法所對(duì)應(yīng)的正規(guī)式： S→0A|1B A→1S|1 B→0S|0
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1