編譯原理復(fù)習(已修改)
2025-08-13 15:29 本頁面
【正文】 《 編譯原理 》 復(fù)習 西安電子科技大學 軟件工程研究所 劉 堅 2 課程內(nèi)容 一、引言 二、詞法分析 三、語法分析 四、語法制導(dǎo)翻譯生成中間代碼 五、運行環(huán)境 要求 ① 牢固掌握基本概念 ② 靈活使用基本方法 ③ 善于歸納總結(jié)（抽象能力） 3 第一章 引言 1 語言的翻譯 不同的翻譯形式：匯編 、 編譯 、 轉(zhuǎn)換 （ 預(yù)編譯 ） 、 逆向翻譯 翻譯方法： 編譯器目標程序源程序 目標程序輸入數(shù)據(jù) 輸出解釋器源程序輸入數(shù)據(jù)輸出4 2 編譯器的基本組成 詞法分析語法分析語義分析中間代碼生成代碼優(yōu)化目標代碼生成源程序目標代碼符號表管理出錯處理5 3 編譯器的分析－綜合模式 4 編譯器的掃描遍數(shù)與編譯器的編寫 編譯器分析（前端） 綜合（后端）語法/語義分析 代碼生成/優(yōu)化源程序 中間代碼 目標代碼6 第二章 詞法分析 對于單詞的識別，首先應(yīng)該有單詞形成的規(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)處理。 詞法分析器是編譯器與源程序打交道的唯一階段，可以被認為是編譯器的預(yù)處理階段，它有以下幾個重要作用： 7 1 記號、模式與單詞 ? 模式 （ pattern） ：規(guī)定單詞識別的規(guī)則 ? 記號 （ token） ：按照某模式識別出的一類單詞 （ 記號種類 ） ? 單詞 （ lexeme） ：被識別出的字符串本身 ? 詞法分析器的輸出：記號 =記號種類 +記號屬性 2 記號的說明－模式的形式化描述 ① 正規(guī)式與正規(guī)集： ? 正規(guī)式與正規(guī)集的定義（ 基本正規(guī)式、三個運算 ）； ? 正規(guī)式的等價（ 描述相同的集合 ）； ? 利用正規(guī)式的等價對正規(guī)式進行化簡（ 正規(guī)式的代數(shù)性質(zhì) ）。 ② 用正規(guī)式對模式進行形式化描述： ? 如何用正規(guī)式描述程序設(shè)計語言中常見的記號，如標識符、數(shù)字、運算符和分隔符等； ? 正規(guī)式的簡化形式以及輔助定義與規(guī)則。 8 3 記號的識別－有限自動機（ FA） ? NFA與 DFA的定義： M = (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)換圖等） 9 第三章 語法分析 語法分析是編譯器中的重要階段之一，可以認為是語法制導(dǎo)翻譯模式編譯器的核心。語法分析也有雙重含義：根據(jù)一定的規(guī)則構(gòu)成語言的各種結(jié)構(gòu)，即 語法規(guī)則 ；根據(jù)語法規(guī)則識別輸入序列（記號流）中的語言結(jié)構(gòu)，即 語法分析 。 語法分析的分析對象是組成語言的句子，句子具有層次結(jié)構(gòu)
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1