全套編譯原理復(fù)習(xí)與期末必考試題

1、第一章：1.編譯程序的步驟和任務(wù)：1） 詞法分析：從左到右一個(gè)字符一個(gè)字符地讀入源程序，對(duì)構(gòu)成源程序的字符流進(jìn)行掃描和分解，從而識(shí)別出一個(gè)個(gè)單詞。2） 語法分析：是在詞法分析基礎(chǔ)上將單詞序列分解成各類語法短語(比如程序、語句、表達(dá)式等），通過語法分析確定整個(gè)輸入串是否構(gòu)成一個(gè)語法上正確的程序。3） 語義分析：是審查源程序有無語義錯(cuò)誤，為代碼生成階段收集類型信息。4） 中間代碼產(chǎn)生：將源程序變成一種易于翻譯成目標(biāo)代碼的內(nèi)部表示形式。5） 代碼優(yōu)化：對(duì)前階段生成的中間代碼進(jìn)行變換或改造，使生成的目標(biāo)代碼更為高效6） 目標(biāo)代碼生成：把中間代碼變換成特定機(jī)器上的絕對(duì)指令代碼或可重定位的指令代碼或匯編指

2、令代碼。2. 前端和后端的概念，試問前端通常包括那些階段，后端包括那些階段？ 答：前端只依賴于源語言，與目標(biāo)機(jī)無關(guān)。編譯程序的前端通常包括詞法分析程序、語法分析程序、語義分析程序、中間代碼生成程序及相關(guān)的表格管理程序和出錯(cuò)處理程序。后端是指編譯器中依賴于目標(biāo)機(jī)器的部分,只與中間代碼有關(guān)。通常包括目標(biāo)代碼生成程序、代碼優(yōu)化程序以及相關(guān)的表格管理程序和出錯(cuò)處理程序。遍（PASS)：對(duì)輸入文件（源程序或其等價(jià)的中間語言程序）從頭到尾掃視，完成預(yù)定處理的過程。 一個(gè)多遍的編譯程序較之一遍的編譯程序可能少占內(nèi)存，邏輯結(jié)構(gòu)可能清晰些，但效率相對(duì)可能差點(diǎn)3.程序的正確與否：結(jié)構(gòu)上的語法規(guī)則，語義上的語義規(guī)則

3、。翻譯程序：匯編，解釋，編譯。4.解釋程序及其與編譯程序的比較解釋程序功能：源程序+初始數(shù)據(jù)=計(jì)算結(jié)果解釋與編譯的區(qū)別：工作模式：這是根本區(qū)別，編譯把源程序翻譯成目標(biāo)代碼，而解釋直接得到計(jì)算結(jié)果，不生成目標(biāo)代碼。 存儲(chǔ)區(qū)內(nèi)容：編譯方式翻譯和執(zhí)行分開，解釋方式翻譯和執(zhí)行同時(shí)并允許修改源程序，因此二者存儲(chǔ)組織不同。效率：解釋慢于編譯，很多語言兩種方式都有。標(biāo)識(shí)符：=表達(dá)式第三章：文法和語言1.文法的直觀概念：一組判定規(guī)則。在實(shí)踐中，文法不包含多余產(chǎn)生式。2.文法G定義為四元組（VT，VN ,S, P ），其中： VT是一個(gè)非空有窮終結(jié)符號(hào)集合； VN是一個(gè)非空有窮的非終結(jié)符號(hào)集合， 且VTVN；

