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

1、文檔編碼 : CP10X9Q8J5S7 HK3O7R5J3G9 ZC6Y8U4K5C3學(xué)習(xí)必備 歡迎下載 第一章： 編譯過程的六個(gè)階段： 詞法分析,語法分析,語義分析,中間代碼生成, 代碼優(yōu)化,目標(biāo)代碼生成 說明程序： 把某種語言的源程序轉(zhuǎn)換成等價(jià)的另一種語言程序目標(biāo)語言程序, 然后再執(zhí) 行目標(biāo)程序； 說明方式是 接受某高級語言的一個(gè)語句輸入, 進(jìn)行說明并把握運(yùn)算 機(jī)執(zhí)行,立刻得到這句的執(zhí)行結(jié)果,然后再接受下一句； 編譯程序： 就是指這樣一種程序, 通過它能夠?qū)⒂酶呒壵Z言編寫的源程序轉(zhuǎn)換成與之在規(guī)律 上等價(jià)的低級語言形式的目標(biāo)程序 機(jī)器語言程序或匯編語言程序 ； 說明程序和編譯程序的 根本區(qū)分

2、 ：是否生成目標(biāo)代碼 第三章： Chomsky 對文法中的規(guī)章施加不同限制,將文法和語言分為四大類： 0 型文法（ PSG） 0 型語言或短語結(jié)構(gòu)語言 文法 的每個(gè)產(chǎn)生式 中：如 * N 就 是 0 型文法,即短語結(jié)構(gòu)文法； *, 1型文法（ CSG） 1 型語言或上下文有關(guān)語言 N T* , 在 0 型文法的基礎(chǔ)上：如產(chǎn)生式集合中全部 | | | | ,除 空串 外, 就是型文法 , 即：上下文有關(guān)文法 另一種定義： 文法 G 的每一個(gè)產(chǎn)生式具有以下形 A ,其中 , V*, A VN, V+； 式： 2 型文法（ CFG） 2 型語言或上下文無關(guān)語言 文法的每個(gè)產(chǎn)生式 A ,如 A N ,

3、 N T* ,就是型法,即：上下文無 關(guān)文法； 3 型文法（ RG） 3 型語言或正就 正規(guī) 語言 0 型文 法 1 型文2 型文法 3 型 文 如, N, T 或 , 右線性文法：如產(chǎn)生式為或 左線性文法：如產(chǎn)生式為 或 都是型文法（即：正規(guī)文法） 最左（最右）推導(dǎo) 在推導(dǎo)的任何一步 ,其中 , 是句型,都是對 中的最左（右）非終結(jié)進(jìn)行替換 符 規(guī)范推導(dǎo)： 即最右推導(dǎo)； 規(guī)范句型： 由規(guī)范推導(dǎo)所得的句型； 句子的二義性（這里的二義性是指語法結(jié)構(gòu)上的； 文法 GS 的一） 個(gè)句子假如能找到兩種不同的最左推導(dǎo) 語法樹,就稱 這個(gè)句子是二義性的； 文法的二義性 或最右推導(dǎo) ,或者存在兩棵不同的 一

4、個(gè)文法假如包含二義性的句子,就這個(gè)文法是二義文法,否就是無二義文法； 短語 如 S * A 且 A + ,就稱 是句型 相對于非終結(jié) A 的短語； 簡潔短語（直接短語） 符 如 S * A 且 A ,就稱 是句型 相對于非終結(jié)符 A 的簡潔短語； 句柄 一個(gè)句型的最左簡潔短語； （產(chǎn)生式的右部） 第 1 頁,共 8 頁學(xué)習(xí)必備 歡迎下載 子樹與短語的關(guān)系 1 短語：子樹的末端結(jié)點(diǎn) 即樹葉 組成的符號串； E+E*i 的語法樹來說： 2 直接短語：簡潔子樹的末端結(jié)點(diǎn)組成的符號串； 3 句柄：最左簡潔子樹的末端結(jié)點(diǎn)組成的符號串； 左圖所示的關(guān)于句型 它有 3 棵子樹,即 3 個(gè)短語 分別為 i ,

