编译原理与技术 中间代码生成.ppt

2019/10/26,编译原理与技术讲义,1,编译原理与技术,中间代码生成,2019/10/26,编译原理与技术讲义,2,中间代码生成,中间代码形式 控制流语句翻译,2019/10/26,编译原理与技术讲义,3,中间代码生成,中间代码的种类 后缀式（逆波兰式） e.g.1 a + b * -c a b c * + e.g.2 1）a := b* -c + b * -c，其后缀式为 a b c * b c * + assign 2）if ab then c := c + 1 a b c c 1 + assign IF 语法树 vs. 分析树 e.g.3 1）a := b* -c + b * -c，其语法树为,2019/10/26,编译原理与技术讲义,4, e.g.3 1）a := b* -c + b * -c 语法树 vs. 分析树,中间代码的种类,assign,a,+,*,b,c,*,b,c,assign,E,E,E,+,E,*,E,b,E,E,a,赋值语句,c,E,*,E,b,E,c,2019/10/26,编译原理与技术讲义,5, e.g.3 2）a := b* -c + b * -c 语法树 vs. DAG,中间代码的种类,assign,a,+,*,b,c,*,b,c,assign,a,+,*,b,c,2019/10/26,编译原理与技术讲义,6,中间代码的种类,e.g.4 构造表达式的语法树（DAG） 产生式 语义规则 EE1 + E2 E.nptr := mknode(+,E1.nptr, E2.nptr) EE1 - E2 E.nptr := mknode(-,E1.nptr, E2.nptr) EE1 * E2 E.nptr := mknode(*,E1.nptr, E2.nptr) EE1 / E2 E.nptr := mknode(/,E1.nptr, E2.nptr) E( E1 ) E.nptr := E1.nptr E - E1 E.nptr := mknode(,E1.nptr, ) Enumber E.nptr := mkleaf(NUM,number.lex_val) Eid E.nptr := mkleaf(ID,id.entry),2019/10/26,编译原理与技术讲义,7,中间代码的种类,e.g.4 构造表达式的语法树（DAG） E.nptr E的语法树（根结点指针） mknode(op, left, right)建立一个表达式语法树结点，它的运算符为op，左、右运算对象是left和right所指的语法树。 mkleaf(NUM,number.lex_val) mkleaf(ID,id.entry) 建立表达式语法树的叶子结点。,2019/10/26,编译原理与技术讲义,8,e.g.4 构造表达式a+b*-4的语法树（DAG）,中间代码的种类,2019/10/26,编译原理与技术讲义,9,中间代码的种类,三地址代码 一般形式：x := y op z 或 x := op y e.g.5 a := b* -c + b * -c的三地址代码 1）t1 := - c 1） t1 := - c 2）t2 := b * t1 2） t2 := b * t1 3）t3 := - c 3） t3 := t2 + t2 4）t4 := b * t3 4） a := t3 5）t5 := t2 + t4 6）a := t5,2019/10/26,编译原理与技术讲义,10,中间代码的种类,常用的三地址代码 x := y op z 二元运算 x := op y 单目运算 x := y 值拷贝 goto L 无条件转移到代码标号L处 if x RELOP y goto L 条件转移代码：若x和y满足RELOP关系，则转移至代码标号L处 param X 参数X CALL proc，N 调用过程proc，参数个数为N,2019/10/26,编译原理与技术讲义,11,中间代码的种类,常用的三地址代码（续） return y 过程返回，返回值为y x := y i x i := y 变址语句 x := &y *x := y x := *y 指针操作语句 三地址代码实现形式 四元式： （ op, arg1, arg2, result ） 三元式： （ op, arg1, arg2 ） 间接三元式（三元式的指针表）,2019/10/26,编译原理与技术讲义,12,中间代码的种类,e.g.6 a := b* -c + b * -c 的四元式和三元式 四元式 vs. 三元式 1）（ , c, , t1） （ , c, ） 2）（ * , b, t1, t2） （ * , b, ） 3）（ , c, , t3） （ , c, ） 4）（ * , b, t3, t4） （ * , b, ） 5）（ + , t2, t4, t5 ） （ + , , ） 6）（:=, t5, a） （:=, a, ）,2019/10/26,编译原理与技术讲义,13,中间代码的种类,e.g.7 a := b * c + d / f 的间接三元式 间接三元式 / 调整次序 三元式 （ * , b , c ） （ / , d , f ） （ + , , ） （ := , a , ）,2019/10/26,编译原理与技术讲义,14,中间代码的种类,2019/10/26,编译原理与技术讲义,15,说明语句的翻译,一般不产生代码；仅将有关变量的属性填入符号表（如类型、存储偏移位置offset） e.g. 8 一个说明语句的翻译方案 文法G1如下： PD DD ; D Did : T Tint | real | array number of T1 | T1,2019/10/26,编译原理与技术讲义,16,e.g. 8 一个说明语句的翻译方案（续）, 有关符号的属性 T.type 变量所具有的类型，如 整型 INT 实型 REAL 数组类型 array（元素个数，元素类型） 指针类型 pointer（所指对象类型） T.width 该类型数据所占的字节数 offset 变量的存储偏移地址,2019/10/26,编译原理与技术讲义,17,e.g. 8 一个说明语句的翻译方案（续）,2019/10/26,编译原理与技术讲义,18,e.g. 8 一个说明语句的翻译方案（续）,（1）PM D （2）DD1 ; D2 （3）Did : T / 填入变量的相关属性 enter( id.name, T.type, offset) / 计算下一可用偏移位置 offset = offset + T.width （4）M offset := 0 / 偏移初始为0,2019/10/26,编译原理与技术讲义,19,e.g. 8 一个说明语句的翻译方案（续）,（5）Tint T.type := INT; T.width := 4 （6）Treal T.type := REAL; T.width := 4 （7）Tarray number of T1 T.type := array( number.val, T1.type); T.width := number.val * T1.width （8）Tpointer( T1 ) T.type := pointer( T1.type) ; T.width := 4 ,2019/10/26,编译原理与技术讲义,20,e.g. 9 一个嵌套说明语句的翻译方案,文法G2如下： PD DD1 ; D2 Did : T D proc id ; D1 ; S Tint | real | array number of T1 | T1 Sa,2019/10/26,编译原理与技术讲义,21,e.g. 9 一个嵌套说明语句的翻译方案,产生式 D proc id ; D1 ; S 引入过程id的声明；D1为其局部说明语句，可以声明变量或嵌套定义其它过程； 约定每个过程有自己独立的符号表且嵌套定义的过程符号表头有指针指向外围（父）过程的符号表；而父过程符号表中有该嵌套子过程的条目（涉及子过程名和子过程符号表的指针等属性）。,2019/10/26,编译原理与技术讲义,22,相关定义： /* 在父过程符号表中建立子过程名的条目*/ enter-proc（parent-table, sub-proc-name, sub-table） /* 将所声明变量的类型、偏移填入当前符号表*/ enter（current-table, name, type, current-offset） /* 建立新的符号表，其表头指针指向父过程符号表*/ mktable（parent-table） addwidth（table，offset ）/记录变量占用的总空间 符号表栈tblptr和偏移栈offset（栈顶值分别表示当前分析的过程的符号表及可用变量偏移位置）,2019/10/26,编译原理与技术讲义,23,e.g. 9 一个嵌套说明语句的翻译方案,PM D addwidth( top(tblptr), top(offset) ), pop( tblptr ) ; pop( offset ) /* 保留变量分配空间大小并清空符号表和偏移栈 */ M t := mktable(null); push(t,tblptr); push(0,offset) /* 建立主程序（最外围）的符号表 偏移从0开始 */ DD1 ; D2,2019/10/26,编译原理与技术讲义,24,D proc id ; N D1 ; S t := top( tblptr ); addwidth( t, top( offset ) ); pop( tblptr ); pop( offset ); enter-proc( top( tblptr ), id.name, t ) /* 保留当前（子）过程声明变量的总空间；弹出符号表和偏移栈顶（露出父过程的符号表和偏移）；在父过程符号表中填写子过程名有关条目 */ N t := mktable( top( tblptr ) ); push( t, tblptr ) ; push( 0, offset ) /* 建立子过程的符号表和偏移从0开始 */,2019/10/26,编译原理与技术讲义,25,Did : T enter( top( tblptr ), id.name, T.type, top( offset ) ); top( offset ) := top( offset ) + T.width; /* 将变量name的有关属性填入当前符号表 */ /* 以下产生式的翻译方案略 */ Tint | real | array number of T1 | T1 Sa,2019/10/26,编译原理与技术讲义,26,i : int; j : int ; PROC P1 ; k : int; f : real ; PROC P2; l : int ; a1 ; a2; PROC P3; temp : int ; max : int ; a3;,e.g.10 过程嵌套声明,P0,P1,P3,P2,过程声明层次图,2019/10/26,编译原理与技术讲义,27,初始：M,e.g.10 过程嵌套声明（续）,符号栈,偏移栈,P0,0,top,null,总偏移：,P0,2019/10/26,编译原理与技术讲义,28,i : int ; j : int ;,e.g.10 过程嵌套声明（续）,符号栈,偏移栈,P0,8,top,null,总偏移：,P0,i,INT,0,j,INT,4,2019/10/26,编译原理与技术讲义,29,PROC P1 ; （N）,e.g.10 过程嵌套声明（续）,符号栈,偏移栈,P0,8,top,null,总偏移：,P0,i,INT,0,j,INT,4,P1,0,总偏移：,P1,2019/10/26,编译原理与技术讲义,30,k : int ; f : real ;,e.g.10 过程嵌套声明（续）,符号栈,偏移栈,P0,8,top,null,总偏移：,P0,i,INT,0,j,INT,4,P1,8,总偏移：,P1,k,INT,0,f,real,4,2019/10/26,编译原理与技术讲义,31,PROC P2 ; （N）,e.g.10 过程嵌套声明（续）,符号栈,偏移栈,P0,8,top,null,总偏移：,P0,i,INT,0,j,INT,4,P1,8,总偏移：,P1,k,INT,0,f,real,4,P2,0,总偏移：,P2,2019/10/26,编译原理与技术讲义,32,l : int ;,e.g.10 过程嵌套声明（续）,符号栈,偏移栈,P0,8,top,null,总偏移：,P0,i,INT,0,j,INT,4,P1,8,总偏移：,P1,k,INT,0,f,real,4,P2,4,总偏移：,P2,l,INT,0,2019/10/26,编译原理与技术讲义,33,a1 ;,e.g.10 过程嵌套声明（续）,符号栈,偏移栈,P0,8,top,null,总偏移：,P0,i,INT,0,j,INT,4,P1,8,总偏移：,P1,k,INT,0,f,real,4,总偏移：4,P2,l,INT,0,P2,proc,2019/10/26,编译原理与技术讲义,34,a2 ;,e.g.10 过程嵌套声明（续）,符号栈,偏移栈,P0,8,top,null,总偏移：,P0,i,INT,0,j,INT,4,总偏移：8,P1,k,INT,0,f,real,4,总偏移：4,P2,l,INT,0,P2,proc,P1,proc,2019/10/26,编译原理与技术讲义,35,PROC P3 ; （N）,e.g.10 过程嵌套声明（续）,符号栈,偏移栈,P0,8,top,null,总偏移：,P0,i,INT,0,j,INT,4,总偏移：8,P1,k,INT,0,f,real,4,总偏移：4,P2,l,INT,0,P2,proc,P1,proc,P3,0,总偏移：,P3,2019/10/26,编译原理与技术讲义,36,temp : int; max : int;,e.g.10 过程嵌套声明（续）,符号栈,偏移栈,P0,8,top,null,总偏移：,P0,i,INT,0,j,INT,4,总偏移：8,P1,k,INT,0,f,real,4,总偏移：4,P2,l,INT,0,P2,proc,P1,proc,P3,8,总偏移：,P3,temp,INT,0,max,INT,4,2019/10/26,编译原理与技术讲义,37,a3;,e.g.10 过程嵌套声明（续）,符号栈,偏移栈,top,null,总偏移：,P0,i,INT,0,j,INT,4,总偏移：8,P1,k,INT,0,f,real,4,总偏移：4,P2,l,INT,0,P2,proc,P1,proc,P0,8,总偏移：8,P3,temp,INT,0,max,INT,4,P3,proc,2019/10/26,编译原理与技术讲义,38,P M D ；,e.g.10 过程嵌套声明（续）,符号 栈空,偏移 栈空,top,null,总偏移：8,P0,i,INT,0,j,INT,4,总偏移：8,P1,k,INT,0,f,real,4,总偏移：4,P2,l,INT,0,P2,proc,P1,proc,总偏移：8,P3,temp,INT,0,max,INT,4,P3,proc,2019/10/26,编译原理与技术讲义,39,记录的说明,记录（record ）语法如下： T record D end 说明D含义同前面。（一般不含有过程声明，但C+可以） 可以将记录中的域变量声明放在单独的符号表中（参照嵌套过程声明的做法，但外围过程指针为空）。,2019/10/26,编译原理与技术讲义,40,记录说明的翻译,T record L D end T.type := record( top( tblptr ) ); /记录类型定义 T.width := top( offset ); / 记录的占用空间大小 pop( tblptr ); pop( offset ) L t := mktable( null ); / 无外围“过程” push(t, tblptr ); push( 0, offset ); / 域变量偏移从0开始 D的翻译同前。,2019/10/26,编译原理与技术讲义,41,有2个C语言的结构定义如下： struct A struct B char c1; char c1; char c2; long l; long l; char c2; double d; double d; S1; S2;,e.g.11 记录域的偏移,2019/10/26,编译原理与技术讲义,42,e.g.11 记录域的偏移,数据（类型）的对齐alignment 在 X86-Linux下： char ：对齐1，起始地址可分配在任意地址 int，long，double ：对齐4，即从被4整除的地址开始分配 注* ：其它类型机器，double可能对齐到8，如sunSPARC,2019/10/26,编译原理与技术讲义,43,e.g.11 记录域的偏移,结构A 和 B的大小分别为16和20字节(Linux),0,4,8,12,16,结构 A,0,4,8,12,16,结构 B,20,衬垫 padding,2019/10/26,编译原理与技术讲义,44,2个结构中域变量的偏移如下： struct A struct B char c1; 0 char c1; 0 char c2; 1 long l; 4 long l; 4 char c2; 8 double d; 8 double d; 12 S1; S2;,e.g.11 记录域的偏移,2019/10/26,编译原理与技术讲义,45,含简单变量的赋值语句，如id := E，其中， id为普通变量，而E是简单的算术表达式。文法定义如下： A id := E E E1 + E2 E E1 * E2 E - E1 E ( E1 ) E id,赋值语句的翻译,1) E的属性定义： E.place : 存放表达式E“值”的场所 2) newtemp 获取临时变量以存放中间结果 3) emit 产生三地址码（TAC）的过程 4) lookup( name ) 检查name是否在符号表中有定义（条目）,2019/10/26,编译原理与技术讲义,46,含简单变量的赋值语句的翻译 A id := E p = lookup (id.name)； if ( p != null ) emit( p := E.place) else error E E1 + E2 t := newtemp; emit( t := E1.place + E2.place ) E E1 * E2 t := newtemp; emit( t := E1.place * E2.place ) E - E1 t := newtemp; emit( t := - E1.place ) E ( E1 ) E.place := E1.place E id p = lookup (id.name)； if ( p != null ) E.place := p else error ,2019/10/26,编译原理与技术讲义,47,e.g.12 赋值语句a := -b*c+d的翻译,a,:=,-,b,E.place=b,E.place=t1,TAC:,1) t1 := - b,*,c,E.place=c,E.place=t2,2) t2 := t1 * c,+,d,E.place=d,E.place=t3,3) t3 := t2 + d,A,4) a := t3,2019/10/26,编译原理与技术讲义,48,e.g.13 赋值语句后缀式代码生成,A L := E print ( := ) E E1 + E2 print ( + ) E E1 * E2 print ( * ) E - E1 print ( ) E ( E1 ) E id p = lookup (name)； if ( p != null ) print( p ) else error Lid p = lookup (name)； if ( p != null ) print( p ) else error ,2019/10/26,编译原理与技术讲义,49,数组元素的翻译,数组类型的声明 e.g. Pascal的数组声明， A : array low1high1,lownhighn of integer ; 数组元素：A i , j, k, 或 Aijk （下界）low1 i high1（上界） , e.g. C的数组声明， int A 100100100; 数组元素：A i 3040 0 i (100-1),2019/10/26,编译原理与技术讲义,50,数组元素的翻译,数组元素的地址计算 仅讨论按行优先排列（即行主序）。约定数组名，如A，表示整个数组的起始地址（偏移）；w 表示数组元素所占字节数。 一维：A i 的地址addr为， addr = A + ( i - low1 ) * w = i * w + ( A - low1 * w ) 二维：A i1 , i2 的地址addr为，( n2=high2-low2+1) addr = A + ( ( i1 - low1 ) * n2 + ( i2 - low2 ) )*w = ( i1 * n2 + i2 ) *w + (A-(low1*n2+low2)*w),2019/10/26,编译原理与技术讲义,51,数组元素的地址计算（行主序） 多维（K维）：A i1 , i2,ik 的地址， addr = ( ( ( ( i1 * n2 + i2 ) * n3 + i3)*nk+ik) * w + (A - ( ( ( ( low1 * n2 + low2 ) * n3 + low3)*nk+lowk) * w) 数组元素的地址addr由可变部分var-part和常量值const-part相加而得，即 addr = “可变部分” + “常量值” 两部分可以由以下递推式计算（nmhighm-lowm+1） V1 = i1 Vm = Vm-1 * nm + im 1 m K C1 = low1 Cm = Cm-1 * nm + lowm 1 m K 当mK时，Vk * w 即为可变部分；而A-Ck*w为常量值。 “常量值”可以在编译时刻计算；而“可变部分”则必须生成代码在运行时刻加以计算（所有下标是常量的数组元素可以除外。Why?）。,2019/10/26,编译原理与技术讲义,52,数组元素的翻译,含有数组元素的赋值语句文法G3 (1) SV := E (2) V id Elist (3) V id (4) ElistElist1 , E (5) ElistE (6) E V (7) EE1 + E2 | E1 * E2 | (E1) | - E1,2019/10/26,编译原理与技术讲义,53,输入串 A x,y := z的分析树,S,V,:=,E,A,Elist,Elist,E,E,V,x,V,y,V,z,当分析到下标（表达式）x和y时，要计算地址中的“可变部分”。这时需要知晓数组A的有关的属性，如nm，类型宽度w等，而这些信息存于在结点A处。若想使用必须定义有关继承属性来传递之。但在移进归约分析不适合继承属性的计算！,2019/10/26,编译原理与技术讲义,54,改进后的含有数组元素的赋值语句文法G3 (1) SV := E (2) V Elist (3) V id (4) Elistid E (5) ElistElist1 , E (6) E V (7) EE1 + E2 | E1 * E2 | (E1) | - E1,数组元素的翻译,修改文法，使数组名id成为Elist的子结点（类似于前面的类型声明），从而避免继承属性的出现,2019/10/26,编译原理与技术讲义,55,数组元素的翻译,相关符号属性定义： V.place ，V.offset : 若V是简单变量，V.place为其“值”的存放场所，而V.offset为空（null） ；当V表示数组元素时，V.place是其地址的“常量值”部分；而此时V.offset为数组元素地址中可变部分的“值”存放场所，数组元素的表示为：V.place V.offset Elist.place : “可变部分”的值 Elist.array : 数组的属性 Elist.dim : 当前处理的维数,2019/10/26,编译原理与技术讲义,56,数组元素的翻译,翻译方案如下： (1) SV := E if V.offset = null / 简单变量 emit( V.place “:=” E.place ) else emit( V.place V.offset “:=” E.place) /取数组元素的左值 (2) V Elist /* 获取数组元素地址的常量值和可变部分 */ t := newtemp; emit( t “:=” Elist.array - get-CONST(Elist.array) ) V.place := t ; t := newtemp ; emit( t “:=” Elist.place * w ) V.offset := t ,2019/10/26,编译原理与技术讲义,57,数组元素的翻译,翻译方案如下（续）： (3) V id p := lookup( id.name); if (p = null) error() else V.place := p (4) Elistid E p := lookup( id.name); if (p = null) error() else Elist.place := E.place Elist.array := p /第一维下标 Elist.dim := 1 ,2019/10/26,编译原理与技术讲义,58,数组元素的翻译,翻译方案如下（续）： (5) ElistElist1 , E t := newtemp ; m := Elist1.dim + 1; / 当前处理第 m 维下标 nm := limit( Elist1.array, m ); / 计算highm-lowm+1 /以下代码递推计算Vm=Vm-1*nm+im emit( t “:=” Elist1.place * nm ) ; emit( t “:=” t + E.place ) ; Elist.place := t; Elist.array := Elist1.array; Elist.dim := m ,2019/10/26,编译原理与技术讲义,59,数组元素的翻译,翻译方案如下（续）： (6) EV if ( V.offset = null ) /简单变量 E.place := V.place else / 数组元素 t := newtemp ; /取数组元素的右值 emit( t “:=” V.place V.offset ); E.place := t (7) 同简单变量赋值语句。,2019/10/26,编译原理与技术讲义,60,e.g.14 语句 A i, j := B i, j * k 的翻译,数组A：A 110, 120 of integer; 数组B：B 110, 120 of integer; w : 4 （integer） TAC如下： (1) t1 := i * 20 (2) t1 := t1 + j (3) t2 := A - 84 / 84 = ( (1*20)+1 ) * 4 (4) t3 := t1 * 4 / 以上A i, j 的（左值）翻译,2019/10/26,编译原理与技术讲义,61,e.g.14 语句 A i, j := B i, j * k 的翻译,TAC如下（续）： (5) t4 := i * 20 (6) t4 := t4 + j (7) t5 := B - 84 (8) t6 := t4 * 4 (9) t7 := t5 t6 /以上计算Bi,j的右值,TAC如下（续）： (10) t8 := t7 * k /以上整个右值表达 /式计算完毕 (11) t2 t3 := t8 / 完成数组元素的赋值,2019/10/26,编译原理与技术讲义,62,e.g.15 Linux下C数组元素的翻译,1）数组元素下标均为常量 2）下标含变量的数组元素,