編譯原理知識點(diǎn)匯總

編譯原理的復(fù)習(xí)提綱

1.編譯原理=形式語言+編譯技術(shù)

2.匯編程序：把匯編語言程序翻譯成等價(jià)的機(jī)器語言程序3.編譯程序：把高級語言程序翻譯成等價(jià)的低級語言程序

4.解釋執(zhí)行方式：解釋程序，逐個語句地模擬執(zhí)行

翻譯執(zhí)行方式：翻譯程序，把程序設(shè)計(jì)語言程序翻譯成等價(jià)的目標(biāo)程序

5.計(jì)算機(jī)程序的編譯過程類似，一般分為五個階段：詞法分析、語法分析、語義分析及中

間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成

詞法分析的任務(wù)：掃描源程序的字符串，識別出的最小的語法單位（標(biāo)識符或無正負(fù)號數(shù)等）

語法分析是：在詞法分析的基礎(chǔ)上的，語法分析不考慮語義。語法分析讀入詞法分析

程序識別出的符號，根據(jù)給定的語法規(guī)則，識別出各個語法結(jié)構(gòu)。

語義分析的任務(wù)是檢查程序語義的正確性，解釋程序結(jié)構(gòu)的含義，語義分析包括檢查變量是否有定義，變量在使用前是否具有值，數(shù)值是否溢出等。語法分析完成之后，編譯程序通常就依據(jù)語言的語義規(guī)則，利用語法制導(dǎo)技術(shù)把源程序翻譯成某種中間代碼。所謂中間代碼是一種定義明確、便于處理、獨(dú)立于計(jì)算機(jī)硬件的記

號系統(tǒng)，可以認(rèn)為是一種抽象機(jī)的程序

代碼優(yōu)化的主要任務(wù)是對前一階段產(chǎn)生的中間代碼進(jìn)行等價(jià)變換，以便產(chǎn)生速度快、空間小的目標(biāo)代碼

編譯的最后一個階段是目標(biāo)代碼生成，其主要任務(wù)是把中間代碼翻譯成特定的機(jī)器指令或匯編程序

編譯程序結(jié)構(gòu)包括五個基本功能模塊和兩個輔助模塊6.編譯劃分成前端和后端。

編譯前端的工作包括詞法分析、語法分析、語義分析。編譯前端只依賴于源程序，獨(dú)立于目標(biāo)計(jì)算機(jī)。前端進(jìn)行分析

編譯后端的工作主要是目標(biāo)代碼的生成和優(yōu)化后端進(jìn)行綜合。獨(dú)立于源程序，完全依賴于目標(biāo)機(jī)器和中間代碼。

把編譯程序分為前端和后端的優(yōu)點(diǎn)是：可以優(yōu)化配置不同的編譯程序組合，實(shí)現(xiàn)編譯重用，保持語言與機(jī)器的獨(dú)立性。

7.匯編器把匯編語言代碼翻譯成一個特定的機(jī)器指令序列

第二章

1.符號，字母表，符號串，符號串的長度計(jì)算P18，子符號串的含義，符號串的簡單

運(yùn)算XY，Xn，2.符號串集合的概念，符號串集合的乘積運(yùn)算，方冪運(yùn)算，閉包與正閉包的概念P19，

P20A0={ε}

3.重寫規(guī)則，簡稱規(guī)則。非終結(jié)符（Vn），終結(jié)符（Vt）的概念。

4.文法的概念。P23識別符號.P23文法的第一個重寫規(guī)則的左部符號為識別符號。BNF表示法P6

5.直接推導(dǎo)和直接規(guī)約，廣義推導(dǎo)廣義規(guī)約，P24最左推導(dǎo)，最右推導(dǎo)P626.句型和句子Ｐ26，短語，簡單短語，句柄Ｐ２６，Ｐ２７7.語言的定義Ｐ318.遞歸，左遞歸Ｐ9.文法的形式化定義Ｐ36定義重點(diǎn)是正則文法和上下文無關(guān)文法

0型文法，短語結(jié)構(gòu)語言

１型文法，上下文有關(guān)文法CSG2型文法，上下文無關(guān)文法CFG3型文法，正則文法RG

3型語言類（2型語言類（1型語言類（0型語言類但四種語言之間沒有必然的包含關(guān)系P383型語言的定義有窮狀態(tài)自動機(jī)P412型語言下推自動機(jī)1型語言線性界限自動機(jī)0型語言圖靈機(jī)10.消去規(guī)則左遞歸P51

