編譯原理(龍書(shū))習(xí)題(5,6,7,8)章

1、第5章 語(yǔ)法制導(dǎo)的翻譯5.2.3 假設(shè)我們有一個(gè)產(chǎn)生式 。A，B，C，D這四個(gè)非終結(jié)符號(hào)都有兩個(gè)屬性：s是一個(gè)綜合屬性，而i是一個(gè)繼承屬性。對(duì)于下面的每組規(guī)則，指出(i)這些規(guī)則是否滿足S屬性定義的要求。(ii)這些規(guī)則是否滿足L屬性定義的要求。(iii)是否存在和這些規(guī)則一致的求值過(guò)程？1）A.s = B.i + C.s不滿足S屬性定義，滿足L屬性定義2）A.s = B.i + C.s 和 D.i = A.i + B.s不滿足S屬性定義，滿足L屬性定義 3）A.s = B.s + D.s滿足S屬性定義，滿足L屬性定義4）A.s=D.i，B.i=A.s+C.s，C.i=B.s和D.i=B.i+

2、C.i不滿足S屬性定義，不滿足L屬性定義 BCDA5.2.4 這個(gè)文法生成了含“小數(shù)點(diǎn)”的二進(jìn)制： 設(shè)計(jì)一個(gè)L屬性的SDD來(lái)計(jì)算S.val，即輸入串的十進(jìn)制數(shù)值。比如，串101.11應(yīng)該被翻譯為十進(jìn)制數(shù)5.635。提示：使用一個(gè)繼承屬性L.side來(lái)指明一個(gè)二進(jìn)制位在小數(shù)點(diǎn)的哪一邊。1 |0|.BBLBLLLLS為了求小數(shù)部分的值，引入L的綜合屬性b記錄2的L的位數(shù)次冪值(2 length of L)S L1.L2 S.val = L1.val +L2.val / L2.b;S L S.val = L.val;L L1 B L.val = L1.val *2 + B.val; L.b = L1

3、.b*2;L B L.val = B.val; L.b = 2;B 0 B.val = 0;B 1 B.val = 1;5.3.1 下面是涉及運(yùn)算符+和整數(shù)或浮點(diǎn)運(yùn)算分量的表達(dá)式的文法。區(qū)分浮點(diǎn)數(shù)的方法是看它有無(wú)小數(shù)點(diǎn)。 1）給出一個(gè)SDD來(lái)確定每個(gè)項(xiàng)T和表達(dá)式E的類型。2）擴(kuò)展(1)中得到的SDD，使得它可以把表達(dá)式轉(zhuǎn)換成為后綴表達(dá)式。使用一個(gè)單目運(yùn)算符intToFloat把一個(gè)整數(shù)轉(zhuǎn)換為相等的浮點(diǎn)數(shù)。numnumnumTTTEE|.|（）設(shè)code 為綜合屬性，代表各非終結(jié)符的代碼屬性 type為綜合屬性，代表各非終結(jié)符的類型屬性 inttoreal把整型值轉(zhuǎn)換為相等的實(shí)型值 vtocha

4、r將數(shù)值轉(zhuǎn)換為字符串 5.3.3 給出一個(gè)SDD對(duì)x*(3*x+x*x)這樣的表達(dá)式求微分。表達(dá)式中涉及運(yùn)算符+和*，變量x和常量。假設(shè)不進(jìn)行任何簡(jiǎn)化，也就是說(shuō)，比如3*x將被翻譯為3*1+0*x。 exp 為原表達(dá)式的字符串，s 為求導(dǎo)后的字符串。 | 為串聯(lián)接符。5.4.3 下面的SDT計(jì)算了一個(gè)由0和1組成的串的值。它把輸入的符號(hào)串當(dāng)作按照正二進(jìn)制數(shù)來(lái)解釋。 改寫這個(gè)SDT，使得基礎(chǔ)文法不再是左遞歸的，但仍然可以計(jì)算出整個(gè)輸入串的相同的B.val的值。1. 1 | 1.2. 1 | .2. 01111valBvalBvalBBvalBvalBBB0. ; 0. | 1. ;.21. 1