4、P是一個(gè)產(chǎn)生式的非空有窮集合（注意：產(chǎn)生式左部至少含有一個(gè)非終結(jié)符）； SÎ VN ，稱為開始符號(hào)，且S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次 。 通常用V表示VN VT,V稱為文法G的字母表或字匯表.3.句型、句子：設(shè)文法G，如果符號(hào)串x是從識(shí)別符號(hào)推導(dǎo)出來的，即Sx,xV*，則稱x是一個(gè)句型。僅含終結(jié)符號(hào)的句型是一個(gè)句子。4.語言：語言 L(G）是由文法G產(chǎn)生的所有句子所組成的集合。5文法的類型：逐漸對(duì)產(chǎn)生式施加限制 四種類型：0型，1型，2型，3型0型：G=(VT,VN,S,P)，規(guī)則形式 ： b®a a,Îb (VTÈVN)*, a中至少有一個(gè)非終結(jié)

5、符1型（上下文有關(guān)） ：½b½£½a½,僅S-> e除外 規(guī)則形式 ： a A b ® a g bA ÎVN, a ，g， b Î (VTÈVN)*, ge¹ 2型（上下文無關(guān)）：規(guī)則形式 ： Ab® A ÎVN，b Î (VTÈVN)* 3型正規(guī)文法（右線性）： A® aB 或 A ® a A,B ÎVN （左線性） A® Ba 或 A ® a a ÎVTÈe6.最左（最右）推導(dǎo)

6、在推導(dǎo)的任何一步Þ ，其中、是句型，都是對(duì)中的最左（右）非終結(jié)符進(jìn)行替換規(guī)范推導(dǎo)：即最右推導(dǎo)。規(guī)范句型：由規(guī)范推導(dǎo)所得的句型。7.文法的二義性如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹,或者說,若一個(gè)文法中存在某個(gè)句子,它有兩個(gè)不同的最左(最右)推導(dǎo),則說這個(gè)文法是二義的. 如果產(chǎn)生上下文無關(guān)語言的每一個(gè)文法都是二義的，則說此語言是先天二義的。8.自上而下的分析方法：自上而下分析法,是從文法開始符號(hào)出發(fā),反復(fù)使用各種產(chǎn)生式,逐步進(jìn)行推導(dǎo)，直至推導(dǎo)出輸入符號(hào)串。過程：自上而下方法是從文法識(shí)別符號(hào)開始，將它作為語法樹的根，向下逐步建立語法樹，使語法樹的末端結(jié)點(diǎn)符號(hào)串正好是輸入符號(hào)串。關(guān)

7、鍵問題：假定要被代換的最左非終結(jié)符號(hào)是A,且有n條產(chǎn)生式:A ® a1|a2|an,那么如何確定用哪個(gè)產(chǎn)生式右部去替代A? 9.自下而上的分析方法：自下而上分析法，是從輸入符號(hào)串開始，逐步進(jìn)行歸約，直至歸約到文法的開始符號(hào)。 過程：自下而上方法是從輸入符號(hào)串開始，以它作為語法樹的末端結(jié)點(diǎn)，自底向上地構(gòu)造語法樹，使語法樹的根結(jié)點(diǎn)正好是文法的開始符號(hào)。關(guān)鍵問題：因?yàn)榉治龉ぷ鞯拿恳徊蕉际菑漠?dāng)前串中選擇一個(gè)子串,將它歸約到某個(gè)非終結(jié)符,暫且把這個(gè)子串稱為可歸約串,問題是,每一步如何確定這個(gè)可歸約串? 10.短語：若SÞ* A且 A Þ +，則稱是句型相對(duì)于非終結(jié)符A的短語

8、。直接短語：若SÞ * A且AÞ，則稱是句型相對(duì)于非終結(jié)符A 的直接短語。句柄：一個(gè)句型的最左直接短語。（產(chǎn)生式的右部）11.子樹：一棵語法樹中一個(gè)特有的結(jié)點(diǎn)連同它的全部后裔，連接這些后裔的邊以及這些結(jié)點(diǎn)的標(biāo)記，稱為子樹。子樹與短語的關(guān)系 (1) 短語：子樹的末端結(jié)點(diǎn)(即樹葉)組成的符號(hào)串； (2) 直接短語：簡(jiǎn)單子樹的末端結(jié)點(diǎn)組成的符號(hào)串； (3) 句柄：最左簡(jiǎn)單子樹的末端結(jié)點(diǎn)組成的符號(hào)串；左圖所示的關(guān)于句型E+E*i的語法樹來說： 它有3棵子樹，即3個(gè)短語分別為i、E*i和E+E*i；直接短語、句柄均為i。從語法樹中可以看出，所有樹葉的組合就是其相對(duì)應(yīng)的父結(jié)點(diǎn)的短語。

9、句型i+i*i的語法樹有5棵子樹，短語和直接短語如下：直接短語：i1， i2 ， i3短語：i1，i2，i3，i1*i2，i1*i2+i3句柄：i1注意：i2+i3不是短語不是某棵子樹的結(jié)果12.有關(guān)文法的實(shí)用限制：有害規(guī)則是指形為U->U的產(chǎn)生式。會(huì)引起文法二義性。多余規(guī)則是指文法中那些任何句子推導(dǎo)都用不到的規(guī)則,包括兩種規(guī)則,即不可到達(dá)的和不可終止的。不可達(dá)到的：不在文法的任何規(guī)則右部出現(xiàn)的非終結(jié)符。不可終止的：文法中那些不能從其推出終結(jié)符號(hào)串的非終結(jié)符。第四章：詞法分析1.任務(wù)：從左至右逐個(gè)字符地對(duì)源程序進(jìn)行掃描，產(chǎn)生一個(gè)個(gè)單詞序列，用以語法分析2、接口方式：（1）詞法分析工作可以

10、組織成獨(dú)立的一遍,把字符流的源程序變?yōu)閱卧~序列，輸出在一個(gè)中間文件上，這個(gè)文件作為語法分析程序的輸入而繼續(xù)編譯過程。（2）將詞法分析程序設(shè)計(jì)成一個(gè)子程序，當(dāng)語法分析程序需要一個(gè)單詞時(shí)，則調(diào)用該子程序，從源程序中讀入一些字符，直到識(shí)別出一個(gè)單詞，或說直到下一個(gè)單詞的第一個(gè)字符為止，這種設(shè)計(jì)方案是把詞法分析和語法分析程序放在同一遍，省掉了中間文件。單詞符號(hào)的輸出形式：二元組：（單詞種別，單詞自身的值）單詞符號(hào)的分類：關(guān)鍵字，標(biāo)識(shí)符 ，常數(shù)，運(yùn)算符，界符等（這種分類不是唯一的）3. 正規(guī)文法與正規(guī)式的轉(zhuǎn)換（若兩個(gè)正規(guī)式x和y所表示的正規(guī)集相同，則說x和y等價(jià)，寫作x=y。）4.NFA轉(zhuǎn)換為DFA：D