11.語法分析樹的構(gòu)造，能夠根據(jù)語法書來尋找短語，直接短語，句柄。12.文法的二義性問題P58，文法的二義性是不可判定的

-------------------------------第三章

1.詞法分析的功能P69

2.詞法分析器可以有兩種實(shí)現(xiàn)模式：完全融合模式（大多采用）和相對獨(dú)立模式，完全獨(dú)立方式P71

3.有窮狀態(tài)自動機(jī)的概念，如何從正則文法構(gòu)造有窮狀態(tài)轉(zhuǎn)換自動機(jī)P724.5.6.7.

如何從有窮狀態(tài)轉(zhuǎn)換自動機(jī)構(gòu)造正則文法P75

確定有窮狀態(tài)自動機(jī)DFA五元組（K，Σ，M，S，F(xiàn)），五個字母的含義。P75非確定有窮狀態(tài)自動機(jī)NFA，如何將NFA轉(zhuǎn)化為DFAP82DFA的化簡

8.屬性字由符號類和符號值組成。特定符號類，一個符號類對應(yīng)一個符號值：關(guān)鍵字、括

號，運(yùn)算符。非特定符號類：標(biāo)示符，無符號整數(shù)。符號類識別不同類的符號，符號值識別同類的不同符號P90

9.字符表，符號機(jī)內(nèi)表示對照表，標(biāo)示符表，無符號整數(shù)表各自的定義和作用P93詞法

分析程序的大致思路

------------------------------

第四章自頂向下（重點(diǎn)是預(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ù)測分

析表P139進(jìn)行字符串分析P134

-------------------------------------

第五章自底向上（重點(diǎn)是構(gòu)造算符優(yōu)先矩陣并進(jìn)行字符串的分析）

1.規(guī)范分析：最右推導(dǎo)被稱為規(guī)范推導(dǎo)，最左規(guī)約被稱為規(guī)范規(guī)約。P145

2.分析需要解決的兩個基本問題：找出要被歸約的短語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)）:

圓點(diǎn)在產(chǎn)生式最右端的項(xiàng)目稱為可歸約項(xiàng)，如E→E+T；圓點(diǎn)后面是終結(jié)符的項(xiàng)目稱為移進(jìn)項(xiàng)，如E→E+T；圓點(diǎn)后面是非終結(jié)符的項(xiàng)目稱為待約項(xiàng)，如E→E+T。項(xiàng)，項(xiàng)集，項(xiàng)集的閉包

--------------------------------------------

第六章（重點(diǎn)是四元式、逆波蘭式、抽象語法分析樹（三元式）)

1.語義分析的基本功能：確定類型；類型檢查；識別含義，作相應(yīng)的語意處理；其他一些

靜態(tài)語義檢查。P215

2.語義分析以語法分析部分的輸出（語法分析樹或其他等價(jià)內(nèi)部中間表示）為輸入，輸出

中間表示代碼，甚至目標(biāo)代碼。P2153.語義是上下文相關(guān)的4.語法制導(dǎo)翻譯技術(shù)5.抽象語法樹P2976.逆波蘭式P3007.四元組P306

-------------------------------------------------第七章

1.代碼優(yōu)化的定義P348，代碼優(yōu)化進(jìn)行的是等價(jià)變換，為優(yōu)化進(jìn)行努力是值得的。2.基本塊的概念，對基本塊的優(yōu)化：合并常量計(jì)算，消除公共子表達(dá)式，消減計(jì)算強(qiáng)度，

刪除無用代碼。對循環(huán)的優(yōu)化：循環(huán)不變表達(dá)式外提，歸納變量刪除，計(jì)算強(qiáng)度消減。3.代碼優(yōu)化的三個過程：控制流分析，數(shù)據(jù)流分析，變化。P350各自的含義4.代碼優(yōu)化是基于中間表示代碼進(jìn)行的

5.窺孔優(yōu)化：定義P395包括：四種典型優(yōu)化，各自的含義、

擴(kuò)展閱讀：編譯原理知識點(diǎn)匯總

編譯原理知識點(diǎn)匯總

第一章：

一．基礎(chǔ)知識（10）

