《编译原理与技术》讲义编译原理与技术中间代码生成

1、2022/7/12编译原理与技术讲义1编译原理与技术中间代码生成2022/7/12编译原理与技术讲义2中间代码生成中间代码形式控制流语句翻译2022/7/12编译原理与技术讲义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，其语法树为2022/7/12编译原理与技

2、术讲义4 e.g.3 1）a := b* -c + b * -c 语法树 vs. 分析树中间代码的种类assigna+*bc*bcassignEEE+E*EbEEa赋值语句cE*EbEc2022/7/12编译原理与技术讲义5 e.g.3 2）a := b* -c + b * -c 语法树 vs. DAG中间代码的种类assigna+*bc*bcassigna+*bc2022/7/12编译原理与技术讲义6中间代码的种类e.g.4 构造表达式的语法树（DAG）产生式 语义规则EE1 + E2 E.nptr := mknode(+,E1.nptr, E2.nptr)EE1 - E2 E.nptr :

3、= 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.nptrE - E1 E.nptr := mknode(,E1.nptr, )Enumber E.nptr := mkleaf(NUM,number.lex_val)Eid E.nptr := mkleaf(ID,id.entry)2022/7/12编译原理与技术讲义7中间代码的种类e.g.4 构造表达式的语法树（DAG

4、）E.nptr E的语法树（根结点指针） mknode(op, left, right)建立一个表达式语法树结点，它的运算符为op，左、右运算对象是left和right所指的语法树。 mkleaf(NUM,number.lex_val) mkleaf(ID,id.entry)建立表达式语法树的叶子结点。2022/7/12编译原理与技术讲义8e.g.4 构造表达式a+b*-4的语法树（DAG）中间代码的种类+ ID a* ID b NUM42022/7/12编译原理与技术讲义9中间代码的种类三地址代码一般形式：x := y op z或 x := op ye.g.5 a := b* -c + b

5、* -c的三地址代码 1）t1 := - c1） 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 := t52022/7/12编译原理与技术讲义10中间代码的种类常用的三地址代码 x := y op z 二元运算 x := op y 单目运算 x := y 值拷贝 goto L 无条件转移到代码标号L处 if x RELOP y goto L 条件转移代码：若x和y满足RELOP关系，则转移至代码标号L处 par

6、am X 参数X CALL proc，N 调用过程proc，参数个数为N2022/7/12编译原理与技术讲义11中间代码的种类常用的三地址代码（续） return y 过程返回，返回值为y x := y i x i := y 变址语句 x := &y *x := y x := *y 指针操作语句 三地址代码实现形式 四元式： （ op, arg1, arg2, result ） 三元式： （ op, arg1, arg2 ） 间接三元式（三元式的指针表）2022/7/12编译原理与技术讲义12中间代码的种类e.g.6 a := b* -c + b * -c 的四元式和三元式 四元式 vs. 三

7、元式 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, ）2022/7/12编译原理与技术讲义13中间代码的种类e.g.7 a := b * c + d / f 的间接三元式间接三元式 / 调整次序三元式 （ * , b , c ） （ / , d , f ） （ + , , ） （ := , a , ） 2022/7/12编

8、译原理与技术讲义14中间代码的种类四元式按编号次序计算计算结果存于result方便移动，计算次序容易调整大量引入临时变量三元式按编号次序计算由编号代表不方便移动在代码生成时进行临时变量的分配间接三元式按编号次序计算方便移动，计算次序容易调整在代码生成时进行临时变量的分配2022/7/12编译原理与技术讲义15说明语句的翻译一般不产生代码；仅将有关变量的属性填入符号表（如类型、存储偏移位置offset）e.g. 8 一个说明语句的翻译方案文法G1如下：PDDD ; DDid : TTint | real | array number of T1 | T12022/7/12编译原理与技术讲义16e

9、.g. 8 一个说明语句的翻译方案（续） 有关符号的属性 T.type 变量所具有的类型，如整型 INT实型REAL数组类型 array（元素个数，元素类型）指针类型 pointer（所指对象类型） T.width 该类型数据所占的字节数 offset 变量的存储偏移地址2022/7/12编译原理与技术讲义17e.g. 8 一个说明语句的翻译方案（续）T.typeT.width整型INT4实型REAL4数组array（number, T1）number.val * T1.width指针pointer（T1）4enter(name,type,offset)将类型type和偏移offset填入符号

