目标代码生成器解析

1、实验报告实验课名称： 编译原理实验实验名称： 目标代码生成器实验班级： 学号： 姓名： 时间： 2016-4-30一、问题描述二、数据结构设计 逆波兰式 目标代码 char x1,x2;x2=SEM.top(); coutx2endl; SEM.pop(); x1=SEM.top(); coutx1endl; SEM.pop();代码生成器着重考虑两个问题 : 一是如何使生成的目标代码较短； 另一个是 如何充分利用计算机的寄存器， 减少目标代码中访问存储单元的次数。 这两个问 题直接影响代码的执行速度。其中基本问题 :所有代码生成器都要面对何种中间 代码输入 , (是逆波兰式，四元式，还是三元

2、式？等问题)何种代码做为目标程 序 ,选择适当的代码指令 ,最优的寄存器分配方案 ,和计算顺序等基本问提 ,采用堆栈。*/* 从语义栈中弹出俩个操作数，用于判断与运算/* SEM.top 记得后面要加 (),否则没有值 !*/* 用于调试用的，看栈是怎样变化的 */三、算法设计 代码生成算法： 对每个四元式 : i: A:=B op C ，依次执行：1. 以四元式 : i: A:=B op C 为参数，调用函数过程 GETREG(i: A:=B op C) ， 返回一个寄存器 R，用作存放 A 的寄存器。2. 利用 AVALUEB 和AVALUEC ，确定 B和C现行值的存放位置 B和C。 如

3、果其现行值在寄存器中，则把寄存器取作 B和 C3. 如果 B R，则生成目标代码： LD R, Bop R, C 否则生成目标代码 op R, C 如果 B或 C为 R，则删除 AVALUEB 或 AVALUEC 中的 R。4. 令 AVALUEA=R, RV ALUER=A 。5. 若 B 或 C 的现行值在基本块中不再被引用， 也不是基本块出口之后的活 跃变量，且其现行值在某寄存器 Rk 中，则删除 RVALUERk 中的 B 或 C 以及 AVALUEB 或 AVALUEC 中的 Rk ，使得该寄存器不再为 B 或 C 占用。寄存器分配： GETREG（i: A:=B op C） 返回一

4、个用来存放 A 的值的寄存器（1）如果 B 的现行值在某个寄存器 Ri 中，RVALUERi 中只包含 B，此外， 或者 B 与 A 是同一个标识符，或者 B 的现行值在执行四元式 A:=B op C 之后不 会再引用，则选取 Ri 为所需要的寄存器 R，并转 4；（2 ）如果有尚未分配的寄存器， 则从中选取一个 Ri 为所需要的寄存器 R， 并转 4；（3 ）从已分配的寄存器中选取一个 Ri 为所需要的寄存器 R。最好使得 Ri 满足一下条件：占用 Ri 的变量的值也同时存放在该变量的贮存单元中，或者在基本块中 要在最远的将来才会引用到或不会引用到。对 RVALUERi 中每一变量 M ，如

5、果 M 不是 A，或者如果 M 是 A 又是 C， 但不是 B 并且 B 也不在 RVALUERi 中，则1） 如果 AVALUEM 不包含 M ，则生成 目标代码 ST Ri，M2） 如果 M 是 B，或者 M 是 C 但同时 B 也在 RVALUERi 中，则令 AVALUEM=M ， Ri ，否则令 AVALUEM=M3） 删除 RVALUERi 中的 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 U

6、ADD R0 ，R1R0含有VV在R0中R1 含有 UU 在 R0 中D:=V UADD R0 ，R1R0含有DD在R0中/* 基本输入输出流 */* 运用栈，省去自己再写栈*/程序代码： #include #include #include #include #include using namespace std; /* * 数据结构 * 逆波兰式 目标代码*/int op; /* 操作符对应的数值 */char rt;/* 单个寄存器 */char num;/* 操作数 */ObjType;ObjType OB40; /* 目标代码区 */ int o_pt=0;/* 区指针*/int

7、acc;/* 寄存器标志*/char blexp40;/* 逆波兰式区*/ /* 代码区 */ /* 函数声明 */int isop(char);/* 判断操作符是否是 +-/* */void build(char);/* 根据操作符生成目标代码函数 */void B_O(); /* 生成算法 */char* OpString(int); /* 操作符转化成字符显示 */ void display(); /* 显示目标代码 */ /* 判断当前操作符是否是运算符*如果是返回相应的正数 (3-6)*否则返回零int isop(char ch)if(ch= +)return 3;else if(c

8、h=-)return 4;else if(ch=* )return 5;else if(ch=/ )return 6;elsereturn 0;/* 目标代码生成表生成目标代码目标代码生成表操作符W SEMs-1即x1 SEMs即x2* +-/*X1X20* +-/*X1X2K!=0* +-/*RXs-1* +*XRs* /-XRsacc OBJ * LD R,X1;W R,X2;*T=NEW T;ST R,T;LD R,X1;W R,X2;* W R,X; *W R,X;*T=NEW T;ST R,T;LD R,X;W R,T; */void build(char ch)char x1,x2

