【正文】 2022年 2月 16日 編 譯 原 理 語義分析、生成中間代碼 生成目標程序 代碼優(yōu)化 語法分析程序 詞法分析程序 錯 誤 處 理 符 號 表 管 理 2022年 2月 16日 編 譯 原 理 第 4章 語法分析 1. 要求明確語法分析在編譯過程所處的 階段和作用 。 2. 明確語法分析的 基本分析方法 。 3. 掌握 句柄、最左素短語、活前綴和項目 等基本概念。 4. 掌握 消除文法左遞歸 的方法。 5. 掌握構(gòu)造 LL(1)分析表 的方法，會使用 LL(1)分析法 分析句子。 6. 掌握構(gòu)造 優(yōu)先關(guān)系表 的方法，會使用 算符優(yōu)先分析法分析句子。 7. 掌握構(gòu)造 LR(0)、 SLR(1)分析表 的方法，會使用 LR分析法 分析句子。 教學目標 2022年 2月 16日 編 譯 原 理 ? 語法分析的任務 ? 自頂向下分析法 ? 自底向上分析法 ? 算符優(yōu)先分析法 ? LR分析法 教學內(nèi)容 2022年 2月 16日 編 譯 原 理 任務： 根據(jù)文法規(guī)則，從源程序單詞符號串中識別出語法 成分，并進行語法檢查。 兩大類分析方法： 自頂向下分析 自底向上分析 語法分析的任務 2022年 2月 16日 編 譯 原 理 + 若 x?S 則 x?L(G[S]) 否則 x?L(G[S]) G[S] 存在主要問題 : 回溯問題 ,左遞歸問題 主要方法： 遞歸子程序法、 LL分析法 自頂向下分析算法的基本思想為： 自底向上分析算法的基本思想為： + 若 x?S 則 x?L(G[S]) 否則 x?L(G[S]) G[S] 存在主要問題 :“可歸約串”的識別問題 主要方法： 算符優(yōu)先分析法、 LR分析法 2022年 2月 16日 編 譯 原 理 自頂向下分析法 自頂向下分析的一般過程 從 S出發(fā)采用最左推導，試圖逐步推出輸入串 α,α ?L(G[S])? S作為語法樹的根，試圖自上而下地為 α 構(gòu)造一棵語法樹 ?若葉結(jié)點從左向右排列恰好 α ，則表示 α 是文法的句子，而這棵語法樹就是句子 α 的語法結(jié)構(gòu) ?若構(gòu)造不出語法樹，則 α 不是文法的句子 2022年 2月 16日 編 譯 原 理 【 例 】 α =acb G[S]: S→ aAb A→ cd|c 分析過程是設(shè)法建立一 棵語法樹 ,使語法樹的末端結(jié) 點與給定符號串相匹配 . :令 S為根結(jié)點 S S的右部 ,符號串去匹配輸入串 S a A b 完成一步推導 S?aAb 檢查 aa匹配 A是非終結(jié)符 ,將匹配任務交給 A 2022年 2月 16日 編 譯 原 理 A的右部符號串匹配輸入串 A有兩個右部 ,選第一個 a A b c d S 完成進一步推導 A?cd 檢查 ,cc匹配 ,bd不匹配 (失敗 ) 但是還不能冒然宣布 α ?L(G[S]) 即砍掉 A的子樹 改選 A的第二右部 S a A b c A?c 檢查 cc匹配 bb匹配 建立語法樹 ,末端結(jié)點為 acb與輸入 acb相匹配 , 建立了推導序列 S?aAb?acb ∴ acb?L(G[S]) α =acb G[S]: S→ aAb A→ cd|c 2022年 2月 16日 編 譯 原 理 自頂向下分析方法分類 確定的 不確定的 回溯 2022年 2月 16日 編 譯 原 理 什么是回溯（ backtracking） ? 分析工作要部分地或全部地退回去重做叫 回溯 造成回溯的條件： 文法中，對于某個非終結(jié)符號的 規(guī)則其右部 有多個選擇 ，并根據(jù)所面臨的輸入符號不能準確 地確定所要的選擇時，就可能出現(xiàn)回溯。 回溯帶來的問題： 嚴重的 低效率 ，只有在理論上的意義而無實際意義 自頂向下分析存在的主要問題 2022年 2月 16日 編 譯 原 理 迷宮求解 2022年 2月 16日 編 譯 原 理 效率低的原因 1)語法分析要重做 2)語義處理工作要推倒重來 2022年 2月 16日 編 譯 原 理 消除回溯的途徑： 改寫文法 對具有多個右部的規(guī)則 反復 提取 左因子 【 例 】 對下述兩個產(chǎn)生式，提取公共左因子改造文法。 if語句 →if E then S1 else S2 if語句 → if E then S1 if語句 →if E then S1 U U→ else S2 |ε 2022年 2月 16日 編 譯 原 理 A→ αβ1|αβ2|…| αβn 如果 β1~βn中還有幾個首符號相同，可反復提取 引入了許多非終結(jié)符和 ε 產(chǎn)生式 A→ α A′ A′ → β 1|β 2|… |β n 2022年 2月 16日 編 譯 原 理 【 例 】 文法 G[E]： E→E+T|T T→T*F|F F→(E)|i 給出 i*i+i自頂向下的分析過程。 左遞歸文法會使自頂向下分析法陷入死循環(huán) 如果文法具有間接左遞歸，則也將發(fā)生上述問題，只不過循環(huán)的圈子兜的更大 要實行自頂向下分析，必須要消除文法的左遞歸 從左向右掃描源程序，同時實施最左推導 2022年 2月 16日 編 譯 原 理 （ 1） 消除直接左遞歸 方法一：使用 EBNF表示來 改寫文法 【 例 】 文法 G[E]： E→E+T|T T→T*F|F F→(E)|i E→ T{+T} T→ F{*F} F→(E)|i A→ ? |A? 規(guī)則一 A → ?{?} 花括號 { } 表示符號串 x出現(xiàn)零次或多次。 2022年 2月 16日 編 譯 原 理 【 例 】 文法 G[E]： E→E+T| E T|T T→T*F| T/F|F F→(E)|i E→ T{(+|?)T} T→ F{(*|/)F} F→(E)|i A→ A ? |A ? 規(guī)則二 A → A(?|?) 圓括號（ ） 利用圓括號可提出一個非終結(jié)符的多個產(chǎn)生式右部的公共因子。 2022年 2月 16日 編 譯 原 理 【 例 】 條件語句 →if 布爾表達式 語句 | if布爾表達式 語句 ； else 語句 條件語句 →if 布爾表達式 語