編譯原理復(fù)習(xí)資料,基本概念

1、第一章1. 編譯的 5 個(gè)階段：詞法分析、語(yǔ)法分析、語(yǔ)義分析與中間代碼生成、優(yōu)化、目標(biāo)代碼生成2. 翻譯程序：序。能夠把某種語(yǔ)言轉(zhuǎn)換成另一種語(yǔ)言的程序，而兩者在邏輯上是等價(jià)的3. 解釋程序： 以源程序?yàn)檩斎耄划a(chǎn)生目標(biāo)程序，而是邊解釋邊執(zhí)行源程序本身的 程4. 診斷編譯程序： 幫助 xx 和調(diào)試的程序。5. 優(yōu)化編譯程序： 提高目標(biāo)代碼效率的程序。6. 運(yùn)行編譯程序的是宿主機(jī)，運(yùn)行目標(biāo)代碼的是目標(biāo)機(jī)。7. 交叉編譯： 編譯程序產(chǎn)生不同于宿主機(jī)的目標(biāo)代碼。8. 可變編譯程序： 不需要重寫編譯程序中與機(jī)器無(wú)關(guān)的局部就能改變目標(biāo)機(jī)。9. 程序語(yǔ)言由語(yǔ)法和語(yǔ)義兩方面定義。10. 語(yǔ)句包括： 說(shuō)明性語(yǔ)句

2、、執(zhí)行性語(yǔ)句11. 子程序傳參方式： 傳值、傳地址、傳名12. 空間分配分方式：靜態(tài)存儲(chǔ)分配、動(dòng)態(tài)存儲(chǔ)分配對(duì)各種表格進(jìn)行管理 ,包括表格的構(gòu)造、查找、修改、刪除、插入等；詞法分析14. 詞法分析： 把源程序作為字符串進(jìn)行掃描，根據(jù)單詞詞法，識(shí)別出所有單詞，過(guò)濾無(wú) 用符，并檢 查是否為合法的單詞。15. 詞法分析的工具：正規(guī)式、有限自動(dòng)機(jī)。16. 單詞一般分為如下幾種： 根本字，標(biāo)識(shí)符，常數(shù)，算符，界符。17. 詞法規(guī)那么： 規(guī)定了形成單詞的規(guī)那么；如常數(shù)，標(biāo)識(shí)符，根本字，算符等。18. 識(shí)別單詞符號(hào)的方法：超前搜索19. 源程序的預(yù)處理：過(guò)濾無(wú)關(guān)的符號(hào)。20. 狀態(tài)圖由三種結(jié)構(gòu)構(gòu)成：分支結(jié)構(gòu)、

3、循環(huán)結(jié)構(gòu)、終結(jié)點(diǎn)21 丄 EX 語(yǔ)言源程序由兩局部組成 :正規(guī)式輔助定義式、識(shí)別規(guī)那么語(yǔ)法分析22. 語(yǔ)法分析 :根據(jù)語(yǔ)言的語(yǔ)法規(guī)那么 ,從單詞符號(hào)串中識(shí)別出各種語(yǔ)法單位 ,進(jìn)行句子分析 ,并 檢查 整個(gè)輸入字串是否為合法的程序。24. 語(yǔ)法規(guī)那么 :規(guī)定了由單詞構(gòu)造更大語(yǔ)法單位的規(guī)那么；如表達(dá)式，短語(yǔ)，語(yǔ)句，程序 等。25. 語(yǔ)法分析方法 :自上而下算符優(yōu)先、自下而上遞歸下降26. 重要的語(yǔ)法單位 :程序 ,子程序 ,語(yǔ)句,短語(yǔ),表達(dá)式等27. 上下文無(wú)關(guān)文法組成 :終結(jié)符號(hào)、非終結(jié)符號(hào)、開(kāi)始符號(hào)、產(chǎn)生式28. 句柄 . :一個(gè)句型的最左直接短語(yǔ)。29. 素短語(yǔ) :至少含有一個(gè)終結(jié)符 ,且不

4、可在分割成為更小的短語(yǔ)。一個(gè)句型的最左素短 語(yǔ)即為可 歸約串。30. 遞歸下降分析的兩個(gè)問(wèn)題 文法的左遞歸、文法的回溯。31. 語(yǔ)法制導(dǎo)翻譯：在語(yǔ)法分析的每次歸約或推導(dǎo)時(shí) ,根據(jù)產(chǎn)生式的語(yǔ)義進(jìn)行翻譯的一種方法。 符號(hào)表32. 編譯程序中最主要的有如下幾種： 符號(hào)表，常量表，標(biāo)號(hào)表，子程序名表，四 元式表等。33. 符號(hào)表的查找技術(shù)：線性查找、二叉查找樹(shù)、哈希表35. 中間代碼生成：根據(jù)語(yǔ)義規(guī)那么 ,把各種語(yǔ)法單位翻譯成中間代碼序列.36. 靜態(tài)語(yǔ)義檢查： 類型檢查、控制流檢查、一致性檢查、相關(guān)名字檢查37. 中間代碼的表示方法： 四元式、三元式、間接三元式、逆波蘭式、樹(shù)形表示、 DAG 優(yōu)化38. 代碼優(yōu)化： 對(duì)產(chǎn)生的中間代碼序列進(jìn)行加工變換，使變換后的代碼更為高效。39. 優(yōu)化的幾種方法：刪除公共子表達(dá)式、 復(fù)寫傳播、刪除無(wú)用代碼、 代碼外提、強(qiáng)度削弱、刪 除歸納變量。40. 必經(jīng)節(jié)點(diǎn)集： 流圖通路中所必須經(jīng)過(guò)的節(jié)點(diǎn)的集合41. 回邊： 必經(jīng)節(jié)點(diǎn)集中從前方節(jié)點(diǎn)到前方節(jié)點(diǎn)的邊42. 可規(guī)約流圖： 流圖中除去回邊而剩余局部構(gòu)成無(wú)環(huán)路的流圖 .43. 引用定值集 udA ：能到達(dá)引用點(diǎn)u-A u點(diǎn)引用了 A的變量A的所有定值點(diǎn)d1,d2dr