編譯原理考試知識(shí)點(diǎn)復(fù)習(xí)

1、第一章：編譯過程的六個(gè)階段：詞法分析，語法分析，語義分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成解釋程序：把某種語言的源程序轉(zhuǎn)換成等價(jià)的另一種語言程序目標(biāo)語言程序，然后再執(zhí)行目標(biāo)程序。解釋方式是接受某高級(jí)語言的一個(gè)語句輸入，進(jìn)行解釋并控制計(jì)算機(jī)執(zhí)行，馬上得到這句的執(zhí)行結(jié)果，然后再接受下一句。編譯程序：就是指這樣一種程序，通過它能夠?qū)⒂酶呒?jí)語言編寫的源程序轉(zhuǎn)換成與之在邏輯上等價(jià)的低級(jí)語言形式的目標(biāo)程序(機(jī)器語言程序或匯編語言程序)。解釋程序和編譯程序的根本區(qū)別：是否生成目標(biāo)代碼第三章：Chomsky對(duì)文法中的規(guī)則施加不同限制，將文法和語言分為四大類：0型文法（PSG） à 0型語言或短語

2、結(jié)構(gòu)語言文法 的每個(gè)產(chǎn)生式中：若*N*, (NT)* ，則 是0型文法，即短語結(jié)構(gòu)文法。1型文法（CSG） à 1型語言或上下文有關(guān)語言在0型文法的基礎(chǔ)上：若產(chǎn)生式集合中所有|，除(空串)外，則是型文法,即：上下文有關(guān)文法另一種定義：文法G的每一個(gè)產(chǎn)生式具有下列形式：A，其中、V*，AVN，V+；2型文法（CFG） à 2型語言或上下文無關(guān)語言文法的每個(gè)產(chǎn)生式A，若AN ,(NT)*，則是型法，即：上下文無關(guān)文法。2型文法1型文法0型文法3型文法3型文法（RG） à 3型語言或正則(正規(guī))語言 若、N，T或 e，右線性文法：若產(chǎn)生式為或左線性文法：若產(chǎn)生式為 或都

3、是型文法（即：正規(guī)文法）最左（最右）推導(dǎo)在推導(dǎo)的任何一步Þ ，其中、是句型，都是對(duì)中的最左（右）非終結(jié)符進(jìn)行替換規(guī)范推導(dǎo)：即最右推導(dǎo)。規(guī)范句型：由規(guī)范推導(dǎo)所得的句型。句子的二義性（這里的二義性是指語法結(jié)構(gòu)上的。）文法GS的一個(gè)句子如果能找到兩種不同的最左推導(dǎo)(或最右推導(dǎo))，或者存在兩棵不同的語法樹，則稱這個(gè)句子是二義性的。文法的二義性一個(gè)文法如果包含二義性的句子，則這個(gè)文法是二義文法，否則是無二義文法。短語若SÞ* A且 A Þ +，則稱是句型相對(duì)于非終結(jié)符A的短語。簡(jiǎn)單短語（直接短語）若SÞ * A且AÞ，則稱是句型相對(duì)于非終結(jié)符A 的簡(jiǎn)單短

4、語。句柄一個(gè)句型的最左簡(jiǎn)單短語。（產(chǎn)生式的右部）子樹與短語的關(guān)系 (1) 短語：子樹的末端結(jié)點(diǎn)(即樹葉)組成的符號(hào)串； (2) 直接短語：簡(jiǎn)單子樹的末端結(jié)點(diǎn)組成的符號(hào)串； (3) 句柄：最左簡(jiǎn)單子樹的末端結(jié)點(diǎn)組成的符號(hào)串；左圖所示的關(guān)于句型E+E*i的語法樹來說：· 它有3棵子樹，即3個(gè)短語· 分別為i、E*i和E+E*i；· 直接短語、句柄均為i。 從語法樹中可以看出，所有樹葉的組合就是其相對(duì)應(yīng)的父結(jié)點(diǎn)的短語。 句型i+i*i的語法樹有8棵子樹，短語和直接短語如下：直接短語：i1， i2 ， i3短語：i1，i2，i3，i1*i2，i1*i2+i3句柄：i1注意

