編譯原理(龍書)習題(5-6-7-8)章課件

第5章語法制導的翻譯5.2.3假設我們有一個產(chǎn)生式。A，B，C，D這四個非終結(jié)符號都有兩個屬性：s是一個綜合屬性，而i是一個繼承屬性。對于下面的每組規(guī)則，指出(i)這些規(guī)則是否滿足S屬性定義的要求。(ii)這些規(guī)則是否滿足L屬性定義的要求。(iii)是否存在和這些規(guī)則一致的求值過程？1）A.s=B.i+C.s不滿足S屬性定義，滿足L屬性定義2）A.s=B.i+C.s和D.i=A.i+B.s不滿足S屬性定義，滿足L屬性定義3）A.s=B.s+D.s滿足S屬性定義，滿足L屬性定義4）A.s=D.i，B.i=A.s+C.s，C.i=B.s和D.i=B.i+C.i不滿足S屬性定義，不滿足L屬性定義

1可編輯課件PPT5.2.4這個文法生成了含“小數(shù)點”的二進制：

設計一個L屬性的SDD來計算S.val，即輸入串的十進制數(shù)值。比如，串101.11應該被翻譯為十進制數(shù)5.635。提示：使用一個繼承屬性L.side來指明一個二進制位在小數(shù)點的哪一邊。2可編輯課件PPT為了求小數(shù)部分的值，引入L的綜合屬性b記錄2的L的位數(shù)次冪值(2lengthofL)S

L1.L2

S.val=L1.val+L2.val/L2.b;S

L

S.val=L.val;L

L1

B

L.val=L1.val*2+B.val;

L.b=L1.b*2;L

B

L.val=B.val;L.b=2;B0B.val=0;B1

B.val=1;3可編輯課件PPT5.3.1下面是涉及運算符+和整數(shù)或浮點運算分量的表達式的文法。區(qū)分浮點數(shù)的方法是看它有無小數(shù)點。1）給出一個SDD來確定每個項T和表達式E的類型。2）擴展(1)中得到的SDD，使得它可以把表達式轉(zhuǎn)換成為后綴表達式。使用一個單目運算符intToFloat把一個整數(shù)轉(zhuǎn)換為相等的浮點數(shù)。4可編輯課件PPT5可編輯課件PPT（２）設code為綜合屬性，代表各非終結(jié)符的代碼屬性type為綜合屬性，代表各非終結(jié)符的類型屬性inttoreal把整型值轉(zhuǎn)換為相等的實型值vtochar將數(shù)值轉(zhuǎn)換為字符串6可編輯課件PPT7可編輯課件PPT8可編輯課件PPT5.3.3給出一個SDD對x*(3*x+x*x)這樣的表達式求微分。表達式中涉及運算符+和*，變量x和常量。假設不進行任何簡化，也就是說，比如3*x將被翻譯為3*1+0*x。exp為原表達式的字符串，s為求導后的字符串。||為串聯(lián)接符。9可編輯課件PPT10可編輯課件PPT11可編輯課件PPT5.4.3下面的SDT計算了一個由0和1組成的串的值。它把輸入的符號串當作按照正二進制數(shù)來解釋。改寫這個SDT，使得基礎文法不再是左遞歸的，但仍然可以計算出整個輸入串的相同的B.val的值。12可編輯課件PPT非終結(jié)符D的綜合屬性b表示二進制數(shù)的位數(shù)，val表示對應的十進制數(shù)的數(shù)值。消除左遞歸后如下：13可編輯課件PPT第6章中間代碼生成6.1.1為下面的表達式構(gòu)造DAG((x+y)-((x+y)*(x-y)))+((x+y)*(x-y))14可編輯課件PPT6.2.1將算術(shù)表達式a+-(b+c)翻譯成1）抽象語法樹2）四元式序列3）三元式序列4）間接三元式序列15可編輯課件PPT1）抽象語法樹：16可編輯課件PPT2）四元式序列：3）三元式序列：4）間接三元式序列：17可編輯課件PPT6.4.1向圖6-19的翻譯方案中加入對應于下列產(chǎn)生式的規(guī)則：1）2）18可編輯課件PPT6.4.2使用圖6-20中的增量式翻譯方案重復練習6.4.1在增量方式中，gen不僅要構(gòu)造出一個新的三地址指令，還要將它添加到至今為止已生成的指令序列之后。19可編輯課件PPT6.4.3使用使用圖6-22所示的翻譯方案來翻譯下列賦值語句：2）x=a[i][j]+b[i][j]假設w1為數(shù)組a的第一維的寬度，w2為數(shù)組b的第一維的寬度，整數(shù)的寬度為w。t1=i*w1;t6=j*w;t2=j*w;t7=t5+t6;t3=t1+t2;t8=b[t7];t4=a[t3];t9=t4+t8;t5=i*w2;x=t9;20可編輯課件PPT6.6.1在圖6-30的語法制導定義中添加處理下列控制流構(gòu)造的規(guī)則：1）一個repeat語句，repeatSwhileB2）一個for循環(huán)語句，for(S1;B;S2)S3S-->repeatS1whileBbegin=newlabel()S1.next=newlabel()B.true=beginB.false=S.nextS.code=label(begin)||S1.code||label(S1.next)||B.code21可編輯課件PPTS-->for(S1;B;S2)S3S1.next=newlabel()B.true=newlabel()begin=newlabel()B.fale=S.nextS2.next=S1.nextS3.next=beginS.code=S1.code||label(S1.next)||B.code||label(begin)||S2.code||gen('goto'S1.next)||label(B.true)||S3.code||gen('goto'begin)22可編輯課件PPT6.7.7使用圖6-37中的翻譯方案翻譯下列表達式。給出每個子表達式的truelist和falselist。你可以假設第一條被生成的指令的地址是100。1）a==b&&(c==d||e==f)23可編輯課件PPT100:ifa==bgoto102101:goto__

