1、第五章練習(xí)5.1.1：對于圖5-1中的SDD，給出下列表達式對應(yīng)的注釋語法分析樹：1）（3+4）*（5+6）n練習(xí)5.2.4：這個文法生成了含“小數(shù)點”的二進制數(shù)：S-L.L|L L-LB|B B-0|1設(shè)計一個L屬性的SDD來計算S.val，即輸入串的十進制數(shù)值。比如，串101.101應(yīng)該被翻譯為十進制的5.625。提示：使用一個繼承屬性L.side來指明一個二進制位在小數(shù)點的哪一邊。答：元文法消除左遞歸后可得到文法：S-L.L|L L-BL L-BL| B-0|1使用繼承屬性L.side指明一個二進制位數(shù)在小數(shù)點的哪一邊,2表示左邊，1表示右邊使用繼承屬性m記錄B的冪次非終結(jié)符號L和L具有

2、繼承屬性inh、side、m和綜合屬性syn產(chǎn)生式語義規(guī)則1)S-LS.val=L.syn; L.side=2;L.m=1;L.inh=02)S-L1.L2L1.side=2;L2.side=1; L1.inh=0;L1.m=1;L2.m=1/2;L2.inh=0S.val=L1.syn+L2.syn; 3)L-BLL.m=L.m*L.m;L.side=L.sideL.inh=L.inh*L.side+B*L.mL.syn=L.syn4)L-BL1L1.m=L.m*L.m;L1.side=L.sideL1.inh=L.inh*L.side+B*L1.mL.syn=L1.syn5)L-L.syn

3、=L.inh6)B-0B.val=07)B-1B.val=1練習(xí)5.3.1：下面是涉及運算符+和整數(shù)或浮點運算分量的表達式文法。區(qū)分浮點數(shù)的方法是看它有無小數(shù)點。E-E+T|T T-num.num|num1）給出一個SDD來確定每個項T和表達式E的類型2）擴展（1）中得到的SDD，使得它可以把表達式轉(zhuǎn)換成為后綴表達式。使用一個單目運算符intToFloat把一個整數(shù)轉(zhuǎn)換為相等的浮點數(shù)答：(1)產(chǎn)生式語義規(guī)則1)E-E1+TIf E1.type =T.type then E.type=E1.typeelse E.type=float2)E-TE.type=T.type3)T-numT.type=

4、integer4)T-num.numT.type=float(2)產(chǎn)生式語義規(guī)則1)E-E1+TIf E1.type =T.type then E.type=E1.typeElse beginE.type=floatIf(E1.type=integer and T.type=float) then E1=intToFloat(E1)Else if(T.type=integer and E1.type=float) then T=intToFloat(T)ENDE.val = E1.val T.val +2)E-TE.type=T.type ; E.val=T.val3)T-numT.type=

5、integer; T.val=num4)T-num.numT.type=float ; T.val=num.num練習(xí)5.4.4：為下面的產(chǎn)生式寫出一個和例5.10類似的L屬性SDD。這里的每個產(chǎn)生式表示一個常見的C語言中的那樣的控制流結(jié)構(gòu)。你可能需要生成一個三地址語句來跳轉(zhuǎn)到某個標(biāo)號L，此時你可以生成語句goto L1）S-if (C) S1 else S22）S-do S1 while (C)3）S- L ; L - LS|請注意，列表中的任何語句都可以包含一條從它的內(nèi)部跳轉(zhuǎn)到下一個語句的跳轉(zhuǎn)指令，因此簡單地為各個語句按序生成代碼是不夠的。答：產(chǎn)生式語義規(guī)則1) S-if (C) S1 e

6、lse S2C.false=NewLable();C.true=NewLable()S1.next=S2.next=S.nextS.code=C.code | Lable(C.true) | S1.code | gen(goto S.next) | Lable(C.false)| S2.code2) S-do S1 while (C)Begin=NewLable()C.false=NewLable(); C.true=NewLable()S1.next=beginS.code=Lable(begin)|S1.code | Lable(C.true) | gen(gotobegin)3) S-

7、L ;L - L1SL-S.syn=L.syn;S.inh=L1.syn; L.syn=S.synL.inh=L.syn第六章練習(xí)6.1.1：為下面的表達式構(gòu)造DAG（x+y）-（x+y）*（x-y）+（x+y）*（x-y）答：DAG如下*+-+YX練習(xí)6.2.1：將算術(shù)表達式a+ - (b+c)翻譯成1） 抽象語法樹2） 四元式序列3） 三元式序列4） 間接三元式序列答：(1)抽象語法樹cb+minusa(2) 四元式序列t1=b+ct2=minus t1t3=a+t2opArg1Arg2result0+bcT11minusT1T22+aT2T3(3)三元式序列opArg1Arg20+bc1

8、minus(0)2+a(1)(4)間接三元式序列 10(0)11(1)12(2)opArg1Arg20+bc1minus(0)2+a(1) instruction 練習(xí)6.4.3：使用圖6-22中的翻譯方案，來翻譯下列賦值語句x=aij+bij 答：假定數(shù)組a,b均為2*3規(guī)模的整型數(shù)組，且一個整數(shù)的寬度為4x=aij+bij的注釋語法分析樹如下SXE.addr=t8E.addr=t4E.addr=t9=+L.addr=t7L.array=bL.type=integerL.addr=t3L.array=aL.type=integerL.addr=t5L.array=bL.type=array(

9、3,integer)L.addr=t1L.type=array(3,integer)L.array=a E.addr= j E.addr=j j a.type=array(2,array(3,integer) E.addr=i b.type=array(2,array(3,integer) E.addr= i i j i x=aij+bij被翻譯成的三地址代碼如下如下T1=i*12T5=i*12T2=j*4t6=j*4T3=t1+t1t7=t5+t6T4=at3t8=bt7T9=t4+t8X=t9練習(xí)6.6.4：使用圖6.6.5節(jié)中介紹的避免goto語句的翻譯方案，來翻譯下列表達式：If （a

10、=b & c=d | e=f） x=1;答：If e=f goto L2ifFalse a=b goto L1ifFalse c=d goto L1L2: x=1L1:練習(xí)6.7.1：使用圖6-43中的翻譯方案翻譯下列表達式。給出每個子表達式的truelist和falselist。你可以假設(shè)第一條被生成的指令地址是100.a=b & (c=d | e=f)答：構(gòu)造表達式的注釋語法分析樹如下 B.t=102,104B.f=101,105M.i=102)(B.t=102,104B.f=105B.t=102,104B.f=105&B.t=100B.f=101a = bM.i=104|B.t=102B.f=103B.t=104B.f=105&c = de = f各產(chǎn)生式進行歸約時產(chǎn)生的語義動作的相應(yīng)指令如下1) 按B-E1 rel E2 將a=b 歸約為B時語義動作相應(yīng)的指令如下100: if a=b goto 101: goto 2) 產(chǎn)生式 B-B1 & M B2中的標(biāo)記非終結(jié)符號M記錄了nextinstr的值，該值為1023) 按B-E1 rel E2 將c=d 歸約為B時語義動作相應(yīng)的指令如下102: if c=d goto 103: goto 4) 產(chǎn)生式 B-B1 | M B2中的標(biāo)記非終結(jié)符號M記錄了nextinst