5、：i2+i3不是短語不是某棵子樹的結(jié)果第四章：?jiǎn)卧~符號(hào)的輸出形式 二元組：（單詞種別，單詞自身的值）單詞符號(hào)的分類關(guān)鍵字，標(biāo)識(shí)符 ，常數(shù)，運(yùn)算符，界符等（這種分類不是唯一的）【例4.2】 令S=a，b， S上的正規(guī)式和相應(yīng)的正規(guī)集的例子有: 正規(guī)式 正規(guī)集a aa½b a, bab ab(a½b)(a½b) aa, ab, ba, bba * e, a, aa, 任意個(gè)a的串(a½b)* e ,a,b,aa,ab 所有由a和b組成的串(a½b)*(aa½bb)(a½b)* S*上所有至少含有兩個(gè)相繼的a或兩個(gè)相繼的b組成的串

6、 DFA定義:一個(gè)確定的有窮自動(dòng)機(jī)Md是一個(gè)五元組：Md=（K, f, S, Z），其中：(1) K：有窮狀態(tài)集；(2) ：有窮輸入字母表； (3) f ：轉(zhuǎn)換函數(shù)，K× è K的單值映射； 即 f (ki , a)=kj ，其中 ki、kjK，a；(4) S ： SK，惟一初態(tài)；(5) Z：ZÍK，是一個(gè)終態(tài)集，也稱可接受狀態(tài)或結(jié)束狀態(tài)。【例】DFA M=(S,U,V,Q，a,b，f，S，Q)， 其中f定義為：f（S，a）=U，f（V，a）=U f（S，b）=V，f（V，b）=Q f（U，a）=Q，f（Q，a）=Q f（U，b）=V，f（Q，b）=Q DFA的表

7、示（1）用轉(zhuǎn)換函數(shù)；（2）狀態(tài)轉(zhuǎn)換矩陣；（3）狀態(tài)轉(zhuǎn)換圖轉(zhuǎn)換函數(shù) ：DFA M=(0, 1, 2, 3, a, b , f, 0, 3 ) f: f(0,a)=1 f(0,b)=2 f(1,a)3 f(1,b)2 f(2,a)=1 f(2,b)=3 f(3,a)3 f(3,b)3 轉(zhuǎn)換矩陣 狀態(tài)轉(zhuǎn)換圖 NFA M的定義:一個(gè)非確定有窮自動(dòng)機(jī)Mn是一個(gè)五元組Mn=(K, , f, S, Z )，其中： (1) K、Z的意義與DFA相同；(2) f：從K×* è K的子集映射；(3) S Ì K，是一個(gè)非空初態(tài)集。 與DFA的主要區(qū)別允許有多個(gè)初始狀態(tài)。允許狀態(tài)在其輸

8、出邊上有相同的符號(hào)(多值映射)。允許輸出邊上有空串符號(hào)e 。特點(diǎn):在給定狀態(tài)和符號(hào)的情況下，不能唯一的確定下一個(gè)狀態(tài)。NFA的確定化基本方法 基本方法:e邊合并 ,符號(hào)合并 (NFA轉(zhuǎn)化成的DFA不是唯一的) 【 例 】 NFA M如右圖所示，試將其確定化為DFA M'?！窘獯稹浚?）用子集法將圖所示的NFA M確定化為表1。（2）對(duì)表1中的所有子集重新命名得到表2的狀態(tài)轉(zhuǎn)換矩陣_closure(S0)確定有窮自動(dòng)機(jī)的化簡(jiǎn)：第五章：語法分析是編譯程序的核心部分：在詞法分析的基礎(chǔ)上，識(shí)別單詞符號(hào)序列是否是給定文法的正確句子（程序）。自上而下分析的前提：消除左遞規(guī)和消除回溯。自頂向下分析法

9、就是從文法的開始符號(hào)出發(fā)，試圖推導(dǎo)出與輸入的單詞串完全匹配的句子。如果能夠推導(dǎo)出，則該輸入串是給定文法的句子。如果不能推導(dǎo)出，則該輸入串不是給定文法的句子。自頂向下分析法分兩種不確定性分析法：是帶有回溯的分析方法，效率低，代 價(jià)高，極少使用。確定性分析法：對(duì)文法有一定的限制，但實(shí)現(xiàn)簡(jiǎn)單直觀，便于手工或自動(dòng)構(gòu)造。LL(1)文法的定義一個(gè)上下文無關(guān)文法是LL(1)文法的充分必要條件是：對(duì)每個(gè)非終結(jié)符A的任兩個(gè)不同產(chǎn)生式 A®a，A®，滿足：Select(A®a)Select(A®)=Æ,其中：a、不同時(shí)推導(dǎo)出e 注：對(duì)LL(1)文法進(jìn)行語法分析時(shí)不

