第四章自頂向下的語法分析-資料下載頁
2025-10-02 11:25本頁面
【導讀】LL分析表時的使用。遞歸子程序法中如何體現(xiàn)分析的結(jié)果。語法分析是編譯程序的核心部分，言中的句子，亦即是否符合源語言的語法規(guī)則。假定文法是壓縮的：即刪除了單位產(chǎn)生式和無用產(chǎn)生式。自頂向下語法分析的基本思想。從樹根S開始，構(gòu)造所給輸入符號串的語法樹。對于文法G，如果L中存在一個具有兩棵或兩棵以上。文法中每個語法變量A的產(chǎn)生式右部稱為A的。候選式，如果A有多個候選式存在公共前綴，當試探不成功時就需要退回到上一步推導，純通過提取左因子無法徹底避免回溯現(xiàn)象的發(fā)生。時稱之為直接左遞歸。改造的方法就是通過引入新的語法變量等，使文法。含有更多的信息。根據(jù)if語句中else與then配對情況將其分為配對的語。定義為<stmt>，從而導致該文法是二義性的。E→TE'E'→+TE'|εT→FT'T'→*FT'|ε。|βmA'A'→α1A'|α2A'|…
【正文】 020/11/17 43 語法圖和遞歸子程序法 ? 從文法構(gòu)造語法圖，對每個非終結(jié)符 A執(zhí)行如下操作 ? 創(chuàng)建一 個開始狀態(tài)和一個終止狀態(tài)（返回狀態(tài)） ? 對每個產(chǎn)生式 A→X1X2 … X n，創(chuàng)建一條從開始狀態(tài)到終止狀態(tài)的路徑，邊上的標記分別為 X1，X2， … ， Xn 2020/11/17 44 例 簡單表達式文法的語法圖 E→TE‘ E39?！?TE39。|ε T→FT39。 T39?！?FT39。|ε F→(E)|id 0 1 2TE 180。E :3 4 6+E 180。5TE 180。 :ε7 8 9FT 180。T :1 0 1 1 1 3*T 180。1 2FT 180。 :ε1 4 1 5 1 7( )1 6EF :i d2020/11/17 45 ? 初始時，分析器進入狀態(tài)圖的開始狀態(tài)，輸入指針指向 輸入符號串的第一個符號。 ? 如果經(jīng)過一些動作后，它進入狀態(tài) s，且從狀態(tài) s到狀態(tài) t的邊上標記了終結(jié)符 a， 此時下一個輸入符又正好是 a，則分析器將輸入指針向右移動一位，并 進入狀態(tài) t。 2020/11/17 46 ? 另一方面，如果邊上標記的是非終結(jié)符 A，則分析器進入 A的初始狀態(tài)，但不移動輸入指針。一旦到達 A的終態(tài)，則立刻進入狀態(tài) t，事實上，分析器從狀態(tài) s轉(zhuǎn)移到狀態(tài) t時，它已經(jīng)從輸入符號串“讀”了 A （ 調(diào)用 A對應(yīng)的過程 ）。 ? 最后，如果從 s到 t有一條標記為 ε的邊，那么分析器從狀態(tài) s直接進入狀態(tài) t而不移動輸入指針。 2020/11/17 47 60 3T+εE :1 37F*εT :1 5(EF : 1 71 61 4)i d1 0圖 語法圖的化簡與實現(xiàn) ⑴ 左因子提取 將形如 A→YX|YZ的產(chǎn)生式替換為 A→Y(X|Z)； ⑵ 右因子提取 將形如 A→YX|ZX的產(chǎn)生式替換為 A→(Y|Z)X； ⑶ 尾遞歸消除 將形如 X→YX|Z的產(chǎn)生式替換為 X→Y*Z。 2020/11/17 48 ? Ｅ的子程序 (E→T(+T)*) procedure E。 begin T。 T的過程調(diào)用 while lookhead=39。+39。 do begin 當前符號等于 +時 match(‘+’)。 處理終結(jié)符 + T T的過程調(diào)用 end end。 lookhead：當前符號 例 簡單算術(shù)表達式的語法分析器 2020/11/17 49 Ｔ的子程序 (T→F(*F) *) procedure T。 begin F。 F的過程調(diào)用 while lookhead=39。*39。 then begin 當前符號等于 *時 match(‘*’)。 處理終結(jié)符 * F F的遞歸調(diào)用 end end。 2020/11/17 50 Ｆ的子程序 (F→(E)|id) procedure F。 begin if lookhead=39。(39。 then begin 當前符號等于（ match(39。(39。)。 處理終結(jié)符（ E。 Ｅ的遞歸調(diào)用 match(39。)39。)。 處理終結(jié)符） end else if lookhead=id then match(id) 處理終結(jié)符 id else error 出錯處理 end 2020/11/17 51 主程序 begin lookhead:=nexttoken。 調(diào)詞法分析程序 E Ｅ的過程調(diào)用 end procedure match(t:token)。 begin if lookhead=t then lookhead:=nexttoken else error 出錯處理程序 end。 服務(wù)子程序 2020/11/17 52 遞歸子程序法的實現(xiàn)步驟 1) 構(gòu)造文法； 2) 改造文法：消除二義性、消除左遞歸、提取左因子； 3) 求每個候選式的 FIRST集和語法變量的 FOLLOW集； 4) 檢查 G是不是 LL(1) 文法，若 G不是 LL(1)文法，說明文法 G的復雜性超過了自頂向下方法的分析能力，需要附加新的“信息”； 5) 按照 LL(1)文法畫語法圖； 6) 化簡語法圖； 7) 按照語法圖為每個語法變量設(shè)置一個子程序。 2020/11/17 53 遞歸子程序法的優(yōu)缺點分析 ? 優(yōu)點： 1）直觀、簡單、可讀性好 2）便于擴充 ? 缺點： 1) 遞歸算法的實現(xiàn)效率低 2) 處理能力相對有限 3) 通用性差，難以自動生成 ? 從遞歸子程序法及 FIRST與 FOLLOW集看如何進一步用好當前的輸入符號？ 2020/11/17 54 本章小結(jié) 找輸入串的最左推導和最左歸約 、回溯問題、左遞歸引起的無窮推導問題，需對文法進行改造：消除二義性、消除左遞歸、提取公共左因子 3. LL(1)文法是一類可以進行確定分析的文法，利用 FIRST集和 FOLLOW集可以判定某個上下文無關(guān)文法是否為 LL(1)文法 2020/11/17 55 本章小結(jié) 4. LL(1)文法可以用 LL(1)分析法進行分析。 5. 遞歸下降分析法根據(jù)各個候選式的結(jié)構(gòu)為每個非終結(jié)符編寫一個子程序。 6. 使用語法圖可以方便地進行遞歸子程序的設(shè)計。
教學課件相關(guān)推薦
鄂ICP備17016276號-1