第5章語法制導的翻譯5.2.3假設我們有一個產生式。A，B，C，D這四個非終結符號都有兩個屬性：s是一個綜合屬性，而i是一個繼承屬性。對于下面的每組規則，指出(i)這些規則是否滿足S屬性定義的要求。(ii)這些規則是否滿足L屬性定義的要求。(iii)是否存在和這些規則一致的求值過程？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這個文法生成了含“小數點”的二進制：

設計一個L屬性的SDD來計算S.val，即輸入串的十進制數值。比如，串101.11應該被翻譯為十進制數5.635。提示：使用一個繼承屬性L.side來指明一個二進制位在小數點的哪一邊。2可編輯課件PPT為了求小數部分的值，引入L的綜合屬性b記錄2的L的位數次冪值(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下面是涉及運算符+和整數或浮點運算分量的表達式的文法。區分浮點數的方法是看它有無小數點。1）給出一個SDD來確定每個項T和表達式E的類型。2）擴展(1)中得到的SDD，使得它可以把表達式轉換成為后綴表達式。使用一個單目運算符intToFloat把一個整數轉換為相等的浮點數。4可編輯課件PPT5可編輯課件PPT（２）設code為綜合屬性，代表各非終結符的代碼屬性type為綜合屬性，代表各非終結符的類型屬性inttoreal把整型值轉換為相等的實型值vtochar將數值轉換為字符串6可編輯課件PPT7可編輯課件PPT8可編輯課件PPT5.3.3給出一個SDD對x*(3*x+x*x)這樣的表達式求微分。表達式中涉及運算符+和*，變量x和常量。假設不進行任何簡化，也就是說，比如3*x將被翻譯為3*1+0*x。exp為原表達式的字符串，s為求導后的字符串。||為串聯接符。9可編輯課件PPT10可編輯課件PPT11可編輯課件PPT5.4.3下面的SDT計算了一個由0和1組成的串的值。它把輸入的符號串當作按照正二進制數來解釋。改寫這個SDT，使得基礎文法不再是左遞歸的，但仍然可以計算出整個輸入串的相同的B.val的值。12可編輯課件PPT非終結符D的綜合屬性b表示二進制數的位數，val表示對應的十進制數的數值。消除左遞歸后如下：13可編輯課件PPT第6章中間代碼生成6.1.1為下面的表達式構造DAG((x+y)-((x+y)*(x-y)))+((x+y)*(x-y))14可編輯課件PPT6.2.1將算術表達式a+-(b+c)翻譯成1）抽象語法樹2）四元式序列3）三元式序列4）間接三元式序列15可編輯課件PPT1）抽象語法樹：16可編輯課件PPT2）四元式序列：3）三元式序列：4）間接三元式序列：17可編輯課件PPT6.4.1向圖6-19的翻譯方案中加入對應于下列產生式的規則：1）2）18可編輯課件PPT6.4.2使用圖6-20中的增量式翻譯方案重復練習6.4.1在增量方式中，gen不僅要構造出一個新的三地址指令，還要將它添加到至今為止已生成的指令序列之后。19可編輯課件PPT6.4.3使用使用圖6-22所示的翻譯方案來翻譯下列賦值語句：2）x=a[i][j]+b[i][j]假設w1為數組a的第一維的寬度，w2為數組b的第一維的寬度，整數的寬度為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的語法制導定義中添加處理下列控制流構造的規則：1）一個repeat語句，repeatSwhileB2）一個for循環語句，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章運行時環境7.2.3圖7-9中是遞歸計算Fiabonacci數列的C語言代碼。假設f的活動記錄按順序包含下列元素：（返回值，參數n，局部變量s，局部變量t）。通常在活動記錄中還會有其他元素。下面的問題假設初始調用是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)調用即將返回第5個f(1)調用即將返回26可編輯課件PPT7.2.5在一個通過引用傳遞參數的語言中，有一個函數f(x,y)完成下面的計算：x=x+1;y=y+2;returnx+y;如果將a賦值為3，然后調用f(a,a)，那么返回值是什么？

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

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

LDR1,aADDR1,R1,1STx,R128可編輯課件PPT8.2.2假設a和b是元素為4字節值的數組，為下面的三地址語句序列生成代碼。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存放在內存位置中，為下面的語句序列生成代碼：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字節的數組，為下面的三地址語句生成代碼。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為下面的基本塊構造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都在基本塊的出口處活躍，利用加法的結合律和交換律來修改這個基本塊，使得指令個數最少。把原始的賦值語句進行調整：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優化后的三地址語句序列：t1=a+cy=t1+et3=y+