10、會(huì)產(chǎn)生回溯。LL(1)的含義：(LL(1)文法是無二義的； LL(1)文法不含左遞歸)第1個(gè)L：從左到右掃描輸入串 第2個(gè)L：生成的是最左推導(dǎo)1 ：向右看1個(gè)輸入符號(hào)便可決定選擇哪個(gè)產(chǎn)生式某些非LL(1)文法到LL(1)文法的等價(jià)變換: 1. 提取公因子 2. 消除左遞歸 1. 提取左公因子形如: Aa1a2.an 提取左公因子： A a(12.n)改寫為： A a A' A'12.n 2. 消除左遞歸 （如果一個(gè) 文法是左遞歸時(shí)，則不能采用自頂向下分析法。）(1)左遞歸的定義 （含有左遞歸的文法絕對(duì)不是LL（1）文法）一個(gè)文法含有下列形式的產(chǎn)生式時(shí)， A®Ab A&

11、#206;VN , bÎV* 直接左遞歸 A®Bb B® Aa A, BÎVN , a，bÎ V* 間接左遞歸(2)直接左遞歸的消除 （改為右遞歸）S®bS S®aS| S®Sa S®b 形如： A A a|（a非e，不以A打頭）改寫為： A A¢ A¢ aA¢ | e 形如： AAa1 | Aa2 | . . . | Aan | b1 | b2 | . . . | bm 其中，每個(gè)a都不等于e ，b1 , . . . , bm 均不以A開頭。改寫為： A b1 A¢

12、; | b2 A¢ | . . . | bm A¢ A¢ a1 A¢ | a2 A¢ | . . . | an A¢ | e E T E'E' + T E'T F T'T' * F T'F ( E )i E E + TT T T * FFF ( E )i 預(yù)測(cè)分析法（又稱LL(1)分析法，屬于確定的自頂向下分析方法） 基本思想 ：從左到右掃描源程序，直接根據(jù)： (1) 當(dāng)前(需推導(dǎo))的語法變量; (2) 輸入串的當(dāng)前輸入符號(hào); 確定進(jìn)行分析所需的候選式：使其第一個(gè)符號(hào)與當(dāng)前輸入符號(hào)相同，

13、或該候選式可推導(dǎo)出的第一個(gè)符號(hào)與當(dāng)前符號(hào)相同。預(yù)測(cè)分析器構(gòu)成：預(yù)測(cè)分析程序，先進(jìn)后出棧，預(yù)測(cè)分析表與文法有關(guān)第七章對(duì)輸入串的分析過程（已知文法的分析表）LR分析法：是一種規(guī)范規(guī)約過程LR(k)含義L ：從左到右掃描輸入符號(hào)R ：最右推導(dǎo)對(duì)應(yīng)的最左歸約(反序完成最右推導(dǎo))k ：超前讀入k個(gè)符號(hào)，以便確定歸約用的產(chǎn)生式LR(0)項(xiàng)目分類移進(jìn)項(xiàng)目，形如Aa ab，a是終結(jié)符,a ,b ÎV* 以下同 【例】 S bBB 待約項(xiàng)目，形如 A a Bb 【例】 Sb BB SbB B 歸約項(xiàng)目，形如 A a 【例】 SbBB 接受項(xiàng)目，形如 S S 第八章：一個(gè)屬性文法包含一個(gè)上下文無關(guān)文法和

14、一系列語義規(guī)則,這些語義規(guī)則附在每個(gè)產(chǎn)生式上。文法符號(hào)的屬性:單詞的含義，即與文法符號(hào)相關(guān)的一些信息。如，類型、值、存儲(chǔ)地址等。一個(gè)屬性文法(attribute grammar)是一個(gè)三元組A=(G, V, F)G：上下文無關(guān)文法。V：屬性的有窮集。每個(gè)屬性與文法的一個(gè)終結(jié)符或非終結(jié)符相連。屬性與變量一樣，可以進(jìn)行計(jì)算和傳遞。F：關(guān)于屬性的斷言或謂詞(一組屬性的計(jì)算規(guī)則)的有窮集。斷言或語義規(guī)則與一個(gè)產(chǎn)生式相聯(lián)，只引用該產(chǎn)生式左端或右端的終結(jié)符或非終結(jié)符相聯(lián)的屬性。綜合屬性:若產(chǎn)生式左部的單非終結(jié)符A的屬性值由右部各非終結(jié)符的屬性值決定, 則A的屬性稱為綜合屬性。 繼承屬性:若產(chǎn)生式右部符號(hào)B