9、;x2=SEM.top(); coutx2endl; SEM.pop();x1=SEM.top();coutx1endl;SEM.pop();if(acc=0)OBo_pt.op=1;OBo_pt.rt= R;OBo_pt.num=x1;o_pt+;OBo_pt.op=isop(ch);OBo_pt.rt= R;OBo_pt.num=x2;o_pt+; else if(x1!= R&x2!= R&acc!=0)/* x1和x2都不是寄存器的值，且寄存器被占用/*/*/* 从语义栈中弹出俩个操作数， 用于判断与运算 */ /* SEM.top 记得后面要加 (),否则没有值 ! 用于调试用的，看

10、栈是怎样变化的 */*/如果寄存器没被占用，直接生成运算指令/* 装载SEMS-1即x1 到寄存器 R/* 生成对应的运算指令*/*/*/*/temp+; 生成，/* 申请一个临时变量，在执行代码生成过程中，由操作系统这个是模拟 */OBo_pt.op=2; /* 将寄存器的值移出到临时变量 */ OBo_pt.rt= R ;OBo_pt.num=temp;SEM.pop(); /* 将临时变量压入语义栈 */ SEM.push(temp);o_pt+;OBo_pt.op=1; /* 装载操作数 */ OBo_pt.rt= R;OBo_pt.num=x1; o pt+;OBo_pt.op=is

11、op(ch); /* 生成运算指令 */OBo_pt.rt= R;OBo_pt.num=x2;o_pt+;else if(x1= R&x2!= R&acc=(s-1)/* SEMs-1即x1为寄存器的值而 x2是 操作数且 acc为s-1，说明寄存器现在的值为 x1 */ OBo_pt.op=isop(ch); /* 直接生成运算指令，因为此时的寄存器中已经存在 一个操作数 */OBo_pt.rt= R;OBo_pt.num=x2; o_pt+;else if(x1!= R&x2= R&acc=s&(isop(ch)=3|isop(ch)=5) /* 寄存器的值在 SEMs 即x2，如果操作符

12、为 +* */* 直接生成运算指令 */OBo_pt.op=isop(ch); OBo_pt.rt= R; OBo_pt.num=x1; o_pt+;else if(x1!= R&x2= R&acc=s&(isop(ch)=4|isop(ch)=6) /* 如果是- /，则需要调换一下位置 */ temp+; OBo_pt.op=2; OBo_pt.rt= R; OBo_pt.num=temp; o_pt+;OBo_pt.op=1; OBo_pt.rt= R; OBo_pt.num=x1; o_pt+;OBo_pt.op=isop(ch); OBo_pt.rt= R; OBo_pt.num=t

13、emp; o_pt+; else/*/*生成临时变量，用于存储下寄存器值/* 不需要压栈，因为马上就要用到/* 装载 x1如寄存器 */* 利用临时变量生成运算指令出错处理 */*/*/*/ cout”不符合目标代码生成条件，出错 ! ”endl; exit(0);SEM.push(R); /* 将寄存器 R压栈，用于下次判断，而不是寄存器的值*/s-;return;/* 生成算法 */void B_O()int i=0;/* 置初始值 s=0， acc=0，i=0 */char ch; /* 当前处理字符 */ s=0; /* s 为栈顶指示 */ acc=0;while(blexpi!=

14、0) /* 逆波兰式区还没处理完 */ ch=blexpi+; /* 取当前处理字符 */ if(isalnum(ch) /* 是操作数，入栈 */ SEM.push(ch);s+;else if(isop(ch) /* 是操作符，生成指令 */build(ch);acc=s; /* acc标志到栈顶，因为 R入栈了，指示 R的位置用，是个技巧 */ else /* 字符不符合要求，出错处理 */ cout”逆波兰式内字符有错 ! ”endl;exit(0);/* 将操作指令的数值转换成相应的字符串 */char* OpString(int i) switch(i)case 1: return

15、 “ LD”;case 2: return “ ST”;case 3:return“ADD”;case 4:return“SUB”;case 5:return“MUL”;case 6:return“DIV”;default:cout”操作符有错 ! ”endl;exit(0);/* 显示目标代码 */void display()int i;cout”= 目标代码 = ”endl; for(i=0;io_pt;i+)coutOpString(OBi.op) t ”OBi.rt ” , ” OBi.numendl;int main()cout”逆波兰式生成目标代码 ”endl;cout”请输入逆波兰式： ”endl; gets(blexp);B_O();display();return 1;四、界面设计 程序包含输入提示功能和输出提示功能。五、运行测试与分析 (1)运行程序，显示提示，如图 1.2 所示。图 1.2 启动界面2）数据结果输出。如图 1.3 所示。图 1.3 数据结果输出界面六、实验收获与思考在设计的时候，我在网络中搜索了一些有用的资源。 寄存器描述数组 RVALU，E 用来动态记录各寄存器的使用信息， RVALUER=A,B，同时，变量地址描述数 组 AVALU，E 动态记录各变量现行值的存放位置， AVALU