编译原理：第九章目标代码生成(2)

1、【例9.6】单寄存器(R)下表达式目标代码生成示例：(+ a(y) b(y) t1(y)(- c(y) d(y) t2(y)(* t1(y)t2(n)t3(y)(- a(y) t3(n)t4(y)(/ t1(n) 2 t5(y)(+ t4(n)t5(n) x(y)ST R,t1LD R,aSUB R,dMUL R,t1 ST R,t3SUB R,t3ST R,t12DIV R,213ADD R,t411LD R,t1人工翻译目标代码：LD R,cADD R,bLD R,a9.2 目标代码生成算法设计注需要随时观察寄存器状态 ！【例9.7】单寄存器(R)下,条件语句目标代码生成示例：如：if(a

2、b)x=(a+b)*c; ( a(y) b(y) t1(y)(if t1(n) _ _ )(+ a(y) b(y) t2(y)(* t2(n) c(y) x(y)(el _ _ _ )(* a(y) b(y) t3(y)(- 5 t3(n) x(y)(ie _ _ _ )FJ R,？LD R,aLD R,aMUL R,cJMP_,？ ST R,t31213SUB R,t314ST R,x1515ST R,x11GT R,belse x=5-a*b;LD R,5人工翻译过程ADD R,bMUL R,bLD R,a待返填1待返填2返填时机1返填时机2划分基本块注需要及时处理跳转地址返填 ！9.2.

3、1 目标代码生成要点和生成环境 【释放寄存器】编存储指令,保存占有寄存器的活跃变量值；通常发生在如下两个时刻：注 为结果变量申请寄存器时； 基本块出口时； 目标代码生成是在一个基本块上进行的： 入口:寄存器空闲； 出口:释放寄存器。 目标代码生成是以四元式为对象的： 表达式、赋值四元式；首先对结果变量申请寄存器； 转向四元式；首先保存占用寄存器的活跃变量值；然后再编跳转指令（不完备！）；同时记住待返填地址！然后编目标指令；并修改描述表。生成要点 虚拟机：单一寄存器 R ; 指令形式 p:(op R,M )变量内存地址 表、区和栈： QTq 四元式区(附有变量的活跃信息)； OBJp 目标代码区

4、； SEMm 语义栈（登记待返填的目标地址）；R:= (R)op(M)含义：R:= op(M)或 变量和函数：RDL= 0 (R空闲) ； RDL= X (R被X占用)； BACK(pi,pk)(返填函数)把地址 pk 返填到地址 pi中； SYMBLi 符号表； RDLR 寄存器描述表； CODE(op R,M;)(送代码函数)把目标代码送目标区；生成环境9.2.2 表达式四元式目标代码生成算法： 设当前扫描的四元式 q:( B C A) 为 A 预分配器存器，编目标： 算符对应的操作码 若 RDL=0 则 CODE( LD R,B ； R,C ); 若 RDL=B 则 若 B(y) 则 C

5、ODE( ST R,B ； R,C ); 否则 CODE( R,C ); 若 RDL=C 且 可交换 则 若 C(y) 则 CODE( ST R,C ； R,B ); 否则 CODE( R,B ); 若 D(y) 则 CODE( ST R,D ; LD R,B ; R,C );否则 CODE( LD R,B ; R,C ); 变量 A 登录到描述表中： RDL:= A ; 若 RDL=D（上述三种情况之外 ） 则 设当前四元式 q:(= B _ A)9.2.3 赋值四元式目标代码生成算法： 若 RDL=0 若 RDL=B 则 若 RDL=D（D!=B,D!=A ） 则 若 D(y) 则 COD

6、E( ST R,D ; LD R,B );否则 CODE( LD R,B ); 为 A 预分配器存器，编目标： 变量 A 登录到描述表中： RDL:= A ; 若 B(y) 则 CODE( ST R,B ); 则 CODE( LD R,B ); 计算机目标代码生成过程示例：【例9.7】 if(ab)x=(a+b)*c;else x=5-a*b; OBJp QUATqBSEMRDL( a(y) b(y) t1(y)(if t1(n) _ _ )(+ a(y) b(y) t2(y)(* t2(n) c(y) x(y)(el _ _ _ )(* a(y) b(y) t3(y)(- 5 t3(y) x

7、(y)(ie _ _ _ )FJ R,?t1LD R,at2LD R,a ADD R,bMUL R,cxJMP_,? LD R,a MUL R,bt3 ST R,t3 LD R,51213SUB R,t3x14ST R,x1515ST R,x11GT R,bt1t2xt3x实践中，先返填，后编跳转指令！9.2.4 条件语句四元式目标代码生成算法：(接前页) 若 RDV=D（D!=B） 则 PUSH(p) ；RDL:=0; 若 D(y) 则 CODE( ST R,D ; LD R,B ; FJ R,_ ); 否则 CODE( LD R,B ; FJ R,_ ); 设当前四元式 q:(if B _

8、 _ ) 若 RDV=B 则 若 RDV=0 则 CODE( LD R,B ; FJ R,_ ); PUSH(p)； 若 B(y) 则 CODE( ST R,B ; FJ R,_ ); 否则 CODE( FJ R,_ ); PUSH(p)；RDL:=0;条件语句的四元式结构 算法设计： 设当前四元式 q:( ie _ _ _ ) 返填转向地址： POP(p); BACK(p,p+2) 返填转向地址： POP(p);BACK(p,p+1) 编转向指令：CODE( JMP _, _ ); PUSH(p)把这个地址填到 p中 设当前四元式 q:( el _ _ _ )SEM栈顶地址弹到p中(接前页)

9、条件语句的四元式结构 若 RDV=X 且 X(y) 则 CODE( ST R,X ; ); 若 RDV=X 且 X(y) 则 CODE( ST R,X ; ); 计算机目标代码生成过程示例：【例9.7】 while (ab) x=(a+b)*c; OBJp QUATqBSEMRDL(2)( a(y) b(y) t1(y)(3)(do t1(n) _ _ )(4)(+ a(y) b(y) t2(y)(5)(* t2(n) c(y) x(y)(6)(we _ _ _ )FJ R,?t1 LD R,at2LD R,a ADD R,bMUL R,cxJMP_,? 1ST R,xGT R,bt1t2x实

10、践中，先返填，后编跳转指令！ 9.2.5 循环语句四元式目标代码生成算法：(1)(wh _ _ _)(接前页) 设当前四元式 q:(wh _ _ _ )PUSH(p)； 算法设计：(接前页) 若 RDV=D（D!=B） 则 PUSH(p) ；RDL:=0; 若 D(y) 则 CODE( ST R,D ; LD R,B ; FJ R,_ ); 否则 CODE( LD R,B ; FJ R,_ ); 若 RDV=B 则 若 RDV=0 则 CODE( LD R,B ; FJ R,_ ); PUSH(p)； 若 B(y) 则 CODE( ST R,B ; FJ R,_ ); 否则 CODE( FJ

11、R,_ ); PUSH(p)；RDL:=0; 算法设计： 设当前四元式 q:( do B _ _ ) 设当前四元式 q:( we _ _ _ )(3) 返填转向地址： POP(p);BACK(p,p+2)跳转到 p去SEM栈顶地址弹到p中(接前页) 若 RDV=X 且 X(y) 则 CODE( ST R,X ; ); (4) POP(p) ;(5) CODE(JMP _, p );(2) RDL:=0;9.3 一个简单代码生成器的实现开始预处理取下一基本块取到了变量活跃信息生成取下一四元式：q基本块出口结束结束处理释放寄存器编写 目标指令yynn包括划分基本块 主控程序 OBJp QTqBSE

12、MRDL 表达式与赋值四元式【例9.8】设有赋值语句（四元式序列）：x=a*(a+b-d)；a=(a+b)/2; y=5;目标代码生成示例：(* a(n) t2(n) x(y)(+ a(y) b(y) t1(y)(- t1(y) d(y)t2(y)(/ t1(n) 2 a(y)(:= 5 _ y(y)ST R,t1 SUB R,dt1LD R,a ADD R,bt2MUL R,axDIV R,2a9ST R,ayST R,x LD R,t1 基本块出口11ST R,y10LD R,5t1t2xay释放寄存器！ 条件语句目标代码生成示例：【例9.9】单寄存器下条件语句目标代码生成：如：if(ab

13、)x=(a+b)*c;else x=5-a*b; OBJp QUATqBSEMRDL( a(y) b(y) t1(y)(if t1(n) _ _ )(+ a(y) b(y) t2(y)(* t2(n) c(y) x(y)(el _ _ _ )(* a(y) b(y) t3(y)(- 5 t3(y) x(y)(ie _ _ _ )FJ R,?t1LD R,at2LD R,a ADD R,bMUL R,cxJMP_,? LD R,a MUL R,bt3 ST R,t3 LD R,51213SUB R,t3x14ST R,x1515ST R,x11GT R,bt1t2xt3x习题：【习题9.4】解释下列词语： 寄存器状态变量 ； 释放寄存器；【习题9.5】简要叙述代码生成器(控制器)的过程；【习题9.6】已知下列语句： if(a+bc) x