5编译原理-陈意云--课后答案5

编译原理习题课(5)栾俊[e-mail]6/13/20202020/6/[e-mail]27.1•把算术表达式–(a+b)*(c+d)+(a+b-c)翻译成：(a)语法树(b)有向无环图(c)后缀表示(d)三地址代码2020/6/[e-mail]37.1(续)•(a)语法树•(b)有向无环图+-+*++abcd+abc+-+*++abcd2020/6/[e-mail]47.1(续)•(c)后缀表示ab+cd+*-ab+c++•(d)三地址代码t1:=a+bt2:=c+dt3:=t1*t2t4:=-t3t5:=t1+ct6:=t4+t52020/6/[e-mail]57.2•把C程序main(){inti;inta[10];while(i=10)a[i]=0;}的可执行语句翻译成：(a)语法树(b)后缀表示(c)三地址代码2020/6/[e-mail]67.2(续)•(a)语法树•(b)后缀表示i10=aiarray0=whilewhile=i10=0arrayai2020/6/[e-mail]77.2(续)•(c)三地址代码1:ifi=10goto32:goto53:a[i]:=0;4:goto15:return02020/6/[e-mail]87.4•修改图7.4中计算声明的类型和相对地址的翻译方案，允许名字表而不是单个名字出现在形式为D-id:T的声明中。P-{offset=0;}DSD-D;DD-id:T{enter(id.name,T.type,offset);offset+=T.width;}T-integer{T.type=integer;T.width=4;}T-real{T.type=real;T.width=8;}T-array[num]ofT1{T.type=array(num.val,T1.type);T.width=num.val*T1.width;}T-↑T1{T.type=pointer(T1.type);T.width=4;}2020/6/[e-mail]97.4(续)•D-ID_LIST:TID_LIST-ID_LIST,ID_LIST|id•D-{Init(idtable)}ID_LIST:T{foreachnameinidtabledoenter(name,T.type,offset);offset:=offset+T.width;end;}ID_LIST-{Init(idtable1);Init(idtable2)}ID_LIST1,ID_LIST2{merge(idtable1,idtable2,idtable)}ID_LIST-id{add(idtable,id.name);}2020/6/[e-mail]107.5•算符θ作用于表达式e1,e2,...,ek的前缀形式是θp1p2...pk,其中pi是ei的前缀形式。(a)写出a*-(b+c)的前缀形式。(c)给出把表达式翻成前缀形式的语法制导定义。2020/6/[e-mail]117.5(续)•(a)*a-+bc•(c)表达式翻成前缀形式的语法制导定义E-E+T|TT-T*F|FF--F|(E)|idL-En{printf(E.string);}E-E1+T{E.string=“+”+E1.string+T.string;}E-T{E.string=T.string;}T-T1*F{T.string=“*”+T1.string+F.string;}T-F{T.string=F.string;}F--F1{F.string=“-”+F1.string;}F-(E){F.string=E.string;}F-id{F.string=id.value;}2020/6/[e-mail]127.7•修改图7.11的语法制导定义，为栈机器产生代码。EE1orE2{E.place:=newtemp;emit(E.place,‘:=’,E1.place,‘or’,E2.place)}EE1andE2{E.place:=newtemp;emit(E.place,‘:=’,E1.place,‘and’,E2.place)}EnotE1{E.place:=E1.place}E(E1){E.place:=newtemp;emit(E.place,‘:=’,‘not’,E1.place)}Eid1relopid2{E.place:=newtemp;emit(‘if’,id1.place,relop.op,id2.place,‘goto’,nextstat+3);emit(E.place,‘:=’,‘0’);emit(‘goto’,nextstat+2);emit(E.place,‘:=’,‘1’)}Etrue{E.place:=newtemp;emit(E.place,‘:=’,‘1’)}Efalse{E.place:=newtemp;emit(E.place,‘:=’,‘0’)}2020/6/[e-mail]137.7(续)•EE1orE2{emit(‘or’)}EE1andE2{emit(‘and’)}EnotE1{emit(‘not’)}E(E1){}Eid1relopid2{emit(‘push‘||id1.name);emit(‘push’||id2.name);emit(‘relop’||relop.op)}Etrue{emit(‘1’)}Efalse{emit(‘0’)}•指令解释:or:将栈顶和次栈顶值取出,进行或操作,将结果压栈and:将栈顶和次栈顶值取出,进行与操作,将结果压栈not:将栈顶值取出,进行非操作,将结果压栈pushname:将name的值压栈relopop:将栈顶和次栈顶值取出,判断他们的op关系,将结果压栈2020/6/[e-mail]147.8•表7.4的语法制导定义把E-id1id2翻译成一对语句ifid1id2goto...goto...可以用一个语句ifid1=id2goto...来代替，当E是真时执行后继代码。修改表7.4的语法制导定义，使之产生这种性质的代码。2020/6/[e-mail]157.6•假转方式产生式语义规则EE1orE2E1.true:=E.true;E1.false:=newlabel;E2.true:=E.true;E2.false:=E.false;E.code:=E1.code[增加:||gen(‘goto’,E1.true)]||gen(E1.false,‘:’)||E2.codeEE1andE2E1.true:=newlabel;E1.false:=E.false;E2.true:=E.true;E2.false:=E.false;E.code:=E1.code[删去:||gen(E1.true,‘:’)]||E2.code2020/6/[e-mail]167.6(续)续表EnotE1E1.true:=E.false;E1.false:=E.true;E.code:=E1.codeE(E1)E1.true:=E.true;E1.false:=E.false;E.code:=E1.codeEid1relopid2E.code:=gen(‘if’,id1.place,relop.op,id2.place,‘goto’,E.true)||gen(‘goto’,E.false)[修改为:E.code:=gen('if',id1.place,not(relop.op),id2.place,'goto',E.false))]EtrueE.code:=gen(‘goto’,E.true)EfalseE.code:=gen(‘goto’,E.false)2020/6/[e-mail]177.9•下面的C语言程序main(){inti,j;while((i||j)&&(j5)){i=j;}}在x86/Linux机器上编译生成的汇编代码如下：在该汇编代码中有关的指令后加注释，将源程序中的操作和生成的汇编代码对应起来，以判断确实是用短路计算来完成布尔表达式计算的。2020/6/[e-mail]187.9(续)题目.L6:cmpl$5,-8(%ebp)jg.L4jmp.L5.p2align4,,7.L5:jmp.L3.p2align4,,7.L4:movl-8(%ebp),%eaxmovl%eax,-4(%ebp)jmp.L2.p2align4,,7.L3.L1leaveret…….text.align4.globlmain.typemain,@functionmain:pushl%ebpmovl%esp,%ebpsubl$8,%espnop.p2align4,,7.L2:cmpl$0,-4(%ebp)jne.L6cmpl$0,-8(%ebp)jne.L6jmp.L5.p2align4,,72020/6/[e-mail]197.9(续).L2:.L2cmpl$0,-4(%ebp)ifi!=0,goto.L6jne.L6cmpl$0,-8(%ebp)ifj!=0,goto.L6jne.L6jmp.L5goto.L5.L6:.L6cmpl$5,-8(%ebp)ifj5,goto.L4jg.L4jmp.L5goto.L5.L5:.L5jmp.L3goto.L3.p2align4,,7.L4:.L4movl-8(%ebp),%eax%eax=jmovl%eax,-4(%ebp)i=%eaxjmp.L2goto.L2.L3.L3.L1.L1leaveleave2020/6/[e-mail]207.11•用7.3节的翻译方案，把下列赋值语句翻译成三地址代码：A[i,j]:=B[i,j]+C[A[k,1]]+D[i+j]2020/6/[e-mail]217.11(续)S:=ELElist]Elist,Eid[EALidiLidjE+EE+EL类似MLElist]id[ECL类似MLElist]id[EDE+ELidiLidjM2020/6/[e-mail]227.11(续)A[i,j]•A[i,j]:L1=Elist12]=Elist11,E11]=id[E12,E11]=id[L12,E11]=id[id,E11]=id[id,L11]=id[id,id]L11-idL11.place=‘j’;L11.offset=nullE11-L11E11.place=‘j’L12-idL12.place=‘i’;L12.offset=nullE12-L12E12.place=‘i’;Elist11-id[E12Elist11.place=‘i’;Elist11.ndim:=1;Elist11.array:=‘A’;Elist12-Elist11,Et:=‘t1’;m:=1+1:=2;emit(‘t1:=i*n2A’);emit(‘t1:=t1+i’);Elist12.array:=‘A’;Elist12.place=‘t1’;Elist12.ndim=2L1-Elist12]L1.pl