龙书第六章参考答案

6.1节的练习为下面的表达式构造DAG((x+y)-((x+y)*(x-y)))+((x+y)*(x-y))解答为下列表达式构造DAG，且指出他们每个子表达式的值编码。假定+是左结合的。a+b+(a+b)a+b+a+ba+a+(a+a+a+(a+a+a+a))解答a+b+(a+b)1ida2idb3+124+33a+b+a+b1ida2idb3+124+315+42a+a+(a+a+a+(a+a+a+a))1ida2+113+214+315+346+256.2节的练习6.2.1将算数表达式a+-(b+c)翻译成抽象语法树四元式序列三元式序列间接三元式序列解答抽象语法树四元式序列oparg1arg2result0+bct11minust1t22+at2t3三元式序列oparg1arg20+bc1minus(0)2+a(1)间接三元式序列oparg1arg20+bc1minus(0)2+a(1)instruction0(0)1(1)2(2)参考间接三元式更详细的讲解6.2.2对下列赋值语句重复练习6.2.1a=b[i]+c[j]a[i]=b*c-b*dx=f(y+1)+2x=*p+&y解答a=b[i]+c[j]四元式0)=[]bit11)=[]cjt22)+t1t2t33)=t3a三元式0)=[]bi1)=[]cj2)+(0)(1)3)=a(2)间接三元式0)=[]bi1)=[]cj2)+(0)(1)3)=a(2)0）1）2）3）a[i]=b*c-b*d四元式0)*bct11)*bdt22)-t1t2t33)[]=ait44)=t3t4三元式0)*bc1)*bd2)-(0)(1)3)[]=ai4)=(3)(2)间接三元式0)*bc1)*bd2)-(0)(1)3)[]=ai4)=(3)(2)0)1)2)3)4)x=f(y+1)+2四元式0)+y1t11)paramt12)callf1t23)+t22t34)=t3x三元式0)+y11)param(0)2)callf13)+(2)24)=x(3)间接三元式0)+y11)param(0)2)callf13)+(2)24)=x(3)0)1)2)3)4)参考数组元素的取值和赋值6.2.3!说明如何对一个三地址代码序列进行转换，使得每个被定值的变量都有唯一的变量名。6.3节的练习6.3.1确定下列声明序列中各个标识符的类型和相对地址。floatx;record{floatx;floaty;}p;record{inttag;floatx;floaty;}q;解答SDTS-{top=newEvn();offset=0;}DD-Tid;{top.put(id.lexeme,T.type,offset);offset+=T.width}D1D-εT-int{T.type=interget;T.width=4;}T-float{T.type=float;T.width=8;}T-record'{'{Evn.push(top),top=newEvn();Stack.push(offset),offset=0;}D'}'{T.type=record(top);T.width=offset;top=Evn.top();offset=Stack.pop();}标识符类型和相对地址lineidtypeoffsetEvn1)xfloat012)xfloat022)yfloat822)precord()813)tagint033)xfloat433)yfloat1233)qrecord()2416.3.2!将图6-18对字段名的处理方法扩展到类和单继承的层次结构。给出类Evn的一个实现。该实现支持符号表链，使得子类可以重定义一个字段名，也可以直接引用某个超类中的字段名。给出一个翻译方案，该方案能够为类中的字段分配连续的数据区域，这些字段中包含继承而来的域。继承而来的字段必须保持在对超类进行存储分配时获得的相对地址。6.4节的练习6.4.1向图6-19的翻译方案中加入对应于下列产生式的规则：E-E1*E2E-+E1解答产生式语义规则E-E1*E2{E.addr=newTemp();E.code=E1.code||E2.code||gen(E.addr'='E1.addr'*'E2.addr);}|+E1{E.addr=E1.addr;E.code=E1.code;}6.4.2使用图6-20的增量式翻译方案重复练习6.4.1解答产生式语义规则E-E1*E2{E.addr=newTemp();gen(E.addr'='E1.addr'*'E2.addr;}|+E1{E.addr=E1.addr;}6.4.3使用图6-22的翻译方案来翻译下列赋值语句：x=a[i]+b[j]x=a[i][j]+b[i][j]!x=a[b[i][j]][c[k]]解答x=a[i]+b[j]语法分析树:三地址代码t_1=i*awidtht_2=a[t_1]t_3=j*bwidtht_4=b[t_3]t_5=t_2+t_4x=t_5x=a[i][j]+b[i][j]语法分析树：三地址代码：t_1=i*ai_widtht_2=j*aj_widtht_3=t_1+t_2t_4=a[t_3]t_5=i*bi_widtht_6=j*bj_widtht_7=t_5+t_6t_8=b[t_7]t_9=t_4+t_8x=t_9!x=a[b[i][j]][c[k]]6.4.4!修改图6-22的翻译方案，使之适合Fortran风格的数据引用，也就是说n维数组的引用为id[E1,E2,…,En]解答仅需修改L产生式（同图6-22一样，未考虑消除左递归）L-id[A]{L.addr=A.addr;global.array=top.get(id.lexeme);}A-E{A.array=global.array;A.type=A.array.type.elem;A.addr=newTemp();gen(A.addr'='E.addr'*'A.type.width;}A-A1,E{A.array=A1.array;A.type=A1.type.elem;t=newTemp();A.addr=newTemp();gen(t'='E.addr'*'A.type.length);gen(A.addr'='A1.addr'+'t);}注意令a表示一个i*j的数组，单个元素宽度为wa.type=array(i,array(j,w))a.type.length=ia.type.elem=array(j,w)6.4.5将公式6.7推广到多维数据上，并指出哪些值可以被存放到符号表中并用来计算偏移量。考虑下列情况：一个二维数组A，按行存放。第一维的下标从l_1到h_1，第二维的下标从l_2到h_2。单个数组元素的宽度为w。其他条件和1相同，但是采用按列存放方式。！一个k维数组A，按行存放，元素宽度为w，第j维的下标从l_j到h_j。！其他条件和3相同，但是采用按列存放方式。解答令n_i为第i维数组的元素个数，计算公式：n_i=h_i-l_i+13.A[i_1]]…[i_k]=base+((i_1-l_1)*n_2*…*n_k+…+(i_k-1-l_k-1)*n_k+(i_k-l_k))*w4.A[i_1]]…[i_k]=base+((i_1-l_1)+(i_2-l_2)*n_1+…+(i_k-l_k)*n_k-1*n_k-2*…*n_1)*w6.4.6一个按行存放的整数数组A[i,j]的下标i的范围为1~10，下标j的范围为1~20。每个整数占4个字节。假设数组A从0字节开始存放，请给出下列元素的位置：A[4,5]A[10,8]A[3,17]解答计算公式：((i-1)*20+(j-1))*4(3*20+4)*4=256(9*20+7)*4=748(2*20+16)*4=2246.4.7假定A是按列存放的，重复练习6.4.6解答计算公式：((j-1)*10+(j-1))*4(4*10+3)*4=172(7*10+9)*4=316(16*10+2)*4=6486.4.8一个按行存放的实数型数组A[i,j,k]的下标i的范围为1~4，下标j的范围为0~4，且下标k的范围为5~10。每个实数占8个字节。假设数组A从0字节开始存放，计算下列元素的位置：A[3,4,5]A[1,2,7]A[4,3,9]解答计算公式：((i-1)*5*6+j*6+(k-5))*8((3-1)*5*6+4*6+(5-5))*8=672((1-1)*5*6+2*6+(7-5))*8=112((4-1)*5*6+3*6+(9-5))*8=8966.4.9假定A是按列存放的，重复练习6.4.8解答计算公式：((i-1)+j*4+(k-5)*5*4)*8((3-1)+4*4+(5-5)*5*4)*8=144((1-1)+2*4+(7-5)*5*4)*8=384((4-1)+3*4+(9-5)*5*4)*8=7606.5节的练习6.5.1假定图6-26中的函数widen可以处理图6-25a的层次结构中的所有类型，翻译下列表达式。假定c和d是字符类型，s和t是短整型，i和j为整型，x是浮点型。x=s+ci=s+cx=(s+c)*(t+d)解答x=s+ct1=(int)st2=(int)ct3=t1+t2x=(float)t3i=s+ct1=(int)st2=(int)ci=t1+t2x=(s+c)*(t+d)t1=(int)st2=(int)ct3=t1+t2t4=(int)tt5=(int)dt6=t4+t5t7=t3+t6x=(float)t76.5.2像Ada中那样，我们假设每个表达式必须具有唯一的类型，但是我们根据一个子表达式本身只能推导出一个可能类型的集合。也就是说，将函数E1应用于参数E2（文法产生式为E-E1(E2)）有如下规则：E.type={t|对E2.type中的某个s,s-t在E1.type中}描述一个可以确定每个字表达式的唯一类型的SDD。它首先使用属性type，按照自底向上的方式综合得到一个可能类型的集合。在确定了整个表达式的唯一类型之后，自顶向下地确定属性unique的值，整个属性表示各子表达式的类型。6.6节的练习6.6.1在图6-36的语法制导定义中添加处理下列控制流构造的规则：一个repeat语句：repeatSwhileB！一个for循环语句：for(S1;B;S2)S3解答ProductionSyntaxRuleS-repeatS1whileBS1.next=newlabel()B.true=newlabel()B.false=S.nextS.code=label(B.true)||S1.code||label(S1.next)||B.codeS-for(S1;B;S2)S3S1.next=newlabel()B.true=newlabel()B.false=S.nextS2.next=S1.nextS3.next=newlabel()S.code=S1.code||lable(S1.next)||B.code||lable(B.true)||S3.code||label(S3.next)||S2.code||gen('goto',S1.next)6.6.2现代计算机试图在同一个时刻执行多条指令，其中包括各种分支指令。因此，当计算机投机性地预先执行某个分支，但实际控制流却进入另一个分支时，付出的代价是很大的。因此我们希望尽可能地减少分支数量。请注意，在图6-35c中while循环语句的实现中，每个迭代有两个分支：一个是从条件B进入到循环体中，另一个分支跳转回B的代码。基于尽量减少分支的考虑，我们通常更倾向于将while(B)S当作if(B){repeatSuntil!(B)}来实现。给