11、FA的表示（1）用轉(zhuǎn)換函數(shù)；（2）狀態(tài)轉(zhuǎn)換矩陣；（3）狀態(tài)轉(zhuǎn)換圖NFA與DFA的主要區(qū)別：允許有多個(gè)初始狀態(tài)。允許狀態(tài)在其輸出邊上有相同的符號(hào)(多值映射)。允許輸出邊上有空串符號(hào)e 。NFA特點(diǎn):在給定狀態(tài)和符號(hào)的情況下，不能唯一的確定下一個(gè)狀態(tài)。NFA的確定化基本方法 基本方法:e邊合并 ,符號(hào)合并 (NFA轉(zhuǎn)化成的DFA不是唯一的) 【 例 】 NFA M如右圖所示，試將其確定化為DFA M'?！窘獯稹浚?）用子集法將圖所示的NFA M確定化為表1。（2）對(duì)表1中的所有子集重新命名得到表2的狀態(tài)轉(zhuǎn)換矩陣_closure(S0)5.DFA化簡(jiǎn)：通過消除多余狀態(tài)和合并等價(jià)狀態(tài)將一個(gè)DF

12、A M轉(zhuǎn)換成一個(gè)最小的與之等價(jià)的DFA M多余狀態(tài)是指，從該自動(dòng)機(jī)的開始狀態(tài)出發(fā)，任何輸入串都不能到達(dá)的那個(gè)狀態(tài)。在有窮自動(dòng)機(jī)中，兩個(gè)狀態(tài)s和t等價(jià)的條件是：1）一致性條件：即s和t必須同為終態(tài)或同為非終態(tài)2）蔓延性條件：即對(duì)所有輸入符號(hào)，s和t必須轉(zhuǎn)換到等價(jià)的狀態(tài)里。 有窮自動(dòng)機(jī)的狀態(tài)s和t不等價(jià)，則稱這兩個(gè)狀態(tài)是可區(qū)別的。 6.正規(guī)式轉(zhuǎn)換為有窮自動(dòng)機(jī)：r=s|txyN(t)N(s)eeeer=s*xyeeeeN(s)第五章：自頂向下語法分析方法求FIRST集，F(xiàn)OLLOW集LL（1）文法判定1、語法分析是編譯程序的核心部分：在詞法分析的基礎(chǔ)上，識(shí)別單詞符號(hào)序列是否是給定文法的正確句子（程序

13、）。自上而下分析的前提：消除左遞規(guī)和消除回溯。自頂向下分析法就是從文法的開始符號(hào)出發(fā)，試圖推導(dǎo)出與輸入的單詞串完全匹配的句子。如果能夠推導(dǎo)出，則該輸入串是給定文法的句子。如果不能推導(dǎo)出，則該輸入串不是給定文法的句子。2.自頂向下分析法分兩種：不確定的自頂向下分析法：是帶有回溯的分析方法，效率低，代價(jià)高，極少使用。確定的自頂向下分析法：對(duì)文法有一定的限制，但實(shí)現(xiàn)簡(jiǎn)單直觀，便于手工或自動(dòng)構(gòu)造。3.確定的自頂向下分析思想：判定是否為L(zhǎng)L（1）文法首符號(hào)FIRST集：設(shè)G=（ VT ，VN，S，P）是上下文無關(guān)文法FIRST(a)=a| a a,aÎ VT, a ， ÎV*若a ，

14、則規(guī)定 Î FIRST(a).后跟符號(hào)FOLLOW集：FOLLOW(A)=a½S Aa,aÎ VT, A Î VN 若S .A, 則規(guī)定#Follow(A).選擇集合SELECT集：給定上下文無關(guān)文法的產(chǎn)生式A->,A VN, V*，若，則SELECT（A-> ）=FIRST（ ） 如果 ，則SELECT(A->)=(FIRST( )-)ÈFOLLOW(A)4.LL(1)的含義：LL(1)文法是無二義的、LL(1)文法不含左遞歸第1個(gè)L：從左到右掃描輸入串 第2個(gè)L：生成的是最左推導(dǎo)1 ：向右看1個(gè)輸入符號(hào)便可決定選擇哪個(gè)產(chǎn)生

15、式一個(gè)上下文無關(guān)文法是LL(1)文法的充分必要條件是：對(duì)每個(gè)非終結(jié)符A的任兩個(gè)不同產(chǎn)生式 A®a，A®，滿足：Select(A®a)Select(A®)=Æ,其中：a、不同時(shí)推導(dǎo)出e 注：對(duì)LL(1)文法進(jìn)行語法分析時(shí)不會(huì)產(chǎn)生回溯。5.某些非LL(1)文法到LL(1)文法的等價(jià)變換:1. 提取左公因子2. 消除左遞歸（如果一個(gè)文法是左遞歸時(shí)，則不能采用自頂向下分析法。）(1)左遞歸的定義 （含有左遞歸的文法絕對(duì)不是LL（1）文法）一個(gè)文法含有下列形式的產(chǎn)生式時(shí)， A®Ab AÎVN , bÎV* 直接左遞歸 A&#

