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

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

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

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

0型普通（短語(yǔ)）文法

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

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

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

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

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

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

FIRST、FOLLOW集的計(jì)算

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

YACC.第五章語(yǔ)法分析—自下而上分析算符優(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)項(xiàng)目集規(guī)范簇、構(gòu)造相應(yīng)LR分析表.第六章屬性文法和語(yǔ)法制導(dǎo)翻譯基本概念

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

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

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

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

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

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

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

while