1．編譯程序是現(xiàn)代計(jì)算機(jī)系統(tǒng)的基本組成部分之一2．一個計(jì)算機(jī)系統(tǒng)中通常配置多個高級語言的編譯程序

3．在一個計(jì)算機(jī)系統(tǒng)中可為某些高級語言配置多個不同性能的編譯程序

4．編譯程序是一種語言翻譯程序，其功能是把一種語言編寫的程序翻譯成另一種語言的等價(jià)程序

5．被編譯的程序稱為源程序，編譯后的等價(jià)程序稱為目標(biāo)程序6．編譯程序的任務(wù)就是將源語言程序翻譯成等價(jià)的目標(biāo)語言程序

7．通常將編譯過程分為六個階段：詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化和目標(biāo)代碼生成。

8．詞法分析的主要任務(wù)是從左至右掃描字符序列，并按照此法規(guī)則識別出一個個的單詞9．單詞是指邏輯上緊密相連的一組字符，這些字符具有集體含義。

10．計(jì)算機(jī)語言中，單詞的種類通常有保留字、標(biāo)識符、數(shù)、算符、界符等

11．語法分析的主要任務(wù)是：按照語言的語法規(guī)則，把詞法分析所得的單詞序列分解成各類語法成分。

12．詞法分析和語法分析都是對源程序進(jìn)行結(jié)構(gòu)分析，但二者是有區(qū)別的。

13．語義分析的主要功能是審查源程序有無語義錯誤，偽代碼生成階段收集類型信息。14．中間代碼生成階段的主要任務(wù)是，把源程序轉(zhuǎn)換成一種中間代碼15．中間代碼是一種結(jié)構(gòu)簡單、含義明確的記號系統(tǒng)

16．中間代碼可以設(shè)計(jì)成多種形式，其設(shè)計(jì)原則有兩點(diǎn)：一是容易生成，二是容易轉(zhuǎn)換成目標(biāo)代碼

17．代碼優(yōu)化的主要任務(wù)是對中間代碼進(jìn)行改造，使生成的目標(biāo)代碼更為高效18．目標(biāo)代碼生成階段的任務(wù)是把中間代碼轉(zhuǎn)換成特定機(jī)器上的絕對指令代碼或者可重定位的指令代碼或者匯編指令代碼

19．在編譯過程的每個階段中都含有出錯處理和表格管理的工作

20．編譯程序的結(jié)構(gòu)可以按功能分為八個模塊，即詞法分析程序、語法分析程序、語義分析程序、中間代碼生成程序、代碼優(yōu)化程序和目標(biāo)代碼生成程序，此外還有與上述每個階段都有關(guān)系的出錯處理程序和表格管理程序。21．按照編譯程序的工作主要是與源語言有關(guān)還是與目標(biāo)機(jī)有關(guān)，編譯過程也可前端和后端22．前端的工作主要依賴于源語言而與目標(biāo)機(jī)無關(guān)，包括詞法分析、語法分析、語義分析、中間代碼生成以及每個階段中的出錯處理和表格管理工作，還包括代碼優(yōu)化階段的部分工作23．后端的工作主要與目標(biāo)機(jī)有關(guān)而與源語言無關(guān)，主要是代碼生成及相關(guān)的出錯處理和表格管理工作24．編譯過程中，對源程序或者中間語言程序從頭至尾掃描一次并完成相應(yīng)工作的過程稱為“一遍”或者“一趟”

25．解釋程序是另一種語言處理程序，其工作特點(diǎn)是邊分析邊執(zhí)行，不生成目標(biāo)代碼。

第二章：（2）

1．終結(jié)符：構(gòu)成語言文法的單詞，是語法成分的最小單位

2．非終結(jié)符：是由終結(jié)符和非終結(jié)符串或者終結(jié)符串構(gòu)成的語法成分3．終結(jié)符和非終結(jié)符都是語法成分第三章：

一．基礎(chǔ)知識（10）

1．文法，是用有窮集合描述無窮集合的一個工具

2．字母表，是元素的非空有窮集合，表中的元素稱為符號，因此也叫符號集3．符號串，是由字母表中的符號組成的任何有窮序列4．符號串的長度

5．符號串的頭和尾，固有頭和固有尾6．符號串的連接7．符號串的方冪8．符號串集合的乘積9．閉包與正閉包

10．文法的形式定義：G=（VN，VT，P，S），其中每個元素的含義是什么，VN和VT有何關(guān)系

