編譯原理知識點匯總

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

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

2.匯編程序：把匯編語言程序翻譯成等價的機器語言程序3.編譯程序：把高級語言程序翻譯成等價的低級語言程序

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

翻譯執(zhí)行方式：翻譯程序，把程序設(shè)計語言程序翻譯成等價的目標程序

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

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

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

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

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

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

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

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

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

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

編譯前端的工作包括詞法分析、語法分析、語義分析。編譯前端只依賴于源程序，獨立于目標計算機。前端進行分析

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

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

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

第二章

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

運算XY，Xn，2.符號串集合的概念，符號串集合的乘積運算，方冪運算，閉包與正閉包的概念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定義重點是正則文法和上下文無關(guān)文法

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

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

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

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

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

1.詞法分析的功能P69

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

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

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

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

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

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

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

分析程序的大致思路

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

第四章自頂向下（重點是預(yù)測分析表的構(gòu)造和應(yīng)用預(yù)測分析表進行字符串分析）1.帶回溯的自頂向下分析方法P121（一般采用最左或者最右推導(dǎo)）

2.無回溯的自頂向下分析方法：條件，無左遞歸性，無回溯性。

3.預(yù)測分析技術(shù)：消去文法左遞歸P51；構(gòu)造first集合和follow集合P138，構(gòu)造預(yù)測分

析表P139進行字符串分析P134

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

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

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

2.分析需要解決的兩個基本問題：找出要被歸約的短語u；確定歸約到哪個非終結(jié)符號U3.一個符號串的前綴是指該串的任一部分。一個規(guī)范句型的前綴若不含句柄之后的任何符

號就稱為活前綴

4.基本方法：移入規(guī)約法P147四個動作之一：移進歸約接受出錯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)生式最右端的項目稱為可歸約項，如E→E+T；圓點后面是終結(jié)符的項目稱為移進項，如E→E+T；圓點后面是非終結(jié)符的項目稱為待約項，如E→E+T。項，項集，項集的閉包

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

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

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

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

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

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

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

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

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

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

擴展閱讀：編譯原理知識點匯總

編譯原理知識點匯總

第一章：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第二章：（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．文法等價的定義16．文法的四種類型：

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

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

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

第四章：

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

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

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

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

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

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

4．正規(guī)式與有窮自動機的等價變換。記住幾個變換規(guī)則，參考例4.10、4.5．正規(guī)文法與有窮自動機的等價變換。參考例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）文法等價變換的兩種情況：7．引起回溯的幾種情況：二．分析解答題：（10）

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

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

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

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

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

3．自底向上優(yōu)先分析法有簡單優(yōu)先分析法和算法優(yōu)先分析法兩種4．簡單優(yōu)先分析法和算符優(yōu)先分析法的特點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)于《編譯原理知識點匯總》給出的范例僅供您參考拓展思維使用，編譯原理知識點匯總：該篇文章建議您自主創(chuàng)作。

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

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

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