16、174;Bb B® Aa A, BÎVN , a，bÎ V* 間接左遞歸(2)直接左遞歸的消除 （改為右遞歸）S®bS S®aS| S®Sa S®b 形如： A A a|（a非e，不以A打頭）改寫為： A A¢ A¢ aA¢ | e 形如： AAa1 | Aa2 | . . . | Aan | b1 | b2 | . . . | bm 其中，每個(gè)a都不等于e ，b1 , . . . , bm 均不以A開頭。改寫為： A b1 A¢ | b2 A¢ | . . . | bm A

17、¢ A¢ a1 A¢ | a2 A¢ | . . . | an A¢ | e E T E'E' + T E'T F T'T' * F T'F ( E )i E E + TT T T * FFF ( E )i 6不確定性分析思想：（1）由于相同左部的產(chǎn)生式的右部FIRST集交集不為空而引起回塑。 S->xAy A->ab|a（2）由于相同左部產(chǎn)生式的右部存在能的，且非終結(jié)符FOLLOW集中含有其他產(chǎn)生式右部FIRST集的元素。 1)S->aAS 2)S->b 3) A->

18、;bAS 4)A-> FOLLOW（A）=a,b（3）由于文法含有左遞歸而引起回溯7.確定的自頂向下分析方法：遞歸子程序法、預(yù)測(cè)分析法。8.預(yù)測(cè)分析法基本思想 ：從左到右掃描源程序，直接根據(jù)：預(yù)測(cè)分析器構(gòu)成：預(yù)測(cè)分析程序，先進(jìn)后出棧，預(yù)測(cè)分析表與文法有關(guān)第七章:LR分析LR(0)分析表識(shí)別活前綴的DFA分析過程對(duì)輸入串的分析過程（已知文法的分析表）LR分析法：是一種規(guī)范規(guī)約過程LR(k)含義L ：從左到右掃描輸入符號(hào)R ：最右推導(dǎo)對(duì)應(yīng)的最左歸約(反序完成最右推導(dǎo))k ：超前讀入k個(gè)符號(hào)，以便確定歸約用的產(chǎn)生式LR(0)項(xiàng)目分類移進(jìn)項(xiàng)目，形如Aa ab，a是終結(jié)符,a ,b ÎV

19、* 以下同 【例】 S bBB 待約項(xiàng)目，形如 A a Bb 【例】 Sb BB SbB B 歸約項(xiàng)目，形如 A a 【例】 SbBB 接受項(xiàng)目，形如 S S 第八章：1.語義處理的兩個(gè)功能：（1）審查每個(gè)語法結(jié)構(gòu)的靜態(tài)語義，即驗(yàn)證語法結(jié)構(gòu)合法的程序是否真正有意義。（2）執(zhí)行真正的翻譯，生成中間代碼或目標(biāo)代碼。2.屬性文法：一個(gè)屬性文法包含一個(gè)上下文無關(guān)文法和一系列語義規(guī)則,這些語義規(guī)則附在每個(gè)產(chǎn)生式上。文法符號(hào)的屬性:單詞的含義，即與文法符號(hào)相關(guān)的一些信息。如，類型、值、存儲(chǔ)地址等。一個(gè)屬性文法是一個(gè)三元組A=(G, V, F)G：上下文無關(guān)文法。V：屬性的有窮集。每個(gè)屬性與文法的一個(gè)終結(jié)符

20、或非終結(jié)符相連。屬性與變量一樣，可以進(jìn)行計(jì)算和傳遞。F：關(guān)于屬性的斷言或謂詞(一組屬性的計(jì)算規(guī)則)的有窮集。斷言或語義規(guī)則與一個(gè)產(chǎn)生式相聯(lián)，只引用該產(chǎn)生式左端或右端的終結(jié)符或非終結(jié)符相聯(lián)的屬性。綜合屬性:若產(chǎn)生式左部的單非終結(jié)符A的屬性值由右部各非終結(jié)符的屬性值決定, 則A的屬性稱為綜合屬性。 繼承屬性:若產(chǎn)生式右部符號(hào)B的屬性值是根據(jù)左部非終結(jié)符的屬性值或者右部其它符號(hào)的屬性值決定的,則B的屬性為繼承屬性。在兩種情況下，都說屬性b依賴于屬性c1,c2,ck(1)非終結(jié)符既可有綜合屬性也可有繼承屬性，但文法開始符號(hào)沒有繼承屬性。(2) 終結(jié)符只有綜合屬性，沒有繼承屬性，它們由詞法程序提供。在計(jì)

