編譯原理期末考試試卷A卷

1、試卷編號：試卷編號：1-A第 頁共8頁試卷編號試卷編號1-A第3頁共8頁332（3）化簡，并畫出DFAM（1分）劃分為狀態(tài)：0,213將這三個狀態(tài)命名為0,1,2三個狀態(tài)設(shè)文法G設(shè)文法GS：（共5分）SfS+aTIaTI+aTTf*aTI*a（1）寫出句型aT（1）寫出句型aT+a*a*a的最右推導(dǎo)并畫出語法樹（2分）*a（2）寫出該句型中所有的短語、直接短語、句柄和最左素短語。（3分）短語：aT、*a*a、*a、aT+a*a*a直接短語：aT、*a句柄：aT最左素短語:aT（共5（共5分）a=（b+c）*e+（b+c）/f（1）逆波蘭表示（1分）abc+e*bc+f/+=（2）三元式（1分）

2、（+，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分）St*AAt0A1|*（1）求文法G的各非終結(jié)符號的FIRSTVT和LASTVT集合.（5分）FIRSTVT（S）=*LASTVT（S）=1,*FIRSTVT（A）=0,*LASTVT（S）=1,*（2）構(gòu)造文法G的優(yōu)先關(guān)系矩陣，并判斷

3、該文法是否是算符優(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#41#5#*0A1#6#*A#7#S#分析正確步驟符號棧輸入串輸出2。已知文法G(S)：(共15分)SaSIbSIa構(gòu)造該文法的拓廣文法.(1分)(O)SfsS-aSA-bSA-a構(gòu)造其LR(0)項目集規(guī)范族，并給出識別活前綴的DFA。(7分)(3)構(gòu)造其SLR分析表，并判斷該文法是否是SLR(1)文法。(7分)狀態(tài)I1移進一規(guī)約沖突，計算S的Follow集合:Foll

4、ow=#，可以采用SLR沖突消解法,得到如下SLR分析表：狀態(tài)ACTIONGOTOab#S0SiS231S1S2r342SiS253acc4ri5r2該文法是SLR(1)文法。3。設(shè)有如下基本塊：(共10分)T1=A+BT2=5M=T2*4T3=C-DT4=M+T3L=T1T3T4=A+BN=T4AB520CD假設(shè)變量L,M,N在基本塊出口之后是活躍的，給出優(yōu)化后的四元式序列。（5分）N=A+BM=20T3=C-DL=NT34。以下程序段是最內(nèi)循環(huán)（共13分）A=0I=1L1:B=J+1C=B+IA=C+AifI=100GOTOL2I=I+1GOTOL1L2:流圖中有一條回邊B3一B2,且B2

5、DOMB3,所以，有一個循環(huán)B2,B3,B2是循環(huán)入口結(jié)點，也是出口結(jié)點。(2)對循環(huán)優(yōu)化(8分)代碼外提：對于B2中的賦值四元式B=J+1，由于循環(huán)中沒有對J的定值操作,所有對J的定值都在循環(huán)外,所以,它是循環(huán)中的不變運算,可以進行代碼外提.刪除歸納變量：循環(huán)中I是基本歸納變量，C是與I同族的歸納變量，兩者有如下線性關(guān)系:C=B+I，則1=100可以用C=B+100替代，相應(yīng)的1=1+1可用C=C+1替代，再將新的不變運算提到循環(huán)外。5。有一程序如下：programex;a:integer；procedurePP（x：integer）；begin:x：=5;x：=a+1end；begina：=2;PP（a）；write（a）end試用圖表示DISPLAY表PPSPexSP形式參數(shù)x參數(shù)個數(shù)：1全局DISPLAY地址返回地址ex_SP局部變量:aDISPLAY表ex_SP參數(shù)個數(shù)：0全局DISPLAY地址返回地址ex_SP