11．推導(dǎo)，長度>=1的推導(dǎo)，長度>=0的推導(dǎo)12．句型的定義13．句子的定義14．語言的定義15．文法等價(jià)的定義16．文法的四種類型：

17．語法樹，也叫推導(dǎo)樹，它需滿足四個條件：18．最左推導(dǎo)，最右推導(dǎo)，規(guī)范推導(dǎo)19．文法的二義性

20．短語，直接短語，句柄

21．多余規(guī)則：有不可到達(dá)和不可中止兩種二．分析解答題：（20）習(xí)題1,2,3,4,5,6,8,11,13

第四章：

一．基礎(chǔ)知識（10）

1．詞法分析的工具有正規(guī)文法，正規(guī)式和有窮自動機(jī)三種，三者之間存在等價(jià)性2．正規(guī)式的定義，參考例4.23．正規(guī)式服從的代數(shù)規(guī)律：

4．正規(guī)式與正規(guī)文法的等價(jià)變換，表4.15．有窮自動機(jī)分為兩類：6．DFA的定義7．NFA的定義

8．每個NFA都可以確定化為一個等價(jià)的DFA9．有窮自動機(jī)的無用狀態(tài)有兩種情況：

10．有窮自動機(jī)中兩個狀態(tài)等價(jià)的條件有兩個：二．分析解答題：（20）

1．正規(guī)文法與正規(guī)式的等價(jià)變換。參考例4.3、4.42．畫出有窮自動機(jī)的狀態(tài)圖。參考例4.6、4.73．DFA化簡。例4.9

4．正規(guī)式與有窮自動機(jī)的等價(jià)變換。記住幾個變換規(guī)則，參考例4.10、4.5．正規(guī)文法與有窮自動機(jī)的等價(jià)變換。參考例4.12、4.136．習(xí)題：1(1)、4(b)只需最小化、7（只需消除多余規(guī)則）、8

第五章：

一．基礎(chǔ)知識（5）

1．開始符號集的定義（定義5.1）2．后跟符號集的定義（定義5.2）3．SELECT集合的定義（定義5.3）4．LL（1）文法的定義（即充要條件）5．LL（1）文法的含義

6．非LL（1）文法到LL（1）文法等價(jià)變換的兩種情況：7．引起回溯的幾種情況：二．分析解答題：（10）

1．判斷一個文法是否為LL（1）文法。參考例5.15.42．非LL（1）文法到LL（1）文法等價(jià)變換。

（1）提取左公因子，參考例5.6、5.7

（2）消除左遞歸，參考P88-89頁1）和2）3．習(xí)題：1（1,3），2（1,2），7（1,5）

第六-八章：（15）一．基礎(chǔ)知識（）

1．自底向上分析法也叫移進(jìn)-歸約分析法2．規(guī)范歸約是指自左向右的歸約

3．自底向上優(yōu)先分析法有簡單優(yōu)先分析法和算法優(yōu)先分析法兩種4．簡單優(yōu)先分析法和算符優(yōu)先分析法的特點(diǎn)5．算符優(yōu)先文法的基本概念（定義6.1,6.2,6.3）

6．LR分析法是自底向上分析法，其分析過程是一種規(guī)范歸約過程。二．分析解答題（）

1．求算符優(yōu)先關(guān)系。參考例6.3

2．求中間代碼（逆波蘭式、樹形表示、三元式和四元式）。參考教材8.3節(jié)例題及表8.113．習(xí)題：P122：1，4（都只需求出優(yōu)先關(guān)系即可）P202：1（1,3,5），

友情提示：本文中關(guān)于《編譯原理知識點(diǎn)匯總》給出的范例僅供您參考拓展思維使用，編譯原理知識點(diǎn)匯總：該篇文章建議您自主創(chuàng)作。

來源：網(wǎng)絡(luò)整理 免責(zé)聲明：本文僅限學(xué)習(xí)分享，如產(chǎn)生版權(quán)問題，請聯(lián)系我們及時刪除。

《編譯原理知識點(diǎn)匯總》由互聯(lián)網(wǎng)用戶整理提供,轉(zhuǎn)載分享請保留原作者信息,謝謝!
鏈接地址：http://m.seogis.com/gongwen/747406.html

• 上一篇：化工原理重點(diǎn)內(nèi)容綱要
• 下一篇：sql語句增刪改查