编译器的设计与实现.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