編譯原理知識點總結(jié)

1、考試題型：填空24%+ 簡答 4*4=16%+ 解答 4*15=6chapter 1重要概念1. 什么編譯程序？ p3 答：編譯程序的主要功能是把用高級語言編寫的源程序翻譯為等價的目標(biāo)程序。2. 編譯程序的工作過程？（6 個階段） p41、詞法分析程序2 、語法分析程序3 、語義分析程序4 、中間代碼生成5、代碼優(yōu)化程序6 、目標(biāo)代碼生成（不做優(yōu)化是4 個階段， 5、6 不要）3. 編譯程序的邏輯結(jié)構(gòu)？ p4 圖 1-2 編譯程序的邏輯結(jié)構(gòu)4. 執(zhí)行高級語言編寫的程序：（編譯執(zhí)行、解釋執(zhí)行）1）按編譯方式在計算機(jī)上執(zhí)行用高級語言編寫的程序，一般須經(jīng)過兩個階段。第一個階段稱為編譯階段，其任務(wù)是由

2、編譯程序?qū)⒃闯绦蚓幾g為目標(biāo)程序，若目標(biāo)程序不是機(jī)器代碼，而是匯編語言程序，則尚需匯編程序再行匯編為機(jī)器代碼程序；第二階段稱為運行階段，其任務(wù)是在目標(biāo)計算機(jī)上執(zhí)行編譯階段所得到的目標(biāo)程序。2）用高級語言編寫的程序也可以通過解釋程序來執(zhí)行。解釋程序也以源程序作為它的輸入，它與編譯程序的主要區(qū)別是在解釋程序的執(zhí)行過程中不產(chǎn)生目標(biāo)程序，而是解釋執(zhí)行源程序本身。缺點：這種邊翻譯邊執(zhí)行的方式工作效率很低，但由于解釋程序的結(jié)構(gòu)比編譯程序簡單，且占用內(nèi)存較少，在執(zhí)行過程中也易于在源程序一級對程序進(jìn)行修改，因此一些規(guī)模較小的語言，如 basic ，也常采用此種方式。5.p11第一段編譯程序的各部分之間的關(guān)系，是

3、指他們之間的邏輯關(guān)系，而不一定是執(zhí)行時間上的先后順序，事實上，可按不同的執(zhí)行流程來組織上述各部分的工作，這在很大程度上依賴與編譯過程中對源程序掃描的遍數(shù)，以及如何劃分各遍掃描所進(jìn)行的工作。此處所說的“遍” ，是指對源程序或其內(nèi)部表示從頭到尾掃視一次，并進(jìn)行有關(guān)的加工處理工作。（執(zhí)行過程：單遍掃描、多遍掃描（大多數(shù)）chapter 2前后文無關(guān)文法和語言1. 文法和語言的形式定義產(chǎn)生語言就是制定出有限個規(guī)則（文法），借助于它們，就能產(chǎn)生出此語言的全部句子。2. 文法規(guī)則四要素:文法 : 四要素（ vn， vt， s，p）。1) 產(chǎn)生語言的規(guī)則中的一系列需定義的語法范疇的名字稱為非終結(jié)符號 ( 大

4、寫字母), 其集合記為vn2) 規(guī)則中不需進(jìn)一步定義的基本符號稱為終結(jié)符號 , 其集合記為vt3) 非終結(jié)符中最終需定義的那個為推導(dǎo)句子開始的語法范疇, 稱其為開始符號或識別符號,記作 s4) 每一規(guī)則是用:=或 -連接起來的有序?qū)? 也稱為產(chǎn)生式 , 用 p 表示 .3. 句型的分析是指構(gòu)造一種算法，用以判斷所給符號串是否為某一文法的句型( 或句子)。分兩類方法：自頂向下分析：從開始符推導(dǎo)出句子或句型自底向上分析：從句子或句型歸約出開始符4. 短語和句柄語法樹的應(yīng)用語法分析（自頂向下分析，自底向上分析）用語法樹進(jìn)行句型分析 : 用語法樹自頂向下進(jìn)行推導(dǎo),-最右推導(dǎo)用語法樹自底向上進(jìn)行歸約。-

5、 最左 規(guī)約5. 文法和語言的 chomsky 分類1） 0 型文法或短語結(jié)構(gòu)文法(psg)2） 1 型文法或前后文有關(guān)文法(csg)3） 2 型文法或前后文無關(guān)文法(cfg).4） 3 型文法或正規(guī)文法。（左線性文法+右線性文法）編譯過程的詞法分析使用正規(guī)文法（3 型文法）描述單詞結(jié)構(gòu)；語法分析采用前后文無關(guān)文法（2 型文法）描述語句結(jié)構(gòu)課堂練習(xí)1） chomsky 定義的四種形式語言文法分別為0 型文法， 1 型文法，2 型文法 , 3 型文法其中 3 型文法用于描述詞法，2 型文法用于描述語法。2）遞歸文法產(chǎn)生的語言語句集合是無限集合。3）規(guī)范推導(dǎo)是最右推導(dǎo)，規(guī)范歸約是最左歸約。定義每種

