編譯原理總復(fù)習(xí)

《編譯原理》總復(fù)習(xí)題型及分值教材各章知識點概覽習(xí)題講解.題型及分值一、判斷題（1′×5=5′）二、填空題（1′×15=15′）三、選擇題（2′×5=10′）四、名詞解釋題（3′×5=15′）五、計算題(5小題)（5′+10′+15′+15′+10′=55′）.教材各章知識點概覽第一章引論第二章高級語言及其語法描述第三章詞法分析第四章語法分析—自上而下分析第五章語法分析—自下而上分析第六章屬性文法和語法制導(dǎo)翻譯第七章語義分析和中間代碼產(chǎn)生第八章符號表第十章優(yōu)化.第一章引論基本概念

翻譯程序，編譯程序，編譯前端、編譯后端編譯過程的五個階段，各階段的任務(wù)及其依循的規(guī)則、描述工具分別是什么？編譯錯誤的種類語法錯誤、語義錯誤.第一章引論程序翻譯的兩種方式，它們的區(qū)別

編譯方式、解釋方式編譯程序的生成方法用機器語言/匯編語言作工具用高級語言作工具自編譯方式建立專門的編制編譯程序的有效工具.第二章高級語言及其語法描述基本概念

文法、上下文無關(guān)文法、推導(dǎo)、句型、句子、語言、語義、詞法規(guī)則、語法規(guī)則、語義規(guī)則名字和標(biāo)識符及其區(qū)別數(shù)組，內(nèi)情向量、表達式最左推導(dǎo)、最右推導(dǎo)、語法分析樹及其與推導(dǎo)之間的關(guān)系文法的二義性及其消除.第二章高級語言及其語法描述語句的分類功能上：說明性語句、執(zhí)行性語句形式上：簡單句、復(fù)合句、分程序形式語言分類(chomsky,1956)

0型普通（短語）文法

1型上下文有關(guān)文法

2型上下文無關(guān)文法

3型線性（正規(guī)、正則）文法.第三章詞法分析基本概念

DFA、NFA、狀態(tài)等價詞法分析器的功能及其輸出形式單詞符號的種類關(guān)鍵字、標(biāo)識符、常數(shù)、運算符、界符正規(guī)式→NFA→DFA→最少化DFA（注意：狀態(tài)函數(shù)定義不完整之情形）詞法分析器的自動產(chǎn)生工具：

LEX狀態(tài)轉(zhuǎn)換圖的構(gòu)造(標(biāo)識符、整數(shù)).第四章語法分析—自上而下分析語法分析的方法自上而下、自下而上自上而下分析的基本思想自上而下分析面臨的主要問題左遞歸、回溯自上而下分析的基本方法

LL（1）分析法、遞歸下降分析器LL（1）的含義，LL（1）文法的判別.第四章語法分析—自上而下分析LL(1)分析器的組成部分輸入緩沖區(qū)、分析棧、分析表、總控程序LL(1)分析的四種動作成功、匹配、推導(dǎo)、報錯預(yù)測分析表的構(gòu)造左遞歸的消除（直接、間接）

FIRST、FOLLOW集的計算

LL(1)文法的判定及其分析表的構(gòu)造.第五章語法分析—自下而上分析基本概念短語、直接短語、句柄、素短語、最左素短語、規(guī)范歸約與規(guī)范推導(dǎo)自下而上分析的基本思想及其核心自下而上分析的基本方法算符優(yōu)先分析法（非規(guī)范歸約）LR分析法（規(guī)范歸約）給定一個文法的句型，找出其短語、直接短語、句柄、素短語和最左素短語.第五章語法分析—自下而上分析LR分析法的基本思想及其組成部分思想：記住歷史、展望未來、定奪現(xiàn)在組成：輸入緩沖區(qū)、分析棧（狀態(tài)、符號）、分析表（動作、轉(zhuǎn)換）、總控程序可歸約串的刻畫方式算符優(yōu)先：最左素短語LR分析法：句柄LR(0)、LR(1)、LR(k)、SLR的含義.第五章語法分析—自下而上分析LR分析器的四種動作移進、歸約、接受、報錯LR分析法可能遇到的問題及其解決辦法移進——歸約沖突歸約——歸約沖突語法分析器的自動產(chǎn)生工具

YACC.第五章語法分析—自下而上分析算符優(yōu)先關(guān)系表的構(gòu)造

算符文法及其算符優(yōu)先文法的判定

FIRSTVT、LASTVT集的構(gòu)造算符優(yōu)先表的構(gòu)造優(yōu)先表與優(yōu)先函數(shù)之間的關(guān)系LR（0）、SLR、LALR（1）、LR（1）分析表的構(gòu)造

拓廣文法、構(gòu)造LR(0)或LR(1)項目集規(guī)范簇、構(gòu)造相應(yīng)LR分析表.第六章屬性文法和語法制導(dǎo)翻譯基本概念

S—屬性文法L—屬性文法屬性的分類綜合屬性繼承屬性抽象語法樹的表示.第七章語義分析和中間代碼產(chǎn)生

常見的中間代碼的幾種形式后綴式（逆波蘭式）、三地址代碼（三元式、四元式、間接三元式）、DAG圖表示、抽象語法樹后綴式（逆波蘭式）的表示各類語句的翻譯（四元式）表達式（算術(shù)及布爾）、賦值語句、數(shù)組、IF語句、WHILE語句.第八章符號表

符號表的基本組成、基本操作組成：名字欄和信息欄操作：查表、填表、訪表、更新、刪除符號表的組織方式直接方式、間接方式符號表的構(gòu)造和處理方法線性表、二叉樹、雜湊（哈希）.第八章符號表

內(nèi)情向量的基本表項維數(shù)、首地址、各維界差、各維上界、各維下屆、數(shù)組元素類型、地址不變量.第十章優(yōu)化基本概念優(yōu)化、基本塊、局部優(yōu)化優(yōu)化遵循的原則等價原則、有效原則、合算原則常見的優(yōu)化的幾種方法刪除公共子表達式、復(fù)寫傳播、刪除無用代碼、合并已知量、代碼外提、強度削弱、刪除歸納變量。（后三種涉及循環(huán)優(yōu)化）.第十章優(yōu)化基本塊的劃分及其程序流圖的構(gòu)造

.習(xí)題講解計算題注意復(fù)習(xí)書上的例題及其平時作業(yè)題。在復(fù)習(xí)時，一定要親手獨立做一遍！.習(xí)題講解計算題構(gòu)造與下列正規(guī)式等價的最少化DFA

1(0|1)*101(0|1)*(00|11)(0|1)*.習(xí)題講解計算題令文法G為：

E→E-T|TT→T/F|FF→（E）|i（1）消除文法的左遞歸并構(gòu)造其LL(1)分析表（2）構(gòu)造該文法的算符優(yōu)先分析表.習(xí)題講解計算題（3）分析該文法是否為LR(0)、LR(1)、SLR、LALR文法，若是構(gòu)造相應(yīng)分析表（4）使用最左（右）推導(dǎo)的方法證明（T/F-i）/i是該文法的一個句型（5)求出句型（T/F-i）/i的所有短語、直接短語、句柄、素短語、最左素短語。.習(xí)題講解計算題將下列程序段翻譯成四元式序列。

while