10、表中name所在的表项。2022/7/12编译原理与技术讲义18e.g. 8 一个说明语句的翻译方案（续）（1）PM D（2）DD1 ; D2（3）Did : T / 填入变量的相关属性 enter( , T.type, offset) / 计算下一可用偏移位置 offset = offset + T.width （4）M offset := 0 / 偏移初始为02022/7/12编译原理与技术讲义19e.g. 8 一个说明语句的翻译方案（续）（5）Tint T.type := INT; T.width := 4 （6）Treal T.type := REAL; T.width

11、:= 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 2022/7/12编译原理与技术讲义20e.g. 9 一个嵌套说明语句的翻译方案文法G2如下：PDDD1 ; D2Did : T D proc id ; D1 ; S Tint | real | array number of T1 | T1Sa2022/7/12编译原理与技术讲

12、义21e.g. 9 一个嵌套说明语句的翻译方案产生式 D proc id ; D1 ; S 引入过程id的声明；D1为其局部说明语句，可以声明变量或嵌套定义其它过程；约定每个过程有自己独立的符号表且嵌套定义的过程符号表头有指针指向外围（父）过程的符号表；而父过程符号表中有该嵌套子过程的条目（涉及子过程名和子过程符号表的指针等属性）。2022/7/12编译原理与技术讲义22相关定义：/* 在父过程符号表中建立子过程名的条目*/enter-proc（parent-table, sub-proc-name, sub-table）/* 将所声明变量的类型、偏移填入当前符号表*/enter（curren

13、t-table, name, type, current-offset）/* 建立新的符号表，其表头指针指向父过程符号表*/mktable（parent-table）addwidth（table，offset ）/记录变量占用的总空间符号表栈tblptr和偏移栈offset（栈顶值分别表示当前分析的过程的符号表及可用变量偏移位置）2022/7/12编译原理与技术讲义23e.g. 9 一个嵌套说明语句的翻译方案PM D addwidth( top(tblptr), top(offset) ), pop( tblptr ) ; pop( offset ) /* 保留变量分配空间大小并清空符号表和偏

14、移栈 */M t := mktable(null); push(t,tblptr); push(0,offset) /* 建立主程序（最外围）的符号表偏移从0开始 */DD1 ; D22022/7/12编译原理与技术讲义24D proc id ; N D1 ; S t := top( tblptr );addwidth( t, top( offset ) );pop( tblptr ); pop( offset );enter-proc( top( tblptr ), , t ) /* 保留当前（子）过程声明变量的总空间；弹出符号表和偏移栈顶（露出父过程的符号表和偏移）；在父过程

15、符号表中填写子过程名有关条目 */N t := mktable( top( tblptr ) ); push( t, tblptr ) ; push( 0, offset ) /* 建立子过程的符号表和偏移从0开始 */2022/7/12编译原理与技术讲义25Did : T enter( top( tblptr ), , T.type, top( offset ) ); top( offset ) := top( offset ) + T.width; /* 将变量name的有关属性填入当前符号表 */ /* 以下产生式的翻译方案略 */Tint | real | array n

16、umber of T1 | T1Sa2022/7/12编译原理与技术讲义26i : 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 过程嵌套声明P0P1P3P2过程声明层次图2022/7/12编译原理与技术讲义27初始：Me.g.10 过程嵌套声明（续）符号栈偏移栈P00topnull总偏移：P02022/7/12编译原理与技术讲义28i : int ; j : int ;e.g.10 过程嵌套声明（续）符号栈偏移栈P08t

17、opnull总偏移：P0iINT0jINT42022/7/12编译原理与技术讲义29PROC P1 ; （N）e.g.10 过程嵌套声明（续）符号栈偏移栈P08topnull总偏移：P0iINT0jINT4P10总偏移：P12022/7/12编译原理与技术讲义30k : int ; f : real ;e.g.10 过程嵌套声明（续）符号栈偏移栈P08topnull总偏移：P0iINT0jINT4P18总偏移：P1kINT0freal42022/7/12编译原理与技术讲义31PROC P2 ; （N）e.g.10 过程嵌套声明（续）符号栈偏移栈P08topnull总偏移：P0iINT0jINT

