天津理工大學編譯原理期末考試試卷試題

1、天津理工大學考試試卷 20092010學年度第二學期編譯原理 期末考試試卷課程代碼： 0660116 試卷編號： 1-A 命題日期： 2010 年 6 月 15 日答題時限： 120 分鐘 考試形式：閉卷筆試得分統(tǒng)計表：大題號總分 一二三四一、單項選擇題（請從4個備選答案中選擇最適合的一項，每小題2分，共20分）得分注意：須將本題答案寫在下面的表格中，寫在其它地方無效12345678910DCBDDBCBDC1. 編譯程序是對（ ）A. 匯編程序的翻譯 B. 高級語言程序的解釋執(zhí)行 C. 機器語言的執(zhí)行 D. 高級語言的翻譯 2. 詞法分析器的輸出結(jié)果是（ ）A單詞的種別編碼B單詞在符號表中的

2、位置C單詞的種別編碼和自身值D單詞自身值3. 在規(guī)范規(guī)約中，用（ ）來刻畫可規(guī)約串。A直接短語 B句柄 C最左素短語 D素短語4. 與正規(guī)式(a* | b) * (c | d)等價的正規(guī)式是（ ）Aa* (c | d) | b(c | d) Ba* (c | d) * | b(c | d) *Ca* (c | d) | b* (c | d)D(a | b) * c | (a | b) * d5. 若項目集IK含有A®·，則在狀態(tài)K時，僅當面臨輸入符號aFOLLOW(A)時，才采取A®·動作的一定是（ ）ALALR文法 BLR(0) 文法 CLR(1)文法

3、 DSLR(1)文法6. 四元式之間的聯(lián)系是通過（ ）實現(xiàn)的。A. 指示器 B. 臨時變量 C. 符號表 D. 程序變量7文法G：S ® x Sx | y所識別的語言是（ ）Axyx B(xyx) * Cxnyxn(n0) Dx*yx*8. 有一語法制導翻譯如下所示：S ® b Ab print “1”A®(B print “2”A®a print “3”B®Aa) print “4”若輸入序列為b(aa)a)a)b，且采用自下而上的分析方法，則輸出序列為（ ）A B. C D. 9關(guān)于必經(jīng)結(jié)點的二元關(guān)系，下列敘述不正確的是（ ）A滿足自反性

4、B滿足傳遞性 C滿足反對稱型 D滿足對稱性10錯誤的局部化是指（ ）。 A把錯誤理解成局部的錯誤 B對錯誤在局部范圍內(nèi)進行糾正C當發(fā)現(xiàn)錯誤時，跳過錯誤所在的語法單位繼續(xù)分析下去D當發(fā)現(xiàn)錯誤時立即停止編譯，待用戶改正錯誤后再繼續(xù)編譯 二、判斷題（每小題1分，共5分）得分1. 文法G的一個句子對應于多個推導，則G是二義性的。（× ）2. 動態(tài)的存儲分配是指在運行階段為源程序中的數(shù)據(jù)對象分配存儲單元。（ ）3. 算符優(yōu)先文法采用“移進規(guī)約”技術(shù)，其規(guī)約過程是規(guī)范的。（ × ）4. 刪除歸納變量是在強度削弱以后進行。（ ）5. 在目標代碼生成階段，符號表用于目標代碼生成。（ 

5、15; ）三、簡答題（每小題5分，共15分）得分1. 構(gòu)造正規(guī)式(01)*00相應的正規(guī)式并化簡。（共5分）（1）根據(jù)正規(guī)式，畫出相應的NFA M（2分）0e40031e21X（2）用子集法將NFA確定化（2分）II0I1x,1,21,2,31,21,2,31,2,3,41,21,21,2,31,2 1,2,3,4 1,2,3,41,2 將所有子集重命名，得到轉(zhuǎn)換矩陣：S01012132212332（3）化簡，并畫出DFA M（1分）劃分為狀態(tài)：0,2 1 3 將這三個狀態(tài)命名為0，1，2三個狀態(tài)S010101202201200100112. 設文法GS: （共5分）S S + aT | aT