6、語言的文法都是不 （不 | ）唯一的。文法的化簡與改造主要包括無用符號和無用產(chǎn)生式的刪除, 產(chǎn)生式的消除, 單產(chǎn)生式的消除幾項內(nèi)容。大題： 1）畫出句子的語法樹，找出所有的短語，直接短語和句柄（運算符最低原則）,chapter3 詞法分析及詞法分析程序1）了解 6 種定義，特點正規(guī)文法、狀態(tài)轉(zhuǎn)換圖、有限自動機(jī) fa（ nfa、dfa）、狀態(tài)轉(zhuǎn)換矩陣、正規(guī)表達(dá)式、正規(guī)集大題：正規(guī)式狀態(tài)圖（ nfa ）確定化最小化順序：或，連接，閉包（）狀態(tài)轉(zhuǎn)換圖的五要素1）有限非空狀態(tài)集 k 2）有限輸入字母表3）狀態(tài)之間的映射關(guān)系 f 4）初態(tài) s0 k 5）終態(tài)集 z k （） 1. 確定的有限自動機(jī)（df

7、a ）若 fa 在每個狀態(tài)，對輸入符號的下一狀態(tài)是唯一的，稱此種fa 為確定的有限自動機(jī)dfa2. 非確定的有限自動機(jī)（ nfa ）若 fa 在某個狀態(tài)，對輸入符號的下一狀態(tài)不是唯一的，而是狀態(tài)集的一個子集，稱此種fa為非確定的有限自動機(jī)nfa。（3）正規(guī)式中用到符號：*閉包最優(yōu)（優(yōu)先順序可用括號加以改變）連接（不引起混亂可略去）次之|或最后正規(guī)式：將文法的終結(jié)符號用以上三種運算符連接起來組成的正規(guī)文法的表達(dá)式，是另一種用于描述正規(guī)文法的直觀表示。正規(guī)集：正規(guī)式所描述的字符串的集合。（4）詞法分析方法（正規(guī)文法、狀態(tài)轉(zhuǎn)換圖、狀態(tài)轉(zhuǎn)換矩陣）（5）單詞描述（正規(guī)文法、狀態(tài)轉(zhuǎn)換圖、有限自動機(jī) fa（

8、 nfa、 dfa ）、狀態(tài)轉(zhuǎn)換矩陣、正規(guī)表達(dá)式、正規(guī)集）課堂練習(xí)：1. 單詞的編譯器內(nèi)部表示為二元式（ class , value ）2. 單詞的描述形式有許多種，包括文法形式正規(guī)文法，圖示方式狀態(tài)轉(zhuǎn)換圖，便于計算機(jī)存儲的狀態(tài)轉(zhuǎn)換矩陣，自動機(jī)又分為nfa,dfa 兩種，正規(guī)表達(dá)式和正規(guī)集最便于體現(xiàn)單詞的結(jié)構(gòu)3.bell實驗室m.lesk等人用c 語言研制的一個詞法分析程序的自動生成工具叫l(wèi)ex4. 判斷（對）所有帶有 的自動機(jī)都是非確定的自動機(jī)chapter 4語法分析和語法分析程序1. 語法分析方法 :自頂向下分析法：如遞歸下降法，ll（ 1）等（最左推導(dǎo)）自底向上分析法：如算符優(yōu)先法（分

9、析表達(dá)式常用）， lr 等（最右規(guī)約）大題 lr、 slr1（ 1） ll（1）- 預(yù)測分析法（ ll（ 1）分析法最左推導(dǎo)ll（1）分析表）1)編寫文法，消除二義性；2)消除左遞歸、提取左因子；3)求 first 集和 follow 集first( ) : 可以推出的開頭的終結(jié)符號( 或 )follow(a): 在所有句型中可能直接跟在a 之后的終結(jié)符號4）檢查是不是ll(1)文法（若不是ll(1) ，說明文法的復(fù)雜性超過自頂向下方法的分析能力5） 按照 ll(1)文法構(gòu)造預(yù)測分析表6） 實現(xiàn)預(yù)測分析器）（ 2）算符優(yōu)先分析法( 構(gòu)造算符優(yōu)先矩陣分析句子)廣義運算符 :文法的終結(jié)符號廣義運算

10、對象:非終結(jié)符（3） lr（ 0）分析法a. 引入 s -s 拓廣文法b. 構(gòu)造識別所有規(guī)范句型全部的活前綴的dfac.構(gòu)造 lr（）分析表產(chǎn)生式編號d.分析句子（4） slr(1) 分析表課堂練習(xí)1、 ll（ 1）分析器由緩沖區(qū)， 分析棧，分析表，控制程序四部分組成。2、語法分析的方法主要分為自頂向下和 自底向上兩大類，前者又包括ll(1) 分析法和遞歸下降法兩種具體方法，后者又包括lr 分析法和算符優(yōu)先分析法兩種具體方法3、判斷（ 錯） 1、自頂向下語法分析采用規(guī)范推導(dǎo)。（最左）（ 對） 2、所有左遞歸文法均無法直接用ll（ 1）分析方法進(jìn)行語法分析。（ 錯） 3、所有的自底向上語法分析，每步分析都是找出當(dāng)前句型的句柄進(jìn)行歸約。（算符優(yōu)先矩陣最左素短語）（ 對） 4、一個文法如果是lr（ 0）文法，則必定是lr（ 1）文法。（更多的文法適應(yīng)（）chapter 5語法制導(dǎo)翻譯及中間代碼生成1) 語法制導(dǎo)翻譯：在一遍掃描中，由語法分析引導(dǎo) , 既完成語法分析任務(wù)，又完成語義分析和中間代碼生成方面的工作。實現(xiàn)方法 : 對文法中的每一產(chǎn)生式，都附加一“語義動作”或“語義子程序” ，且在語法分析過程中，每當(dāng)用一產(chǎn)生式進(jìn)行推導(dǎo)或歸約時，語法分析程序除執(zhí)行相應(yīng)的語法分析動