【正文】 《 編譯原理 》 復(fù)習(xí) 延安大學(xué)計算機學(xué)院 郝繼升 2 課程內(nèi)容 要求（希望） 1. 牢固掌握基本概念 2. 靈活使用基本方法 3. 歸納總結(jié)所學(xué)內(nèi)容（鍛煉提高抽象能力） 一、引言 二、詞法分析 三、語法分析 四、語義分析 —語法制導(dǎo)翻譯生成中間代碼 學(xué)習(xí)不能走捷徑，付出多少勞動就有多少收獲。 掌握正確的學(xué)習(xí)方法，學(xué)會聯(lián)想與歸納總結(jié)。 3 第一章 引言 1 語言的翻譯 不同的翻譯形式： 匯編 、 編譯 、 轉(zhuǎn)換 （ 預(yù)編譯 ） 、 逆向翻譯 翻譯方法： 編 譯 器目 標 程 序源 程 序 目 標 程 序輸 入 數(shù) 據(jù)輸 出解 釋 器源 程 序輸 入 數(shù) 據(jù)輸 出4 2 編譯器的基本組成 詞 法 分 析語 法 分 析語 義 分 析中 間 代 碼 生 成代 碼 優(yōu) 化目 標 代 碼 生 成源 程 序目 標 代 碼符號表管理出錯處理5 3 編譯器的分析－綜合模式 4 編譯器的掃描遍數(shù)與編譯器的編寫 編 譯 器分 析 （ 前 端 ） 綜 合 （ 后 端 ）語 法 / 語 義 分 析 代 碼 生 成 / 優(yōu) 化源 程 序 中 間 代 碼 目 標 代 碼6 第二章 詞法分析 構(gòu)詞規(guī)則與詞法分析： 首先規(guī)定單詞形成的規(guī)則，稱為 構(gòu)詞規(guī)則 ；然后根據(jù)構(gòu)詞規(guī)則識別輸入序列，稱為 詞法分析 。 主要內(nèi)容： 1 記號、模式與單詞 2 記號的說明－模式的形式化描述（正規(guī)式與正規(guī)集） 3 記號的識別－有限自動機 4 從正規(guī)式到詞法分析器 詞法分析器的作用： ? 濾掉源程序中的無用成分； ? 處理與具體操作系統(tǒng)或機器有關(guān)的輸入； ? 識別記號并交給語法分析器； ? 調(diào)用符號表管理器和出錯處理器進行相關(guān)處理。 7 1 記號、模式與單詞 ? 模式 （ pattern） ：規(guī)定單詞識別的規(guī)則 ? 記號 （ token） ：按照某模式識別出的一類單詞 （ 記號種類 ） ? 單詞 （ lexeme） ：被識別出的字符串本身 ? 詞法分析器的輸出：記號 =記號種類 +記號屬性 2 記號的說明－模式的形式化描述 1. 正規(guī)式與正規(guī)集： ? 正規(guī)式與正規(guī)集的定義 (基本正規(guī)式、三個運算 ) ? 正規(guī)式的等價 (描述相同的集合 ) ? 利用正規(guī)式的等價對正規(guī)式進行化簡 (正規(guī)式的代數(shù)性質(zhì) ) 2. 用正規(guī)式形式化描述模式： ? 如何用正規(guī)式描述程序設(shè)計語言中常見的記號，如標識符、數(shù)字、運算符和分隔符等 ? 正規(guī)式的簡化形式以及輔助定義與規(guī)則 8 3 記號的識別－有限自動機（ FA） ? NFA與 DFA的定義： FA = (S, Σ, move, s0, F) ； ? NFA與 DFA的表示：定義表示、狀態(tài)轉(zhuǎn)換圖、狀態(tài)轉(zhuǎn)換矩陣； ? NFA與 DFA的關(guān)鍵區(qū)別： NFA的不確定性（當前狀態(tài)下，對同一字符可能有多于一個的下一狀態(tài)轉(zhuǎn)移）； ? 用 NFA識別輸入序列的弱點：嘗試所有路徑才能確定一個輸入不被接收、回溯帶來的問題； ? 模擬 DFA的算法：用 DFA識別記號。 4 從正規(guī)式到詞法分析器 ? 構(gòu)造 NFA的 Thompson算法 (與 NFA定義的對應(yīng)關(guān)系 )； ? 模擬 NFA的 “ 并行 ” 算法； ? 從 NFA構(gòu)造 DFA－子集法： smove(S, a)與 ε 閉包 (T)的計算； ? DFA的最小化－可區(qū)分的概念：所有不可區(qū)分的狀態(tài)看作是一個狀態(tài)； ? 靈活運用各種方法構(gòu)造 DFA(正規(guī)式化簡、狀態(tài)轉(zhuǎn)換圖等 )，特別是手工構(gòu)造和算法構(gòu)造的區(qū)別。 10 第三章 語法分析 語法分析是編譯器中的重要階段之一，可以認為是語法制導(dǎo)翻譯模式編譯器的核心。語法分析也有雙重含義：根據(jù)一定的規(guī)則構(gòu)成語言的各種結(jié)構(gòu)，即 語法規(guī)則 ；根據(jù)語法規(guī)則識別輸入序列（記號流）中的語言結(jié)構(gòu)，即 語法分析 。 語法分析的分析對象是組成語言的句子，句子具有層次結(jié)構(gòu)的特征，表征該結(jié)構(gòu)的最好方法是樹，從而使得對語法的分析就有了從根到葉子和從葉子到根兩種分析方法。 主要內(nèi)容 1 程序設(shè)計語言與文法 2 有關(guān)推導(dǎo)的基本概念 3 自上而下分析 4 自下而上分析 11 1 程序設(shè)計語言與文法 ? 正規(guī)式與正規(guī)文法： 正規(guī)式與正規(guī)文法用于描述線性結(jié)構(gòu)，如構(gòu)成句子的記號 (終結(jié)符 )；識別正規(guī)語言的自動機是有限自動機，它們的特征是沒有記憶能力； ? 上下文無關(guān)文法 (CFG=(N, T, S, P))： CFG用于描述層次結(jié)構(gòu)，如構(gòu)成程序的句子；識別 CFL的自動機是下推自動機，它是在有限自動機的基礎(chǔ)上增加了一個下推棧，從而有了簡單的記憶能力； ? 文法的分類： 0型、 1型、 2型和 3型文法 ? 詞法分析器與語法分析器：FA與 PDA 驅(qū) 動 器輸 入 記 號 流輸 出i p分 析 表下推棧top12 2 有關(guān)推導(dǎo)的基本概念 1. CFG產(chǎn)生語言的基本方法－推導(dǎo)： 從文法的開始符號開始，反復(fù)地用產(chǎn)生式的右部替換句型中的非終結(jié)符。 2. 推導(dǎo)的基本概念： 句子、直接推導(dǎo)、最左推導(dǎo)、左句型（最右推導(dǎo)、右句型）； 3. 分析樹與語法樹： 分析樹和語法樹都反映了語言結(jié)構(gòu)；分析樹還記錄了分析的過程（含有非終結(jié)符）； 4. 文法的二義性： 二義性的本質(zhì)是在文法中缺少對文法符號優(yōu)先級和結(jié)合性的限制，從而使得一個句子可以推導(dǎo)出多于一棵分析樹。 5. 二義性的消除： ? 改寫二義文法為非二義文法； ? 對文法符號施加優(yōu)先級與結(jié)合性的限制，使得分析的每一步有唯一選擇。 13 3 自上而下分析 1. 分析方法： 推導(dǎo)，從上到下構(gòu)造分析樹，是一種預(yù)測的、試探的方法； 2. 對文法的要求： 沒有公共左因子和左遞歸； 3. 遞歸下降子程序方法： 匹配終結(jié)符，展開非終結(jié)符（子程序調(diào)用） 4. 預(yù)測分析表方法 : ? 工作方式與過程： PDA（ DPDA） 、格局與改變格局的動作； ? 預(yù)測分析表的構(gòu)造： FIRST集合與 FOLLOW集合， FIRST與 FOLLOW的計算； ? LL(1)文法及其判別： 預(yù)測分析表中沒有多重定義條目（推論 ）。 14