編譯原理 龍書 第二版 第5、6章

第五章練習(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具有繼承屬性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=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=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=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)到某個標號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 else 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-> 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+bc1minus(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(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=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中的標記非終結(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中的標記非終結(jié)符號M記錄了nextinstr的值，該值為1045) 按B->E1 rel E2 將e=f 歸約為B時語義動作相應(yīng)的指令如下104: if e=f goto 105: goto 6) 按照產(chǎn)生式B->B1 | M B2進行歸約7) 按照產(chǎn)生式B->（B1）進行歸約8) 按照產(chǎn)生式B->B1 && M B2進行歸約9) 各子表達式的truelist和falselist在上圖中已標出