注：加粗表示可能考簡(jiǎn)答題簡(jiǎn)答題(每小題 5 分，共 20 分) 論述題(每小題 10 分，共 20 分) 計(jì)算(每小題 12 分 ，共 60 分)1、編譯程序的構(gòu)成：源程序詞法分析語(yǔ)法分析語(yǔ)義分析和優(yōu)化目標(biāo)代碼生成第二章 文法與語(yǔ)言1、一些概念性的東西（1）推導(dǎo)：句型句子，自頂向下。（2）歸約：句子句型，自底向上。（2）句型：一個(gè)文法經(jīng)過(guò)N（N=1）步推導(dǎo)后得到的結(jié)果（含有非終結(jié)符號(hào)）（3）句子：一個(gè)文法經(jīng)過(guò)N（N=1）步推導(dǎo)后得到的結(jié)果（僅含有終結(jié)符號(hào)）（4）句柄：一個(gè)句型的最左簡(jiǎn)單短語(yǔ)。（樹(shù)的最下面）（5）VN：文法的非終結(jié)符號(hào)集合（6）VT：文法的終結(jié)符號(hào)集合（7）P：文法的規(guī)則的集合（8）S：文法的識(shí)別符號(hào)或開(kāi)始符號(hào)（9）短語(yǔ)：由樹(shù)的各個(gè)樹(shù)葉節(jié)點(diǎn)組成的符號(hào)組，有相對(duì)于XX的區(qū)別。（10）簡(jiǎn)單短語(yǔ)：也叫直接短語(yǔ)，有非終結(jié)符一步退出的短語(yǔ)。2、Chomsky文法分類0型文法：短語(yǔ)結(jié)構(gòu)文法 圖靈機(jī)（TM，Turing Machine）1型文法（CSG）：上下文有關(guān)文法 線性界限自動(dòng)機(jī)（LBA，Linear bounded automata）2型文法（CFG）：上下文無(wú)關(guān)文法 下推自動(dòng)機(jī)（PDA，Push Down automata）3型文法（RG）：正則文法 有窮狀態(tài)自動(dòng)機(jī)（FA，F(xiàn)inite automata）文法的判斷：3型文法：左邊必須只有一個(gè)字符，且必須是非終結(jié)符； 其右邊最多只能有兩個(gè)字符，且當(dāng)有兩個(gè)字符時(shí)必須有一個(gè)為終結(jié)符而另一個(gè)為非終結(jié)符。當(dāng)右邊只有一個(gè)字符時(shí)，此字符必須為終結(jié)符。 對(duì)于3型文法中的所有產(chǎn)生式，其右邊有兩個(gè)字符的產(chǎn)生式，這些產(chǎn)生式右邊兩個(gè)字符中終結(jié)符和非終結(jié)符的相對(duì)位置一定要固定，也就是說(shuō)如果一個(gè)產(chǎn)生式右邊的兩個(gè)字符的排列是：終結(jié)符非終結(jié)符，那么所有產(chǎn)生式右邊只要有兩個(gè)字符的，都必須前面是終結(jié)符而后面是非終結(jié)符。2型文法：左邊必須有且僅有一個(gè)非終結(jié)符。 2型文法所有產(chǎn)生式的右邊可以含有若干個(gè)終結(jié)符和非終結(jié)符（只要是有限的就行，沒(méi)有個(gè)數(shù)限制）。1型文法：1型文法所有產(chǎn)生式左邊可以含有一個(gè)、兩個(gè)或兩個(gè)以上的字符，但其中必須至少有一個(gè)非終結(jié)符。 與2型文法第二點(diǎn)相同。3、文法壓縮，消除左遞歸4、已知文法，證明某符號(hào)串是該文法的句子5、文法壓縮：P506、消除文法左遞歸：P537、文法四要素：VN（非終結(jié)符），VT（終結(jié)符），P（重寫規(guī)則），Z（識(shí)別符號(hào)）第三章 詞法分析1、詞法分析的任務(wù)（1）讀入源程序，（2）識(shí)別開(kāi)單詞（符號(hào)）并轉(zhuǎn)換為內(nèi)部表示,（3）做力所能及的工作（刪除無(wú)效字符、預(yù)處理）。2、正則表達(dá)式。3、對(duì)簡(jiǎn)單的正則表達(dá)式，能畫出狀態(tài)轉(zhuǎn)換圖（自動(dòng)機(jī)）4、NFA確定化為DFA（難） ，二者的異同。5、正則表達(dá)式引進(jìn)的必要性易理解正被定義的是什么符號(hào)集合。更容易構(gòu)造高效識(shí)別程序有利于自動(dòng)地構(gòu)造識(shí)別程序可用于其他各種信息流的處理6、文法壓縮的基本思想若一個(gè)符號(hào)不能出現(xiàn)在文法的任何句型中，則該符號(hào)是無(wú)用的若一個(gè)非終結(jié)符號(hào)不能推導(dǎo)出終結(jié)符號(hào)串，該非終結(jié)符號(hào)是無(wú)用的第四章 語(yǔ)法分析自頂向下分析技術(shù)1、遞歸下降分析技術(shù)是無(wú)回溯的自頂向下分析技術(shù)。2、遞歸下降分析器是一個(gè)不帶回溯的自頂向下分析程序，該程序是由一組遞歸函數(shù)或過(guò)程組成的。其函數(shù)名應(yīng)該是終結(jié)符，函數(shù)體是根據(jù)重寫規(guī)則右部符號(hào)串的結(jié)構(gòu)編寫。3、求First，F(xiàn)ollow集合。第一步，壓縮文法，消除左遞歸，消除回溯。第二步，求First集合第三步，求Follow集合4、遞歸下降分析程序構(gòu)造的基本思想：每個(gè)函數(shù)名應(yīng)該是非終結(jié)符號(hào)當(dāng)遇到終結(jié)符時(shí)，讀入下一個(gè)符號(hào)當(dāng)遇到非終結(jié)符號(hào)時(shí)，調(diào)用該終結(jié)符的相應(yīng)函數(shù)當(dāng)遇到空時(shí)，返回第五章 語(yǔ)法分析自底向上分析技術(shù)1、移進(jìn)-歸約技術(shù)2、算符優(yōu)先分析基本思想，優(yōu)先函數(shù)的構(gòu)造3、求文法的LR(0)項(xiàng)集規(guī)范族，繪制對(duì)應(yīng)自動(dòng)機(jī)4、題型可見(jiàn)以前布置的練習(xí)題5、算符文法：沒(méi)有連續(xù)2個(gè)非終結(jié)符同時(shí)出現(xiàn)的情況，即兩個(gè)非終結(jié)符中間必然有一個(gè)或幾個(gè)終結(jié)符（算符）。6、質(zhì)短語(yǔ)：句型中至少包含一個(gè)終結(jié)符號(hào)，且除它自身外不再包含其他質(zhì)短語(yǔ)的短語(yǔ)。7、求算符優(yōu)先矩陣（P151-153）：等于號(hào)（=）：形如Z：=aXb，則a=b小于號(hào)（）：第一步，求各個(gè)非終結(jié)符的LastTeam集合（非終結(jié)符推導(dǎo)出的最后一個(gè)終結(jié)符，可能為空）；第二步，若有X：=xxxY的情況，則將Y的LastTeam放入X的LastTeam里；第三步：根據(jù)文法，若存在X：=A+B，則A的LastTeam的每一個(gè)元素都大于+。8、LR(k)基本思想：向前看k個(gè)符號(hào)，能一點(diǎn)都不回溯地識(shí)別給定的符號(hào)串。SLR(k)的實(shí)現(xiàn)思想：可不向前看就不看，否則至多看k個(gè)符號(hào)。9、算符優(yōu)先函數(shù)的基本思想：以數(shù)值的比較代替算符優(yōu)先關(guān)系的比較10、移入歸約的基本思想：使符號(hào)從左到右逐個(gè)進(jìn)棧，每當(dāng)棧頂形成一個(gè)“可歸約子串”，就把該子串歸約成一個(gè)非終結(jié)符號(hào)，即把該子串從棧頂彈出，再把歸約成的子串入棧，如此反復(fù)進(jìn)行。第六章 語(yǔ)義分析與中間代碼的生成1、屬性文法的概念屬性文法是擴(kuò)充的壓縮了的上下文無(wú)關(guān)文法，往往以語(yǔ)法制導(dǎo)定義或翻譯方案的形式出現(xiàn)語(yǔ)義規(guī)則：同一條產(chǎn)生式規(guī)則中符號(hào)的屬性之間的計(jì)算法則綜合屬性：由語(yǔ)法分析樹(shù)的子結(jié)點(diǎn)計(jì)算而得，是自下而上傳遞的。繼承屬性：由語(yǔ)法分析樹(shù)的父結(jié)點(diǎn)和兄弟結(jié)點(diǎn)計(jì)算而得，是自上而下傳遞的。2、賦值語(yǔ)句和If語(yǔ)句逆波蘭式的翻譯逆波蘭式又稱后綴表示法，其特點(diǎn)是無(wú)括號(hào)。例一：a+b*c/(d+e) 逆波蘭表示為：abc*de+/+例二：t=(a+b)*c/(d-e)逆波蘭式為：tab+c*de-/=例三：if (ab)max=b;else max=a;逆波蘭表示為：ab 11 GOF max b = 14 GO max a =ab11GOFmaxb=14GOmaxa=12345678910111213143、賦值語(yǔ)句翻譯成四元式形式: ( op , arg1 , arg2 , result )。 其中：op是運(yùn)算符， arg1和arg2是操作對(duì)象， result存放最終結(jié)果。若op是單目運(yùn)算符，則arg2可以省略。例：賦值語(yǔ)句:x=12+a*(b-10)/c; 寫出其四元式序列。從100號(hào)單元開(kāi)始存放四元式。OPArg1Arg2Result100-b10T1101*aT1T2102/T2cT3103+12T3T4104:=T4x第八章 代碼優(yōu)化1、基本塊劃分和構(gòu)造流圖基本塊：從第一個(gè)四元式進(jìn)入, 從最后一個(gè)四元式離開(kāi), 其間沒(méi)有停止也無(wú)分支的連續(xù)的四元式序列。流圖是一種有向圖，它由把控制流信息加到基本塊集合而形成。流圖中的結(jié)點(diǎn)是基本塊，流圖中的有向邊指明了控制流向。2、DAG圖畫法3、基本塊優(yōu)化（種類） 合并常量計(jì)算 消除公共子表達(dá)式 削減計(jì)算強(qiáng)度 刪除無(wú)用代碼基本塊的定義：程序的第一