《編譯原理 龍書(shū) 第二版 第5、6章》由會(huì)員分享，可在線閱讀，更多相關(guān)《編譯原理 龍書(shū) 第二版 第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指明

2、一個(gè)二進(jìn)制位數(shù)在小數(shù)點(diǎn)的哪一邊,2表示左邊，1表示右邊 使用繼承屬性m記錄B的冪次 非終結(jié)符號(hào)L和L’具有繼承屬性inh、side、m和綜合屬性syn 產(chǎn)生式 語(yǔ)義規(guī)則 1)S->L S.val=L.syn; L.side=2;L.m=1;L.inh=0 2)S->L1.L2 L1.side=2;L2.side=1; L1.inh=0;L1.m=1;L2.m=1/2;L2.inh=0 S.val=L1.syn+L2.syn; 3)L->BL’ L’.m=L.m*L.m;L’.side=L.side L’.inh=L.inh*L.side+B

3、*L.m L.syn=L’.syn 4)L’->BL1’ L1’.m=L’.m*L’.m;L1’.side=L’.side L1’.inh=L’.inh*L’.side+B*L1’.m L’.syn=L1’.syn 5)L’->ε L’.syn=L’.inh 6)B->0 B.val=0 7)B->1 B.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|num 1）給出一個(gè)SDD來(lái)確定每個(gè)項(xiàng)T和表達(dá)式E的類(lèi)型 2）擴(kuò)展（1）中得到的SDD，使

4、得它可以把表達(dá)式轉(zhuǎn)換成為后綴表達(dá)式。使用一個(gè)單目運(yùn)算符intToFloat把一個(gè)整數(shù)轉(zhuǎn)換為相等的浮點(diǎn)數(shù) 答： (1) 產(chǎn)生式 語(yǔ)義規(guī)則 1)E->E1+T If E1.type ==T.type then E.type=E1.type else E.type=float 2)E->T E.type=T.type 3)T->num T.type=integer 4)T->num.num T.type=float (2) 產(chǎn)生式 語(yǔ)義規(guī)則 1)E->E1+T If E1.type ==T.type then E.type=E1.type El

5、se begin E.type=float If(E1.type==integer and T.type==float) then E1=intToFloat(E1) Else if(T.type==integer and E1.type==float) then T=intToFloat(T) END E.val = E1.val T.val + 2)E->T E.type=T.type ; E.val=T.val 3)T->num T.type=integer; T.val=num 4)T->num.num T.type=float ; T.val=num.nu

6、m 練習(xí)5.4.4：為下面的產(chǎn)生式寫(xiě)出一個(gè)和例5.10類(lèi)似的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 L 1）S->if (C) S1 else S2 2）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 else S2 C.false=Ne

7、wLable();C.true=NewLable() S1.next=S2.next=S.next S.code=C.code || Lable(C.true) || S1.code || gen(‘goto’ S.next) || Lable(C.false)|| S2.code 2) S->do S1 while (C) Begin=NewLable() C.false=NewLable(); C.true=NewLable() S1.next=begin S.code=Lable(begin)||S1.code |

8、| Lable(C.true) || gen(‘goto’begin) 3) S->’{’ L ‘}’; L -> L1S L->ε S.syn=L.syn; S.inh=L1.syn; L.syn=S.syn L.inh=L.syn 第六章 練習(xí)6.1.1：為下面的表達(dá)式構(gòu)造DAG （（x+y）-（（x+y）*（x-y）））+（（x+y）*（x-y）） 答：DAG如下 * + - - + Y X 練習(xí)6.2.1：將算術(shù)表達(dá)式a+ - (b+c)翻譯成 1） 抽象語(yǔ)法樹(shù) 2） 四

9、元式序列 3） 三元式序列 4） 間接三元式序列 答：(1)抽象語(yǔ)法樹(shù) c b + + minus a (2) 四元式序列 t1=b+c t2=minus t1 t3=a+t2 op Arg1 Arg2 result 0 + b c T1 1 minus T1 T2 2 + a T2 T3 (3)三元式序列 op Arg1 Arg2 0 + b c 1 minus (0) 2 + a (1) (4)間接三元式序列 10

10、(0) 11 (1) 12 (2) op Arg1 Arg2 0 + b c 1 minus (0) 2 + a (1) instruction 練習(xí)6.4.3：使用圖6-22中的翻譯方案，來(lái)翻譯下列賦值語(yǔ)句 x=a[i][j]+b[i][j] 答： 假定數(shù)組a,b均為2*3規(guī)模的整型數(shù)組，且一個(gè)整數(shù)的寬度為4 x=a[i][j]+b[i][j]的注釋語(yǔ)法分析樹(shù)如下 S X E.addr=t8

11、E.addr=t4 E.addr=t9 = + L.addr=t7 L.array=b L.type=integer L.addr=t3 L.array=a L.type=integer L.addr=t5 L.array=b L.type=array(3,integer) L.addr=t1 L.type=array(3,integer) L.array=a [ E.addr= j ] [ E.addr=j ] j a.type =array(2,array(3,integer)) [

12、E.addr=i ] b.type =array(2,array(3,integer)) [ E.addr= i ] i j i x=a[i][j]+b[i][j]被翻譯成的三地址代碼如下如下 T1=i*12 T5=i*12 T2=j*4 t6=j*4 T3=t1+t1 t7=t5+t6 T4=a[t3] t8=b[t7] T9=t4+t8 X=t9 練習(xí)6.6.4：使用圖6.6.5節(jié)中介紹的避免goto語(yǔ)句的翻譯方案，來(lái)翻譯下列表達(dá)式： If （a==b && c

13、==d || e==f） x==1; 答： If e==f goto L2 ifFalse a==b goto L1 ifFalse c==d goto L1 L2: x==1 L1: 練習(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,104} B.f={101,105}

14、M.i={102} ) ( B.t={102,104} B.f={105} B.t={102,104} B.f={105} && B.t={100} B.f={101} a == b M.i={104} || B.t={102} B.f={103} B.t={104} B.f={105} ε& ε& c == d e == 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:

15、 if a==b goto – 101: goto – 2) 產(chǎn)生式 B->B1 && M B2中的標(biāo)記非終結(jié)符號(hào)M記錄了nextinstr的值，該值為102 3) 按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的值，該值為104 5) 按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)出