5、| 1. ;. 0.21. 111.1111.1bDvalDbDbDvalDvalDDbDbDvalDvalDDDvalDvalBDBbDbD非終結(jié)符D的綜合屬性b表示二進(jìn)制數(shù)的位數(shù)，val表示對(duì)應(yīng)的十進(jìn)制數(shù)的數(shù)值。消除左遞歸后如下：第6章 中間代碼生成6.1.1 為下面的表達(dá)式構(gòu)造DAG (x+y)-(x+y)*(x-y)+(x+y)*(x-y)6.2.1 將算術(shù)表達(dá)式 a+-(b+c) 翻譯成1）抽象語(yǔ)法樹(shù)2）四元式序列3）三元式序列4）間接三元式序列1）抽象語(yǔ)法樹(shù)：2）四元式序列：3）三元式序列：4）間接三元式序列：6.4.1 向圖6-19的翻譯方案中加入對(duì)應(yīng)于下列產(chǎn)生式的規(guī)則：1）2）

6、)(*121單目加EEEEE6.4.2 使用圖6-20中的增量式翻譯方案重復(fù)練習(xí)6.4.1在增量方式中，gen不僅要構(gòu)造出一個(gè)新的三地址指令，還要將它添加到至今為止已生成的指令序列之后。6.4.3 使用使用圖6-22所示的翻譯方案來(lái)翻譯下列賦值語(yǔ)句：2） x = aij + bij假設(shè)w1為數(shù)組a的第一維的寬度，w2為數(shù)組b的第一維的寬度，整數(shù)的寬度為w。 t1 = i * w1; t6 = j * w; t2 = j * w; t7 = t5 + t6; t3 = t1 + t2; t8 = bt7; t4 = at3; t9 = t4 + t8; t5 = i * w2; x = t9;6

7、.6.1 在圖6-30的語(yǔ)法制導(dǎo)定義中添加處理下列控制流構(gòu)造的規(guī)則：1）一個(gè)repeat語(yǔ)句，repeat S while B2）一個(gè)for循環(huán)語(yǔ)句，for (S1 ; B ; S2) S3S-repeat S1 while Bbegin=newlabel()S1.next=newlabel()B.true=beginB.false = S.nextS.code=label(begin)| S1.code| label(S1.next)| B.codeS-for ( S1; B; S2 ) S3S1.next=newlabel()B.true=newlabel()begin=newlabel(

8、)B.fale=S.nextS2.next =S1.nextS3.next=beginS.code=S1.code|label(S1.next)| B.code|label(begin)| S2.code| gen(goto S1.next)| label(B.true)|S3.code| gen(goto begin)6.7.7 使用圖6-37中的翻譯方案翻譯下列表達(dá)式。給出每個(gè)子表達(dá)式的truelist和falselist。你可以假設(shè)第一條被生成的指令的地址是100。1）a=b&(c=d|e=f)100: if a=b goto 102101: goto _ 102: if c=d

9、 goto _103: goto 104104: if e=f goto _105: goto _第7章 運(yùn)行時(shí)環(huán)境7.2.3 圖7-9中是遞歸計(jì)算Fiabonacci數(shù)列的C語(yǔ)言代碼。假設(shè)f的活動(dòng)記錄按順序包含下列元素：（返回值，參數(shù)n，局部變量s，局部變量t）。通常在活動(dòng)記錄中還會(huì)有其他元素。下面的問(wèn)題假設(shè)初始調(diào)用是f(5)。int f(int n) int t,s; if (n2) return 1; s = f(n-1); t = f(n-2); return s+t;圖7-9活動(dòng)樹(shù)活動(dòng)樹(shù)第1個(gè)f(1)調(diào)用即將返回第5個(gè)f(1)調(diào)用即將返回7.2.5 在一個(gè)通過(guò)引用傳遞參數(shù)的語(yǔ)言中，有

10、一個(gè)函數(shù)f(x,y)完成下面的計(jì)算： x = x + 1; y = y + 2; return x + y; 如果將a賦值為3，然后調(diào)用f(a,a)，那么返回值是什么？ 函數(shù)返回值為：12 此時(shí)a的值為：6第8章 代碼生成8.2.1 假設(shè)所有的變量都存放在內(nèi)存中，為下面的三地址語(yǔ)句生成代碼： 1） x = 1 LD R1 , 1 ST x , R1 3) x = a + 1 LD R1 , a ADD R1 , R1 , 1 ST x , R18.2.2 假設(shè)a和b是元素為4字節(jié)值的數(shù)組，為下面的三地址語(yǔ)句序列生成代碼。2）三個(gè)語(yǔ)句序列 x = ai y = bi z = x * yLD R1

