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

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

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

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

0型普通（短語）文法

1型上下文有關文法

2型上下文無關文法

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

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

LEX狀態轉換圖的構造(標識符、整數).第四章語法分析—自上而下分析語法分析的方法自上而下、自下而上自上而下分析的基本思想自上而下分析面臨的主要問題左遞歸、回溯自上而下分析的基本方法

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

FIRST、FOLLOW集的計算

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

YACC.第五章語法分析—自下而上分析算符優先關系表的構造

算符文法及其算符優先文法的判定

FIRSTVT、LASTVT集的構造算符優先表的構造優先表與優先函數之間的關系LR（0）、SLR、LALR（1）、LR（1）分析表的構造

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

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

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

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

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

.習題講解計算題注意復習書上的例題及其平時作業題。在復習時，一定要親手獨立做一遍！.習題講解計算題構造與下列正規式等價的最少化DFA

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

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

while