目标代码生成器教程.doc

实验报告 实验课名称：编译原理实验实验名称：目标代码生成器实验班级：学号：姓名：时间：2016-4-30 一、问题描述 代码生成器着重考虑两个问题: 一是如何使生成的目标代码较短；另一个是如何充分利用计算机的寄存器，减少目标代码中访问存储单元的次数。这两个问题直接影响代码的执行速度。其中基本问题:所有代码生成器都要面对何种中间代码输入, （是逆波兰式，四元式，还是三元式？等问题）何种代码做为目标程序,选择适当的代码指令,最优的寄存器分配方案,和计算顺序等基本问提 二、数据结构设计 逆波兰式? 目标代码 ,采用堆栈。 char x1,x2; /* 从语义栈中弹出俩个操作数，用于判断与运算 */ x2=SEM.top(); /* SEM.top 记得后面要加(),否则没有值!!! */ coutx2endl; /* 用于调试用的，看栈是怎样变化的 */ SEM.pop(); x1=SEM.top(); coutx1endl; SEM.pop(); 三、算法设计 代码生成算法： 对每个四元式: i: A:=B op C，依次执行： 1. 以四元式: i: A:=B op C 为参数，调用函数过程GETREG(i: A:=B op C)，返回一个寄存器R，用作存放A的寄存器。 2. 利用AVALUE[B]和AVALUE[C]，确定B和C现行值的存放位置B’和C’。如果其现行值在寄存器中，则把寄存器取作B’和C’ 3. 如果B’≠R，则生成目标代码： LD R, B’ op R, C’ 否则生成目标代码 op R, C’ 如果B’或C’为R，则删除AVALUE[B]或AVALUE[C]中的R。 4. 令AVALUE[A]={R}, RVALUE[R]={A}。 5. 若B或C的现行值在基本块中不再被引用，也不是基本块出口之后的活跃变量，且其现行值在某寄存器Rk中，则删除RVALUE[Rk]中的B或C以及AVALUE[B]或AVALUE[C] 中的Rk ，使得该寄存器不再为B或C占用。 寄存器分配：GETREG(i: A:=B op C) 返回一个用来存放A的值的寄存器 （1） 如果B的现行值在某个寄存器Ri中，RVALUE[Ri]中只包含B，此外，或者B与A是同一个标识符，或者B的现行值在执行四元式A:=B op C之后不会再引用，则选取Ri为所需要的寄存器R，并转4； （2 ） 如果有尚未分配的寄存器，则从中选取一个Ri为所需要的寄存器R，并转4； （3 ）从已分配的寄存器中选取一个Ri为所需要的寄存器R。最好使得Ri满足一下条件： 占用Ri的变量的值也同时存放在该变量的贮存单元中，或者在基本块中要在最远的将来才会引用到或不会引用到。 对RVALUE[Ri]中每一变量M，如果M不是A，或者如果M是A又是C，但不是B并且B也不在RVALUE[Ri]中，则 1) 如果AVALUE[M]不包含M，则生成 目标代码 ST Ri，M 2) 如果M是B，或者M是C但同时B也在RVALUE[Ri]中，则令AVALUE[M]={M， Ri} ，否则令AVALUE[M]={M} 3) 删除RVALUE[Ri]中的M （4） 给出R，返回。 中间代码目标代码RVALUEAVALUET:=A－BLD R0，AR0含有TT在R0中SUB R0，BU:=A－CLD R1，AR0含有TT在R0中SUB R1，CR1含有UU在R1中V:=T＋UADD R0，R1R0含有VV在R0中R1含有UU在R0中D:=V＋UADD R0，R1R0含有DD在R0中 分配操作寄存器 R:GETREG（i:A:=B OP C) 取B,C现行值存放的位置B′，C′ B′：=AVALUE[B] C′：=AVALUE[C] B′=R？ 生成目标代码 Op R,C′ 生成目标代码 LD R，B′ OP R,C′ yes no 图1.1 设计流程图 程序代码： #includeiostream /* 基本输入输出流 */ #includestack /* 运用栈，省去自己再写栈 */ #include ctype.h #includestdio.h #include cstdlib using namespace std; /*************************************** * 数据结构 *