15、的屬性值是根據(jù)左部非終結(jié)符的屬性值或者右部其它符號(hào)的屬性值決定的,則B的屬性為繼承屬性。在兩種情況下，都說屬性b依賴于屬性c1,c2,ck(1)非終結(jié)符既可有綜合屬性也可有繼承屬性，但文法開始符 號(hào)沒有繼承屬性。(2) 終結(jié)符只有綜合屬性，沒有繼承屬性，它們由詞法程序提供。在計(jì)算時(shí)： 綜合屬性沿屬性語法樹向上傳遞；繼承屬性沿屬性語法樹向下傳遞。 語法制導(dǎo)翻譯：是指在語法分析過程中，完成附加在所使用的產(chǎn)生式上的語義規(guī)則描述的動(dòng)作。語法制導(dǎo)翻譯實(shí)現(xiàn)：對(duì)單詞符號(hào)串進(jìn)行語法分析，構(gòu)造語法分析樹，然后根據(jù)需要構(gòu)造屬性依賴圖，遍歷語法樹并在語法樹的各結(jié)點(diǎn)處按語義規(guī)則進(jìn)行計(jì)算。中間代碼（中間語言）1、是復(fù)雜

16、性介于源程序語言和機(jī)器語言的一種表示形式。/2、一般，快速編譯程序直接生成目標(biāo)代碼。3、為了使編譯程序結(jié)構(gòu)在邏輯上更為簡(jiǎn)單明確，常采用中間代碼，這樣可以將與機(jī)器相關(guān)的某些實(shí)現(xiàn)細(xì)節(jié)置于代碼生成階段仔細(xì)處理，并且可以在中間代碼一級(jí)進(jìn)行優(yōu)化工作，使得代碼優(yōu)化比較容易實(shí)現(xiàn)。何謂中間代碼：源程序的一種內(nèi)部表示，不依賴目標(biāo)機(jī)的結(jié)構(gòu)，易于代碼的機(jī)械生成。為何要轉(zhuǎn)換成中間代碼邏輯結(jié)構(gòu)清楚；利于不同目標(biāo)機(jī)上實(shí)現(xiàn)同一種語言。便于移植，便于修改，便于進(jìn)行與機(jī)器無關(guān)的優(yōu)化。中間代碼的幾種形式：逆波蘭記號(hào) ，三元式和樹形表示 ，四元式 逆波蘭記號(hào)：把運(yùn)算分量(操作數(shù))寫在前面，把運(yùn)算符寫在后面的表示法，又稱后綴表示法。

17、中綴表達(dá)式向逆波蘭表達(dá)式轉(zhuǎn)換postfix(x)=x postfix(c)=cpostfix(E1 op E2)= postfix(E1) postfix(E2) oppostfix(E)= postfix(E) 第九章：符號(hào)表的一般形式：一張符號(hào)表的的組成包括兩項(xiàng)，即名字欄和信息欄。 信息欄包含許多子欄和標(biāo)志位，用來記錄相應(yīng)名字和種種不同屬性，名字欄也稱主欄。主欄的內(nèi)容稱為關(guān)鍵字（key word）。符號(hào)表的功能：（1）收集符號(hào)屬性在分析語言程序中標(biāo)識(shí)符說明部分時(shí)，編譯程序根據(jù)說明信息收集有關(guān)標(biāo)識(shí)符的屬性，并在符號(hào)表中建立符號(hào)的相應(yīng)屬性信息。(2) 上下文語義的合法性檢查的依據(jù)： 檢查標(biāo)識(shí)符

18、屬性在上下文中的一致性和合法性。(3)作為目標(biāo)代碼生成階段地址分配的依據(jù)符號(hào)的主要屬性及作用：1. 符號(hào)名 2. 符號(hào)的類型 （整型、實(shí)型、字符串型等）3. 符號(hào)的存儲(chǔ)類別（公共、私有）4. 符號(hào)的作用域及可視性 （全局、局部） 5. 符號(hào)變量的存儲(chǔ)分配信息 （靜態(tài)存儲(chǔ)區(qū)、動(dòng)態(tài)存儲(chǔ)區(qū)）6. 符號(hào)的其它屬性 數(shù)組內(nèi)情向量(類型、維數(shù)、各維的上下界、首地址等) 記錄結(jié)構(gòu)型的成員信息函數(shù)及過程的形參 第十章：運(yùn)行時(shí)的存儲(chǔ)區(qū)為了使目標(biāo)程序能夠運(yùn)行，編譯程序要從操作系統(tǒng)中得到一塊存儲(chǔ)區(qū)，以使目標(biāo)程序能夠在其上運(yùn)行。運(yùn)行時(shí)的存儲(chǔ)區(qū)劃分目標(biāo)區(qū)：存放目標(biāo)代碼。靜態(tài)數(shù)據(jù)區(qū)：編譯時(shí)能確定所占用空間的數(shù)據(jù)。棧區(qū)和堆

