編譯原理知識(shí)點(diǎn)總結(jié)

1、考試題型：填空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)信息表管憂程序錯(cuò)濱栓查和攤理程序4. 執(zhí)行高級(jí)語(yǔ)言編寫(xiě)的程序：（編譯執(zhí)行、解釋執(zhí)行）1）按編譯方式在計(jì)算機(jī)上執(zhí)行用高級(jí)語(yǔ)言編寫(xiě)的程序，一般須經(jīng)過(guò)兩個(gè)階段。第一個(gè)階段 稱為編譯階段，其任務(wù)是由

2、編譯程序?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. P 11第一段編譯程序的各部分之

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)（

4、大寫(xiě)字母）,其集合記為VN2）規(guī)則中不需進(jìn)一步定義的基本符號(hào)稱為終結(jié)符號(hào),其集合記為VT3）非終結(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ǔ)言的文法都是 不（不| ）唯一的。文法

6、的化簡(jiǎn)與改造主要包括無(wú)用符號(hào)和無(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 確定化最小化順序：或，連接，閉包（1）狀態(tài)轉(zhuǎn)換圖的五要素1 ）有限非空狀態(tài)集 K2 ）有限輸入字母表刀3 ）狀態(tài)之間的映射關(guān)系 f4 ）初態(tài)S0 K5 ）終態(tài)集Z K（2）1.確定的有限自動(dòng)機(jī)（DFA若FA在每個(gè)狀態(tài)，對(duì)輸入符號(hào)的下一狀態(tài)是唯一的，

7、稱此種FA為確定的有限自動(dòng)機(jī) DFA2. 非確定的有限自動(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. 單詞

8、的編譯器內(nèi)部表示為二元式（class , value ）2. 單詞的描述形式有許多種，包括文法形式正規(guī)文法，圖示方式狀態(tài)轉(zhuǎn)換圖，便于計(jì)算機(jī)存儲(chǔ)的 狀態(tài)轉(zhuǎn)換矩陣，自動(dòng)機(jī)又分為NFAQFA兩種，正規(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）

9、-預(yù)測(cè)分析法（LL （1）分析法一最左推導(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拓廣

10、文法B. 構(gòu)造識(shí)別所有規(guī)范句型全部的活前綴的DFAC. 構(gòu)造LR （0 ）分析表 r產(chǎn)生式編號(hào)D. 分析句子（4）SLR（1）分析表將文法拓廣（2）構(gòu)造識(shí)別文法全部規(guī)范句型活前綴的DFA求非終結(jié)符號(hào)Follow（）集合（4）對(duì)每個(gè)項(xiàng)目集按以下四條規(guī)則填表： 若項(xiàng)目集L中有S,->S 置if#=Me 若項(xiàng)目集Ii中有a的項(xiàng)目，A” 口為第j個(gè)產(chǎn)生式，則Follow（A）元素所在列置歸約動(dòng)作為町 若項(xiàng)目集I沖形如A> a 的項(xiàng)目若二口/為終結(jié)符，置i以】為Sj”x為非終結(jié)符,置【i“為j - ©分析表中無(wú)定義的元素均表示"出錯(cuò)課堂練習(xí)1、LL （1）分析器由_緩沖區(qū)

11、 _ ,分析棧_，分析表 _,控制程序四部分組成。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)先矩陣t最左素短語(yǔ) ）（對(duì)）4、一個(gè)文法如果是 LR （ 0）文法，則必定是 LR （1）文法。（更多的文法適應(yīng)SL R（l）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ǔ)法分