目标代码生成器

1、实验报告实验课名称：编译原理实验实验名称：目标代码生成器实验班级：学号：姓名：时间：2016-4-30一、问题描述 代码生成器着重考虑两个问题: 一是如何使生成的目标代码较短；另一个是如何充分利用计算机的寄存器，减少目标代码中访问存储单元的次数。这两个问题直接影响代码的执行速度。其中基本问题:所有代码生成器都要面对何种中间代码输入, （是逆波兰式，四元式，还是三元式？等问题）何种代码做为目标程序,选择适当的代码指令,最优的寄存器分配方案,和计算顺序等基本问提二、数据结构设计逆波兰式è 目标代码 ,采用堆栈。char x1,x2; /* 从语义栈中弹出俩个操作数，用于判断与运算 */

2、x2=SEM.top(); /* SEM.top 记得后面要加(),否则没有值! */ cout<<x2<<endl; /* 用于调试用的，看栈是怎样变化的 */ SEM.pop(); x1=SEM.top(); cout<<x1<<endl; SEM.pop();三、算法设计代码生成算法：对每个四元式: i: A:=B op C，依次执行： 1. 以四元式: i: A:=B op C 为参数，调用函数过程GETREG(i: A:=B op C)，返回一个寄存器R，用作存放A的寄存器。 2. 利用AVALUEB和AVALUEC，确定B和C现行值的

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

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

5、 ST Ri，M2) 如果M是B，或者M是C但同时B也在RVALUERi中，则令AVALUEM=M， Ri ，否则令AVALUEM=M3) 删除RVALUERi中的M（4） 给出R，返回。 中间代码目标代码RVALUEAVALUET:=ABLD R0，AR0含有TT在R0中SUB R0，BU:=ACLD R1，AR0含有TT在R0中SUB R1，CR1含有UU在R1中V:=TUADD R0，R1R0含有VV在R0中R1含有UU在R0中D:=VUADD R0，R1R0含有DD在R0中分配操作寄存器R:GETREG（i:A:=B OP C)取B,C现行值存放的位置B，CB：=AVALUEBC：=A

6、VALUECB=R？生成目标代码Op R,C生成目标代码LD R，BOP R,Cyesno图1.1 设计流程图程序代码：#include<iostream> /* 基本输入输出流 */#include<stack> /* 运用栈，省去自己再写栈 */#include <ctype.h>#include<stdio.h>#include <cstdlib>using namespace std;/* 数据结构 * 逆波兰式è 目标代码 */* 目标代码指令：LD，ST，ADD，SUB，MUL，DIV * 相应的数值 ：1， 2

7、， 3， 4， 5， 6 * 数据段开始：设置为a-z；单个寄存器 * acc为寄存器标志：为0表示为空，非0，被占用*/char temp=a-1; /* 临时变量a-z */stack<char> SEM; /* 语义栈 */int s; /* 栈指针 */typedef struct int op; /* 操作符对应的数值 */ char rt; /* 单个寄存器 */ char num; /* 操作数 */ObjType;ObjType OB40; /* 目标代码区 */int o_pt=0; /* 区指针 */int acc; /* 寄存器标志 */char blexp4

8、0; /* 逆波兰式区 */* 代码区 */* 函数声明 */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(ch=-) return 4; else i

9、f(ch=*) return 5; else if(ch=/) return 6; else return 0;/* 目标代码生成表生成目标代码 */*目标代码生成表* 操作符W SEMs-1即x1 SEMs即x2 acc OBJ * +-/* X1 X2 0 LD R,X1;W R,X2; * +-/* X1 X2 K!=0 T=NEW T;ST R,T;LD R,X1;W R,X2;* +-/* R X s-1 W R,X; * +* X R s W R,X; * /- X R s T=NEW T;ST R,T;LD R,X;W R,T; */void build(char ch) cha

10、r x1,x2; /* 从语义栈中弹出俩个操作数，用于判断与运算 */ x2=SEM.top(); /* SEM.top 记得后面要加(),否则没有值! */ cout<<x2<<endl; /* 用于调试用的，看栈是怎样变化的 */ SEM.pop(); x1=SEM.top(); cout<<x1<<endl; SEM.pop(); if(acc=0) /* 如果寄存器没被占用，直接生成运算指令 */ OBo_pt.op=1; /* 装载SEMS-1即x1 到寄存器R */ OBo_pt.rt=R; OBo_pt.num=x1; o_pt+;

11、 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都不是寄存器的值，且寄存器被占用 */ temp+; /* 申请一个临时变量，在执行代码生成过程中，由操作系统生成，这个是模拟 */ OBo_pt.op=2; /* 将寄存器的值移出到临时变量 */ OBo_pt.rt=R; OBo_pt.num=temp; SEM.pop(); /* 将临时变量压入语义栈 */ SEM.push(temp);

12、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=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; OB

13、o_pt.num=x2; o_pt+; else if(x1!=R&&x2=R&&acc=s&&(isop(ch)=3|isop(ch)=5)/* 寄存器的值在SEMs即x2，如果操作符为+* */ 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+; /

14、* 生成临时变量，用于存储下寄存器值 */ OBo_pt.op=2; OBo_pt.rt=R; /* 不需要压栈，因为马上就要用到 */ OBo_pt.num=temp; o_pt+; OBo_pt.op=1; /* 装载x1如寄存器 */ OBo_pt.rt=R; OBo_pt.num=x1; o_pt+; OBo_pt.op=isop(ch); /* 利用临时变量生成运算指令 */ OBo_pt.rt=R; OBo_pt.num=temp; o_pt+; else /* 出错处理 */ cout<<”不符合目标代码生成条件，出错!”<<endl; exit(0);

15、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!=0) /* 逆波兰式区还没处理完 */ ch=blexpi+; /* 取当前处理字符 */ if(isalnum(ch) /* 是操作数，入栈 */ SEM.push(ch); s+; else if(isop(ch) /* 是操作符，生成指令 */ bui

16、ld(ch); acc=s; /* acc标志到栈顶，因为R入栈了，指示R的位置用，是个技巧 */ else /* 字符不符合要求，出错处理 */ cout<<”逆波兰式内字符有错!”<<endl; exit(0); /*l 将操作指令的数值转换成相应的字符串 */char* OpString(int i) switch(i) case 1: return “LD”; case 2: return “ST”; case 3: return “ADD”; case 4: return “SUB”; case 5: return “MUL”; case 6: return

17、“DIV”; default: cout<<”操作符有错!”<<endl; exit(0); /* 显示目标代码 */void display() int i; cout<<”=目标代码=”<<endl; for(i=0;i<o_pt;i+) cout<<OpString(OBi.op)<<”t”<<OBi.rt<<”,”<<OBi.num<<endl; int main() cout<<”逆波兰式生成目标代码”<<endl; cout<<”请输入逆波兰式：”<<endl; gets(blexp); B_O(); display(); return 1;四、界面设计 程