21、算時(shí)： 綜合屬性沿屬性語法樹向上傳遞；繼承屬性沿屬性語法樹向下傳遞。 3.語法制導(dǎo)翻譯：是指在語法分析過程中，完成附加在所使用的產(chǎn)生式上的語義規(guī)則描述的動(dòng)作。語法制導(dǎo)翻譯實(shí)現(xiàn)：對(duì)單詞符號(hào)串進(jìn)行語法分析，構(gòu)造語法分析樹，然后根據(jù)需要構(gòu)造屬性依賴圖，遍歷語法樹并在語法樹的各結(jié)點(diǎn)處按語義規(guī)則進(jìn)行計(jì)算。4.中間代碼：1、是復(fù)雜性介于源程序語言和機(jī)器語言的一種表示形式。2、一般，快速編譯程序直接生成目標(biāo)代碼。3、為了使編譯程序結(jié)構(gòu)在邏輯上更為簡(jiǎn)單明確，常采用中間代碼，這樣可以將與機(jī)器相關(guān)的某些實(shí)現(xiàn)細(xì)節(jié)置于代碼生成階段仔細(xì)處理，并且可以在中間代碼一級(jí)進(jìn)行優(yōu)化工作，使得代碼優(yōu)化比較容易實(shí)現(xiàn)。何謂中間代碼：源

22、程序的一種內(nèi)部表示，不依賴目標(biāo)機(jī)的結(jié)構(gòu)，易于代碼的機(jī)械生成。為何要轉(zhuǎn)換成中間代碼邏輯結(jié)構(gòu)清楚；利于不同目標(biāo)機(jī)上實(shí)現(xiàn)同一種語言。便于移植，便于修改，便于進(jìn)行與機(jī)器無關(guān)的優(yōu)化。中間代碼的幾種形式：逆波蘭記號(hào) ，三元式和樹形表示 ，四元式 逆波蘭記號(hào)：把運(yùn)算分量(操作數(shù))寫在前面，把運(yùn)算符寫在后面的表示法，又稱后綴表示法。中綴表達(dá)式向逆波蘭表達(dá)式轉(zhuǎn)換第十章：運(yùn)行時(shí)的存儲(chǔ)區(qū)為了使目標(biāo)程序能夠運(yùn)行，編譯程序要從操作系統(tǒng)中得到一塊存儲(chǔ)區(qū)，以使目標(biāo)程序能夠在其上運(yùn)行。運(yùn)行時(shí)的存儲(chǔ)區(qū)劃分目標(biāo)區(qū)：存放目標(biāo)代碼。代碼區(qū)（code）靜態(tài)數(shù)據(jù)區(qū)（static data）：編譯時(shí)能確定所占用空間的數(shù)據(jù)。棧區(qū)和堆區(qū)（st

23、ack and heap）：可變數(shù)據(jù)及管理過程活動(dòng)的控制信息。存儲(chǔ)分配方案策略：靜態(tài)存儲(chǔ)分配；動(dòng)態(tài)存儲(chǔ)分配：棧式、 堆式。 靜態(tài)存儲(chǔ)分配1、基本策略在編譯時(shí)就安排好目標(biāo)程序運(yùn)行時(shí)的全部數(shù)據(jù)空間，并能確定每個(gè)數(shù)據(jù)項(xiàng)的單元地址。2、適用的分配對(duì)象：子程序的目標(biāo)代碼段；全局?jǐn)?shù)據(jù)目標(biāo)（全局變量）3、靜態(tài)存儲(chǔ)分配的要求：不允許遞歸調(diào)用，不含有可變數(shù)組。FORTRAN程序是段結(jié)構(gòu)，不允許遞歸，數(shù)據(jù)名大小、性質(zhì)固定。 是典型的靜態(tài)分配動(dòng)態(tài)存儲(chǔ)分配 1、如果一個(gè)程序設(shè)計(jì)語言允許遞歸過程、可變數(shù)組或允許用戶自由申請(qǐng)和釋放空間，那么，就需要采用動(dòng)態(tài)存儲(chǔ)管理技術(shù)。2、兩種動(dòng)態(tài)存儲(chǔ)分配方式：棧式，堆式棧式動(dòng)態(tài)存儲(chǔ)分配

24、分配策略：將整個(gè)程序的數(shù)據(jù)空間設(shè)計(jì)為一個(gè)棧。 【例】在具有遞歸結(jié)構(gòu)的語言程序中，每當(dāng)調(diào)用一個(gè)過程時(shí)，它所需的數(shù)據(jù)空間就分配在棧頂，每當(dāng)過程工作結(jié)束時(shí)就釋放這部分空間。過程所需的數(shù)據(jù)空間包括兩部分一部分是生存期在本過程這次活動(dòng)中的數(shù)據(jù)對(duì)象。如局部變量、參數(shù)單元、臨時(shí)變量等；另一部分則是用以管理過程活動(dòng)的記錄信息(連接數(shù)據(jù))。活動(dòng)記錄（AR） 一個(gè)過程的一次執(zhí)行所需要的信息使用一個(gè)連續(xù)的存儲(chǔ)區(qū)來管理，這個(gè)區(qū) (塊)叫做一個(gè)活動(dòng)記錄。構(gòu)成1、臨時(shí)工作單元；2、局部變量；3、機(jī)器狀態(tài)信息；4、存取鏈；5、控制鏈；6、實(shí)參；7、返回地址第十一章：什么是代碼優(yōu)化所謂優(yōu)化，就是對(duì)代碼進(jìn)行等價(jià)變換，使得變換后

