南信大編譯原理考題.docx

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