《編譯原理 龍書 第二版 第5、6章》由會(huì)員分享,可在線閱讀,更多相關(guān)《編譯原理 龍書 第二版 第5、6章(6頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、第五章練習(xí)5.1.1:對(duì)于圖5-1中的SDD,給出下列表達(dá)式對(duì)應(yīng)的注釋語(yǔ)法分析樹(shù):1)(3+4)*(5+6)n練習(xí)5.2.4:這個(gè)文法生成了含“小數(shù)點(diǎn)”的二進(jìn)制數(shù):S-L.L|L L-LB|B B-0|1設(shè)計(jì)一個(gè)L屬性的SDD來(lái)計(jì)算S.val,即輸入串的十進(jìn)制數(shù)值。比如,串101.101應(yīng)該被翻譯為十進(jìn)制的5.625。提示:使用一個(gè)繼承屬性L.side來(lái)指明一個(gè)二進(jìn)制位在小數(shù)點(diǎn)的哪一邊。答:元文法消除左遞歸后可得到文法:S-L.L|L L-BL L-BL| B-0|1使用繼承屬性L.side指明一個(gè)二進(jìn)制位數(shù)在小數(shù)點(diǎn)的哪一邊,2表示左邊,1表示右邊使用繼承屬性m記錄B的冪次非終結(jié)符號(hào)L和L具有
2、繼承屬性inh、side、m和綜合屬性syn產(chǎn)生式語(yǔ)義規(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:下面是涉及運(yùn)算符+和整數(shù)或浮點(diǎn)運(yùn)算分量的表達(dá)式文法。區(qū)分浮點(diǎn)數(shù)的方法是看它有無(wú)小數(shù)點(diǎn)。E-E+T|T T-num.num|num1)給出一個(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ù)答:(1)產(chǎn)生式語(yǔ)義規(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)生式語(yǔ)義規(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)生式寫出一個(gè)和例5.10類似的L屬性SDD。這里的每個(gè)產(chǎn)生式表示一個(gè)常見(jiàn)的C語(yǔ)言中的那樣的控制流結(jié)構(gòu)。你可能需要生成一個(gè)三地址語(yǔ)句來(lái)跳轉(zhuǎn)到某個(gè)標(biāo)號(hào)L,此時(shí)你可以生成語(yǔ)句goto L1)S-if (C) S1 else S22)S-do S1 while (C)3)S- L ; L - LS|請(qǐng)注意,列表中的任何語(yǔ)句都可以包含一條從它的內(nèi)部跳轉(zhuǎn)到下一個(gè)語(yǔ)句的跳轉(zhuǎn)指令,因此簡(jiǎn)單地為各個(gè)語(yǔ)句按序生成代碼是不夠的。答:產(chǎn)生式語(yǔ)義規(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:為下面的表達(dá)式構(gòu)造DAG(x+y)-(x+y)*(x-y)+(x+y)*(x-y)答:DAG如下*+-+YX練習(xí)6.2.1:將算術(shù)表達(dá)式a+ - (b+c)翻譯成1) 抽象語(yǔ)法樹(shù)2) 四元式序列3) 三元式序列4) 間接三元式序列答:(1)抽象語(yǔ)法樹(shù)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中的翻譯方案,來(lái)翻譯下列賦值語(yǔ)句x=aij+bij 答:假定數(shù)組a,b均為2*3規(guī)模的整型數(shù)組,且一個(gè)整數(shù)的寬度為4x=aij+bij的注釋語(yǔ)法分析樹(shù)如下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語(yǔ)句的翻譯方案,來(lái)翻譯下列表達(dá)式: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中的翻譯方案翻譯下列表達(dá)式。給出每個(gè)子表達(dá)式的truelist和falselist。你可以假設(shè)第一條被生成的指令地址是100.a=b & (c=d | e=f)答:構(gòu)造表達(dá)式的注釋語(yǔ)法分析樹(shù)如下 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
11、.f=103B.t=104B.f=105&c = de = f各產(chǎn)生式進(jìn)行歸約時(shí)產(chǎn)生的語(yǔ)義動(dòng)作的相應(yīng)指令如下1) 按B-E1 rel E2 將a=b 歸約為B時(shí)語(yǔ)義動(dòng)作相應(yīng)的指令如下100: if a=b goto 101: goto 2) 產(chǎn)生式 B-B1 & M B2中的標(biāo)記非終結(jié)符號(hào)M記錄了nextinstr的值,該值為1023) 按B-E1 rel E2 將c=d 歸約為B時(shí)語(yǔ)義動(dòng)作相應(yīng)的指令如下102: if c=d goto 103: goto 4) 產(chǎn)生式 B-B1 | M B2中的標(biāo)記非終結(jié)符號(hào)M記錄了nextinstr的值,該值為1045) 按B-E1 rel E2 將e=f 歸約為B時(shí)語(yǔ)義動(dòng)作相應(yīng)的指令如下104: if e=f goto 105: goto 6) 按照產(chǎn)生式B-B1 | M B2進(jìn)行歸約7) 按照產(chǎn)生式B-(B1)進(jìn)行歸約8) 按照產(chǎn)生式B-B1 & M B2進(jìn)行歸約9) 各子表達(dá)式的truelist和falselist在上圖中已標(biāo)出