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

天津理工大學考試試卷2009～2010學年度第二學期《編譯原理》期末考試試卷課程代碼：0660116試卷編號：1-A命題日期：2010年6月15日答題時限：120分鐘考試形式：閉卷筆試得分統(tǒng)計表：大題號總分一二三四一、單項選擇題（請從4個備選答案中選擇最適合的一項，每小題2分，共20分）得分注意：須將本題答案寫在下面的表格中，寫在其它地方無效12345678910DCBDDBCBDC1.編譯程序是對（）A.匯編程序的翻譯 B.高級語言程序的解釋執(zhí)行C.機器語言的執(zhí)行 D.高級語言的翻譯2.詞法分析器的輸出結果是（）A．單詞的種別編碼 B．單詞在符號表中的位置C．單詞的種別編碼與自身值 D．單詞自身值3.在規(guī)范規(guī)約中，用（）來刻畫可規(guī)約串。A．直接短語B．句柄C．最左素短語D．素短語4.及正規(guī)式(a*|b)*(c|d)等價的正規(guī)式是（）A．a(chǎn)*(c|d)|b(c|d) B．a(chǎn)*(c|d)*|b(c|d)*C．a(chǎn)*(c|d)|b*(c|d) D．(a|b)*c|(a|b)*d5.若項目集IK含有A?·，則在狀態(tài)K時，僅當面臨輸入符號aFOLLOW(A)時，才采取A?·動作的一定是（）A．LALR文法B．LR(0)文法 C．LR(1)文法D．SLR(1)文法6.四元式之間的聯(lián)系是通過（）實現(xiàn)的。A.指示器B.臨時變量C.符號表D.程序變量7．文法G：S?xSx|y所識別的語言是（）A．xyxB．(xyx)*C．xnyxn(n≥0)D．x*yx*8.有一語法制導翻譯如下所示： S?bAb{print“1”} A?(B{print“2”} A?a{print“3”} B?Aa){print“4”}若輸入序列為b(((aa)a)a)b，且采用自下而上的分析方法，則輸出序列為（）A． B.34242421C．D.9．關于必經(jīng)結點的二元關系，下列敘述不正確的是（）A．滿足自反性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ī)約”技術，其規(guī)約過程是規(guī)范的。（×）4.刪除歸納變量是在強度削弱以后進行。（√）5.在目標代碼生成階段，符號表用于目標代碼生成。（×）三、簡答題（每小題5分，共15分）得分1.構造正規(guī)式(0∣1)*00相應的正規(guī)式并化簡。（共5分）（1）根據(jù)正規(guī)式，畫出相應的NFAM（2分）004003121X4003121X（2）用子集法將NFA確定化（2分）II0I1{x,1,2}{1,2,3}{1,2}{1,2,3}{1,2,3,4}{1,2}{1,2}{1,2,3}{1,2}{1,2,3,4}{1,2,3,4}{1,2}將所有子集重命名，得到轉(zhuǎn)換矩陣：S01012132212332（3）化簡，并畫出DFAM（1分）劃分為狀態(tài)：{0,2}{1}{3}將這三個狀態(tài)命名為0，1，2三個狀態(tài)S0101012022011200102001000SHAPE1SHAPE1112.設文法G[S]:（共5分）S→S+aT|aT|+aTT→*aT|*a（1）寫出句型aT+a*a*a的最右推導并畫出語法樹（2分）SSS＋aTS＋a*aTS+a*a*aaT+a*a*aSTS＋TS＋aaaT**aT**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)三元式（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?*A A?0A1|*(1)求文法G的各非終結符號的FIRSTVT與LASTVT集合。（5分）FIRSTVT(S)={*} LASTVT(S)={1,*}FIRSTVT(A)={0,*} LASTVT(S)={1,*}(2)構造文法G的優(yōu)先關系矩陣，并判斷該文法是否是算符優(yōu)先文法。（5分）*01*<<>0<<=1>文法G中的任何終結符對至多只存在一種優(yōu)先關系，所以文法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分） (0)S’→S (1)S→aS (2)A→bS (3)A→a (2)構造其LR(0)項目集規(guī)范族，并給出識別活前綴的DFA。（7分）SaI4SaI4:S→aS.I1:S→a.SS→.aSS→.bSS→.aS→a.SHAPEI0:S’I0:S’→.SS→.aSS→.bSS→.aI2:S→b.SS→.aSS→.bSS→.aI3:S’→S.I5:S→bS.aaSbbSb(3)構造其SLR分析表，并判斷該文法是否是SLR(1)文法。（7分）狀態(tài)I1移進－規(guī)約沖突，計算S的Follow集合：Follow(S)＝{#}，可以采用SLR沖突消解法，得到如下SLR分析表：狀態(tài)ACTIONGOTOab#S0S1S231S1S2r342S1S253acc4r15r2該文法是SLR（1）文法。3.設有如下基本塊：（共10分） T1=A+BT2=5M=T2*4T3=C-DT4=M+T3L=T1*T3T4=A+Bn10n10n1n2n3n4n5n6n8n77AT1,T4,NB5T4LT2M－C++*畫出該基本塊的DAG圖。（5分）nn9TT3 20D20D假設變量L，M，N在基本塊出口之后是活躍的，給出優(yōu)化后的四元式序列。（5分）N＝A＋BM=20T3=C-DL=N*T3（共13分） A=0 I=1L1:B=J+1 C=B+I A=C+A ifI=100GOTOL2 I=I+1 GOTOL1L2:畫出程序流圖，并找出回邊及循環(huán)。（3分）SHAPEA=0I=1L1：B=J+1C=B+IA=0I=1L1：B=J+1C=B+IA=C+AifI=100gotoL2I=I+1GOTOL1L2：B1B2B3B4流圖中有一條回邊B3 B2，且B2DOMB3，所以，有一個循環(huán){B2,B3}，B2是循環(huán)入口結點，也是出口結點。對循環(huán)優(yōu)化（8分）1.代碼外提：對于B2中的賦值四元式B=J+1，由于循環(huán)中沒有對J的定值操作，所有對J的定值都在循環(huán)外，所以，它是循環(huán)中的不變運算，可以進行代碼外提。2.刪除歸納變量：循環(huán)中I是基本歸納變量，C是及I同族的歸納變量，兩者有如下線性關系：C=B+I，則I=100可以用C=B+100替代，相應的I=I+1可用C=C+1替代，再將新的不變運算提到循環(huán)外。畫出優(yōu)化后的程序流圖（2分）SHAPEA=0I=1B=J+1C=B+IA=0I=1B=J+1C=B+IR=B+100L1：A=C+AifC=RgotoL2C=C+1GOTOL1L2：B1B2B3B45.有一程序如下： programex; a:integer; procedurePP(x:integer); begin: x:=5;x:=a+1 end; begin a:=2; PP(a); write(a) end試用圖表示ex調(diào)用PP(a)前后活動記錄的過程。（共7分）DISPLAY表PP_SPex_