25、的代碼運(yùn)行結(jié)果與變換前代碼運(yùn)行結(jié)果相同，而運(yùn)行速度加快或占用存儲(chǔ)空間減少。優(yōu)化原則：等價(jià)原則：經(jīng)過優(yōu)化后不應(yīng)改變程序運(yùn)行的結(jié)果。 有效原則：使優(yōu)化后所產(chǎn)生的目標(biāo)代碼運(yùn)行時(shí)間較短，占用的存儲(chǔ)空間較小。 合算原則：以盡可能低的代價(jià)取得較好的優(yōu)化效果。優(yōu)化分類：局部?jī)?yōu)化，循環(huán)優(yōu)化，全局優(yōu)化常見的優(yōu)化技術(shù)(1) 刪除多余運(yùn)算(刪除公共子表達(dá)式) (2) 代碼外提:是針對(duì)循環(huán)的(3)強(qiáng)度削弱; 把執(zhí)行時(shí)間較長(zhǎng)的運(yùn)算替換為執(zhí)行時(shí)間較短的運(yùn)算(4)變換循環(huán)控制條件 (5)合并已知量與復(fù)寫傳播 (6)刪除無用賦值基本塊定義程序中只有一個(gè)入口和一個(gè)出口的一段順序執(zhí)行的語句序列，稱為程序的一個(gè)基本塊。對(duì)四元式序列

26、，各個(gè)基本塊的入口語句是：(1)代碼序列的第一個(gè)語句。 (2)轉(zhuǎn)移語句的目標(biāo)語句。 (3)轉(zhuǎn)移語句的下一條語句。例子：(1) read (C)(2) A:= 0(3) B:= 1(4) L1: A:=A + B(5) if B>= C goto L2(6) B:=B+1(7) goto L1(8) L2: write (A)(9) halt必經(jīng)結(jié)點(diǎn)在程序流圖中，對(duì)任意結(jié)點(diǎn)m和n，如果從流圖的首結(jié)點(diǎn)出發(fā)，到達(dá)n的任一通路都要經(jīng)過m，則稱m是n的必經(jīng)結(jié)點(diǎn)，記為m DOM n。必經(jīng)結(jié)點(diǎn)集：流圖中結(jié)點(diǎn)n的所有必經(jīng)結(jié)點(diǎn)的集合稱為結(jié)點(diǎn)n的必經(jīng)結(jié)點(diǎn)集，記為D(n)?；剡叄杭僭O(shè)a b是流圖中一條有向邊，

27、如果b DOM a，則稱ab是流圖中的一條回邊。循環(huán)(依據(jù)回邊判斷)1、給出一個(gè)回邊 n®d，定義這個(gè)邊的(自然)循環(huán)是d加上所有不經(jīng)過d能到達(dá)n的結(jié)點(diǎn)；2、d是這個(gè)循環(huán)的首結(jié)點(diǎn)。 【 例 】 求出左圖的所有回邊?！窘獯稹?1) 66，因?yàn)镈(6)=1,2,4,6， 所以6 DOM 6，故66是回邊； (2) 74，因?yàn)镈(7)=1,2,4,7， 所以4 DOM 7，故74是回邊； (3) 42，因?yàn)镈(4)=1,2,4， 所以2 DOM 4，故42是回邊。容易看出，其它有向邊都不是回邊。 例二：求回邊和循環(huán) 回邊4 3（3 DOM 4） 循環(huán)：3,4,5,6,7,8,10回邊7 4

28、（ 4 DOM 7 ） 循環(huán)：4,5,6,7,8,10回邊107 （ 7 DOM 10 ） 循環(huán)： 7，8，10回邊8 3 （3 DOM 8） 循環(huán)：3,4,5,6,7,8,10 一、填空題（每空2分，共20分）1編譯程序首先要識(shí)別出源程序中每個(gè)單詞，然后再分析每個(gè)句子并翻譯其意義。 2編譯器常用的語法分析方法有自底向上和自頂向下兩種。3通常把編譯過程分為分析前端與綜合后端兩大階段。詞法、語法和語義分析是對(duì)源程序的分析，中間代碼生成、代碼優(yōu)化與目標(biāo)代碼的生成則是對(duì)源程序的綜合。4程序設(shè)計(jì)語言的發(fā)展帶來了日漸多變的運(yùn)行時(shí)存儲(chǔ)管理方案，主要分為兩大類，即靜態(tài)存儲(chǔ)分配方案和動(dòng)態(tài)存儲(chǔ)分配方案。5對(duì)編譯

29、程序而言，輸入數(shù)據(jù)是源程序，輸出結(jié)果是目標(biāo)程序。1計(jì)算機(jī)執(zhí)行用高級(jí)語言編寫的程序主要有兩種途徑：解釋和編譯。 2掃描器是詞法分析器，它接受輸入的源程序，對(duì)源程序進(jìn)行詞法分析并識(shí)別出一個(gè)個(gè)單詞符號(hào)，其輸出結(jié)果是單詞符號(hào)，供語法分析器使用。3自下而上分析法采用移進(jìn)、歸約、錯(cuò)誤處理、接受等四種操作。4一個(gè)LL（1）分析程序需要用到一張分析表和符號(hào)棧。5后綴式abc-/所代表的表達(dá)式是a/(b-c)。 二、單項(xiàng)選擇題（每小題2分，共20分）1詞法分析器的輸出結(jié)果是_C。A 單詞的種別編碼 B 單詞在符號(hào)表中的位置C 單詞的種別編碼和自身值 D 單詞自身值2 正規(guī)式 M 1 和 M 2 等價(jià)是指_C_。

