編譯原理實踐及應(yīng)用習題的參考答案(文件)
【正文】 {S→BbB在I0狀態(tài)下，當輸入符號是a或是b時，不知用A→e還是B→e進行歸約。為 0．S39。(SR, S→SR, S→R, R→}I7 = {R→,R, R→因此，此文法是LR(0)文法。D2 {:=+}D→id:T {:= 1}D→proc id。而display表內(nèi)容的項數(shù)與過程的嵌套層次有關(guān)，一般比過程的嵌套層數(shù)大1。(4) demo →A→B→B→A 此時的運行棧包括主程序demo、2個過程A和2個過程B的實例的5個數(shù)據(jù)區(qū)，但過程A只引用主程序demo全局數(shù)據(jù)和其自身的局部數(shù)據(jù)，因此其display表內(nèi)容只有2項，即主程序數(shù)據(jù)區(qū)首址和過程A的主程序數(shù)據(jù)區(qū)首址。 D(n1) = {n0, n1} D(n5) = {n0, n1, n2, n5} 因為 D(n5) = {n0, n1, n2, n5} ，且 n5 → n2，所以 n5 → n2為一條回邊。6. 解答：(1) 首先劃分基本塊并畫出其程序流圖，其中有三個基本塊B1，B2，B3，有一條回邊B2 → B2，相應(yīng)的循環(huán)是{B2}。(4) 代碼外提：由于刪除歸納變量后有R :=K * 100，是循環(huán)不變運算，可以提到前置結(jié)點B239。 /* 第一個for語句 */ /* 數(shù)組A的基地址 */ goto B2 B6: T4 := i B8: j := 2 * i B10: T6 := j j := j + i B12: (2) 根據(jù)上述中間代碼，可劃分成基本塊B1，B2，B3，B4，B5，B6，B7，B8，B9，B10，B11。根據(jù)這條回邊找到循環(huán) L3 = { B11, B9, B10, B8, B7, B6, B5 }(3) 進行代碼外提把在循環(huán)中不隨循環(huán)變化的操作提到循環(huán)外的前置結(jié)點中，且在基本塊中作復寫傳播和刪除無用賦值。目標代碼如下：(1) MOVR1，R2MOVR0，ASUBR1，CADDR15. 解答：(1) MOV R0,bMUL R0,cADD R0,aMOV x,R0(2) MOV R0,aDIV R0,bSUB R0,cDIV R0,dMOV x,R0(3) MOV R0,0SUB R0,bMUL R0,aMOV R1,dADD R1,eMOV R2,cSUB R2,R1ADD R0,R2MOV x,R06. 解答： 略！。 R1，DMOV S，R0，BMOVx，R14. 解答：MOVR2，dSUB (4) 進行強度削弱和刪除歸納變量后，其程序流圖如圖2。 D(B10) = { B1, B2, B4, B5, B6, B9, B10 }，又有 B10 → B9，所以 B10 → B9 是一條回邊。根據(jù)它找到的循環(huán) L1 = { B2, B3 }。 B11: i := i + 1 T6 := 2 * T6 if T5[T4] goto B8 T4:= 2 * T4 /* [T3]是對T3的值取整 */ T3 := N ** T2[T1] := true T2 := addr(A) i := 2 B1: read N7. 解答：8. 解答：(1) DAG如下： (2) 優(yōu)化后的三地址代碼為：T3:＝S－RT4:＝S＋RA:＝5*T4B:＝T3＋T4 9. 解答：(本題中假設(shè)采用字節(jié)地址，兩個字節(jié)作為一個機器字。優(yōu)化結(jié)果如下圖。 因為D(n6) = {n0, n1, n2, n5, n6} ，且 n6 → n1，所以n6 → n1為一條回邊。 D(n7) = {n0, n1, n2, n5, n6, n7} D(n3) = {n0, n1, n2, n3} 第7章習題解答：1. 解答：A：局部 B：全局 C：代碼外提D：削減運算強度 E：刪除歸納變量2，3. 解答：略！4. 解答：程序流圖如下：回邊為：B4→B3，循環(huán)L={B3,B4}：各結(jié)點n的必經(jīng)結(jié)點集D(n)如下： (2) demo →A→B 此時的運行棧只有主程序demo、過程A和過程B的3個數(shù)據(jù)區(qū)，過程B嵌套定義在過程A中，要引用主程序demo全局數(shù)據(jù)、過程A的數(shù)據(jù)和其自身的局部數(shù)據(jù)，因此其display表內(nèi)容有3項，即主程序數(shù)據(jù)區(qū)首址、過程A的主程序數(shù)據(jù)區(qū)首址和過程B本身的數(shù)據(jù)區(qū)首址。S {:=+1}5. 解答：輸入串為bcccaadadadb時的語法樹為：采用修剪語法樹的方法，按句柄方式自下而上歸約該語法樹，在歸約時調(diào)用相應(yīng)的語義規(guī)則，由此得到最終的翻譯結(jié)果為：34242421.6. 解答： (a+b)+(c+d/(e3))*87. 解答：(1) abc+*(2) A not C D not or not or(3) abcde/+*+(4) A B and C not D or or (5) abcd+*+(6) A B or C D not E and or and8. 解答：三元式四元式① (+,a,b)1.(+,a,b,T1)② (,1,)2.(,T,, T2)③ (+,c,d)3.(+,c,d,T3)④ (*,2,3)4.(*, T2,T 3,T4)⑤ (+,a,b)5.(+,a,b,T5)⑥ (+,c,5)6.(+, T5,c, T6)⑦ (,4,6)7.(, T4, T6 ,T7)9. 解答：四元式代碼為：1. (jnz，A，_， x)2. (j，_，_，3)3. (jnz，B，_，5)4. (j，_，_，y)5. (jnz，C，_，y)6. (j，_，_，7)7. (jnz，D，_，y)8. (j，_，_，x)10. 解答：11. 解答：(1) 四元式序列為： 1．（j,A,C,3）8.(:=,T,,C) 2.(j,,,14)9.(j,,,14) 3.(j,B,D,5)11.(j,,,14)4.(j,,,14)12.(+,A,2,T2) 5.(j=,A,1,7)13.(:=, T2,,A)6.(j,,,10) 14.7.(+,c,1,T1) (2) 四元式序列為：1. (j＞0，x，0，3)7. (j，_，_，12)2. (j，_，_，8)8. (＋，x，2，T2)3. (j＞，y，0，5)9. (:＝，T2，_，x)4. (j，_，_，8)10. (＋，y，3，T3)5. (＋，x，y，T1)11. (:＝，T3，_，y)6. (:＝，T1，_，z)12. (3) 四元式序列為：0. (+，A，3，t0)1. (:=，t0 ， ，t1)2. (*，C，A，t2)3. (*，t2，2，t3)4. (:=， t3， ，B)5. (j，X，0，7)6. (j， ， ，0)7.(4) 四元式序列為：0. (*,b,2,t0)1. (:=, t0, ,i)2. (:=,100, , t1 )3. (j, , , 6)4. (+,i,1,t2 )5. (:=, t2, , i)6. (j, i,t1,
公司管理相關(guān)推薦
鄂ICP備17016276號-1