5、 E*i 和 E+E*i ； 直接短語,句柄均為 i ； 從語法樹中可以看出, 全部樹葉的組合就是其相對應(yīng)的父結(jié)點(diǎn)的短語； 句型 i+i*i 的語法樹 有 8 棵子樹,短語和直接短語如下： 直接短語： i1 , i2 , i3 短語： i1 , i2 , i3 , i1*i2 , i1*i2+i3 句柄： i1 留意： i2+i3 不是短語不是某棵子樹的結(jié)果 第四章： 單詞符號的輸出形式 二元組：（單詞種別,單詞自身的值） 單詞符號的分類 關(guān)鍵字,標(biāo)識符 ,常數(shù),運(yùn)算符,界符等（ 這種分類不是唯獨(dú)的） b 組成的串 【例 】 令 =a ,b , 上的正規(guī)式和相應(yīng)的正規(guī)集的例子有 : 正規(guī)式 正

6、規(guī)集 aa a ba, b ab ab a ba b aa, ab, ba, bb a , a, aa, 任意個(gè) a 的串 a b ,a,b,aa,ab 全部由 a 和 b 組成的串 a b aa bba b * 上全部至少含有兩個(gè)相繼的 a 或兩個(gè)相繼DFA 定義 : 一個(gè)確定的有窮自動的 Md是一個(gè)五元組： Md=（ K, , f, S, Z ）,其中： 機(jī) 1 K ：有窮狀態(tài)集； 2 ：有窮輸入字母表； ab3 f ：轉(zhuǎn)換函數(shù), K K 的單值映射； S UV 即 f k i , a=k j,其中 ki , kj K,a ； UQ V 4 S ： SK,惟一初態(tài)； V Q U Q 5 Z

7、 ： Z K,是一個(gè)終態(tài)集,也稱可接受狀態(tài)或終止?fàn)顟B(tài)； 【例】 DFA M=S,U,V ,Q , a,b ,f, S, Q , Q 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 第 2 頁,共 8 頁學(xué)習(xí)必備 歡迎下載 DFA 的表示（ 1）用轉(zhuǎn)換函數(shù)； （ 2）狀態(tài)轉(zhuǎn)換矩陣； （ 3）狀態(tài)轉(zhuǎn)換圖 轉(zhuǎn)換函數(shù) ： DFAM=0, 1, 2, 3, a, b , f, 0, 3 , f, S, Z ,其中：

8、f:f0,a=1f0,b=2f1,a 3f1,b 2f2,a=1f2,b=3f3,a 3f3,b 3轉(zhuǎn)換矩陣 狀態(tài)轉(zhuǎn)換圖 NFA M 的定義 : 一個(gè)非確定有窮自動Mn是一個(gè)五元組 Mn=K, 機(jī) 1 K , , Z 的意義與 DFA 相2 同； f ：從 K * K 的子集映射； 3 S K ,是一個(gè)非空初態(tài)集； 與 DFA 的主要區(qū)分 答應(yīng)有多個(gè)初始狀態(tài)； 答應(yīng)狀態(tài)在其輸出邊上有相同的符號 ； 多值映射 ； 答應(yīng)輸出邊上有空串符號 特點(diǎn) : 在給定狀態(tài)和符號的情形下,不能唯獨(dú)的確定下一個(gè)狀態(tài)； NFA 的確定化基本方基本方法 : 邊合并 ,符號合并 NFA 轉(zhuǎn)化成的 DFA 不是唯獨(dú)Y2法

9、 【 例 】 NFA M 如右圖所示,試將其確定化為 DFA M； 的 【解答】 a3aa（1）用子集法將圖所示的 NFA M 確定化為a 1； （2）對表 1 中的全部子集重新命名 表 X 1256得到表 2 的狀態(tài)轉(zhuǎn)換矩陣 bb4bb _closure0S確定有窮自動機(jī)的化簡： 第 3 頁,共 8 頁學(xué)習(xí)必備 歡迎下載 第五章： 語法分析是編譯程序的核心部分 法的正確句子（程序） ； 自 上而下分析的前提： 排除左遞 規(guī)和 排除回溯； 自頂向 下分析法就是 從文 法的開頭符號 動 身,試圖推導(dǎo)出與 輸入的單詞串完全 匹配的句子； ：在詞法分析的基礎(chǔ)上,識別單詞符號序列是否是給定文 假如能夠

10、推導(dǎo)出,就該輸入串是給定文法的句子； 假如不能推導(dǎo)出,就該輸入串不是給定文法的句子； 自頂向下分析法分兩種 不確定性分析法： 是帶有回溯的分析方法,效率低,代 價(jià)高,極少使用； 確定性分析法： 對文法有確定的限制,但實(shí)現(xiàn)簡潔直觀,便于手工或自動構(gòu)造； LL1 文法的定義 一個(gè)上下文無關(guān)文法是 LL1 文法的充分必要條件是 ：對每個(gè)非終結(jié)符 A 的任兩個(gè)不同產(chǎn)生 式 A , A ,中意： SelectA SelectA = , 其中： , 不同時(shí)推導(dǎo)出 注：對 LL1 文法進(jìn)行語法分析時(shí)不會產(chǎn)生回溯； LL1 的含義： LL1 文法是無二義的； 第 1 個(gè) L：從左到右掃描輸入串 LL1 文法不