6、 | +aTT *aT | *a （1）寫出句型 aT + a *a *a的最右推導并畫出語法樹（2分）SSÞSaTÞSa*aTÞS+a*a*aÞaT+a*a*aTS a a T * a T* a（2）寫出該句型中所有的短語、直接短語、句柄和最左素短語。（3分）短語：aT、*a*a、*a、aT+a*a*a直接短語：aT、*a句柄：aT最左素短語：aT3. 將下列語句翻譯為逆波蘭表示，三元式、間接三元式和四元式表示：（共5分）a = (b + c) * e + (b + c) / f(1) 逆波蘭表示（1分）abc + e * bc + f / + =(2

7、) 三元式（1分） (+,b, c) (*,e) (+,b, c) (/,f) (+, ) (=,a, )(3) 間接三元式（1分） (+, b, c) (*, , e) (/,f) (+, , ) (=, a, )間接碼表：(4) 四元式（2分） (+, b, c, T1) (*, T1, e,T2) (+, b, c, T3) (/, T3, f, T4) (+, T2, T4, T5) (=, T5, a)四、綜合題（共60分）得分1.已知文法G(S)：（共15分）S® * AA® 0A1 | *(1)求文法G的各非終結(jié)符號的FIRSTVT和LASTVT集合。（5分）

8、FIRSTVT(S)= * LASTVT(S)= 1, *FIRSTVT(A)= 0, * LASTVT(S)= 1, *(2)構(gòu)造文法G的優(yōu)先關(guān)系矩陣，并判斷該文法是否是算符優(yōu)先文法。（5分）*01*< < >0<< =1 >文法G中的任何終結(jié)符對至多只存在一種優(yōu)先關(guān)系，所以文法G是一個算符優(yōu)先文法。(3)分析句子*0*1，并寫出分析過程。（5分）0#*0*1#1#*0*1#2#*0*1#3#*0*1#4#*0A1#5#*0A1#6#*A#7#S#分析正確步驟 符號棧 輸入串 輸出2.已知文法G(S)：（共15分）S® aS | bS | a(1

9、) 構(gòu)造該文法的拓廣文法。（1分）(0)SS(1) SaS(2)AbS(3)Aa(2) 構(gòu)造其LR(0)項目集規(guī)范族，并給出識別活前綴的DFA。（7分）SaI4 : SaS.I1 : Sa.SS.aSS.bSS.aSa.I0 : S.SS.aSS.bSS.aI2 : Sb.SS.aSS.bSS.aI3 : SS.I5 : SbS.aaSbbSb(3)構(gòu)造其SLR分析表，并判斷該文法是否是SLR(1)文法。（7分）狀態(tài)I1移進規(guī)約沖突，計算S的Follow集合：Follow(S)#，可以采用SLR沖突消解法，得到如下SLR分析表：狀態(tài)ACTIONGOTOab#S0S1S231S1S2r342S1

10、S253acc4r15r2該文法是SLR（1）文法。3.設有如下基本塊：（共10分） T1 = A + BT2 = 5M = T2 * 4T3 = C - DT4 = M + T3L = T1 * T3T4 = A + Bn10n1n2n3n4n5n6n8n77AT1,T4,NB5T4LT2MC+*N = T4(1) 畫出該基本塊的DAG圖。（5分）n9T320D(2) 假設變量L，M，N在基本塊出口之后是活躍的，給出優(yōu)化后的四元式序列。（5分）NABM=20T3=C-DL=N*T34.以下程序段是最內(nèi)循環(huán)（共13分）A = 0I = 1L1: B = J + 1C = B + IA = C

11、+ Aif I = 100 GOTO L2I = I + 1GOTO L1L2:(1) 畫出程序流圖，并找出回邊與循環(huán)。（3分）A=0I=1L1：B=J+1C=B+IA=C+Aif I=100 goto L2I=I+1GOTO L1L2：B1B2B3B4流圖中有一條回邊B3B2，且B2DOMB3，所以，有一個循環(huán)B2, B3，B2是循環(huán)入口結(jié)點，也是出口結(jié)點。(2) 對循環(huán)優(yōu)化（8分）1. 代碼外提：對于B2中的賦值四元式B=J+1，由于循環(huán)中沒有對J的定值操作，所有對J的定值都在循環(huán)外，所以，它是循環(huán)中的不變運算，可以進行代碼外提。2. 刪除歸納變量：循環(huán)中I是基本歸納變量，C是與I同族的歸納變量，兩者有如下線性關(guān)系：C=B+I，則I=100可以用C=B+100替代，相應的I=I+1可用C=C+1替代，再將新的不變運算提到循環(huán)外。(3) 畫出優(yōu)化后的程序流圖（2分）A=0I=1B=J+1C=B+IR=B+100L1：A=C+Aif C=R goto L2C=C+1GOTO L1L2：B1B2B3B45. 有一程序如下：program ex;a: integer;procedure PP(x: integer);begin:x:=5; x:=a+1end;begina:=2;PP(a);write(a)end試