11、 , iMUL R1 , R1 , 4LD R2 , a(R1)ST x , R2LD R3 , iMUL R3 , R3 ,4LD R4 , b(R3)ST y , R4LD R5 , xLD R6 , yMUL R5 , R5 , R6ST z , R58.2.4 假設(shè)x,y和z存放在內(nèi)存位置中，為下面的語(yǔ)句序列生成代碼： if x y goto L1 z = 0 goto L2L1:z = 1 LD R1 , x LD R2 , y SUB R1 , R1 , R2 BLTZ R1 , L1 LD R3 , 0 ST z , R3 JMP L2L1:LD R4 , 1 ST z , R4

12、8.2.6 確定下列指令序列的代價(jià)。1） LD R0 , y 2 LD R1 , z 2 ADD R0 , R0 , R1 1 ST x , R0 2 總代價(jià)：73） LD R0 , c 2 LD R1 , i 2 MUL R1 , R2 , 8 2 ST a(R1) , R0 2總代價(jià)：88.3.3 假設(shè)使用棧式分配，且假設(shè)a和b都是元素大小為4字節(jié)的數(shù)組，為下面的三地址語(yǔ)句生成代碼。2）三個(gè)語(yǔ)句序列 x = ai y = bi z = x*yLD R1 , iMUL R1 , R1 , 4ADD R1 , R1 , SPLD R2 , a(R1)ST x(SP) , R2LD R3 , i

13、MUL R3 , R3 , 4ADD R3 , R3 , SPLD R4 , b(R3)ST y(SP) , R4LD R5 , x(SP)LD R6 , y(SP)MUL R5 , R5 , R6ST z(SP) ,R58.5.1 為下面的基本塊構(gòu)造DAG。 d = b*c e = a+b b = b*c a = e-d1)只有a在基本塊的出口處活躍： d = b * c e = a + b a = e - d2)a,b,c在基本塊的出口處活躍： e = a + b b = b * c a = e - b8.5.8 假設(shè)一個(gè)基本塊由下面的C語(yǔ)言賦值語(yǔ)句生成：x = a+b+c+d+e+f;y

14、 = a+c+e;1)給出這個(gè)基本塊的三地址語(yǔ)句（每個(gè)語(yǔ)句只做一次加法）。 t1 = a + b t2 = t1 + c t3 = t2 + d t4 = t3 + e t5 = t4 + f x = t5 t6 = a + c t7 = t6 + e y = t72)假設(shè)x和y都在基本塊的出口處活躍，利用加法的結(jié)合律和交換律來(lái)修改這個(gè)基本塊，使得指令個(gè)數(shù)最少。 把原始的賦值語(yǔ)句進(jìn)行調(diào)整： x = a+c+e+b+d+f y = a+c+e 對(duì)應(yīng)的三地址語(yǔ)句序列：t1 = a + ct2 = t1 + et3 = t2 + bt4 = t3 + dt5 = t4 + fx = t5t6 = a

15、 + ct7 = t6 + ey = t7DAG優(yōu)化后的三地址語(yǔ)句序列： t1 = a + c y = t1 + e t3 = y + b t4 = t3 + d x = t4 + f優(yōu)化后的目標(biāo)代碼序列： LD R1 , a LD R2 , c ADD R1 , R1 , R2 LD R2 , e ADD R1 , R1 , R2 ST y , R1 LD R2 , b ADD R1 , R1 , R2 LD R2 , d ADD R1 , R1 , R2 LD R2 , f ADD R1 , R1 , R2 ST x , R18.6.1 為下面的每個(gè)C語(yǔ)言賦值語(yǔ)句生成三地址代碼1）x = a + b * c; t1 = b * c t2 = a + t1 x = t23) x = ai + 1 t1 = ai t2 = t1 + 1 x = t2LD R1 , bLD R2 , cMUL R1 , R1 , R2LD R3 , aADD R1 , R1 , R3ST