102:ifc==dgoto__103:goto104104:ife==fgoto__105:goto__24可編輯課件PPT第7章運行時環(huán)境7.2.3圖7-9中是遞歸計算Fiabonacci數(shù)列的C語言代碼。假設f的活動記錄按順序包含下列元素：（返回值，參數(shù)n，局部變量s，局部變量t）。通常在活動記錄中還會有其他元素。下面的問題假設初始調(diào)用是f(5)。intf(intn){intt,s;if(n<2)return1;s=f(n-1);t=f(n-2);returns+t;}圖7-9活動樹25可編輯課件PPT第1個f(1)調(diào)用即將返回第5個f(1)調(diào)用即將返回26可編輯課件PPT7.2.5在一個通過引用傳遞參數(shù)的語言中，有一個函數(shù)f(x,y)完成下面的計算：x=x+1;y=y+2;returnx+y;如果將a賦值為3，然后調(diào)用f(a,a)，那么返回值是什么？

函數(shù)返回值為：12此時a的值為：627可編輯課件PPT第8章代碼生成8.2.1假設所有的變量都存放在內(nèi)存中，為下面的三地址語句生成代碼：1）x=1

LDR1,1STx,R13)x=a+1

LDR1,aADDR1,R1,1STx,R128可編輯課件PPT8.2.2假設a和b是元素為4字節(jié)值的數(shù)組，為下面的三地址語句序列生成代碼。2）三個語句序列x=a[i]y=b[i]z=x*yLDR1,iMULR1,R1,4LDR2,a(R1)STx,R2LDR3,iMULR3,R3,4LDR4,b(R3)STy,R4LDR5,xLDR6,yMULR5,R5,R6STz,R529可編輯課件PPT8.2.4假設x,y和z存放在內(nèi)存位置中，為下面的語句序列生成代碼：ifx<ygotoL1z=0gotoL2L1:z=1LDR1,xLDR2,ySUBR1,R1,R2BLTZR1,L1LDR3,0STz,R3JMPL2L1:LDR4,1STz,R430可編輯課件PPT8.2.6確定下列指令序列的代價。1）LDR0,y2LDR1,z2ADDR0,R0,R11STx,R02總代價：73）LDR0,c2LDR1,i2MULR1,R2,82STa(R1),R02總代價：831可編輯課件PPT8.3.3假設使用棧式分配，且假設a和b都是元素大小為4字節(jié)的數(shù)組，為下面的三地址語句生成代碼。2）三個語句序列x=a[i]y=b[i]z=x*yLDR1,iMULR1,R1,4ADDR1,R1,SPLDR2,a(R1)STx(SP),R2LDR3,iMULR3,R3,4ADDR3,R3,SPLDR4,b(R3)STy(SP),R4LDR5,x(SP)LDR6,y(SP)MULR5,R5,R6STz(SP),R532可編輯課件PPT8.5.1為下面的基本塊構(gòu)造DAG。d=b*ce=a+bb=b*ca=e-d1)只有a在基本塊的出口處活躍：d=b*ce=a+ba=e-d2)a,b,c在基本塊的出口處活躍：e=a+bb=b*ca=e-b33可編輯課件PPT8.5.8假設一個基本塊由下面的C語言賦值語句生成：x=a+b+c+d+e+f;y=a+c+e;1)給出這個基本塊的三地址語句（每個語句只做一次加法）。t1=a+bt2=t1+ct3=t2+dt4=t3+et5=t4+fx=t5t6=a+ct7=t6+ey=t734可編輯課件PPT2)假設x和y都在基本塊的出口處活躍，利用加法的結(jié)合律和交換律來修改這個基本塊，使得指令個數(shù)最少。把原始的賦值語句進行調(diào)整：x=a+c+e+b+d+fy=a+c+e對應的三地址語句序列：t1=a+ct2=t1+et3=t2+bt4=t3+dt5=t4+fx=t5t6=a+ct7=t6+ey=t7DAG35可編輯課件PPT優(yōu)化后的三地址語句序列：t1=a+cy=t1+et3=y+