编译器的设计与实现1.ppt

编译器的设计与实现,ppt制作： 张 云 时间：2008-03,课程描述,目标：编译器的设计与实现 方法： 给定语言特性，限定目标机器模型，实现该语言的编译器； 添加新的语言特性，对编译器做相应的修改。,一个简单的编译器的设计与实现,语言的设计 目标机器建模 编译器的实现,1 语言,一个用于教学的编译运行环境,简化的c,函数调用,if语句,while语句,赋值语句,表达式,数组,声明语句,控制语句,1.1简单的c 语言的文法,program var-declaration | fun-declaration var-declaration int id , id /可以声明多个变量 fun-declaration ( int | void ) id( params ) compound-stmt params int id , int id | void | empty compound-stmt var-declaration statement statement expression-stmtcompound-stmt if-stmt while-stmt | return-stmt expression-stmt expression ; if-stmt if( expression ) statement else statement while-stmt while( expression ) statement return-stmt return expression ;,expression id = expression | simple-expression simple-expression additive-expression relop additive-expression relop | = | = | != additive-expression term ( + | - ) term term factor ( * | / ) factor factor ( expression )| id | call | num call id( args ) args expression , expression | empty,1.2程序举例,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; ,1.3进一步的扩展,简化的c+,简单的c,对象,继承,多态,异常处理,垃圾回收,2 目标机器建模,处理器 存储器 指令系统,2.1 cpu的设计,数据结构如下： public struct processor public int ax; / 累加器ax public int bx; / bx public int cx; public int pc; / 程序计数器 public int bp; / 基址指针bp public int sp; / 堆栈指针sp public int hp; public int zf; /标志flag； /其它 详细内容将会在以后解释,2.2存储器组织,线性组织， mem0memmaxaddr,0,1,2,3,maxaddr,低,高,功能分区： 代码区 元数据区 栈（运行时存储空间） 堆 假定每一个功能存储区的地址都是由0开始,2.3目标机器模型,代码区 存储代码,堆 存储动态分配空间,栈 存储函数运行栈,cpu（寄存器组）,元数据 存放符号表等运行信息,简单的栈式存储分配,数据结构,class vm processor cpu; /虚拟机的cpu symtable；/符号表 datatable code; /代码存储空间 int stack = new intstacksize; /栈 int heap = new intheapsize; /堆 ,2.4指令系统,目标程序形式有以下几种： 绝对机器代码 可再定位机器代码 汇编语言程序 我们采用汇编语言的形式表示目标代码 格式如下：,指令集举例,mov ax, bx ;bx ax mov addr, ax ;ax addr所表示的地址空间中 jmp 21 ;无条件跳转指令 cmp ax, bx ;比较ax与bx寄存器的值,设置标志寄存器 jz 21 ;根据标志寄存器的值有条件跳转 ,目标代码数据结构,根据目标代码的结构，不难设计它的数据结构如下： class code private string op; /操作码 private string arg1; /操作数 private string arg2; /操作数 ,大纲,语言 目标机器 编译器的实现,3 编译程序的实现,编译器的各个阶段的回顾 涉及的主要数据结构 具体实现,简单回顾编译的各个阶段,源程序 字符流,目标代码,虚拟机执行,扫描器（词法分析）,分析器（语法分析）,单词流,语法单位,语义分析和中间代码生成,目标代码生成,抽象语法树or 其它中间形式,优化器,符 号 表,示例源代码,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; ,3.1词法分析,任务：输入源程序；扫描、分解字符串，识别出一个个单词（定义符、标识符、运算符、界符、常数）,源程序符号串,词法分析器,单词符号,问题：单词符号是什么？如何表示？,单词符号是什么？,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; ,关键字 标识符 常量 运算符 界符 如何表示单词符号？,如何表示单词符号？,1) 需要对单词分类，每一个识别出来的单词都属于不同的类型 public enum tokentype /关键字 if,else,while,return,void,int, /运算符 + - * / = = != plus,minus,star,slash, lt,lteq,gt,gteq,eq,neq,assign, /界符 ; , ( ) /* */ semi,comma,lparen,rparen,lsquar,rsquar,lbrace,rbrace, lcomment,rcomment, id, /标识符 number, /数字常量 nontoken,error,endfile / 其它 ;,如何表示单词符号？,2) 单词符号的数据结构设计 public class token string str; /单词字符串 tokentype ttype; /单词的类型 int line; /所在行号信息 ,示例,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; ,词法分析结束后，得到如下内容：,词法分析器的实现,gettoken(),语法分析器,返回一个记号,调用,与语法分析器的接口,词法分析 状态转换图,自 动 机 dfa,int f1(int x,int y) if(xy) x = x+y; x = x*2; return x; ,实现代码,class scanner enum scanstate inid,innum,inlteq, ,start,done ; token gettoken() char ch; string str=“”; tokentype toktype; scanstate state = scanstate.start; while(state!=scanstate.done) ch=getnextchar(); switch(state) case scanstate.start: if(isletter(ch) scanstate=scanstate.inid; if(isdigit(ch) scanstate=scanstate.innum; if(ch=) scanstate=scanstate.inlteq; break;,case scanstate. inid: if(!char.isletter(ch) ,3.2语法分析,任务：在词法分析基础上，将单词符号串转化为语法单位（语法范畴）（短语、子句、句子、程序段、程序），并确定整个输入串是否构成语法上正确的程序。,单词符号,语法分析器,语法单位,问题： 1 该语言的语法规则是什么？什么样的程序是语法正确的程序？ 2 语法单位是什么？如何表示？,简单的c 语言的文法,program var-declaration | fun-declaration var-declaration int id , id /可以声明多个变量 fun-declaration ( int | void ) id( params ) compound-stmt params int id , int id | void | empty compound-stmt var-declaration statement statement expression-stmtcompound-stmt if-stmt while-stmt | return-stmt expression-stmt expression ; if-stmt if( expression ) statement else statement while-stmt while( expression ) statement return-stmt return expression ;,expression id = expression | simple-expression simple-expression additive-expression relop additive-expression relop | = | = | != additive-expression term ( + | - ) term term factor ( * | / ) factor factor ( expression )| id | call | num call id( args ) args expression , expression | empty,示例,根据上述文法规则，我们来判断语句if(ab) a = a-b;是否符合语法规则。 语法分析树如下图：,语句if(ab) a = a-b;的语法分析树,if-stmt,if,（,expression,statement,factor,relop,a,simple-expression,additive-expression,=,expression,term,a,id,factor,additive-expression,term,id,b,expression-stmt,;,expression,simple-expression,factor,additive-expression,term,id,b,）,对应的语法分析子程序,if-stmt if( expression ) statement else statement void if_stmt() match(“if”); match(“(”); exp(); match(“)”); statement(); if(curtoken.str=“else”) match(“else”); statement(); ,statement expression-stmt compound-stmt if-stmt while-stmt | return-stmt 对应的递规下降程序如下： void statement() switch(curtoken.str) case “if”: if_stmt(); case “while”: while_stmt(); case “return”: return_stmt(); case “”: comp_stmt(); default: exp_stmt(); ,语法分析树与抽象语法树,语法分析树也称为具体语法树，因为这种树中的一切都是明示的，完全而又具体，显示了如何根据相应上下文无关文法推导出特定的单词序列。在我们知道了一个单词序列为合法之后，后续的编译阶段就不再需要语法分析树上的许多信息了。 因此，语法分析结束以后，一般会将这种语法分析树转换为一棵抽象语法树（又称ast，简称语法树），删除树内部的大部分“人为”结点，并对剩下的结点标注有用的信息。附在特定节点上的标注被称为它的属性。,语句if(ab) a = a-b;的抽象语法树,if,if语句,条件部分 语句,then部分 语句,else部分 语句,if语句的抽象语法树 说明：对于if语句，根节点是if，第一个孩子节点表示条件，第二个孩子节点是条件为真的时候的执行语句，第三个孩子节点是else部分的执行语句（如果有的话）,child0,child1,child2,if-stmt if( expression ) statement else statement,a,b,=,a,-,a,b,3.3抽象语法树与中间表示,在许多编译器里，带标注的语法树就是从前端传递到后端的中间形式，而在另一些编译器里，语义分析器最后可能还要遍历这棵树，生成某种另外的中间形式。 我们将这种语法树作为中间表示，不再对它做一步的转换。,作业1：还有哪些不同的中间表示方法？不同的中间表示方法有什么特点？,抽象语法树 节点表示,函数定义 节点,语句1,语句2,sibling,参数1,同样，对于其它的语法节点，我们可以设计相应的抽象语法树； 例如，对于函数声明节点 fun-declaration ( void | int ) id( params ) compound-stmt 抽象语法树如下：,参数2,sibling,child0,child1,函数名 返回类型,while-stmt while( expression ) statement,while语句,cond部分,body部分,child0,child1,抽象语法树 节点表示,= + - ,id num,id num,表达式： expression id = expression | simple-expression simple-expression additive-expression relop additive-expression relop | = | = | != additive-expression term ( + | - ) term term factor ( * | / ) factor factor ( expression )| id | call | num,程序 program var-declaration | fun-declaration ,全局变量,函数,函数,sibling,sibling,参数列表,child,child,child,root,全局变量声明 函数定义,局部内容,例如： int pi; void add(int x, int y) void main() ,pi,add,main,sibling,sibling,child,child,child,全局变量,示例,f1,x,y,if,=,=,x,main,null,a,b,=,a,b,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; ,x,y,+,x,y,x,*,2,x,return,x,语法分析器的实现,语法树节点的分析 节点类型？,语法树节点设计,/语法树节点类型 public enum nodetype fundecl,vardecl,para, add, sub, mul, div, req, rlt, rgt, rneq, rngt, rnlt, assignstm,ifstm,ifelsestm,elsestm,whilestm,returnstm, funcall, constid, varid, other, error ;,语法树节点设计,public class treenode int lineno; /行号 treenode child = null, null, null, null; /子节点; treenode sibling; /兄弟节点 nodetype ntype; /节点类型 string nodestr; /保存标识符的名称，便于在语法树中显示 string vartype; /用于标明变量类型int char float string rettype; /函数返回类型void int char float /other property info ,语法分析器的实现,class parser token curtoken; void parse() curtoken = getnexttoken(); /取得第一个token treenode root = null; root = program();/递规下降分析！构建语法树，并返回根节点 void match(tokentype expected) if(curtoken.ttype = expected) curtoken=getnexttoken(); else parseerror(); treenode program() token p, q; p = root; while(curtoken.ttype!=tokentype.endfile) if(curtoken.ttype=tokentype.fundecl) q=fun_decl(); if(curtoken.ttype=tokentype.vardecl) q =var_decl(); p.sibling = q; p = p.sibling; return root; ,treenode var_decl() treenode retnode, nextnode, curnode; retnode = curnode; retnode.ntype = curnode.ntype = nodetype.vardecl; while(curtoken.ttype!=tokentype.semi) switch(curtoken.ttype) case tokentype.int: match(tokentype.int); break; case tokentype.id: nextnode.nodestr = curtoken.str; /nextnode.isarray = 0; nextnode.arraysize = 0; 数组？ curnode.sibling = nextnode; curnode = nextnode; match(tokentype.id); break; case tokentype.comma: match(tokentype.comma); break; default: parseerror(); break; match(tokentype.semi); return retnode; ,treenode fun_decl() treenode retnode; retnode.ntype = nodetype. fundecl; while(curtoken.ttype!=tokentype. lparen) switch(curtoken.ttype) case tokentype.int: case tokentype.void: retnode.rettype = curtoken.str; match(curtoken.ttype); break; case tokentype.id: retnode.nodestr = curtoken.str; match(tokentype.id); break; default: parseerror(); break; match(tokentype.lparen); if(token.ttype != tokentype.rparen) /匹配参数列表,第1个子节点 treenode paramsnode = param_list(); retnode.child0 = paramsnode; match(tokentype.rparen); treenode stmtnode = compound_stmt();/函数体，第2个子节点 retode.child1 = stmtnode; return retnode; ,3.4语义分析与符号表,语义分析,紧接在词法分析和语法分析之后，编译程序要做的工作是进行静态语义检查。举例说，它检查并确定： 每个标识符在使用之前是否已有定义； 标识符是否被用在不合适的上下文中； 为子程序调用提供的的数目和类型是否正确； 每个函数里是否至少包含了一个刻画返回值的语句； 等等。 为了支持所需的工作，语义分析器通常构造并维护着一个符号表数据结构，符号表把每个标识符映射到有关它的已知信息。这些信息包括各个标识符的类型信息、内部结构以及作用域等。,符号表,符号表类似于一个字典：它把名字映射到编译器已知的有关信息。,问题： 1 符号表中应该包含哪些内容？（名字？） 2 如何设计符号表？,符号表,函数名,语句1,语句2,sibling,参数1,参数2,sibling,child0,child1,返回类型？ 参数个数？ 局部变量信息？ 其它？,变量名,变量类型？ 是不是数组？ 其它？,符号表 数据结构设计,函数定义 列表,全局变量 列表,函数定义,函数定义,变量定义,变量定义,函数表,函数定义,参数变量列表,局部变量列表,变量表,变量定义,变量名,变量地址,符号表设计变量信息,public enum place global,local, para /varinfo public class varinfo public string var_name; public string var_type; public int isarray; / 0:simplevar 1:array(一维数组) public int arraysize; public int rva; /offset public place place;/参数变量？局部变量？全局变量？ ,符号表设计函数信息,/funinfo public class funinfo public string fun_name; public string ret_type; /0:void 1:int 2:user_defined_type public int para_size; /所有局部变量所占空间的大小； public hashtable paravar_list;/列出所有的参数变量的位置 public int local_size; public hashtable localvar_list; /同上 public int entry_addr; /入口地址 ,符号表的生成,扫描语法树，判断出其中的变量声明节点以及函数定义节点，构建符号表,class symtable hashtable globalsymtable = new hashtable(); /全局变量符号表 hashtable funsymtable = new hashtable();/函数符号表 void buildsymtable(treenode r) while(r!=null) switch(r.ntype) case nodetype.vardecl: /全局变量处理 tmpvarsym = processvar(r); this.globalsymtable.add(r.nodestr,tmpvarsym); break; case nodetype.fundecl: tmpfunsym = processfun(r,null); this.funsymtable.add(r.nodestr,tmpfunsym); break; default: system.console.out.writeline(“undefined declaration“); break; r=r.sibling; ,示例,函数定义 列表,全局变量 列表 null,f1,main,f1,main,参数列表,局部变量 列表,a,b,null,参数列表,局部变量 列表,a,b,null,语义分析过程？,语义分析要做什么？ 举例说，它检查并确定： 每个标识符在使用之前是否已有定义； 标识符是否被用在不合适的上下文中； 为子程序调用提供的的数目和类型是否正确； 每个函数里是否至少包含了一个刻画返回值的语句； 等等。,作业2：枚举所有可能的语义分析需要做的工作,3.5代码生成,代码生成,编译器的代码生成阶段把中间形式翻译到目标语言。有了语法树以及符号表中的所包含的各种信息，生成正确的代码一般说并不是很困难的工作（生成好的代码则是很困难的！） 为了生成汇编或者机器语言，代码生成器需要遍历语法树，根据中间表示节点的类型和所处的位置进行相应处理。（语法制导代码生成）,目标代码,我们选择汇编代码作为目标语言。 目标代码数据结构如下： class code private string label; /标号 private string op; /操作码 private string arg1; /操作数 private string arg2; /操作数 ,问题,如何生成目标代码？ 目标代码如何运行？,语法中间表示示例,f1,a,b,=,=,a,1,b,2,main,null,a,b,call f1(),a,b,目标代码示例,line0: call near ptr _main line1: halt line2:f1: f1 proc near line3: add sp 4 line4: mov bp+2 0 line5: mov bp+3 0 line6: mov ax bp line7: add ax 4 line8: mov bp+4 ax line9: mov bp+5 sp line10: mov ax 1 line11: mov bp-1-0+0 ax line12: mov ax 2 line13: mov bp-1-1+0 ax line14: ret line15: f1 endp,line16: main: main proc near line17: add sp 6 line18: mov bp+2 0 line19: mov bp+3 1 line20: mov ax -1 line21: mov bp+4 ax line22: mov bp+5 sp line23: mov ax bp+6+1+0 line24: push ax line25: mov ax bp+6+0+0 line26: push ax line27: call near ptr _f1 line28: sub sp 2 line29: ret line30: main endp,目标代码的执行,按顺序解释执行代码存储空间中的代码 直到遇到halt指令结束 图示如下：,0,1,2,3,maxaddr,低,高,pc,pc,pc,pc,pc,程序结束！,初始化,当前pc所指指令的 操作码,mov 把操作数2的值 传给操作数1,jmp 将pc设为 目标位置,halt 程序结束,call 调用操作数2 指定的函数,从新的pc中 取出指令,pc+,pc+,pc+,pc+,运行时存储空间组织,函数调用情况： main()bar()widget(),main的活动记录,bar的活动记录,widget的活动记录,全局数据区,程序结构： 全局数据声明 main() main中的数据声明 bar() bar中的数据声明 wiget() ,活动记录,上图示意了运行时堆栈的详细情况 当前在cpu中运行的函数是widget()，我们取出它的活动记录进行分析：,sp,bp,未使用 的空间,举例,void widget(int x, int y) int a, b; a = x+y; b = x-y; ,sp,bp,未使用 的空间,举例,举例： void widget(int x, int y) int a, b; a = x+y; b = x-y; ,bp,sp,相对位置！,目标代码运行的实现,class vm processor cpu; /虚拟机的cpu datagrid symtable；/符号表 datagrid asmcode; /代码存储空间 const int stacksize = 200; int stack = new intstacksize; /栈 /int heap = new intheapsize; /堆 ,public struct processor public int ax; / 累加器ax public int bx; / bx public int cx; public int pc; / 程序计数器 pub