11、含左遞歸 第 2 個(gè) L：生成的是最左推導(dǎo) 1 ：向右看 1 個(gè)輸入符號便可預(yù)備挑選哪個(gè)產(chǎn)生式 某些非 LL1 文法到 LL1 文法的等價(jià)變換 : 1. 提取公因子 2. 排除左遞歸 1. 提取左公因子 形如 : A a 1 a 2 .a n 提取左公因子： A a 1 2 . n 改寫為： A a A A 1 2 . n 2. 排除左遞歸 （假如一個(gè) 文法是左遞歸時(shí),就不能接受自頂向下分析法； ） 1 左遞歸的定義 （含有左遞歸的文法確定不是 LL （ 1）文法） 一個(gè)文法含有以下形式的產(chǎn)生式時(shí), A A A B B A V N , A A, B V * VN , 直接左遞歸 , V *間接

12、左遞歸 2 直接左遞歸的排除 （改為右遞歸） 形如： 改寫為： A A a| （ a 非 , 不以 A A A aA| A 打頭） S S Sa b S S aS| bS 形如： A Aa1 | Aa2 | . . . | Aan | b1 | b2 | . . . | bm 其中,每個(gè) a 都不等于 , b1 , . . . , bm 均不以 A 開頭； 改寫為： A b1 A| b2 A| . . . | bm A A a1 A| a2 A| . . . | an A| E T E E E + T T E + T E T T * F F T F T F E i T * F T F E i

13、第 4 頁,共 8 頁學(xué)習(xí)必備 歡迎下載 估計(jì)分析法（又稱 LL1 分析法,屬于確定的自頂向下分析方法） 基本思想 ：從左到右掃描源程序,直接依據(jù)： 1 當(dāng)前 需推導(dǎo) 的語法變量 ; 2 輸入串的當(dāng)前輸入符號 ; 或該候選式可推導(dǎo)出的 確定進(jìn)行分析所需的候選式： 使其第一個(gè)符號與當(dāng)前輸入符號相同, 第一個(gè)符號與當(dāng)前符號相同； 估計(jì)分析器構(gòu)成：估計(jì)分析程序,先進(jìn)后出棧,估計(jì)分析表 第七章 對輸入串的分析過程（已知文法的 分析表） LR 分析法：是一種規(guī)范規(guī)約過程 LRk 含義 L ：從左到右掃描輸入符號 R ：最右推導(dǎo)對應(yīng)的最左歸約 反序完成最右推導(dǎo) k ：超前讀入 k 個(gè)符號,以便確定歸約用的

14、產(chǎn)生式 LR0 項(xiàng)目分類 與文法有關(guān) 移進(jìn)項(xiàng)目, 形如 A A . a , a 是終結(jié)符 , , V * 以下同 【例】 . B 【例】 Sb . BB SbB . B S . bBB 待約項(xiàng)目, 形如 歸約項(xiàng)目, 形如 A .【例】 SbBB . 接受項(xiàng)目, 形如 S S . 第八章： 一個(gè)屬性文法包含一個(gè)上下文無關(guān)文法和一系列語義規(guī)章 ,這些語義規(guī)章附在每個(gè)產(chǎn)生式上； 文法符號的屬性 : 單詞的含義,即與文法符號相關(guān)的一些信息；如,類型,值,儲備地址等； 一個(gè)屬性文法 attribute grammar 是一個(gè)三元組 A=G , V, F G ： 上下文無關(guān)文法； V ：屬性的有窮集；每個(gè)

