汇编语言中间代码生成课件

汇编语言中言中间代代码生成生成7.1 中中 间间 语语 言言7.1.1 后缀表示后缀表示表达式表达式E的的后缀表示后缀表示可以如下归纳定义可以如下归纳定义如果如果E是变量或常数，那么是变量或常数，那么E的后缀表示就是的后缀表示就是E本身。本身。2020/11/1427.1 中中 间间 语语 言言7.1.1 后缀表示后缀表示表达式表达式E的的后缀表示后缀表示可以如下归纳定义可以如下归纳定义如果如果E是变量或常数，那么是变量或常数，那么E的后缀表示就是的后缀表示就是E本身。本身。如果如果E是形式为是形式为E1 opE2的表达式，那么的表达式，那么E的后的后缀表示是缀表示是E1 E2 op，其中其中E1 和和E2 分别是分别是E1和和E2的后缀表示。的后缀表示。2020/11/1437.1 中中 间间 语语 言言7.1.1 后缀表示后缀表示表达式表达式E的的后缀表示后缀表示可以如下归纳定义可以如下归纳定义如果如果E是变量或常数，那么是变量或常数，那么E的后缀表示就是的后缀表示就是E本身。本身。如果如果E是形式为是形式为E1 opE2的表达式，那么的表达式，那么E的后的后缀表示是缀表示是E1 E2 op，其中其中E1 和和E2 分别是分别是E1和和E2的后缀表示。的后缀表示。如果如果E是形式为是形式为(E1)的表达式，那么的表达式，那么E1的后缀的后缀表示也是表示也是E的后缀表示的后缀表示。2020/11/1447.1 中中 间间 语语 言言后缀表示不需要括号后缀表示不需要括号(8 4)+2 的后缀表示是的后缀表示是8 4 2+2020/11/1457.1 中中 间间 语语 言言后缀表示不需要括号后缀表示不需要括号(8 4)+2 的后缀表示是的后缀表示是8 4 2+后缀表示的最大优点是便于计算机处理表达后缀表示的最大优点是便于计算机处理表达式式2020/11/1467.1 中中 间间 语语 言言后缀表示不需要括号后缀表示不需要括号(8 4)+2 的后缀表示是的后缀表示是8 4 2+后缀表示的最大优点是便于计算机处理表达后缀表示的最大优点是便于计算机处理表达式式后缀表示很容易拓广到含一元算符的表达式后缀表示很容易拓广到含一元算符的表达式 2020/11/1477.1 中中 间间 语语 言言后缀表示不需要括号后缀表示不需要括号(8 4)+2 的后缀表示是的后缀表示是8 4 2+后缀表示的最大优点是便于计算机处理表达后缀表示的最大优点是便于计算机处理表达式式后缀表示很容易拓广到含一元算符的表达式后缀表示很容易拓广到含一元算符的表达式 后缀表示也可以拓广到表示赋值语句和控制后缀表示也可以拓广到表示赋值语句和控制语句，但很难用栈来描述它的计算语句，但很难用栈来描述它的计算2020/11/1487.1 中中 间间 语语 言言7.1.2 图形表示图形表示语法树是一种图形化的中间表示语法树是一种图形化的中间表示 assigna+bcdcduminus(a)语法树语法树 a=(b+c d)+c d的图形的图形表示表示2020/11/1497.1 中中 间间 语语 言言7.1.2 图形表示图形表示抽象语法树是一种图形化的中间表示抽象语法树是一种图形化的中间表示有向无环图有向无环图也是一种中间表示也是一种中间表示assigna+bcdcduminusassigna+bcduminus(a)语法树语法树(b)dag a=(b+c d)+c d的图形的图形表示表示2020/11/14107.1 中中 间间 语语 言言构造赋值语句抽象语法树的语法制导定义构造赋值语句抽象语法树的语法制导定义产产 生生 式式 语语 义义 规规 则则S id:=E S.nptr=mknode(assign,mkleaf(id,id.entry),E.nptr)E E1+E2 E.nptr=mknode(+,E1.nptr,E2.nptr)E E1 E2E.nptr=mknode(,E1.nptr,E2.nptr)E E1E.nptr=mkunode(uminus,E1.nptr)E (E1)E.nptr=E1.nptr F id E.nptr=mkleaf(id,id.entry)2020/11/14117.1 中中 间间 语语 言言7.1.3 三地址代码三地址代码一般形式：一般形式：x=y op z表达式表达式x+y z翻译成的三地址语句序列是翻译成的三地址语句序列是t1=y z t2=x+t1 2020/11/14127.1 中中 间间 语语 言言三地址代码是抽象语法树或三地址代码是抽象语法树或dag的一种线性表示的一种线性表示a=(b+c d)+c d抽象语法树的代码抽象语法树的代码t1=bt2=c dt3=t1+t2t4=c dt5=t3+t4a=t5assigna+bcdcduminus2020/11/14137.1 中中 间间 语语 言言三地址代码是语法树或三地址代码是语法树或dag的一种线性表示的一种线性表示a=(b+c d)+c d语法树的代码语法树的代码dag的代码的代码t1=bt1=bt2=c dt2=c dt3=t1+t2t3=t1+t2t4=c dt4=t3+t2t5=t3+t4 a=t4a=t5assigna+bcduminus2020/11/14147.1 中中 间间 语语 言言本书常用的三地址语句本书常用的三地址语句赋值语句赋值语句x=y op z，x=op y，x=y无条件转移无条件转移goto L条件转移条件转移if x relop y goto L过程调用过程调用param x 和和call p,n过程返回过程返回 return y索引赋值索引赋值x=yi和和 xi=y地址和指针赋值地址和指针赋值x=&y，x=y和和 x=y2020/11/14157.1 中中 间间 语语 言言赋值语句生成三地址代码的属性文法赋值语句生成三地址代码的属性文法产产 生生 式式 语语 义义 规规 则则S id:=E S.code=E.code|gen(id.place=E.place)E E1+E2 E E1 E22020/11/14167.1 中中 间间 语语 言言赋值语句生成三地址代码的属性文法赋值语句生成三地址代码的属性文法产产 生生 式式 语语 义义 规规 则则S id:=E S.code=E.code|gen(id.place=E.place)E E1+E2 E.Place=newtemp;E.Code=E1.code|E2.code|gen(E.place=E1.place+E2.place)E E1 E22020/11/14177.1 中中 间间 语语 言言赋值语句生成三地址代码的属性文法赋值语句生成三地址代码的属性文法产产 生生 式式 语语 义义 规规 则则S id:=E S.code=E.code|gen(id.place=E.place)E E1+E2 E.Place=newtemp;E.Code=E1.code|E2.code|gen(E.place=E1.place+E2.place)E E1 E2E.Place=newtemp;E.Code=E1.code|E2.code|gen(E.place=E1.place*E2.place)2020/11/14187.1 中中 间间 语语 言言赋值语句生成三地址代码的属性文法赋值语句生成三地址代码的属性文法产产 生生 式式 语语 义义 规规 则则E E1E.Place=newtemp;E.Code=E1.code|gen(E.place=uminus E1.place)E (E1)E id 2020/11/14197.1 中中 间间 语语 言言赋值语句生成三地址代码的属性文法赋值语句生成三地址代码的属性文法产产 生生 式式 语语 义义 规规 则则E E1E.Place=newtemp;E.Code=E1.code|gen(E.place=uminus E1.place)E (E1)E.place=E1.place;E.Code=E1.code;E id 2020/11/14207.1 中中 间间 语语 言言赋值语句生成三地址代码的属性文法赋值语句生成三地址代码的属性文法产产 生生 式式 语语 义义 规规 则则E E1E.Place=newtemp;E.Code=E1.code|gen(E.place=uminus E1.place)E (E1)E.place=E1.place;E.Code=E1.code;E id E.place=id.place;E.Code=;2020/11/14217.1 中中 间间 语语 言言三地址代码的具体表现形式：三地址代码的具体表现形式：四元式四元式三元式三元式间接三元式间接三元式2020/11/14227.1 中中 间间 语语 言言四元式四元式:a=b*-c+b*-ca=b*-c+b*-coparg1arg2result(0)uminus cT1(1)*bT1T2(2)uminus cT3(3)*bT3T4(4)+T2T4T5(5)=T5a2020/11/14237.1 中中 间间 语语 言言三元式三元式:a=b*-c+b*-ca=b*-c+b*-coparg1arg2(0)uminus c(1)*b(0)(2)uminus c(3)*b(2)(4)+(1)(3)(5)=a(4)2020/11/14247.1 中中 间间 语语 言言间接三元式间接三元式:a=b*-c+b*-ca=b*-c+b*-coparg1arg2(0)uminusc(1)*b(0)(2)+(1)(1)(3)=a(2)间接代码表间接代码表(0)(1)(0)(1)(2)(3)2020/11/14257.1 中中 间间 语语 言言练习：练习：将表达式将表达式:-(a+b)*(c+d)-(a+b+c):-(a+b)*(c+d)-(a+b+c)分别表示成分别表示成:后缀式、抽象语法树、后缀式、抽象语法树、DAGDAG、三元式、间接三元式、四元式、三元式、间接三元式、四元式2020/11/14267.2 声声 明明 语语 句句为局部名字建立符号表条目为局部名字建立符号表条目为它分配存储单元为它分配存储单元符号表中包含名字的类型和分配给它的存储符号表中包含名字的类型和分配给它的存储单元的相对地址等信息单元的相对地址等信息2020/11/14277.2 声声 明明 语语 句句7.2.1 过程中的声明过程中的声明例子：例子：i:integer;j:real;k:array10 of real;m:integer假设假设integer占占4个字节，个字节，real占占8个字节个字节名称类型长度偏移符号表符号表2020/11/14287.2 声声 明明 语语 句句7.2.1 过程中的声明过程中的声明例子：例子：i:integer;j:real;k:array10 of real;m:integer假设假设integer占占4个字节，个字节，real占占8个字节个字节名称类型长度偏移iint40符号表符号表2020/11/14297.2 声声 明明 语语 句句7.2.1 过程中的声明过程中的声明例子：例子：i:integer;j:real;k:array10 of real;m:integer假设假设integer占占4个字节，个字节，real占占8个字节个字节名称类型长度偏移iint40jreal84符号表符号表2020/11/14307.2 声声 明明 语语 句句7.2.1 过程中的声明过程中的声明例子：例子：i:integer;j:real;k:array10 of real;m:integer假设假设integer占占4个字节，个字节，real占占8个字节个字节名称类型长度偏移iint40jreal84karray(10,real)8012符号表符号表2020/11/14317.2 声声 明明 语语 句句7.2.1 过程中的声明过程中的声明例子：例子：i:integer;j:real;k:array10 of real;m:integer假设假设integer占占4个字节，个字节，real占占8个字节个字节名称类型长度偏移iint40jreal84karray(10,real)8012mpointer(integer)492符号表符号表2020/11/14327.2 声声 明明 语语 句句计算被声明名字的类型和相对地址计算被声明名字的类型和相对地址P offset=0 D SD D;D D id:T enter(id.name,T.type,offset);offset=offset+T.width T integer T.type=integer;T.width=4 T real T.type=real;T.width=8 T array num of T1T.type=array(num.val,T1.type);T.width=num.val T1.widthT T1 T.type=pointer(T1.type);T.width=4 2020/11/14337.2 声声 明明 语语 句句7.2.2 作用域信息的保存作用域信息的保存所讨论语言的文法所讨论语言的文法P D SD D;D|id:T|proc id;D;S 语义动作用到的函数语义动作用到的函数mktable(previous)enter(table,name,type,offset)addwidth(table,width)enterproc(table,name,newtable)2020/11/14347.2 声声 明明 语语 句句Program sort(input,output)var a:array0.10 of integer;x:integer;procedure readarray;var i:integer;begin.aendreadarray;procedure exchange(i,j:integer);beginx:=ai;ai:=aj;aj:=xendexchange;2020/11/14357.2 声声 明明 语语 句句procedure quicksort(m,n:integer);var k,v:integer;function partition(y,z:integer):integer;var i,j:integer;beginavexchange(i,j);endpartition;beginendquicksort;beginendsort.2020/11/14367.2 声声 明明 语语 句句嵌套关系嵌套关系sortreadarrayexchangepartitionSort当中定义了数当中定义了数组组a，readarray中中需要使用这一变量，需要使用这一变量，应该如何去组织符应该如何去组织符号表呢？号表呢？2020/11/14377.2 声声 明明 语语 句句exchangereadarrayxa表表 头头空空sortquicksort指向指向readarraypartitionvk表表 头头quicksortreadarrayi表表 头头exchange表表 头头指向指向exchangepartition2020/11/14387.2 声声 明明 语语 句句P M D S addwidth(top(tblptr),top(offset);pop(tblptr);pop(offset)M t=mktable(nil);push(t,tblprt);push(0,offset)D D1;D2D proc id;N D1;S t=top(tblptr);addwidth(t,top(offset);pop(tblptr);pop(offset);enterproc(top(tblptr),id.name,t)Did:T enter(top(tblptr),id.name,T.type,top(offset);top(offset)=top(offset)+T.width N t=mktable(top(tblptr);push(t,tblptr);push(0,offset)2020/11/14397.2 声声 明明 语语 句句7.2.3 记录的域名记录的域名T record D endT record L D endT.type=record(top(tblptr);T.width=top(offset);pop(tblptr);pop(offset)L t=mktable(nil);push(t,tblptr);push(0,offset)2020/11/14407.3 赋赋 值值 语语 句句a=(b+c d)+c d三地址代码三地址代码t1=bt2=c dt3=t1+t2t4=c dt5=t3+t4 a=t5四元式四元式0(,b,-,t1)1(*,c,d,t2)2(+,t1,t2,t3)3(*,c,d,t4)4(+,t3,t4,t5)5(=,t5,-,a)2020/11/14417.3 赋赋 值值 语语 句句7.3.1 赋值语句的翻译模式赋值语句的翻译模式S id:=E p=lookup(id.lexeme);if p!=nil thenemit(p,=,E.place)else error E E1+E2E.place=newtemp;emit(E.place,=,E1.place,+,E2.place)2020/11/14427.3 赋赋 值值 语语 句句7.3.1 赋值语句的翻译模式赋值语句的翻译模式E E1 E.place=newtemp;emit(E.place,=,uminus,E1.place)E (E1)E.place=E1.place E id p=lookup(id.lexeme);if p!=nil then E.place=p else error 2020/11/14437.3 赋赋 值值 语语 句句7.3.2 临时名字的重新使用临时名字的重新使用大量临时变量的使用对优化有利大量临时变量的使用对优化有利大量临时变量会增加符号表管理的负担大量临时变量会增加符号表管理的负担也会增加运行时临时数据占的空间也会增加运行时临时数据占的空间2020/11/14447.3 赋赋 值值 语语 句句7.3.2 临时名字的重新使用临时名字的重新使用大量临时变量的使用对优化有利大量临时变量的使用对优化有利大量临时变量会增加符号表管理的负担大量临时变量会增加符号表管理的负担也会增加运行时临时数据占的空间也会增加运行时临时数据占的空间E E1+E2的动作产生的代码的一般形式为的动作产生的代码的一般形式为计算计算E1到到t1计算计算E2到到t2t3=t1+t2()()()()临时变量的生存期像配对括号那样嵌套或并列临时变量的生存期像配对括号那样嵌套或并列2020/11/14457.3 赋赋 值值 语语 句句基于临时变量生成期特征的三地址代码基于临时变量生成期特征的三地址代码x=a b+c d e f语语 句句 c的值的值 0$0=a b 1$1=c d 2$0=$0+$1 1$1=e f 2$0=$0$1 1 x=$0 02020/11/14467.3 赋赋 值值 语语 句句数组的翻译：一维数组二维数组三维数组多维数组2020/11/14477.3 赋赋 值值 语语 句句7.3.3 数组元素的地址计算数组元素的地址计算一维数组一维数组A的第的第i个元素的地址计算个元素的地址计算base+(i low)w2020/11/14487.3 赋赋 值值 语语 句句7.3.3 数组元素的地址计算数组元素的地址计算一维数组一维数组A的第的第i个元素的地址计算个元素的地址计算base+(i low)w 重写成重写成(base low w)+i w基址基址变址变址2020/11/1449二维数组的翻译二维ai1,i2的维数d1*d22020/11/1450D=a+d2(i1 1)+i2 1 =a (d2+1)+i1 d2+i2 =Conspart+Varpart对对D的四元式翻译的四元式翻译*,i1,d2,T1+,T1,i2,T2-,a,c,T3所以所以 Ai1,i2的地址的地址D=T3T22020/11/1451三维Ai1,i2,i3的维数d1*d2*d3i1i2i3d2d3d12020/11/1452D=a+d2d3(i1 1)+d3(i2-1)+i3 1 =a (d2d3+d3+1)+(i1d2d3+i2d3+i3)=Conspart+Varpart对对D的四元式翻译的四元式翻译*,i1,d2,T1+,T1,i2,T2*,T2,d3,T3+,T3,i3,T4-,a,c,T5所以所以 Ai1,i2,i3的地址的地址D=T5T4VarpartConspart2020/11/14537.3 赋赋 值值 语语 句句总总结结：对对于于所所有有的的数数组组Ai1,i3,i3,来来讲讲，数数组组的的地地址址都都可可以以概概括括成成A-C+V的的格格式式，其其中中A是是数数组组的的首首地地址址，C是是编编译译时时可可以以预预先先确确定定的的常数，常数，V根据下标的变化而变化。根据下标的变化而变化。一维：一维：C=1w，V=i1w二维：二维：C=(d2+1)w，V=(i1d2+i2)w三维：三维：C=(d2d3+d3+1)w =(d2+1)d3)+1)w2020/11/14547.3 赋赋 值值 语语 句句三维：三维：V=(i1d2d3+i2d3+i3)w =(i1d2+i2)d3)+i3)w多维：多维：C=(d2+1)d3)+1)dn+1)w V=(i1d2+i2)d3)+i3)dn+in)w2020/11/14557.3 赋赋 值值 语语 句句7.3.4 数组元素地址计算的翻译方案数组元素地址计算的翻译方案下标变量访问的产生式下标变量访问的产生式L id Elist|idElist Elist,E|E改成改成L Elist|idElist Elist,E|id E2020/11/14567.3 赋赋 值值 语语 句句所有产生式所有产生式S L:=EE E+EE (E)E LL Elist L idElist Elist,EElist id E2020/11/14577.3 赋赋 值值 语语 句句L id L.place=id.place;L.offset=null 2020/11/14587.3 赋赋 值值 语语 句句L id L.place=id.place;L.offset=null Elist id E Elist.place=E.place;Elist.ndim=1;Elist.array=id.place 2020/11/14597.3 赋赋 值值 语语 句句L id L.place=id.place;L.offset=null Elist id E Elist.place=E.place;Elist.ndim=1;Elist.array=id.place Elist Elist1,E t=newtemp;m=Elist1.ndim+1;emit(t,=,Elist1.place,limit(Elist1.array,m);emit(t,=,t,+,E.place);Elist.array=Elist1.array;Elist.place=t;Elist.ndim=m2020/11/14607.3 赋赋 值值 语语 句句L id L.place=id.place;L.offset=null Elist id E Elist.place=E.place;Elist.ndim=1;Elist.array=id.place Elist Elist1,E t=newtemp;m=Elist1.ndim+1;emit(t,=,Elist1.place,limit(Elist1.array,m);emit(t,=,t,+,E.place);Elist.array=Elist1.array;Elist.place=t;Elist.ndim=mL Elist L.place=newtemp;emit(L.place,=,base(Elist.array),invariant(Elist.array);L.offset=newtemp;emit(L.offset,=,Elist.place,w)2020/11/14617.3 赋赋 值值 语语 句句E Lif L.offset=null then/L是简单变量是简单变量 /E.place=L.place else begin E.place=newtemp;emit(E.place,=,L.place,L.offset,)end 2020/11/14627.3 赋赋 值值 语语 句句E Lif L.offset=null then/L是简单变量是简单变量 /E.place=L.place else begin E.place=newtemp;emit(E.place,=,L.place,L.offset,)end E E1+E2E.place=newtemp;emit(E.place,=,E1.place,+,E2.place)2020/11/14637.3 赋赋 值值 语语 句句E Lif L.offset=null then/L是简单变量是简单变量 /E.place=L.place else begin E.place=newtemp;emit(E.place,=,L.place,L.offset,)end E E1+E2E.place=newtemp;emit(E.place,=,E1.place,+,E2.place)E (E1)E.place=E1.place 2020/11/14647.3 赋赋 值值 语语 句句E Lif L.offset=null then/L是简单变量是简单变量 /E.place=L.place else begin E.place=newtemp;emit(E.place,=,L.place,L.offset,)end E E1+E2E.place=newtemp;emit(E.place,=,E1.place,+,E2.place)E (E1)E.place=E1.place S L=E if L.offset=null then/L是是简简单单变变量量 /emit(L.place,=,E.place)else emit(L.place,L.offset,=,E.place)2020/11/14657.3 赋赋 值值 语语 句句例题：设A为一个1020的数组，即d1=10，d2=20，并设w=4，试对赋值语句x=Ay,z进行翻译。假设数组的下标从1开始。2020/11/14667.3 赋赋 值值 语语 句句S:=L.place=xL.offset=nullxE.place=t4L.place=t2L.offset=t3Elist.place=t1Elist.ndim=2Elist.array=A,Elist.place=yElist.ndim=1Elist.array=AE.place=zL.place=zL.offset=nullE.place=yL.place=yL.offset=nullAzy x:=A y,z 的注释分析树的注释分析树2020/11/14677.3 赋赋 值值 语语 句句S:=L.place=xL.offset=nullxE.place=t4L.place=t2L.offset=t3Elist.place=t1Elist.ndim=2Elist.array=A,Elist.place=yElist.ndim=1Elist.array=AE.place=zL.place=zL.offset=nullE.place=yL.place=yL.offset=nullAzy x:=A y,z 的注释分析树的注释分析树t1=y 20 t1=t1+z 2020/11/14687.3 赋赋 值值 语语 句句S:=L.place=xL.offset=nullxE.place=t4L.place=t2L.offset=t3Elist.place=t1Elist.ndim=2Elist.array=A,Elist.place=yElist.ndim=1Elist.array=AE.place=zL.place=zL.offset=nullE.place=yL.place=yL.offset=nullAzy x:=A y,z 的注释分析树的注释分析树t1=y 20 t1=t1+z t2=A 84 t3=4 t1 2020/11/14697.3 赋赋 值值 语语 句句S:=L.place=xL.offset=nullxE.place=t4L.place=t2L.offset=t3Elist.place=t1Elist.ndim=2Elist.array=A,Elist.place=yElist.ndim=1Elist.array=AE.place=zL.place=zL.offset=nullE.place=yL.place=yL.offset=nullAzy x:=A y,z 的注释分析树的注释分析树t1=y 20 t1=t1+z t2=A 84 t3=4 t1 t4=t2 t3 2020/11/14707.3 赋赋 值值 语语 句句S:=L.place=xL.offset=nullxE.place=t4L.place=t2L.offset=t3Elist.place=t1Elist.ndim=2Elist.array=A,Elist.place=yElist.ndim=1Elist.array=AE.place=zL.place=zL.offset=nullE.place=yL.place=yL.offset=nullAzy x:=A y,z 的注释分析树的注释分析树t1=y 20 t1=t1+z t2=A 84 t3=4 t1 t4=t2 t3 x=t4 2020/11/14717.3 赋赋 值值 语语 句句T1=y20T1=T1+zT2=A-84T3=4*T1T4=T2T3X=T4T1=y20T2=T1+zT3=A-84T4=4*T1T5=T3T4X=T52020/11/14727.3 赋赋 值值 语语 句句7.3.5 类型转换类型转换x=y+i j（x和和y的类型是的类型是real，i和和j的类型是的类型是integer）中间代码中间代码t1=i int jt2=inttoreal t1 t3=y real+t2 x=t32020/11/14737.3 赋赋 值值 语语 句句E E1+E2E.place=newtempif E1.type=integer&E2.type=integer then begin emit(E.place,=,E1.place,int+,E2.place);E.type=integerendelse if E1.type=integer&E2.type=real then beginu=newtemp;emit(u,=,inttoreal,E1.place);emit(E.place,=,u,real+,E2.place);E.type=realend .2020/11/14747.4 布尔表达式和控制流语句布尔表达式和控制流语句布尔表达式有两个基本目的布尔表达式有两个基本目的计算逻辑值计算逻辑值在控制流语句中用作条件表达式在控制流语句中用作条件表达式2020/11/14757.4 布尔表达式和控制流语句布尔表达式和控制流语句布尔表达式有两个基本目的布尔表达式有两个基本目的计算逻辑值计算逻辑值在控制流语句中用作条件表达式在控制流语句中用作条件表达式布尔表达式的完全计算布尔表达式的完全计算布尔表达式的布尔表达式的“短路短路”计算计算E1 or E2 定义成定义成 if E1 then true else E2E1 and E2 定义成定义成 if E1 then E2 else false2020/11/14767.4 布尔表达式和控制流语句布尔表达式和控制流语句7.4.1 布尔表达式的翻译布尔表达式的翻译E E or E|E and E|not E|(E)|id relop id|true|falsea b的翻译的翻译100:if a b goto 103101:t=0102:goto 104103:t=1104:2020/11/14777.4 布尔表达式和控制流语句布尔表达式和控制流语句7.4.2 控制流语句的翻译控制流语句的翻译S if E then S1|if E then S1 else S2|while E do S1|S1;S2 2020/11/14787.4 布尔表达式和控制流语句布尔表达式和控制流语句E.codeS1.codeE.true:.指向指向E.true指向指向E.false(a)if-thenE.codeS1.codeE.true:.指向指向E.true指向指向E.falseE.false:goto S.nextS2.code(b)if-then-elseE.codeS1.codeE.true:.指向指向E.true指向指向E.falsegoto S.beginS.begin:(c)while-doS1.codeS2.codeS1.next:.(d)S1;S22020/11/14797.4 布尔表达式和控制流语句布尔表达式和控制流语句布尔表达式翻译用到的三种四元式结构布尔表达式翻译用到的三种四元式结构(jnz,a,-,p)if a goto p(jrop,x,y,p)if x rop y goto p(j,-,-,p)goto p2020/11/14807.4 布尔表达式和控制流语句布尔表达式和控制流语句布尔表达式的翻译规则布尔表达式的翻译规则先顺序翻译布尔变量和关系表达式，暂时先顺序翻译布尔变量和关系表达式，暂时不管布尔运算符号（不管布尔运算符号（not，and，or等）。等）。其中，每一个布尔变量和关系表达式对其中，每一个布尔变量和关系表达式对应两条四元式，第一条是有条件跳转，应两条四元式，第一条是有条件跳转，第二条是无条件跳转。最后一个域即跳第二条是无条件跳转。最后一个域即跳转到何处暂时不填，等到全部完成后再转到何处暂时不填，等到全部完成后再填。填。2020/11/14817.4 布尔表达式和控制流语句布尔表达式和控制流语句对于布尔变量对于布尔变量A可以翻译成：可以翻译成：(1)(jnz,A,-,-)(2)(j,-,-,-)对于关系表达式对于关系表达式A rop B(1)(jrop,A,B,-)(2)(j,-,-,-)2020/11/14827.4 布尔表达式和控制流语句布尔表达式和控制流语句举例：举例：If A or(B D)then s1 else s22020/11/14837.4 布尔表达式和控制流语句布尔表达式和控制流语句举例：举例：If A or(B D)then s1 else s2(1)(jnz,A,-,-)(2)(j,-,-,-)(3)(j,B,D,-)(4)(j,-,-,-)(5)S1的四元式序列的四元式序列(p)(j,-,-,-)(q)(p+1)S2的四元式序列的四元式序列(r)(q)2020/11/14847.4 布尔表达式和控制流语句布尔表达式和控制流语句举例：举例：If A or(B D)then s1 else s2(1)(jnz,A,-,5)(2)(j,-,-,3)(3)(j 0 then y=x+1 else y=x+22020/11/14877.4 布尔表达式和控制流语句布尔表达式和控制流语句If x 0 then y=x+1 else y=x+2100(j,x,0,-)101(j,-,-,-)102(+,x,1,t1)103(=,t1,-,y)104(j,-,-,-)105(+,x,2,t2)106(=,t2,-,y)1072020/11/14887.4 布尔表达式和控制流语句布尔表达式和控制流语句If x 0 then y=x+1 else y=x+2100(j,x,0,102)101(j,-,-,105)102(+,x,1,t1)103(=,t1,-,y)104(j,-,-,107)105(+,x,2,t2)106(=,t2,-,y)1072020/11/14897.4 布尔表达式和控制流语句布尔表达式和控制流语句练习：练习：If not a or(c d)then y=x+1 else y=x+22020/11/1490循环结构的翻译模版Do E while SES P (j,_,_,100)P+1 ()100E.TCE.FC2020/11/14917.4 布尔表达式和控制流语句布尔表达式和控制流语句循环语句的翻译循环语句的翻译While(AD)then x=y+z;2020/11/14927.4 布尔表达式和控制流语句布尔表达式和控制流语句While(AD)then x=y+z;100(j,C,D,-)103103(j,-,-,-)104104(+,y,z,t1)105105(=,t1,-,x)106106(j,-,-,100)2020/11/14937.4 布尔表达式和控制流语句布尔表达式和控制流语句While(AD)then x=y+z;100(j,C,D,104)103103(j,-,-,100)104104(+,y,z,t1)105105(=,t1,-,x)106106(j,-,-,100)2020/11/14947.4 布尔表达式和控制流语句布尔表达式和控制流语句练习：练习：While(i or j)and(j 5)do i=j2020/11/14957.4 布尔表达式和控制流语句布尔表达式和控制流语句布尔表达式的语法制导翻译布尔表达式的语法制导翻译（1）E-E1 or M E2Backpatch(E1.falselist,M.quad);E.Truelist=merge(E1.truelist,E2.truelist);E.Falselist=E2.falselist;2020/11/14967.4 布尔表达式和控制流语句布尔表达式和控制流语句（2）E-E1 and M E2Backpatch(E1.truelist,M.quad);E.truelist=E2.truelist;E.falselist=merge(E1.falselist,E2.falselist);2020/11/14977.4 布尔表达式和控制流语句布尔表达式和控制流语句（3）E-not E1E.truelist=E1.falselist;E.falselist=E1.truelist;（4）E-(E1)E.truelist=E1.truelist;E.Falselist=E1.falselist;2020/11/14987.4 布尔表达式和控制流语句布尔表达式和控制流语句（5）E-id1 relop id2E.truelist=makelist(nextquad);E.falselist=makelist(nextquad+1);Emit(j relop.op,id1.place,id2.place,0);Emit(j,-,-,0);2020/11/14997.4 布尔表达式和控制流语句布尔表达式和控制流语句（6）E-idE.truelist=makelist(nextquad);E.falselist=makelist(nextquad+1);Emit(jnz,id.place,-,0);Emit(j,-,-,0);（7）M-M.quad=nextquad;2020/11/141007.4 布尔表达式和控制流语句布尔表达式和控制流语句布尔表达式的语法制导翻译举例布尔表达式的语法制导翻译举例ab or cd and ef2020/11/14101orE.tc=100E.fc=101a bE.tc=104E.fc=103,105E.tc=102E.fc=103ab or cd and ef的注释分析树的注释分析树M.q=102c dandM.q=104E.tc=104E.fc=105e fE.tc=100,104E.fc=10.,1052020/11/141027.4 布尔表达式和控制流语句布尔表达式和控制流语句布尔表达式的语法制导翻译举例布尔表达式的语法制导翻译举例ab or cd and ef100(j,a,b,0)101(j,-,-,102)102(j,c,d,104)103(j,-,-,0)104(j if E then M1 S1 N else M2 S2Backpatch(E.truelist,M1.quad);Backpatch(E.falselist,M2.quad);S.Nextlist=merge(S1.nextlist,N.nextlist,S2.nextlist)2020/11/141047.4 布尔表达式和控制流语句布尔表达式和控制流语句（2）N-N.nextlist=makelist(nextquad);Emit(j,-,-,-)（3）M-M.quad=nextquad;Backpatch(E.truelist,M.quad)2020/11/141057.4 布尔表达式和控制流语句布尔表达式和控制流语句（4）S-if E then M S1backpatch(E.truelist,M.quad);S.Nextlist=merge(E.falselist,S1.nextlist);2020/11/141067.4 布尔表达式和控制流语句布尔表达式和控制流语句（5）S-while M1 E do M2 S2backpatch(S1.nextlist,M1.quad);Backpatch(E.truelist,M2.quad);S.Nextlist=E.falselist;Emit(j,-,-,M1.quad);2020/11/141077.4 布尔表达式和控制流语句布尔表达式和控制流语句（6）S-begin L endS.nextlist=L.nextlist（7）S-AS.nextlist=makelist()（8）L-L1;M Sbackpatch(L1.nextlist,M.quad);L.Nextlist=S.nextlist（9）L-SL.nextlist=S.nextlist2020/11/141087.4 布尔表达式和控制流语句布尔表达式和控制流语句7.4.4 开关语句的翻译开关语句的翻译switch Ebegincase V1:S1case V2:S2.case Vn-1:Sn 1default:Snend2020/11/141097.4 布尔表达式和控制流语句布尔表达式和控制流语句分支数较少时分支数较少时t=E的代码的代码|Ln-2:if t!=Vn-1 goto Ln-1 if t!=V1 goto L1|Sn-1的代码的代码 S1的代码的代码|goto nextgoto next|Ln-1:Sn的代码的代码 L1:if t!=V2 goto L2|next:S2的代码的代码goto nextL2:.2020/11/141107.4 布尔表达式和控制流语句布尔表达式和控制流语句分支较多时，将分支测试的代码集中在一起，分支较多时，将分支测试的代码集中在一起，便于生成较好的分支测试代码。便于生成较好的分支测试代码。t=E的代码的代码|Ln:Sn的代码的代码goto test|goto nextL1:S1的代码的代码|test:if t=V1 goto L1 goto next|if t=V2 goto L2 L2:S2的代码的代码|.goto next|if t=Vn-1 goto Ln-1.|goto LnLn-1:Sn-1的代码的代码|next:goto next2020/11/141117.4 布尔表达式和控制流语句布尔表达式和控制流语句中间代码增加一种中间代码增加一种case语句，便于代码生成器语句，便于代码生成器对它进行特别处理对它进行特别处理 test:case V1 L1case V2 L2.case Vn-1 Ln-1case t Ln next:2020/11/141127.4 布尔表达式和控制流语句布尔表达式和控制流语句7.4.5 过程调用的翻译过程调用的翻译S call id(Elist)Elist Elist,EElist E2020/11/141137.4 布尔表达式和控制流语句布尔表达式和控制流语句过程调用过程调用id(E1,E2,En)的中间代码结构的中间代码结构E1.place=E1的代码的代码E2.place=E2的代码的代码.En.place=En的代码的代码param E1.placeparam E2.place.param En.placecall id.place,n2020/11/141147.4 布尔表达式和控制流语句布尔表达式和控制流语句S call id(Elist)为长度为为长度为n的队列中的每个的队列中的每个E.place，emit(param,E.place);emit(call,id.plase,n)Elist Elist,E把把E.place放入队列末尾放入队列末尾Elist E将队列初始化，并让它仅含将队列初始化，并让它仅含E.place 2020/11/14115本本 章章 要要 点点中间代码的几种形式，它们之间的相互转换中间代码的几种形式，它们之间的相互转换符号表的组织和作用域信息的保存符号表的组织和作用域信息的保存数数组组元元素素定定址址的的翻翻译译方方案案，布布尔尔表表达达式式的的两两种不同实现方式种不同实现方式赋赋值值语语句句和和各各种种控控制制流流语语句句的的中中间间代代码码格格式式和生成中间代码的翻译方案和生成中间代码的翻译方案过过程程调调用用的的中中间间代代码码格格式式和和生生成成中中间间代代码码的的翻译方案翻译方案2020/11/14116例例 题题 1Pascal语言的标准将语言的标准将for语句语句for v:=initial to final do stmt定义成和下面的代码序列有同样的含义：定义成和下面的代码序列有同样的含义：begint1:=initial;t2:=final;if t1=t2 then beginv:=t1;stmt;while v t2 do beginv:=succ(v);stmtendendend2020/11/14117例例 题题 1Pascal语言的标准将语言的标准将for语句语句for v:=initial to final do stmt能否定义成和下面的代码序列有同样的含义？能否定义成和下面的代码序列有同样的含义？begint1:=initial;t2:=final;v:=t1;while v t2 goto L1v=t1 L2:stmtif v=t2 goto L1v=v+1goto L2 L1:2020/11/14119例例 题题 2C语言的语言的for语句有下列形式语句有下列形式for(e1;e2;e3)stmt它和它和e1;while(e2)do beginstmt;e3;end2020/11/14120例例 题题 2C语言的语言的for语句语句for(e1;e2;e3)stmt的中间代码的中间代码结构如下结构如下 e1的代码的代码L1:e2的代码的代码L2:e3的代码的代码 goto L1 stmt的代码的代码 goto L2真转真转假转，由外层语句决定假转，由外层语句决定2020/11/14121例例 题题 3Pascal语言语言var a,b:array1.100 of integer;a:=b允许数组之间赋值允许数组之间赋值若若a和和b是同一类型记录，也允许是同一类型记录，也允许C语言语言数组不行，结构可以数组不行，结构可以为为这这种种赋赋值值选选用用或或设设计计一一种