〈編譯原理〉歷年試題及答案一. (每項(xiàng)選擇2分，共20分)選擇題將編譯程序分成若干個(gè)“遍”是為7_b_。提高程序的執(zhí)行效率使程序的結(jié)構(gòu)更加清晰利用有限的機(jī)器內(nèi)存并提高機(jī)器的執(zhí)行效率利用有限的機(jī)器內(nèi)存但降低了機(jī)器的執(zhí)行效率構(gòu)造編譯程序應(yīng)掌握__d__。a.源程序 丘目標(biāo)語言c.編譯方法 d.以上三項(xiàng)都是變量應(yīng)當(dāng)_c。a.持有左值 b.持有右值c.既持有左值又持有右值d.既不持有左值也不持有右值編譯程序絕大多數(shù)時(shí)間花在__d__上。a,出錯(cuò)處理 b.詞法分析c.目標(biāo)代碼生成d.管理表格詞法分析器的輸出結(jié)果是_c。a.單詞的種別編碼 b.單詞在符號(hào)表中的位置c.單詞的種別編碼和自身值d.單詞自身值正規(guī)式MI和M2等價(jià)是指__c__。a.MI和M2的狀態(tài)數(shù)相等b.Ml和M2的有向弧條數(shù)相等。C.M1和M2所識(shí)別的語言集相等 d.Ml和M2狀態(tài)數(shù)和有向弧條數(shù)相等中間代碼生成時(shí)所依據(jù)的是一c。a.語法規(guī)則b.詞法規(guī)則c.語義規(guī)則d.等價(jià)變換規(guī)則8.后綴式ab+cd+/可用表達(dá)式__b_來表示。a.a+b/c+db.(a+b)/(c+d) c.a+b/(c+d)d.a+b+c/d程序所需的數(shù)據(jù)空間在程序運(yùn)行前就可確定，稱為__c管理技術(shù)。a.動(dòng)態(tài)存儲(chǔ) b.棧式存儲(chǔ) c.靜態(tài)存儲(chǔ) d.堆式存儲(chǔ)堆式動(dòng)態(tài)分配申請(qǐng)和釋放存儲(chǔ)空間遵守d原則。a.先請(qǐng)先放b,先請(qǐng)后放c,后請(qǐng)先放d.任意二(每小題10分，共80分)簡答題畫出編譯程序的總體結(jié)構(gòu)圖，簡述各部分的主要功能。已知文法G[E]:E一ET+|TT一TF*|FF—玲|a試證：FFM*是文法的句型，指出該句型的短語、簡單短語和句柄.為正規(guī)式(alb)*a(alb)構(gòu)造一個(gè)確定的有限自動(dòng)機(jī)。設(shè)文法G(S)：S一(L)|aS|aL—L，SIS(1)消除左遞歸和回溯；計(jì)算每個(gè)非終結(jié)符的FIRST和FOLLOW；構(gòu)造預(yù)測分析表。已知文法A->aAd|aAb|s判斷該文法是否SLR(1)文法，若是構(gòu)造相應(yīng)分析表，并對(duì)輸入串a(chǎn)b#給出分析過程。構(gòu)造算符文法G[H]的算符優(yōu)先關(guān)系(含#)。G[H]：H—H;M|MM—d|aHb已構(gòu)造出文法G(S)S BBB aBB b。給出DFA圖.給出LR分析表.假定輸入串為abaab，請(qǐng)給出LR分析過程(即狀態(tài)，符號(hào)，輸入串的變化過程)。將下面的語句翻譯成四元式序列：whileA<CAB<DdoifA=1thenC:=C+lelsewhileA<DdoA:=A+2；對(duì)下面的流圖，求出流圖中各結(jié)點(diǎn)N的必經(jīng)結(jié)點(diǎn)集D(n)，求出流圖中的回邊，⑶求出流圖中的循環(huán)。參考答案單項(xiàng)選擇題將編譯程序分成若干個(gè)“遍”是為了使編譯程序的結(jié)構(gòu)更加清晰，故選b。.構(gòu)造編譯程序應(yīng)掌握源程序、目標(biāo)語言及編譯方法等三方面的知識(shí)，故選d。對(duì)編譯而言，變量既持有左值又持有右值，故選c。編譯程序打交道最多的就是各種表格，因此選d。詞法分析器輸出的結(jié)果是單詞的種別編碼和自身值，選C。正規(guī)式M1和M2所識(shí)別的語言集相等，故選C。選c。選b。選C堆式動(dòng)態(tài)分配申請(qǐng)和釋放存儲(chǔ)空間不一定遵守先請(qǐng)后放和后請(qǐng)先放的原則，故選d簡答題1. 【解答】編譯程序的總體結(jié)構(gòu)圖如圖1.2所示。詞法分析器：輸入源程序，進(jìn)行詞法分析，輸出單詞符號(hào)。