30、  A M1和M2的狀態(tài)數(shù)相等         B M1和M2的有向邊條數(shù)相等C M1和M2所識(shí)別的語言集相等 D M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等 3 文法G：SxSx|y所識(shí)別的語言是_C_。A xyx  B (xyx)* C xnyxn(n0)     D x*yx* 4如果文法G是無二義的，則它的任何句子_A_。A最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹必定相同 B最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹可能不同 C最左推導(dǎo)和最右推導(dǎo)必定相同   D可能存在兩個(gè)不同的最左推導(dǎo)，

31、但它們對(duì)應(yīng)的語法樹相同 5構(gòu)造編譯程序應(yīng)掌握_D_。A源程序   B目標(biāo)語言       C 編譯方法      D以上三項(xiàng)都是 6四元式之間的聯(lián)系是通過_B_實(shí)現(xiàn)的。 A指示器         B臨時(shí)變量 C符號(hào)表              D程序變量 7表達(dá)式(AB)(CD)的逆波蘭表示為_B_。A AB

32、CD B ABCD      C ABCD          D ABCD 8. 優(yōu)化可生成_D_的目標(biāo)代碼。A運(yùn)行時(shí)間較短               B占用存儲(chǔ)空間較小C運(yùn)行時(shí)間短但占用內(nèi)存空間大 D運(yùn)行時(shí)間短且占用存儲(chǔ)空間小9下列_C_優(yōu)化方法不是針對(duì)循環(huán)優(yōu)化進(jìn)行的。A. 強(qiáng)度削弱     B刪除歸納變

33、量     C刪除多余運(yùn)算   D代碼外提10編譯程序使用_B_區(qū)別標(biāo)識(shí)符的作用域。 A. 說明標(biāo)識(shí)符的過程或函數(shù)名 B說明標(biāo)識(shí)符的過程或函數(shù)的靜態(tài)層次C說明標(biāo)識(shí)符的過程或函數(shù)的動(dòng)態(tài)層次 D. 標(biāo)識(shí)符的行號(hào)三、判斷題（對(duì)的打，錯(cuò)的打×，每小題1分，共10分）2一個(gè)有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)唯一的終態(tài)。x3一個(gè)算符優(yōu)先文法的每個(gè)非終結(jié)符號(hào)間都也可能存在優(yōu)先關(guān)系。X4語法分析時(shí)必須先消除文法中的左遞歸 。X6逆波蘭表示法表示表達(dá)式時(shí)無須使用括號(hào)。R9兩個(gè)正規(guī)集相等的必要條件是他們對(duì)應(yīng)的正規(guī)式等價(jià)。 X1編譯程序是對(duì)高級(jí)語言程序的編譯執(zhí)

34、行。X2一個(gè)有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)唯一的初始態(tài)。R3一個(gè)算符優(yōu)先文法的每個(gè)非終結(jié)符號(hào)間都不存在優(yōu)先關(guān)系。R4LL（1）語法分析時(shí)必須先消除文法中的左遞歸 。 R5LR分析法在自左至右掃描輸入串時(shí)就能發(fā)現(xiàn)錯(cuò)誤，但不能準(zhǔn)確地指出出錯(cuò)地點(diǎn)。 R6逆波蘭表示法表示表達(dá)式時(shí)根據(jù)表達(dá)式會(huì)使用括號(hào)。 X7靜態(tài)數(shù)組的存儲(chǔ)空間可以在編譯時(shí)確定。X8進(jìn)行代碼優(yōu)化時(shí)應(yīng)著重考慮循環(huán)的代碼優(yōu)化，這對(duì)提高目標(biāo)代碼的效率將起更大作用。X9兩個(gè)正規(guī)集相等的必要條件是他們產(chǎn)生的符號(hào)串是相同的。 R10一個(gè)語義子程序描述了一個(gè)文法所對(duì)應(yīng)的翻譯工作。 X1什么是S-屬性文法？什么是L-屬性文法？它們之間有什么關(guān)系？S-屬性

35、文法是只含有綜合屬性的屬性文法。 （2分）L-屬性文法要求對(duì)于每個(gè)產(chǎn)生式AàX1X2Xn，其每個(gè)語義規(guī)則中的每個(gè)屬性或者是綜合屬性，或者是Xj的一個(gè)繼承屬性，且該屬性僅依賴于：（1） 產(chǎn)生式Xj的左邊符號(hào)X1,X2Xj-1的屬性；（2） A的繼承屬性。 （2分）S-屬性文法是L-屬性文法的特例。 （分）什么是L（）分析器什么是L（）分析器所謂LR()分析，是指從左至右掃描和自底向上的語法分析，且在分析的每一步，只須根據(jù)分析棧當(dāng)前已移進(jìn)和歸約出的全部文法符號(hào)，并至多再向前查看0個(gè)輸入符號(hào)，就能確定相對(duì)于某一產(chǎn)生式左部符號(hào)的句柄是否已在分析棧的頂部形成，從而也就可以確定當(dāng)前所應(yīng)采取的分析

