《編譯原理》歷年試題及答案

<編譯原理>歷年試題及答案一． （每項選擇2分，共20分）選擇1．將編譯程序分成若干個遍是為了_b 。a.提高程序的執(zhí)行效率b.c.利用有限的機器內(nèi)存并提高機器的執(zhí)行效率d.利用有限的機器內(nèi)存但降低了機器的執(zhí)行效2．構(gòu)造編譯程序應(yīng)掌握 d 。a.源程序 b.目標語言c.編譯方法 d.以上三項都3．變量應(yīng)當(dāng)＿c。a.持有左值 持有右值c.既持有左值又持有右值d.既不持有左值也不持有右4．編譯程序絕大多數(shù)時間花在 d 上。a.出錯處理 詞法分析c.目標代碼生成d.管理表格5．詞法分析器的輸出結(jié)果是_c a.單詞的種別編碼 b.單詞在符號表中的位置c.單詞的種別編碼和自身值d.單詞自身6．正規(guī)式MI和M2等價是指 c 。a.MI和M2的狀態(tài)數(shù)相等 b.Ml和M2的有向弧條數(shù)相等。C.M1和M2所識別的語言集相等 d.Ml和M2狀態(tài)數(shù)和有向弧條數(shù)相等中間代碼生成時所依據(jù)的是—c。a．語法規(guī)則b．詞法規(guī)則c．語義規(guī)則d．等價變換規(guī)8．后綴式ab+cd+/可用表達式 b_來表示。a．a(chǎn)+b/c+d b．(a+b)/(c+d) c．a(chǎn)+b/(c+d) d．a(chǎn)+b+c/d程序所需的數(shù)據(jù)空間在程序運行前就可確定，稱為 c ＿管理技術(shù)a.動態(tài)存儲 棧式存儲 c.靜態(tài)存儲 d.堆式存儲堆式動態(tài)分配申請和釋放存儲空間遵守 d ＿原則a.先請先放b.先請后放c.后請先放d.任意二（每小題10分，共80分）簡答題畫出編譯程序的總體結(jié)構(gòu)圖，簡述各部分的主要功能。G[E]:E→ET+|TT→TF*|FF→F^|a試證：FF^^*是文法的句型，指出該句型的短語、簡單短語和句柄.為正規(guī)式(a|b)*a(a|b)構(gòu)造一個確定的有限自動機。G(S)：S→(L)|aS|aL→L，S|S消除左遞歸和回溯；FIRST構(gòu)造預(yù)測分析表。已知文法A->aAd|aAb|ε判斷該文法是否SLR（1）文法，若是構(gòu)造相應(yīng)分析表，并對輸入串a(chǎn)b#給出分析過程。構(gòu)造算符文法G[H的算符優(yōu)先關(guān)系（含＃G[H]：H→H;M|MM→d|aHbG（S）（1）S BB（2）B aB（3）B b。給出DFA圖2）.給出LR分析表．假定輸入串為abaa，請給出LR分析過程（即狀態(tài)，符號，輸入串的變化過程。將下面的語句翻譯成四元式序列：whileA<C∧B<DdoifA=1thenC:=C+lelsewhileA≤DdoA:=A+2；對下面的流圖，(1)N的必經(jīng)結(jié)點集(2)求出流圖中的回邊，(3)求出流圖中的循環(huán)。參考答案一．單項選擇題將編譯程序分成若干個遍b。.d。對編譯而言，變量既持有左值又持有右值，故選c。編譯程序打交道最多的就是各種表格，因此選d。詞法分析器輸出的結(jié)果是單詞的種別編碼和自身值，選。正規(guī)式M1M2。選c。b。Cd二．簡答題【解答】編譯程序的總體結(jié)構(gòu)圖如圖1.2所示。詞法分析器：輸入源程序，進行詞法分析，輸出單詞符號。語法分析器：在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則（文法規(guī)則）把單詞符號串分解成各類語法單位，并判斷輸入串是否構(gòu)成語法上正確的“程序”。中間代碼生成器：按照語義規(guī)則把語法分析器歸約（或推導(dǎo)）出的語法單位翻譯成一定形式的中間代碼，比如說四元式。優(yōu)化：對中間代碼進行優(yōu)化處理。目標代碼生成器：把中間代碼翻譯成目標語言程序。表格管理模塊保存一系列的表格，登記源程序的各類信息和編譯各階段的進展情況。編譯過程都在不斷地和表格打交道。出錯處理程序?qū)Πl(fā)現(xiàn)的錯誤都及時進行處理?！窘獯稹縀TFF^^*,F;相對于F的短語有F^;F^^;簡單短語有F;F^;句柄為F.【解答】最簡DFA如圖2.66所示。【解答】(1)S→(L)|aS’S’→S|εL→SL’L’→SL’|ε評分細則：消除左遞歸2分，提公共因子2分。(2)FIRST和FOLLOWFIRST)S)＝{(，a} FOLLOW(S)＝{#，，)}FIRST(S’)＝{，a,ε} FOLLOW(S’)＝{#，，)}FIRST(L)＝{(，a} )}FIRST(L’)＝{，ε} 〕＝{)}【解答】拓廣文法(0)S->A(1)A->aAd(2)A->aAb(3)A->εDFAFOLLOW(A)={d,b,#}對于狀態(tài)I0：FOLLOW(A)∩{a}=Ф對于狀態(tài)I1：FOLLOW(A)∩{a}=Ф因為，在DFA中無沖突的現(xiàn)象，所以該文法是SLR(1)文法。(3)SLR(1)分析表狀態(tài)ACTIONGOTOaBd#A0S2r3r3r311acc2S2r3r3r333S5S44r1r1r15r2r2r2(4)串a(chǎn)b#的分析過程步驟狀態(tài)棧符號棧當(dāng)前字符 剩余字符串動作10 #ab#移進202 #ab# 3023 #aAb# 移進40235 #aAb#歸約A->aAb501 #A#接受【解答】由d和得：FIRSTVT(M)=｛d,a；由H得：FIRSTVT(H)｛｝由H→M得：FIRSTVT(M)cFIRSTVT(H)，即FIRSTVT(H)={;,d,a}M→dM→…b得：LASTVT(M)={d,b}；由H--m得：LASTVT(H)｛；由M得：LASTV（）cLASTVT(，即LASTVT(H)｛;,d,b}對文法開始符H有#H存在，即有＃=＃，#<FIRSTVT(H)，LASTVT(H)>#,#<d.#<a,；＞＃，d>#,。對形如P→…ab…，或P→…aQb…，有a=b，由M→a|b得：a=b；a∈LASTVT(R)．a(chǎn)>b。由；M<FIRSTVT(M)<d<a由得：a<FIRSTVT(H，即：a<，＜a由；得：LASTVT(H)>d>b＞；由b得：LASTVT(H)>b，d>b，＞b。【解答】LR分析表如下：分析表狀態(tài) ACTION GOTOa b # S B0 s3 s4 1 1 acc2 S3 S4 53s33s3s44r3r35R1R1r16R2R2R2(3)abaab表abaab的分析過程步驟 狀態(tài) 符號棧 輸入串 所得產(chǎn)生式#0 # abaad##03 #a baad#2#034#abaab#B→b3#036#aBaab#B→aB4#02#Baab#5#023#Baab#6#0233#Baab#7#02334#Baab#8#02336#BaaB#9#0236#BaBad#10#025#BBad#11#01#Sd#12# #d#13識別成功【解答】該語句的四元式序列如下（、E2E3分別對應(yīng)：A<C∧B<D,A=1A≤D并且關(guān)系運算符優(yōu)先級高：100(j<,A,C,102)101(j,_,_,113） /*E1F*/102(j<,B,D,104) /*ElT*/103(j,_,_,113) /*ElF*/104(j=,A,1,106) /*EzT*/105(j,_,_,108） /*EZ為F*/106(＋,C,1,C) /*C:=C+1*/107(j,_,_,112) /*跳過else后的語句*/108(j≤,A,D,110) /*E3T*/109(j,_,_,112) /*E3F*/110/*A:=A+2*/111(j,_,_,108) /*轉(zhuǎn)回內(nèi)層while語句開始處*/112(j,_,_,100) /*轉(zhuǎn)回外層while語句開始處*/113【解答】