编译器的设计与实现PPT课件2.ppt

编译器的设计与实现,ppt制作： 张 云 时间：2008-03,回顾,语言设计 简单的c 目标机器建模 编译系统框架 一些主要的数据结构（词法节点，语法节点，中间表示，目标代码） 目标代码的运行,本节内容描述,目标代码的生成：如何从中间表示（语法树）得到目标代码呢？ 示例： 声明语句 赋值语句 if语句 while语句 函数调用与返回,问题,要处理什么样的c代码？ 对应的语法树结构（中间表示）是什么？ 对应什么样的asm代码 ？ 如何生成目标代码？具体实现,编译器前端,编译器后端,源程序,中间表示,目标代码,*.c,*.asm,语法树,要处理什么样的c代码？,简化的c,函数调用与返回,if语句,while语句,赋值语句,表达式,数组,声明语句,控制语句,示例,int f1(int x,int y) if(xy) x = x+y; x = x*2; return x; void main() int a; int b; a = 5; b = a + 2; a = f1(a,b); return; ,赋值语句,示例： int p ; p = 1; int a3; a2=7;,对虚拟机中memory产生的影响,对应中间形式,a,1,b2,7,对应的asm代码,p = 1; 生成代码如下： mov ax,1 mov p的地址，ax,a2=7; 生成代码如下： mov ax,7 mov a2的地址, ax,问题： 如何知道变量p的地址？如何知道数组元素a2的地址？,举例,举例： void widget(int x, int y) int a, b; a = x+y; b = x-y; ,bp,sp,相对位置！,对于例子 int p ; p = 1;,在遇到int p;语句的时候，建立对应的符号表项，如图： 遇到赋值语句p=1;以后，查找符号表中名称为p的项，找到p的相对地址1，因此，p的地址是： bp+1+1 同样，可以得到数组元素a2的地址 a的地址 = bp+1+2 a2的地址 bp+1+2+2,p,pc,a0,old_bp,a1,a2,bp,0,+1,+2,+3,+4,+5,asm代码,p = 1; （ 假定p的相对地址为1） 生成代码如下： mov ax,1 mov bp+1+1，ax,a2=7; （ 假定a的相对地址为2） 生成代码如下： mov ax,7 mov bp+1+2+2，ax,赋值语句具体实现,扫描语法树的过程中，遇到赋值节点,赋值节点,p,1,switch(tn.ntype) case nodetype.assignstm: if(tn.child0.ntype=nodetype.varid） /根据变量名查找符号表，取出变量的地址 varaddr=varprocess(tn.child0); /表达式语句处理；最终结果存放到ax中 expprocess(tn.child1); code tmpcode = this.nextcode(); tmpcode.op = “mov“; tmpcode.arg1 = varaddr; tmpcode.arg2 = “ax“; break; ,/查找符号表，找出变量的相对地址，构造变量的地址，返回 string varprocess(treenode tn) string varaddr; /局部变量？参数变量？全局变量？注意区分！ varinfo varsym = getvar(symtable, tn); if(varsym!=null) varaddr=“bp+1+”+varsym.rva+”; return varaddr; ,void expprocess(treenode tn) switch(tn.ntype) case nodetype.varid: varaddr=varprocess(tn); tmpcode = nextcode(); tmpcode.op = “mov“; tmpcode.arg1 = “ax“; tmpcode.arg2 = varaddr; break; case nodetype.constid: tmpcode = nextcode(); tmpcode.op = “mov“; tmpcode.arg1 = “ax“; tmpcode.arg2 = tn.nodestr; break; case nodetype.add: expprocess(tn.child1); tmpcode = nextcode(); tmpcode.op = “mov“; tmpcode.arg1 = “bx“; tmpcode.arg2 = “ax”; expprocess(tn.child0); tmpcode = nextcode(); tmpcode.op = “add“; tmpcode.arg1 = “ax“; tmpcode.arg2 = “bx”; break; case nodetype.funcall: funcall(tn); break; case nodetype.req: break; default: break; ,表达式！,mov ax, num,mov ax, varaddr,表达式,a,2,case nodetype.add: expprocess(tn.child1); tmpcode = nextcode(); tmpcode.op = “mov“; tmpcode.arg1 = “bx“; tmpcode.arg2 = “ax”; expprocess(tn.child0); tmpcode = nextcode(); tmpcode.op = “add“; tmpcode.arg1 = “ax“; tmpcode.arg2 = “bx”; break; ,借助寄存器ax来传递值,mov ax, 2 mov bx, ax mov ax, a add ax, bx,=,p,(a*b)+(c*d)如何处理?,*,a,b,*,c,d,if语句,int a,b; b = 10; a = b/2; if ( a1) a = 0; else b=1; a= a + b;,b = 10; a = b/2;,if语句,if ( 条件语句) then部分语句 else else部分语句 其它语句,if语句,条件部分 语句,then部分 语句,else部分 语句,child0,child1,child2,jxx thenpart jmp elsepart,thenpart: . jmp out,将条件部分的 表达式值 放入ax,bx,elsepart: ,out:,if语句具体实现,扫描语法树的过程中，遇到if节点orifelse节点,switch(tn.ntype) case nodetype.ifstm: ifstm(tn); break; case nodetype.ifelsestm: ifelsestm(tn); break; ,ifstm,void ifstm(treenode tn) int tmpcodep=this.curcodep; switch(tn.child0.ntype) /处理条件部分的语句，生成相应的中间代码 /jxx thenpart部分 code tmpcode = this.nextcode(); /跳转指令；跳转到条件为假的位置 tmpcode.op = “jmp“; tmpcode.arg1 = “0“; tmpcodep = this.curcodep; this.stmtprocess(tn.child1); /处理truepart语句部分，生成相应的中间代码 /(code)codelisttmpcodep).label+=“true_part:“; /修改假跳转的出口地址 0-curcodep 返填操作！ (code)codelisttmpcodep-1).arg1 = this.curcodep.tostring(); ,ifstm,条件部分,then部分,child0,child1,ifelsestm,void ifstm(treenode tn) int tmpcodep=this.curcodep; switch(tn.child0.ntype) /处理条件部分的语句，生成相应的中间代码 code tmpcode = this.nextcode(); /跳转指令；跳转到条件为假的位置 tmpcode.op = “jmp“; tmpcode.arg1 = “0“; int falsepart = this.curcodep-1; /处理truepart语句部分，生成相应的中间代码 this.stmtprocess(tn.child1); tmpcode = this.nextcode(); /跳转指令；跳转到出口位置 tmpcode.op = “jmp“; tmpcode.arg1 = “0“; int outcodep = this.curcodep-1;,ifelsestm,条件部分,then部分,else部分,child0,child1,child2,ifelsestm,/修改前面的假跳转的地址，跳转到当前位置 返填 (code)codelistfalsepart).arg1 = this.curcodep.tostring(); /处理falsepart语句部分，生成相应的中间代码 this.stmtprocess(tn.child2); /修改前面 处理完thenpart部分后的无条件跳转语句，跳转到当前位置 (code)codelistoutcodep).arg1 = this.curcodep.tostring(); ,ifelsestm,条件部分,then部分,else部分,child0,child1,child2,while语句,int a = 10; while (a1) a-; a = 1;,while语句,jxx bodypart jmp out,bodypart: . jmp cond,cond: 将条件部分的 表达式值 放入ax,bx,out: .,while (条件语句) body部分语句 其它语句,while语句,cond部分,body部分,child0,child1,while语句具体实现,扫描语法树的过程中，遇到while节点,switch(tn.ntype) case nodetype. whilestm: whilestm (tn); break; ,whilestm,void whilestm(treenode tn) int condloc = this.curcodep; /记录条件部分的入口位置switch(tn.child0.ntype) /处理条件部分的语句，生成相应的中间代码 /生成无条件跳转语句，跳转到整个while语句出口处 code tmpcode = this.nextcode(); tmpcode.op = “jmp“; tmpcode.arg1 = “0“; int outcodep = this.curcodep-1; this.stmtprocess(tn.child1); /处理循环语句部分，生成相应的中间代码 /生成无条件跳转语句，跳转到整个while语句条件判断处；用于循环执行 tmpcode = this.nextcode(); tmpcode.op = “jmp“; tmpcode.arg1 = condloc.tostring /修改前面 条件为假时候的无条件跳转语句，跳转到当前位置 (code)codelistoutcodep).arg1 = this.curcodep.tostring(); ,whilestm,条件部分,then部分,child0,child1,while语句实现,while节点,a,5,赋值节点,a,+,1,a,while(a5) a=a+1; output(a);,condloc 12；,true,真,假,记录需要返填outcodep的位置,目标代码生成,赋值语句 if语句 while语句 函数目标代码生成以及函数调用语句,函数目标代码生成,函数定义,在符号表中 记录函数信息,生成函数 目标代码,问题： 需要记录哪些函数信息？ 函数目标代码是什么样子的？,需要记录哪些函数信息？,函数名 返回类型 局部变量列表 参数列表 函数入口地址 函数所需栈大小,函数所需栈的大小怎么计算？,如何得到函数入口地址？,函数信息,函数栈的设计,函数,函数栈 or 运行时 活动记录,用来保存函数中出现的局部变量和函数体中表达式计算过程中用到的临时变量,sp,bp,未使用 的空间,函数栈的大小：局部变量的所占空间2,序言prologue ： 创建并初始化栈桢,/函数代码开始；记录当前的代码位置，函数的入口地址 _funname proc near push bp ; 把原来的栈桢指针保存到栈上 mov bp, sp ; 激活新的栈桢 add sp, x ; 加上一个数字，让sp指向栈桢的末尾,函数所需空间大小 如何计算？,尾声epilogue ：清除栈桢,mov sp, bp pop bp ; 激活主调函数的栈桢 ret ; 返回主调函数 _funname endp /函数代码结束,实现（函数信息）,函数名 局部变量列表 参数列表 返回类型 函数入口地址 函数所需栈大小,public class funinfo public string fun_name; public string ret_type; /参数变量所占空间的大小 public int para_size; /用来列出所有的参数变量的位置 public hashtable paravar_list; public int local_size; public hashtable localvar_list; public int entry_addr; /入口地址 ,设置函数入口地址,void codegen(treenode root, symtable st) treenode tn=root; funcsymbol fs; while(tn!=null) switch(tn.nodetype) case nodetype.fundecl: fs=st.fetchfs(tn.nodestr); /取得当前要处理函数的符号表 fs.entry_addr = curcp; /得到函数的入口地址！ funprocess(tn, fs); /生成函数目标代码 break; tn = tn.sibling; ,函数代码生成,void funprocess(treenode root,funcsymbol fs) prologue(fs); for(int i=0;itn.child.length;i+) stmtprocess(tn.childi); epilogue(fs); ,函数定义,语句,语句,sibling,参数2,参数1,void stmtprocess(treenode tn) while(tn!=null) switch(tn.ntype) case nodetype.assignstm: assignstm(tn); break; case nodetype.ifstm: ifstm(tn); break; case nodetype.whilestm: whilestm(tn); break; case nodetype.funcall: funcall(tn); break; tn = tn.sibling; ,函数目标代码,产生的代码： _name proc near push bp mov bp, sp add sp, xx mov sp, bp pop bp ret _name endp,同时会将 函数的入口地址 存放到符号表中,示例目标代码,line0: call near ptr _main line1: halt line2:f1: f1 proc near line3: push bp line4: mov bp sp line5: add sp 3 line6: mov ax bp-1-0 line7: mov bx ax line8: mov ax bp-1-1 line9: add ax bx line 10: mov bp+2+0 ax line11: mov sp bp line12: pop bp line13: ret line14: f1 endp,int f1(int x,int y) int z; z = x+y; return z; void main() int a; int b; a = 5; b = a + 2; a = f1(a,b); return; ,示例目标代码,line15: main: main proc near line16: push bp line17: mov bp sp line18: add sp 4 line19: mov ax 5 line25: mov ax bp+2+1 line26: push ax line27: mov ax bp+2+0 line28: push ax line29: call near ptr _f1 /2 line30: sub sp 2 line31: mov sp bp line32: pop bp line33: ret line34: main endp,int f1(int x,int y) int z; z = x+y; return z; void main() int a; int b; a = 5; b = a + 2; a = f1(a,b); return; ,函数的调用与返回,函数的进入 函数的退出/返回,示例,函数调用,void h() f(a,b); void main() h(); ,int f(int x, int y) ,main,h,f,函数调用主要体现在函数运行栈的变化上； 需要对主调函数的运行环境进行保存； 将指针指向正确的位置上；,思考：,参数入栈次序问题 函数调用与返回时，由谁来负责参数入栈以及清除栈中参数所占空间？,函数调用,进入被调函数,退出函数,主调函数中： 参数入栈 call 被调函数名 参数退栈 继续执行后续代码 ,被调函数体： _funname proc near push bp mov bp, sp ret 被调函数代码 执行结束后，返回,函数进入,参数入栈 call 函数名,将参数放入ax push ax 重复将所有参数入栈,从符号表中找到函数项获取函数信息： （所需栈大小、函数入口地址） 当前函数栈底指针入栈（bp） 返回地址（pc）入栈 移动bp到sp-2 移动sp到sp+函数大小 pc=函数地址,示例目标代码,line0: call near ptr _main line1: halt line2:f1: f1 proc near line3: push bp line4: mov bp sp line5: add sp 3 line6: mov ax bp-1-0 line7: mov bx ax line8: mov ax bp-1-1 line9: add ax bx line 10: mov bp+2+0 ax line11: mov sp bp line12: pop bp line13: ret line14: f1 endp,int f1(int x,int y) int z; z = x+y; return z; void main() int a; int b; a = 5; b = a + 2; a = f1(a,b); return; ,示例目标代码,line15: main: main proc near line16: push bp line17: mov bp sp line18: add sp 4 line19: mov ax 5 line25: mov ax bp+2+1 line26: push ax line27: mov ax bp+2+0 line28: push ax line29: call near ptr _f1 /2 line30: sub sp 2 line31: mov sp bp line32: pop bp line33: ret line34: main endp,int f1(int x,int y) int z; z = x+y; return z; void main() int a; int b; a = 5; b = a + 2; a = f1(a,b); return; ,void run() init(); 装入 symtable and asmcode; while(1) switch(codepc.op) case “push“: push(operand1); break; case “pop“: pop(operand1); break; case “mov“: mov(operand1,operand2);break; case “add“: add(operand1,operand2);break; case “jmp“: jmp(operand1); break; case “call“: call(operand2); break; case “ret“: ret(); break; case “halt“: halt(); break; default: break; ,void call(string arg) this.stackcpu.sp = cpu.bp;/原bp/当前函数栈底 cpu.bp = cpu.sp; this.stackcpu.bp+1=cpu.pc;/返回地址 cpu.sp+=2; /从metadatafield中取得函数的入口地址 string funname=null; int i = arg.indexof(_); funname = arg.substring(i+1); int entryaddr; funinfo fs = sr.getfs(funname,sr.funsymtable); /assert(fs!=null); entryaddr = fs.entry_addr; cpu.pc = convert.toint32(entryaddr);/修改pc指针 ,函数退出,ret 如需要返回值则将返回值 放入固定位置,计算返回值 mov 返回值，ax,从栈中取出返回地址 pc=返回地址 栈顶退到当前栈底 从栈底中取出旧栈底赋给bp 栈顶按照参数个数回到旧栈顶,void run() init(); 装入 symtable and asmcode; while(1) switch(codepc.op) case “push“: push(operand1); break; case “pop“: pop(operand1); break; case “mov“: mov(operand1,operand2);break; case “add“: add(operand1,operand2);break; case “jmp“: jmp(operand1); break; case “call“: call(operand2); break; case “ret“: ret(); break; case “halt“: halt(); break; default: break; ,void ret() cpu.pc = this.stackcpu.bp+1; cpu.sp = cpu.bp; cpu.bp = this.stackcpu.sp; ,实现,f1 函数调用节点,a,a,b,eg: a = f1(a, b);,函数调用中间表示,实现,void stmtprocess(treenode tn) while(tn!=null) switch(tn.ntype) case nodetype.assignstm: assignstm(tn); break; case nodetype.ifstm: ifstm(tn); break; case nodetype.whilestm: whilestm(tn); break; case nodetype.funcall: funcall(tn); break; tn = tn.sibling; ,函数调用 代码生成,void funcall(treenode tn) treenode argtn = tn.child0; arraylist arglist = null; /处理参数：将参数由右向左依次入栈 while(argtn!=null) arglist.add(argtn); argtn=argtn.sibling; for(int i=arglist.count;i0;i-) argtn = (treenode)arglisti-1; expprocess(argtn); asmcode tmpcode = nextcode(); tmpcode.op = “push”; tmpcode.arg1 = “ax”; ,f1 函数调用节点,arg1,arg2,/生成函数调用语句 tmpcode = nextcode(); tmpcode.op = “call”; tmpcode.arg1 = “near proc”; tmpcode.arg2 = “_”+tn.nodestr; /栈的清理；释放参数所占的栈空间 if(arglist!=null) tmpcode = nextcode(); tmpcode.op = “sub”; tmpcode.arg1 = “sp”; tmpcode.arg2 = arglist.count; ,产生的代码： mov ax 2 push ax mov ax 3 push ax call near proc _f1 sub sp 2 ,一个完整的例子,line0: call near ptr _main line1: halt line2:f1: f1 proc near line3: add sp 3 line10: mov ax bp-1-1 line11: mov bx ax line12: mov ax bp-1-0 line13:add ax bx line13: mov bp+2+0 ax line14: ret line15: f1 endp,line16: main: main proc near line17: add sp 4 line23: mov ax bp+2+1 line24: push ax line25: mov ax bp+2+0