36、動(dòng)作 (是移進(jìn)還是按某一產(chǎn)生式進(jìn)行歸約等)。 五、綜合題（共40分）1（10分）對(duì)于文法 GS ： S 1A | 0B | A 0S | 1AA B 1S | 0BB (3 分 ) 請(qǐng)寫出三個(gè)關(guān)于 GS 的句子； (4 分 ) 符號(hào)串 11A0S 是否為 G S 的句型？試證明你的結(jié)論。 (3 分 ) 試畫出 001B 關(guān)于 G S 的語法樹。 答：（1） 三個(gè) 0 和 1 數(shù)量相等的串 （每個(gè)1分）（2） S => 1A => 11AA => 11A 0S （3）  2.（10分）設(shè)有語言 L= | 0,1 + ，且不以 0 開頭，但以 00 結(jié)尾 。 2 分）試

37、寫出描述 L 的正規(guī)表達(dá)式； （分）構(gòu)造識(shí)別 L 的 DFA （要求給出詳細(xì)過程，并畫出構(gòu)造過程中的 NFA 、 DFA 的狀態(tài)轉(zhuǎn)換圖，以及最小DFA的狀態(tài)轉(zhuǎn)換圖 ) 。 答：（ 1 ）（分）正規(guī)表達(dá)式： 1(0|1) * 00 （ 2 ）（分）第一步（分）：將正規(guī)表達(dá)式轉(zhuǎn)換為 NFA 第二步（分）：將 NFA 確定化為 DFA ：（分） 狀態(tài) 輸入 I 0 I 1   t 0 1 S A,D,B   q 0 q 1 A,D,B D,B,C D,B 重新命名 q 1 q 2 q 3 D,B,C D,B,C,Z D,B q 2 q 4 q 3 D,B D,B,C D,B &#

38、160; q 3 q 2 q 3 D,B,C,Z D,B,C,Z D,B   q 4 q 4 q 3 DFA 的狀態(tài)轉(zhuǎn)換圖（分） 第三步（分）：將DFA 最小化 ：（分） 將狀態(tài)劃分終態(tài)與非終態(tài)兩個(gè)集合：，根據(jù)、集合的情況，對(duì)集合進(jìn)行劃分狀態(tài) 輸入 I 0 I 1 將狀態(tài)集劃分為兩個(gè)集合：，根據(jù)、集合的情況，對(duì)集合進(jìn)行劃分狀態(tài) 輸入 I 0 I 1 將狀態(tài)集劃分為兩個(gè)集合：，根據(jù)、集合的情況，對(duì)集合進(jìn)行劃分狀態(tài) 輸入 I 0 I 1 最小DFA 的狀態(tài)轉(zhuǎn)換圖（分） （20分）給定文法 GE ： E E+T | T T T*F | FF (E) | i 該文法是 LL(1) 文法嗎？（

39、要求給出詳細(xì)過程，如果是LL（1），給出分析表）答：（1）該文法不是LL（1）文法，因?yàn)橛凶筮f歸，消除左遞歸可獲得一個(gè)LL（1）文法 （2分）（2） 消除左遞歸，得新文法 (3分)E TEE +TE| T FTT *FT |F (E) | i (3)求產(chǎn)生式右部的First集 (2.5分)First(TE) = First(T)= First(F)=(,i First(+TE) = + First(FT) = First(F)=(,i First(*FT) = * First(E) = ( First(i) = i （4） 求所有非終結(jié)符的Follow集(2.5分)Follow(E) = $,

40、) Follow(E) = Follow(E) = $,) Follow(T) = First(E)Follow(E)=+ $,)=$,+,) Follow(T) = Follow(T) =$,*,) Follow(F) = First(T)Follow(T) Follow(T)= $,*,) （5） 求所有產(chǎn)生式的Select集 (2.5分)Select（E TE）=First(TE)= (,i Select（E +TE）=First(+TE)= + Select（E ）= Follow(E) = $,) Select（T FT）=First(FT)= (,i Select（T *FT）=F

41、irst(*FT)= *Select（T ）= Follow(T) =$,+,) Select（F (E)）=First(E)= ( Select（F i）=First(i)= i （6）對(duì)相同左部的所有Select即求交集(2.5分)Select（E +TE）Select（E ）= Select（T *FT）Select（T ）= Select（F (E)）Select（F i）= 所以，改造后的文法是LL（1）文法，其分析表如下（7） LL(1) 分析表（ 5 分） V N V T + * i ( )$E E TE E TE    E E +TE    E E TT FTT FT  TT T *FTT T FF (E)F i1（10分）對(duì)于文法G：S®aSbS|aS|d證明該文法是二義性文法。答：一個(gè)文法，如果存在某個(gè)句子有不只一棵語法分析樹與之對(duì)應(yīng)，那么稱這個(gè)文法是二義性文法。（5分）句子aadbd有兩棵語法樹（5分，劃一棵樹給3分）。如下圖：（分）SaSSabSdddSSabSSad(1) (2)由此可知，