編譯原理知識(shí)點(diǎn)總結(jié)(共4頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上考試題型：填空24%+簡(jiǎn)答4*4=16%+解答4*15=6Chapter 1 重要概念1. 什么編譯程序？P3答：編譯程序的主要功能是把用高級(jí)語(yǔ)言編寫(xiě)的源程序翻譯為等價(jià)的目標(biāo)程序。2. 編譯程序的工作過(guò)程？（6個(gè)階段）P41、 詞法分析程序 2、語(yǔ)法分析程序 3、語(yǔ)義分析程序 4、中間代碼生成5、 代碼優(yōu)化程序 6、目標(biāo)代碼生成（不做優(yōu)化是4個(gè)階段，5、6不要）3. 編譯程序的邏輯結(jié)構(gòu)？P4 圖1-2 編譯程序的邏輯結(jié)構(gòu)4. 執(zhí)行高級(jí)語(yǔ)言編寫(xiě)的程序：（編譯執(zhí)行、解釋執(zhí)行）1） 按編譯方式在計(jì)算機(jī)上執(zhí)行用高級(jí)語(yǔ)言編寫(xiě)的程序，一般須經(jīng)過(guò)兩個(gè)階段。第一個(gè)階段稱為編譯階段，其

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

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

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

5、語(yǔ)言的Chomsky分類1）0型文法或短語(yǔ)結(jié)構(gòu)文法(PSG)2）1型文法或前后文有關(guān)文法(CSG)3）2型文法或前后文無(wú)關(guān)文法(CFG).4）3型文法或正規(guī)文法。（左線性文法+右線性文法）編譯過(guò)程的詞法分析使用正規(guī)文法（3型文法）描述單詞結(jié)構(gòu)；語(yǔ)法分析采用前后文無(wú)關(guān)文法（2型文法）描述語(yǔ)句結(jié)構(gòu)課堂練習(xí)1）Chomsky定義的四種形式語(yǔ)言文法分別為 0型文法，1型文法，2型文法 ,3型文法,其中3型文法用于描述詞法，2型文法用于描述語(yǔ)法。2）遞歸文法產(chǎn)生的語(yǔ)言語(yǔ)句集合是無(wú)限集合。3）規(guī)范推導(dǎo)是最右推導(dǎo)，規(guī)范歸約是最左歸約。定義每種語(yǔ)言的文法都是不 （不|）唯一的。文法的化簡(jiǎn)與改造主要包括無(wú)用符號(hào)

6、和無(wú)用產(chǎn)生式的刪除 ,產(chǎn)生式的消除 ,單產(chǎn)生式的消除幾項(xiàng)內(nèi)容。大題：1）畫(huà)出句子的語(yǔ)法樹(shù)，找出所有的短語(yǔ)，直接短語(yǔ)和句柄（運(yùn)算符最低原則）Chapter3 詞法分析及詞法分析程序1）了解6種定義，特點(diǎn)正規(guī)文法、狀態(tài)轉(zhuǎn)換圖、有限自動(dòng)機(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)S0K 5）終態(tài)集ZK （）1.確定的有限自動(dòng)機(jī)（DFA）若FA在每個(gè)狀態(tài)，對(duì)輸入符號(hào)的下一狀態(tài)是唯一的，稱此種FA為確定的有限自動(dòng)機(jī)DFA2.非確定

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

8、部表示為二元式（class , value）2.單詞的描述形式有許多種，包括文法形式正規(guī)文法，圖示方式狀態(tài)轉(zhuǎn)換圖，便于計(jì)算機(jī)存儲(chǔ)的狀態(tài)轉(zhuǎn)換矩陣，自動(dòng)機(jī)又分為NFA,DFA兩種，正規(guī)表達(dá)式和正規(guī)集最便于體現(xiàn)單詞的結(jié)構(gòu)3.Bell實(shí)驗(yàn)室M.Lesk等人用C語(yǔ)言研制的一個(gè)詞法分析程序的自動(dòng)生成工具叫LEX4.判斷（對(duì)）所有帶有的自動(dòng)機(jī)都是非確定的自動(dòng)機(jī)Chapter 4 語(yǔ)法分析和語(yǔ)法分析程序1.語(yǔ)法分析方法: 自頂向下分析法：如遞歸下降法，LL（1）等（最左推導(dǎo)）自底向上分析法：如算符優(yōu)先法（分析表達(dá)式常用），LR等（最右規(guī)約）大題LR、SLR1（1）LL（1）-預(yù)測(cè)分析法（LL（1）分析法最左推

9、導(dǎo)LL（1）分析表）1) 編寫(xiě)文法，消除二義性；2) 消除左遞歸、提取左因子；3) 求 FIRST 集和 FOLLOW 集FIRST():可以推出的開(kāi)頭的終結(jié)符號(hào)(或)FOLLOW(A):在所有句型中可能直接跟在A之后的終結(jié)符號(hào)4）檢查是不是 LL(1) 文法（若不是 LL(1)，說(shuō)明文法的復(fù)雜性超過(guò)自頂向下方法的分析能力 ）5） 按照 LL(1) 文法構(gòu)造預(yù)測(cè)分析表6） 實(shí)現(xiàn)預(yù)測(cè)分析器（2）算符優(yōu)先分析法(構(gòu)造算符優(yōu)先矩陣分析句子)廣義運(yùn)算符: 文法的終結(jié)符號(hào) 廣義運(yùn)算對(duì)象: 非終結(jié)符（3） LR（0）分析法A. 引入S->S拓廣文法B. 構(gòu)造識(shí)別所有規(guī)范句型全部的活前綴的DFAC.

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