18、4P18总偏移：P1kINT0freal4P20总偏移：P22022/7/12编译原理与技术讲义32l : int ;e.g.10 过程嵌套声明（续）符号栈偏移栈P08topnull总偏移：P0iINT0jINT4P18总偏移：P1kINT0freal4P24总偏移：P2lINT02022/7/12编译原理与技术讲义33a1 ;e.g.10 过程嵌套声明（续）符号栈偏移栈P08topnull总偏移：P0iINT0jINT4P18总偏移：P1kINT0freal4总偏移：4P2lINT0P2proc 2022/7/12编译原理与技术讲义34a2 ;e.g.10 过程嵌套声明（续）符号栈偏移栈P0

19、8topnull总偏移：P0iINT0jINT4总偏移：8P1kINT0freal4总偏移：4P2lINT0P2proc P1proc 2022/7/12编译原理与技术讲义35PROC P3 ; （N）e.g.10 过程嵌套声明（续）符号栈偏移栈P08topnull总偏移：P0iINT0jINT4总偏移：8P1kINT0freal4总偏移：4P2lINT0P2proc P1proc P30总偏移：P32022/7/12编译原理与技术讲义36temp : int; max : int;e.g.10 过程嵌套声明（续）符号栈偏移栈P08topnull总偏移：P0iINT0jINT4总偏移：8P1k

20、INT0freal4总偏移：4P2lINT0P2proc P1proc P38总偏移：P3tempINT0maxINT42022/7/12编译原理与技术讲义37a3;e.g.10 过程嵌套声明（续）符号栈偏移栈topnull总偏移：P0iINT0jINT4总偏移：8P1kINT0freal4总偏移：4P2lINT0P2proc P1proc P08总偏移：8P3tempINT0maxINT4P3proc 2022/7/12编译原理与技术讲义38P M D ；e.g.10 过程嵌套声明（续）符号栈空偏移栈空topnull总偏移：8P0iINT0jINT4总偏移：8P1kINT0freal4总偏移

21、：4P2lINT0P2proc P1proc 总偏移：8P3tempINT0maxINT4P3proc 2022/7/12编译原理与技术讲义39记录的说明记录（record ）语法如下：T record D end说明D含义同前面。（一般不含有过程声明，但C+可以）可以将记录中的域变量声明放在单独的符号表中（参照嵌套过程声明的做法，但外围过程指针为空）。 2022/7/12编译原理与技术讲义40记录说明的翻译T record L D end T.type := record( top( tblptr ) ); /记录类型定义 T.width := top( offset ); / 记录的占用空

22、间大小 pop( tblptr ); pop( offset ) L t := mktable( null ); / 无外围“过程” push(t, tblptr ); push( 0, offset ); / 域变量偏移从0开始D的翻译同前。2022/7/12编译原理与技术讲义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 记录域的偏移2022/7/12编译原理与技术讲义42e.g.11 记录域的偏移数据（

23、类型）的对齐alignment在 X86-Linux下：char ：对齐1，起始地址可分配在任意地址int，long，double ：对齐4，即从被4整除的地址开始分配注* ：其它类型机器，double可能对齐到8，如sunSPARC2022/7/12编译原理与技术讲义43e.g.11 记录域的偏移结构A 和 B的大小分别为16和20字节(Linux)c1 c2l0l1l2l3d0d1d2d3d4d5d6d7 0481216结构 Ac1 l0l1l2l3c2d0d1d2d3d4d5d6d70481216结构 B20衬垫padding2022/7/12编译原理与技术讲义442个结构中域变量的偏移

24、如下：struct A struct B char c1; 0char c1; 0char c2; 1long l; 4long l; 4 char c2; 8double d; 8double d; 12 S1; S2;e.g.11 记录域的偏移2022/7/12编译原理与技术讲义45含简单变量的赋值语句，如id := E，其中，id为普通变量，而E是简单的算术表达式。文法定义如下：A id := EE E1 + E2E E1 * E2E - E1E ( E1 )E id 赋值语句的翻译1) E的属性定义：E.place : 存放表达式E“值”的场所2) newtemp 获取临时变量以存放中

