1、精選優(yōu)質(zhì)文檔-傾情為你奉上編譯原理的復(fù)習(xí)提綱1. 編譯原理=形式語言+編譯技術(shù)2. 匯編程序：把匯編語言程序翻譯成等價的機器語言程序3. 編譯程序：把高級語言程序翻譯成等價的低級語言程序4. 解釋執(zhí)行方式： 解釋程序，逐個語句地模擬執(zhí)行 翻譯執(zhí)行方式： 翻譯程序，把程序設(shè)計語言程序翻譯成等價的目標(biāo)程序5. 計算機程序的編譯過程類似，一般分為五個階段：詞法分析、語法分析、語義分析及中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成詞法分析的任務(wù)：掃描源程序的字符串，識別出的最小的語法單位（標(biāo)識符或無正負(fù)號數(shù)等）語法分析是：在詞法分析的基礎(chǔ)上的，語法分析不考慮語義。語法分析讀入詞法分析程序識別出的符號，根據(jù)給定

2、的語法規(guī)則，識別出各個語法結(jié)構(gòu)。語義分析的任務(wù)是檢查程序語義的正確性，解釋程序結(jié)構(gòu)的含義，語義分析包括檢查變量是否有定義，變量在使用前是否具有值，數(shù)值是否溢出等。語法分析完成之后，編譯程序通常就依據(jù)語言的語義規(guī)則，利用語法制導(dǎo)技術(shù)把源程序翻譯成某種中間代碼。所謂中間代碼是一種定義明確、便于處理、獨立于計算機硬件的記號系統(tǒng)，可以認(rèn)為是一種抽象機的程序代碼優(yōu)化的主要任務(wù)是對前一階段產(chǎn)生的中間代碼進(jìn)行等價變換，以便產(chǎn)生速度快、空間小的目標(biāo)代碼編譯的最后一個階段是目標(biāo)代碼生成，其主要任務(wù)是把中間代碼翻譯成特定的機器指令或匯編程序編譯程序結(jié)構(gòu)包括五個基本功能模塊和兩個輔助模塊6. 編譯劃分成前端和后端。

3、編譯前端的工作包括詞法分析、語法分析、語義分析。編譯前端只依賴于源程序，獨立于目標(biāo)計算機。前端進(jìn)行分析編譯后端的工作主要是目標(biāo)代碼的生成和優(yōu)化后端進(jìn)行綜合。獨立于源程序，完全依賴于目標(biāo)機器和中間代碼。把編譯程序分為前端和后端的優(yōu)點是：可以優(yōu)化配置不同的編譯程序組合，實現(xiàn)編譯重用，保持語言與機器的獨立性。7. 匯編器把匯編語言代碼翻譯成一個特定的機器指令序列第二章1. 符號，字母表，符號串，符號串的長度計算 P18，子符號串的含義，符號串的簡單運算XY ，Xn，2. 符號串集合的概念，符號串集合的乘積運算，方冪運算，閉包與正閉包的概念 P19，P20 A0 =3. 重寫規(guī)則，簡稱規(guī)則。非終結(jié)符（

4、Vn），終結(jié)符（Vt）的概念。4. 文法的概念。P23 識別符號.P23 文法的第一個重寫規(guī)則的左部符號為識別符號。BNF表示法 P65. 直接推導(dǎo)和直接規(guī)約，廣義推導(dǎo)廣義規(guī)約，P24 最左推導(dǎo)，最右推導(dǎo)P626. 句型和句子 26，短語，簡單短語，句柄，7. 語言的定義318. 遞歸，左遞歸32 9. 文法的形式化定義36定義 重點是正則文法和上下文無關(guān)文法0型文法，短語結(jié)構(gòu)語言型文法，上下文有關(guān)文法 CSG2型文法，上下文無關(guān)文法 CFG3型文法，正則文法RG3型語言類（2型語言類（1型語言類（0型語言類但四種語言之間沒有必然的包含關(guān)系 P383型語言的定義 有窮狀態(tài)自動機 P412型語言