語法分析器：在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則(文法規(guī)則)把單詞符號(hào)串分解成各類語法單位，并判斷輸入串是否構(gòu)成語法上正確的“程序”。中間代碼生成器：按照語義規(guī)則把語法分析器歸約(或推導(dǎo))出的語法單位翻譯成一定形式的中間代碼，比如說四元式。優(yōu)化：對(duì)中間代碼進(jìn)行優(yōu)化處理。目標(biāo)代碼生成器：把中間代碼翻譯成目標(biāo)語言程序。表格管理模塊保存一系列的表格，登記源程序的各類信息和編譯各階段的進(jìn)展情況。編譯程序各階段所產(chǎn)生的中間結(jié)果都記錄在表格中，所需信息多數(shù)都需從表格中獲取，整個(gè)編譯過程都在不斷地和表格打交道。出錯(cuò)處理程序?qū)Τ霈F(xiàn)在源程序中的錯(cuò)誤進(jìn)行處理。此外，編譯的各階段都可能出現(xiàn)錯(cuò)誤，出錯(cuò)處理程序?qū)Πl(fā)現(xiàn)的錯(cuò)誤都及時(shí)進(jìn)行處理?！窘獯稹吭摼湫蛯?duì)應(yīng)的語法樹如下：該句型相對(duì)于E的短語有FFAA*；相對(duì)于T的短語有FFAA*,F;相對(duì)于F的短語有FA;FAA;簡單短語有F;FA;句柄為F.【解答】最簡DFA如圖2.66所示。4.⑴【解答】S—(L)|aS’S’—S|￡

L—SL’L’—SL’|￡4.⑴【解答】S—(L)|aS’S’—S|￡

L—SL’L’—SL’|￡評(píng)分細(xì)則：消除左遞歸2分(2)FIRST和FOLLOWFIRST)S)={(，F(xiàn)IRST(S’)={，F(xiàn)IRST(L)={(，F(xiàn)IRST(L’)={，【解答】提公共因子2分。a}a,￡}a}￡}FOLLOW(S)={#，，，)}FOLLOW(S’)={#，，，)}FOLLOW(L)={)}FOLLOW(L’〕={)}5.拓廣文法(0)S->A(1)A->aAd(2)A->aAb(3)A->￡構(gòu)造識(shí)別活前綴的DFAFOLLOW(A)={d,b,#}對(duì)于狀態(tài)I0：FOLLOW(A)n{a}=Q對(duì)于狀態(tài)I1：FOLLOW(A)n{a}=Q因?yàn)椋贒FA中無沖突的現(xiàn)象，所以該文法是SLR(1)文法。(3)SLR(1)分析表狀態(tài)aACTIONBGOTOAd#0S2r3r3r311acc2S2r3r3r33

3S5S44r1r1 r15r2r2 r2⑷串a(chǎn)b#的分析過程步驟狀態(tài)棧符號(hào)棧當(dāng)前字符 剩余字符串動(dòng)作10#a b#移進(jìn)202#ab#歸約A->￡3023#aAb# 移進(jìn)40235#aAb#歸約A->aAb501#A#接受【解答】由M—d和M—a...得：FIRSTVT(M)={d,a}；由H-H;...得：FIRSTVT(H)={；}由H—M得：FIRSTVT(M)cFIRSTVT(H),即FIRSTVT(H)={;,d,a}由M—d和M—.b得：LASTVT(M)={d,b}；由H---,；m得：LASTVT(H)={；}；由H—M得：LASTVT(M)cLASTVT(H),即LASTVT(H)={;,d,b}對(duì)文法開始符H,有#H#存在，即有#=#,#<FIRSTVT(H),LASTVT(H)>#,也即#<；,#<d.#<a,；>#,d>#,b>#。對(duì)形如P—...ab...，或P—.aQb.,有a=b,由M—a|b得：a=b；對(duì)形如P—...aR...,而beFIRSTVT(R),有a<b,對(duì)形如P—...Rb...,而a^LASTVT(R).有a>b。由H—...；M得：；<FIRSTVT(M)，即：：<d,：<a由M—aH...得：a<FIRSTVT(H),即：a<；,a<d,a<a由H—H”?得：LASTVT(H)>;,即：；>；,d>；,b>；由M—.Hb得：LASTVT(H)>b，即：；>b,d>b,b>b由此得到算符優(yōu)先關(guān)系表，見表3.5?！窘獯稹縇R分析表如下:分析表狀態(tài)ACTIONGOTOSBab#0s3s4121acc2S3S453s3s464r3r35R1R1r16R2R2R2

(3)句子abaab的分析過程表:句子abaab的分析過程步驟狀態(tài)符號(hào)棧輸入串所得產(chǎn)生式0#0# abaad#1#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識(shí)別成功8. 【解答】該語句的四元式序列如下(其中E1、E2和E3分別對(duì)應(yīng)：A<CAB<D,A=1和A<D并且關(guān)系運(yùn)算符優(yōu)先級(jí)高)：100(j<,A,C,102)101(j,_,_,113)/*E1為F*/102(j<,B,D,104)/*El為T*/103(j,_,_,113)/*El為F*/104(j=,A,1,106)/*Ez為T*/105(j,_,_,108)/*EZ為F*/106(+,C,1,C)/*C:=C+1*/107(j,_,_,112)/*跳過else后的語句*/108(j<,A,D,110)/*E3為T*/109(j,_,_,112)/*E3為F*/110(+,A,2,A)/*A:=A+2*/111(j,_,_,108)/*轉(zhuǎn)回內(nèi)層while語句開始處*/112(j,_,_,100)/*轉(zhuǎn)回外層wh