25、间结果3) emit 产生三地址码（TAC）的过程4) lookup( name ) 检查name是否在符号表中有定义（条目）2022/7/12编译原理与技术讲义46含简单变量的赋值语句的翻译A id := E p = lookup ()； if ( p != null ) emit( p := E.place) else error E E1 + E2 t := newtemp; E.place := t ;emit( t := E1.place + E2.place ) E E1 * E2 t := newtemp; E.place := t; emit( t := E1.p

26、lace * E2.place ) E - E1 t := newtemp; ;E.place := t; emit( t := - E1.place ) E ( E1 ) E.place := E1.place E id p = lookup ()； if ( p != null ) E.place := p else error 2022/7/12编译原理与技术讲义47e.g.12 赋值语句a := -b*c+d的翻译a:=-bE.place=bE.place=t1TAC:1) t1 := - b*cE.place=cE.place=t22) t2 := t1 * c +dE

27、.place=dE.place=t33) t3 := t2 + d A4) a := t32022/7/12编译原理与技术讲义48e.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

28、 2022/7/12编译原理与技术讲义49数组元素的翻译数组类型的声明e.g. Pascal的数组声明，A : array low1.high1,lown.highn of integer ;数组元素：A i , j, k, 或 Aijk （下界）low1 i high1（上界） , e.g. C的数组声明，int A 100100100; 数组元素：A i 3040 0 i (100-1)2022/7/12编译原理与技术讲义50数组元素的翻译数组元素的地址计算仅讨论按行优先排列（即行主序）。约定数组名，如A，表示整个数组的起始地址（偏移）；w 表示数组元素所占字节数。一维：A i 的地址ad

29、dr为，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)2022/7/12编译原理与技术讲义51数组元素的地址计算（行主序）多维（K维）：A i1 , i2,ik 的地址，addr = ( ( ( ( i1 * n2 + i2 ) * n3 + i3)*nk+ik)

30、 * w + (A - ( ( ( ( low1 * n2 + low2 ) * n3 + low3)*nk+lowk) * w)数组元素的地址addr由可变部分var-part和常量值const-part相加而得，即 addr = “可变部分” + “常量值”两部分可以由以下递推式计算（nmhighm-lowm+1）V1 = i1Vm = Vm-1 * nm + im 1 m KC1 = low1Cm = Cm-1 * nm + lowm 1 m K当mK时，Vk * w 即为可变部分；而A-Ck*w为常量值。“常量值”可以在编译时刻计算；而“可变部分”则必须生成代码在运行时刻加以计算（所有

31、下标是常量的数组元素可以除外。Why?）。2022/7/12编译原理与技术讲义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 2022/7/12编译原理与技术讲义53输入串 A x,y := z的分析树 SV:=EAElistElist,EEVxVyVz当分析到下标（表达式）x和y时，要计算地址中的“可变部分”。这时需要知晓数组A的有关的属性，如nm，类型宽度w等，而这些信息存于在结点A处

32、。若想使用必须定义有关继承属性来传递之。但在移进归约分析不适合继承属性的计算！2022/7/12编译原理与技术讲义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的子结点（类似于前面的类型声明），从而避免继承属性的出现2022/7/12编译原理与技术讲义55数组元素的翻译相关符号属性定义：V.place，V.offset :若V是简单变量，V.pla

33、ce为其“值”的存放场所，而V.offset为空（null） ；当V表示数组元素时，V.place是其地址的“常量值”部分；而此时V.offset为数组元素地址中可变部分的“值”存放场所，数组元素的表示为：V.place V.offset Elist.place : “可变部分”的值Elist.array : 数组的属性Elist.dim : 当前处理的维数2022/7/12编译原理与技术讲义56数组元素的翻译翻译方案如下：(1) SV := E if V.offset = null / 简单变量 emit( V.place “:=” E.place )else emit( V.place V

34、.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 2022/7/12编译原理与技术讲义57数组元素的翻译翻译方案如下（续）：(3) V id p := lookup( ); if (p = null) error() else V.place := p (4) El