5、 下推自動機1型語言 線性界限自動機0型語言 圖靈機10. 消去規(guī)則左遞歸P5111. 語法分析樹的構(gòu)造，能夠根據(jù)語法書來尋找短語，直接短語，句柄。12. 文法的二義性問題P58，文法的二義性是不可判定的-第三章1. 詞法分析的功能 P692. 詞法分析器可以有兩種實現(xiàn)模式：完全融合模式（大多采用）和相對獨立模式，完全獨立方式 P713. 有窮狀態(tài)自動機的概念，如何從正則文法構(gòu)造有窮狀態(tài)轉(zhuǎn)換自動機 P724. 如何從有窮狀態(tài)轉(zhuǎn)換自動機構(gòu)造正則文法P755. 確定有窮狀態(tài)自動機DFA五元組（K，M，S，F(xiàn)），五個字母的含義。P756. 非確定有窮狀態(tài)自動機NFA，如何將NFA轉(zhuǎn)化為DFA P82

6、7. DFA的化簡8. 屬性字由符號類和符號值組成。特定符號類，一個符號類對應(yīng)一個符號值：關(guān)鍵字、括號，運算符。非特定符號類：標(biāo)示符，無符號整數(shù)。符號類識別不同類的符號，符號值識別同類的不同符號 P909. 字符表，符號機內(nèi)表示對照表，標(biāo)示符表，無符號整數(shù)表各自的定義和作用P93 詞法分析程序的大致思路-第四章 自頂向下（重點是預(yù)測分析表的構(gòu)造和應(yīng)用預(yù)測分析表進(jìn)行字符串分析）1. 帶回溯的自頂向下分析方法P121 （一般采用最左或者最右推導(dǎo)）2. 無回溯的自頂向下分析方法：條件，無左遞歸性，無回溯性。3. 預(yù)測分析技術(shù)：消去文法左遞歸P51；構(gòu)造first集合和follow集合P138，構(gòu)造預(yù)

7、測分析表P139 進(jìn)行字符串分析 P134-第五章 自底向上（重點是構(gòu)造算符優(yōu)先矩陣并進(jìn)行字符串的分析）1. 規(guī)范分析：最右推導(dǎo)被稱為規(guī)范推導(dǎo)，最左規(guī)約被稱為規(guī)范規(guī)約。 P1452. 分析需要解決的兩個基本問題：找出要被歸約的短語u；確定歸約到哪個非終結(jié)符號U3. 一個符號串的前綴是指該串的任一部分。一個規(guī)范句型的前綴若不含句柄之后的任何符號就稱為活前綴4. 基本方法：移入規(guī)約法 P147 四個動作之一：移進(jìn)歸約接受出錯5. 算符優(yōu)先分析技術(shù)： P150 定義5.2 構(gòu)造算符優(yōu)先關(guān)系表 P151-154 算符優(yōu)先識別算法6. LR(k)分析技術(shù),要知道其中定義（為什么引入LR(K)）:圓點在產(chǎn)

8、生式最右端的項目稱為可歸約項，如EE+T· ；圓點后面是終結(jié)符的項目稱為移進(jìn)項 ，如EE·+T ； 圓點后面是非終結(jié)符的項目稱為待約項 ， 如EE+·T。項，項集，項集的閉包-第六章（重點是四元式、逆波蘭式、抽象語法分析樹（三元式）)1. 語義分析的基本功能：確定類型；類型檢查；識別含義，作相應(yīng)的語意處理；其他一些靜態(tài)語義檢查。 P2152. 語義分析以語法分析部分的輸出（語法分析樹或其他等價內(nèi)部中間表示）為輸入，輸出中間表示代碼，甚至目標(biāo)代碼。 P2153. 語義是上下文相關(guān)的4. 語法制導(dǎo)翻譯技術(shù)5. 抽象語法樹 P2976. 逆波蘭式 P3007. 四元組P306-第七章1. 代碼優(yōu)化的定義 P348 ，代碼優(yōu)化進(jìn)行的是等價變換，為優(yōu)化進(jìn)行努力是值得的。2. 基本塊的概念， 對基本塊的優(yōu)化：合并常量計算，消除公共子表達(dá)式，消減計算強度，刪除無用代碼