程序設(shè)計(jì)語(yǔ)言編譯原理第三版第4章-展示頁(yè)
2025-01-15 18:29本頁(yè)面
【正文】 P1,P2,… ,Pn。 LL(1)分析法 一、左遞歸的消除： 1. 規(guī)則 :（直接左遞歸消除） P?β 1p’|β 2P’|… |β nP’ P’?α 1P’|α 2P’|… |α mP’|? P?βP ’ P’?αP ’|? P?Pα ｜ β P?Pα １ |Pα ２ |… Pα ｍ |β １ |β ２ |… |β ｎ 167。 ,難于知道輸入串中 出錯(cuò)的確切位置 。 自上而下面臨的問(wèn)題 三、困難和缺點(diǎn) ? 使自上而下的分析過(guò)程陷入無(wú)限循環(huán) 。一旦發(fā)現(xiàn) 它的某個(gè)候選與輸入串相匹配，就用這個(gè)候選 去擴(kuò)展語(yǔ)法樹，并返回 “ 真 ” 值；否則，保持原 來(lái)的語(yǔ)法樹和 IP值不變，并返回 “ 假 ” 值。 自上而下面臨的問(wèn)題 實(shí)現(xiàn)上述帶回溯試探法的簡(jiǎn)單途徑： 讓每個(gè)非終結(jié)符對(duì)應(yīng)一個(gè)遞歸子程序。 167。 167。 ： 自上而下分析法 自下而上分析法 167。 ： 單詞符號(hào) 取下一單 詞符號(hào) 語(yǔ)法分 析樹 符號(hào)表 詞法分析器 語(yǔ)法分析器 編譯程序 后續(xù)部分 源程序 167。第四章 語(yǔ)法分析 — 自上而下分析 語(yǔ)法分析器的功能 自上而下分析面臨的問(wèn)題 LL（ 1）分析法 遞歸下降分析程序構(gòu)造 預(yù)測(cè)分析程序 LL（ 1）分析中的錯(cuò)誤處理 (略 ) 167。 語(yǔ)法分析器的功能 ： 在詞法分析識(shí)別出單詞符號(hào)串的 基礎(chǔ)上，分析并判定程序的語(yǔ)法 結(jié)構(gòu)是否符合語(yǔ)法規(guī)則。 語(yǔ)法分析器的功能 ： 按文法的產(chǎn)生式，識(shí)別輸入符號(hào)串 是否為一個(gè)句子。 自上而下面臨的問(wèn)題 一、基本思想： ： 從文法的開始符號(hào)出發(fā)，向下 推導(dǎo)，推出句子 ： 對(duì)任何輸入串，試圖用一切可能的 辦法，從開始符號(hào)出發(fā)，自上而下 地為輸入串建立一棵語(yǔ)法樹。 自上而下面臨的問(wèn)題 二、舉例： 自上而下方法的分析過(guò)程 本質(zhì) 上 是一種 試探過(guò)程 ，是 反復(fù)使用 不同產(chǎn)生 式謀求 匹配輸入串 的過(guò)程。 自上而下面臨的問(wèn)題 S S x A y S x A y * 例： 文法 S?xAy A?**|* 輸入串 α :x*y x A y * * 167。每 個(gè)這種子程序可作為一個(gè)布爾過(guò)程。 167。 。 ,效率很低 , 代價(jià)極高 . 167。 LL(1)分析法 例題： 已經(jīng)文法：Ｅ ?Ｅ +Ｔ｜Ｔ Ｔ ?Ｔ＊Ｆ｜Ｆ Ｆ ?(Ｅ )｜ｉ Ｅ ?ＴＥ ’ Ｅ ’ ?+ＴＥ ’ ｜ ? Ｔ ?ＦＴ ’ Ｔ ’ ?*ＦＴ ’ ｜ ? Ｆ ?(Ｅ )|ｉ 167。 按此順序執(zhí)行 : （２） FOR i = 1 To n Do Begin For j :=1 To i1 Do 把形如 Pi ? Pj γ 的規(guī)則改寫成 Pi?δ 1γ|δ 2γ| … |δ k γ 其中 Pj?δ 1|δ 2|… |δ k是關(guān)于 Pj的所有規(guī)則； 消除 關(guān)于 Pi規(guī)則的 直接左遞歸性 End 167。 LL(1)分析法 G: S? Qc|c Q? Rb|b R? Sa|a i=3， j=1 無(wú)關(guān)系 i=3， j=2 S ? Qc|c Q? Sab|ab|b S ? Sabc|abc|bc|c 消除 S的直接左遞歸 S ? abcS’|bcS’|cS’ S’ ? abcS’| ? 返回 S?abcS’ |bcS’ |cS’ S’ ?abcS’| ? 故 S?abcS’ |bcS’ |cS’ S’ ?abcS’| ? Q?Sab|ab|b R?Sa|a 167。 LL(1)分析法 １ .消除回溯必須保證 : 對(duì)文法的 任何非終結(jié)符 ,當(dāng)要它去匹配輸入串時(shí)，能夠根據(jù)它所面臨的輸入符號(hào) 準(zhǔn)確地指派 它的一個(gè)候選去執(zhí)行任務(wù)，并且此候選的 工作結(jié)果 應(yīng)是 確信無(wú)疑 的。
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1