編譯原理 龍書 第二版 第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在上圖中已標出