19、區(qū)：可變數(shù)據(jù)及管理過程活動(dòng)的控制信息。存儲(chǔ)分配方案策略：靜態(tài)存儲(chǔ)分配；動(dòng)態(tài)存儲(chǔ)分配：棧式、 堆式。 靜態(tài)存儲(chǔ)分配1、基本策略在編譯時(shí)就安排好目標(biāo)程序運(yùn)行時(shí)的全部數(shù)據(jù)空間，并能確定每個(gè)數(shù)據(jù)項(xiàng)的單元地址。2、適用的分配對(duì)象：子程序的目標(biāo)代碼段；全局?jǐn)?shù)據(jù)目標(biāo)（全局變量）3、靜態(tài)存儲(chǔ)分配的要求：不允許遞歸調(diào)用，不含有可變數(shù)組。FORTRAN程序是段結(jié)構(gòu)，不允許遞歸，數(shù)據(jù)名大小、性質(zhì)固定。 是典型的靜態(tài)分配動(dòng)態(tài)存儲(chǔ)分配 1、如果一個(gè)程序設(shè)計(jì)語言允許遞歸過程、可變數(shù)組或允許用戶自由申請(qǐng)和釋放空間，那么，就需要采用動(dòng)態(tài)存儲(chǔ)管理技術(shù)。2、兩種動(dòng)態(tài)存儲(chǔ)分配方式：棧式，堆式棧式動(dòng)態(tài)存儲(chǔ)分配分配策略：將整個(gè)程序的數(shù)

20、據(jù)空間設(shè)計(jì)為一個(gè)棧。 【例】在具有遞歸結(jié)構(gòu)的語言程序中，每當(dāng)調(diào)用一個(gè)過程時(shí)，它所需的數(shù)據(jù)空間就分配在棧頂，每當(dāng)過程工作結(jié)束時(shí)就釋放這部分空間。過程所需的數(shù)據(jù)空間包括兩部分一部分是生存期在本過程這次活動(dòng)中的數(shù)據(jù)對(duì)象。如局部變量、參數(shù)單元、臨時(shí)變量等；另一部分則是用以管理過程活動(dòng)的記錄信息(連接數(shù)據(jù))。活動(dòng)記錄（AR） 一個(gè)過程的一次執(zhí)行所需要的信息使用一個(gè)連續(xù)的存儲(chǔ)區(qū)來管理，這個(gè)區(qū) (塊)叫做一個(gè)活動(dòng)記錄。構(gòu)成1、臨時(shí)工作單元；2、局部變量；3、機(jī)器狀態(tài)信息；4、存取鏈；5、控制鏈；6、實(shí)參；7、返回地址第十一章：什么是代碼優(yōu)化所謂優(yōu)化，就是對(duì)代碼進(jìn)行等價(jià)變換，使得變換后的代碼運(yùn)行結(jié)果與變換前代碼運(yùn)行結(jié)果相同，而運(yùn)行速度加快或占用存儲(chǔ)空間減少。優(yōu)化原則：等價(jià)原則：經(jīng)過優(yōu)化后不應(yīng)改變程序運(yùn)行的結(jié)果。 有效原則：使優(yōu)化后所產(chǎn)生的目標(biāo)代碼運(yùn)行時(shí)間較短，占用的存儲(chǔ)空間較小。 合算原則：以盡可能低的代價(jià)取得較好的優(yōu)化效果。常見的優(yōu)化技術(shù)(1) 刪除多余運(yùn)算(刪除公共子表達(dá)式) (2) 代碼外提:是針對(duì)循環(huán)的(3)強(qiáng)度削弱; 把執(zhí)行時(shí)間較長(zhǎng)的運(yùn)算替換為執(zhí)行時(shí)間較短的運(yùn)算(4)變換循環(huán)控制條件 (5)合并已知量與復(fù)寫傳播 (6)刪除無用賦值基本塊定義程序中只有一個(gè)入口和一個(gè)出口的一段順序執(zhí)行的語句序列，稱為程序的一個(gè)基本塊。