編譯原理ppt課件-在線瀏覽
2025-06-20 01:55本頁(yè)面
【正文】 | …| ?? n | ? 1 | ? 2 | … ? m (其中，每個(gè) ? 不以 ?開(kāi)頭 ) ? 那么，可以把這些規(guī)則改寫(xiě)成 A→ ?A? | ? 1 | ? 2 | … | ? m A?→ ? 1 | ? 2 | … | ? n ? 經(jīng)過(guò) 反復(fù)提取左因子 ，就能夠把每個(gè)非終結(jié)符（包括新引進(jìn)者）的 所有候選首符集變成為兩兩不相交 消除回溯、提左因子（三） ? 例 ：考察文法 G： ? S → iCtS | iCtSeS | a ? C → b ? 解：由于 S的前兩個(gè)候選項(xiàng)中含有左因子iCtS，提取左因子之后，等價(jià)文法 G’如下： ? S → iCtSS39。 這 時(shí) ，不得不 “ 回溯 ” 左遞歸與回溯 P P?? ? LL(1)分析法 ? 語(yǔ)法分析器的功能 ? 自上而下分析面臨的問(wèn)題 ? LL(1)分析法 ? 不帶回溯的自上而下分析算法 ? 左遞歸的消除 ? 回溯的消除 ? LL(1)分析條件 ? 遞歸下降分析程序構(gòu)造 ? 預(yù)測(cè)分析程序 ? LL(1)分析中的錯(cuò)誤處理 不帶回溯的自上而下分析算法 ? 自上而下分析方法 ?不允許文法含有任何左遞歸 ?構(gòu)造不帶回溯的自上而下分析算法 ?消除文法的左遞歸性 ?找出克服回溯的充分必要條件 左遞歸的消除（一） ? 直接消除產(chǎn)生式中的左遞歸 ?假定關(guān)于非終結(jié)符 P的規(guī)則為 P→P ? | ? 其中 ?不以 P開(kāi)頭 ?那么，我們可以把 P的規(guī)則 等價(jià) 地改寫(xiě)為如下的非直接左遞歸形式： P→ ?P? P?→ ?P?|? 左遞歸的消除（二） ? 一般而言，假定關(guān)于 P的全部產(chǎn)生式是 P→P ?1 | P?2 | … | P ?m | ?1 | ?2|…| ?n 其中，每個(gè) ?都不等于 ?，而每個(gè) ?都不以 P開(kāi)頭 那么，消除 P的直接左遞歸性就是 改寫(xiě) 這些規(guī)則： P→ ?1P? | ?2P? | … | ?nP? P?→ ?1P? | ?2P? |… | ?mP? | ? 左遞歸的消除（三） ? 例 文法 ? E→E ＋ T | T ? T→T*F | F ? F→(E) | i ? 經(jīng)消去直接左遞歸后變成： ? E→TE ? ? E?→+TE ? | ? ? T→FT ? ? T?→*FT ? | ? ? F→(E) | i 注意：這個(gè)例子后面將再度用到 左遞歸的消除（四） ? 例如文法 ? S→Qc|c ? Q→Rb|b ? R→Sa|a ? 雖沒(méi)有直接左遞歸，但 S、 Q、 R都是左遞歸的，如： S?Qc?Rbc?Sabc ? 一個(gè)文法 消除左遞歸 的條件 ?不含以 ?為右部的產(chǎn)生式（空產(chǎn)生式） ?不含回路，形如 PP ?? 左遞歸的消除（五） ? 消除左遞歸的算法 ? 把文法 G的所有非終結(jié)符按任一種順序排列成 P1， P2， … ， Pn ；按此順序執(zhí)行； ? FOR i:=1 TO n DO BEGIN FOR j:=1 TO i1 DO 把形如 Pi→P j ?的規(guī)則改寫(xiě)成 Pi→ ?1?|?2?|…| ?k? 。第四章 語(yǔ)法分析 — 自上而下分析 內(nèi)容 ? 語(yǔ)法分析器的功能 ? 自上而下分析面臨的問(wèn)題 ? LL（ 1）分析法 ? 遞歸下降分析程序構(gòu)造 ? 預(yù)測(cè)分析程序 ? LL（ 1）分析中的錯(cuò)誤處理 語(yǔ)法分析器的功能 ? 語(yǔ)法分析器的功能 ?語(yǔ)法分析器的功能 ?語(yǔ)法分析方法 ? 自上而下分析面臨的問(wèn)題 ? LL（ 1）分析法 ? 遞歸下降分析程序構(gòu)造 ? 預(yù)測(cè)分析程序 ? LL（ 1）分析中的錯(cuò)誤處理 語(yǔ)法分析器的功能 ? 高級(jí)語(yǔ)言的語(yǔ)法結(jié)構(gòu) ? 適合用 上下文無(wú)關(guān)文法 描述 ? 語(yǔ)法分析器 ? 任務(wù)：分析與判定 程序的語(yǔ)法結(jié)構(gòu)是否符合語(yǔ)法規(guī)則 ? 工作本質(zhì)： 根據(jù)產(chǎn)生式識(shí)別輸入串是否為一個(gè)句子 ? 在編譯器中的地位：核心部分 詞法分析器 語(yǔ)法分析器 編譯器的 后繼部分 符號(hào)表 源程序 單詞符號(hào) 取下一個(gè)單詞符號(hào) 語(yǔ)法分析樹(shù) 語(yǔ)法分析方法 ? 自上而下分析法 ? 從文法的開(kāi)始符號(hào)出發(fā) ，反復(fù)使用文法的產(chǎn)生式，尋找與輸入符號(hào)串匹配的 推導(dǎo) ? 將文法開(kāi)始符號(hào)做為語(yǔ)法樹(shù)的根， 向下逐步建立語(yǔ)法樹(shù) ，使語(yǔ)法樹(shù)的結(jié)果正好是輸入符號(hào)串 ? 自下而上分析法 ? 從輸入符號(hào)串開(kāi)始 ，逐步進(jìn)行 歸約 ，直至歸約到文法的開(kāi)始符號(hào) ? 從輸入符號(hào)串開(kāi)始，以它做為語(yǔ)法樹(shù)的結(jié)果， 自底向上地構(gòu)造語(yǔ)法樹(shù) 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 S S S c A d c A d a b 推導(dǎo)過(guò)程： S ? cAd cAd ? cabd 例：文法 G： S → cAd A → ab A → a 識(shí)別輸入串 w=cabd是否為該文法的 句子 自上而下分析 自下而上分析 自上而下分析面臨的問(wèn)題 ? 語(yǔ)法分析器的功能 ? 自上而下分析面臨的問(wèn)題 ?自上而下分析的主旨 ?回溯舉例 ?自上而下的帶回溯試探法 ?自上而下分析面臨的問(wèn)題 ?左遞歸與回溯 ? LL（ 1）分析法 ? 遞歸下降分析程序構(gòu)造 ? 預(yù)測(cè)分析程序 ? LL（ 1）分析中的錯(cuò)誤處理 自上而下分析的主旨 ? 自上而下 ? 從文法的開(kāi)始符號(hào)出發(fā)，向下推導(dǎo)，推出句子 ?存在問(wèn)題：帶 “ 回溯 ” ? 克服方法 ?不帶回溯的遞歸子程序（遞歸
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1