15、屬性與文法的一個(gè)終結(jié)符或非終結(jié)符相連；屬性與變量一樣,可以 進(jìn)行運(yùn)算和傳遞； F： 關(guān)于屬性的斷言或謂詞 一組屬性的運(yùn)算規(guī)章 的有窮集；斷言或語義規(guī)章與一個(gè)產(chǎn)生式 相聯(lián),只引用該產(chǎn)生式左端或右端的終結(jié)符或非終結(jié)符相聯(lián)的屬性； 第 5 頁,共 8 頁綜合屬性 :如產(chǎn)生式左部的單非終結(jié)符 學(xué)習(xí)必備 歡迎下載 , 就 A A 的屬性值由右部各非終結(jié)符的屬性值預(yù)備 的屬性稱為 綜合屬性； 繼承屬性 :如產(chǎn)生式右部符號 B 的屬性值是依據(jù)左部非終結(jié)符的屬性值或者右部其它符號的 屬性值預(yù)備的 ,就 B 的屬性為 繼承屬性； 在兩種情形下,都說屬性 b 依靠于屬性 c1,c2,ck1 非終結(jié)符既可有綜合屬性

16、也可有繼承屬性,但文法開頭符 號沒有繼承屬性； 2 終結(jié)符只有綜合屬性,沒有繼承屬性,它們由詞法程序供應(yīng)； 在運(yùn)算時(shí)： 綜合屬性沿屬性語法樹向上傳遞；繼承屬性沿屬性語法樹向下傳遞； 語法制導(dǎo)翻譯： 是指在語法分析過程中, 作； 完成附加在所使用的產(chǎn)生式上的語義規(guī)章描述的動 語法制導(dǎo)翻譯實(shí)現(xiàn)： 對單詞符號串進(jìn)行語法分析, 構(gòu)造語法分析樹, 然后依據(jù)需要構(gòu)造屬性 依靠圖,遍歷語法樹并在語法樹的各結(jié)點(diǎn)處按語義規(guī)章進(jìn)行運(yùn)算； 中間代碼（中間語言） 1, 是復(fù)雜性介于源程序語言和機(jī)器語言的一種表示形式； / 2,一般,快速編譯程序直接生成目標(biāo)代碼； 3, 為了使編譯程序結(jié)構(gòu)在規(guī)律上更為簡潔明確,常接受中

17、間代碼,這樣可以將與機(jī)器相關(guān) 的某些實(shí)現(xiàn)細(xì)節(jié)置于代碼生成階段認(rèn)真處理, 并且可以在中間代碼一級進(jìn)行優(yōu)化工作, 使得 代碼優(yōu)化比較簡潔實(shí)現(xiàn)； 何謂中間代碼 ：源程序的一種內(nèi)部表示,不依靠目標(biāo)機(jī)的結(jié)構(gòu),易于代碼的機(jī)械生成； 為何要轉(zhuǎn)換成中間代碼 規(guī)律結(jié)構(gòu)清晰；利于不同目標(biāo)機(jī)上實(shí)現(xiàn)同一種語言； 便于移植,便于修改,便于進(jìn)行與機(jī)器無關(guān)的優(yōu)化； 中間代碼的幾種形式： 逆波蘭記號 ,三元式和樹形表示 ,四元式 逆波蘭記號 ：把運(yùn)算重量 操作數(shù) 寫在前面, 把運(yùn)算符寫在后面的表示法, 又稱后綴表示法； 中綴表達(dá)式向逆波蘭表達(dá)式轉(zhuǎn)換 postfixx=x postfixc=cpostfixE 1 op E2=

18、 postfixE 1 postfixE 2 oppostfixE= postfixE第九章： 符號表的一般形式： 一張符號表的的組成包括兩項(xiàng),即名字欄和信息欄； 信息欄包含很多子欄和標(biāo)志位,用來記錄相應(yīng)名字和種種不同屬性,名字欄也稱主欄； 主欄的內(nèi)容稱為關(guān)鍵字（ key word ）； 符號表的功能： （ 1）收集符號屬性 在分析語言程序中標(biāo)識符說明部分時(shí),編譯程序依據(jù)說明信息收集有關(guān)標(biāo)識符的屬性, 并在符號表中建立符號的相應(yīng)屬性信息； 2 上下文語義的合法性檢查的依據(jù) ： 檢查標(biāo)識符屬性在上下文中的一樣性和合法性； 3 作為目標(biāo)代碼生成階段地址支配的依據(jù) 符號的主要屬性及作用： 1. 符號

