【正文】 器目 標 程 序源 程 序 目 標 程 序輸 入 數(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ī)則識別輸入序列，稱為 詞法分析 。《 編譯原理 》 復習 延安大學計算機學院 郝繼升 2 課程內(nèi)容 要求（希望） 1. 牢固掌握基本概念 2. 靈活使用基本方法 3. 歸納總結(jié)所學內(nèi)容（鍛煉提高抽象能力） 一、引言 二、詞法分析 三、語法分析 四、語義分析 —語法制導翻譯生成中間代碼 學習不能走捷徑，付出多少勞動就有多少收獲。 掌握正確的學習方法，學會聯(lián)想與歸納總結(jié)。 主要內(nèi)容： 1 記號、模式與單詞 2 記號的說明－模式的形式化描述（正規(guī)式與正規(guī)集） 3 記號的識別－有限自動機 4 從正規(guī)式到詞法分析器 詞法分析器的作用： ? 濾掉源程序中的無用成分； ? 處理與具體操作系統(tǒng)或機器有關的輸入； ? 識別記號并交給語法分析器； ? 調(diào)用符號表管理器和出錯處理器進行相關處理。 4 從正規(guī)式到詞法分析器 ? 構(gòu)造 NFA的 Thompson算法 (與 NFA定義的對應關系 )； ? 模擬 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ū)別。語法分析也有雙重含義：根據(jù)一定的規(guī)則構(gòu)成語言的各種結(jié)構(gòu)，即 語法規(guī)則 ；根據(jù)語法規(guī)則識別輸入序列（記號流）中的語言結(jié)構(gòu)，即 語法分析 。 主要內(nèi)容 1 程序設計語言與文法 2 有關推導的基本概念 3 自上而下分析 4 自下而上分析 11 1 程序設計語言與文法 ? 正規(guī)式與正規(guī)文法： 正規(guī)式與正規(guī)文法用于描述線性結(jié)構(gòu)，如構(gòu)成句子的記號 (終結(jié)符 )；識別正規(guī)語言的自動機是有限自動機，它們的特征是沒有記憶能力； ? 上下文無關文法 (CFG=(N, T, S, P))： CFG用于描述層次結(jié)構(gòu)，如構(gòu)成程序的句子；識別 CFL的自動機是下推自動機，它是在有限自動機的基礎上增加了一個下推棧，從而有了簡單的記憶能力； ? 文法的分類： 0型、 1型、 2型和 3型文法 ? 詞法分析器與語法分析器：FA與 PDA 驅(qū) 動 器輸 入 記 號 流輸 出i p分 析 表下推棧top12 2 有關推導的基本概念 1. CFG產(chǎn)生語言的基本方法－推導： 從文法的開始符號開始，反復地用產(chǎn)生式的右部替換句型中的非終結(jié)符。 5. 二義性的消除： ? 改寫二義文法為非二義文法； ? 對文法符號施加優(yōu)先級與結(jié)合性的限制，使得分析的每一步有唯一選擇。 14 4 自下而上分析 1. 分析方法： 歸約 (推導的逆過程 )，從葉子到根構(gòu)造分析樹； 2. 基本概念： 短語、直接短語、句柄、歸約、規(guī)范歸約； 3. 采用的方法 : 用移進 歸約方法實現(xiàn)剪句柄（格局中的兩個關鍵動作），關鍵問題是如何確定棧頂已經(jīng)形成句柄，當句柄形成時，如何判定采用哪個產(chǎn)生式進行規(guī)約； 4. 識別活前綴的 DFA： 活前綴與 LR(0)項目 (NFA狀態(tài) )，拓廣文法與子集法構(gòu)造 DFA； T → . T * F. . .αT → T . * FTT → T * . F*T → T * F .F? 一個產(chǎn)生式是一個識別活前綴的 NFA ? 一個 LR(0)項目是 NFA的一個狀態(tài) 15 4 自下而上分析（續(xù)） 5. DFA分析輸入序列： 有效項目、可移進項目、可規(guī)約項目、移進 /歸約沖突、歸約 /歸約沖突；解決沖突的方法－SLR(1)：簡單向前看一個終結(jié)符（計算歸約項非終結(jié)符的FOLLOW，與可移進終結(jié)符比較）； 6. 移進 歸約分析表： 動作表＋轉(zhuǎn)移表； 7. LR文法與 LR分析： LR(0)、 SLR(1)、 LALR(1)、 LR(1)。 與前兩章詞法分析和語法分析不同的是 ， 詞法分析和語法分析的討論側(cè)重于理論 ， 而本章則側(cè)重于結(jié)合程序設計語言的實際例子討論語言結(jié)構(gòu)的具體翻譯方法和一些實用的技術 。 18 3 聲明語句的翻譯 1. 定義與聲明：類型定義與變量聲明，過程定義與過程聲明 2. 變量聲明：符號表信息的填寫 3. 過程聲明： ? 左值與右值 ? 參數(shù)傳遞：參數(shù)傳遞的不同形式 ? 名字的作用域：靜態(tài)作用域與最近嵌套原則 ? 聲明中作用域信息的保存 1. 符號表的條目與信息的存儲（關鍵字＋內(nèi)容） 2. 作用域信息的保存（棧結(jié)構(gòu)） 3. 線性表與散列表 2 符號表的組織 19 4 可執(zhí)行語句的翻譯 1. 簡單算術表達式和賦值句的翻譯：語法制導翻譯的設計，類型轉(zhuǎn)換； 2. 數(shù)組元素的引用：數(shù)組元素地址計算的遞推公式，地址的可變部分與不變部分，可變部分計算的語法制導翻譯； 3. 布爾表達式短路計算的翻譯：為什么需要短路計算，短路計算的控制流，真出口與假出口，真值鏈與假值鏈； 4. 控制語句的翻譯：控制語句的分類，無條件轉(zhuǎn)移與條件轉(zhuǎn)移，拉鏈 /回填技術； 習題與試題 ? 認真復習，重點是掌握基本概念。 ? 習題與試題的目的區(qū)別：習題的目的是通過反復的練習理解、掌握所學知識，會有不少繁、難、大量步驟的題；試題的目的是考察對本課程綜合掌握的情況，特點是短時間內(nèi)覆蓋大量內(nèi)容。 ? 自己要會辨別什么是主要的什么是次要的，抓什么丟什么。 ? 總之一句話，學習方法的掌握是個人努力的結(jié)果，單純靠別