19、名 2. 符號的類型 （整型,實(shí)型,字符串型等） ） 3. 符號的儲備類別 （公共,私有） 4. 符號的作用域及可視性 （全局,局部） 第 6 頁,共 8 頁學(xué)習(xí)必備 歡迎下載 5. 符號變量的儲備支配信息 6. 符號的其它屬性 （靜態(tài)儲備區(qū),動態(tài)儲備區(qū)） 數(shù)組內(nèi)情向量 類型,維數(shù),各維的上下界,首地址等 記錄結(jié)構(gòu)型的成員信息 函數(shù)及過程的形參 第十章： 運(yùn)行時(shí)的儲備區(qū) 為了使目標(biāo)程序能夠運(yùn)行, 編譯程序要從操作系統(tǒng)中得到一塊儲備區(qū), 以使目標(biāo)程序能 夠在其上運(yùn)行； 運(yùn)行時(shí)的儲備 區(qū)劃分 目標(biāo)區(qū)：存放目標(biāo)代碼； 靜態(tài)數(shù)據(jù)區(qū)：編譯時(shí)能確定所占用空間的數(shù)據(jù)； 棧區(qū)和堆區(qū)：可變數(shù)據(jù)及治理過程活動的把

20、握信息； 儲備支配方案策略 ： 靜態(tài)儲備支配 ；動態(tài)儲備支配：棧式, 堆式； 靜態(tài)儲備支配 1,基本策略 在編譯時(shí)就支配好目標(biāo)程序運(yùn)行時(shí)的全部數(shù)據(jù)空間,并能確定每個(gè)數(shù)據(jù)項(xiàng)的單元地址； 2,適用的支配對象 ：子程序的目標(biāo)代碼段；全局?jǐn)?shù)據(jù)目標(biāo)（全局變量） 3,靜態(tài)儲備支配的要求 ：不答應(yīng)遞歸調(diào)用,不含有可變數(shù)組； FORTRAN 程序是段結(jié)構(gòu),不答應(yīng)遞歸,數(shù)據(jù)名大小,性質(zhì)固定； 是典型的靜態(tài)支配 動態(tài)儲備支配 1,假如一個(gè)程序設(shè)計(jì)語言答應(yīng)遞歸過程, 可變數(shù)組或答應(yīng)用戶自由申請和釋放空間, 那么, 就需要接受動態(tài)儲備治理技術(shù)； 2,兩種動態(tài)儲備支配方式： 棧式,堆式 棧式動態(tài)儲備支配 支配策略： 將

21、整個(gè)程序的數(shù)據(jù)空間設(shè)計(jì)為一個(gè)棧； 【例】在具有遞歸結(jié)構(gòu)的語言程序中,每當(dāng)調(diào)用一個(gè)過程時(shí),它所需的數(shù)據(jù)空間就支配 在棧頂,每當(dāng)過程工作終止時(shí)就釋放這部分空間 ； 過程所需的數(shù)據(jù)空間包括兩部分 一部分是生存期在本過程這次活動中的數(shù)據(jù)對象；如局部變量,參數(shù)單元,暫時(shí)變量等； 另一部分就是用以治理過程活動的記錄信息 連接數(shù)據(jù) ； 活動記錄（ AR ） 一個(gè)過程的一次執(zhí)行所需要的信息使用一個(gè)連續(xù)的儲備區(qū)來治理,這個(gè)區(qū) 塊 叫做一 個(gè)活動記錄； 構(gòu)成 1,暫時(shí)工作單元； 2,局部變量； 3,機(jī)器狀態(tài)信息； 4,存取鏈； 5,把握鏈； 6,實(shí)參； 7,返回地址 第十一章： 什 么是代碼優(yōu)化 所謂優(yōu)化, 就是

22、對代碼進(jìn)行等價(jià)變換, 使得變換后的代碼運(yùn)行結(jié)果與變換前代碼運(yùn)行結(jié) 果相同,而運(yùn)行速度加快或占用儲備空間削減； 優(yōu)化原就： 等價(jià)原就：經(jīng)過優(yōu)化后不應(yīng)轉(zhuǎn)變程序運(yùn)行的結(jié)果； 有效原就：使優(yōu)化后所產(chǎn) 生的目標(biāo)代碼運(yùn)行時(shí)間較短,占用的儲備空間較??； 合算原就：以盡可能低的代價(jià)取得較好的優(yōu)化成效； 第 7 頁,共 8 頁學(xué)習(xí)必備 歡迎下載 常見的優(yōu)化技術(shù) 1 刪除余外運(yùn)算 刪除公共子表達(dá)式 2 代碼外提 :是針對循環(huán)的 3 強(qiáng)度減弱 ; 把執(zhí)行時(shí)間較長的運(yùn)算替換為執(zhí)行時(shí)間較短的運(yùn)算 4 變換循環(huán)把握條件 5合并已知量與復(fù)寫傳播 6刪除無用賦值 基本塊定義 程序中只有一個(gè)入口和一個(gè)出口的一段次序執(zhí)行的語句序列,稱為程