编译器的设计与实现.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-stmtparams int ID,int ID|void|emptycompound-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-expressionsimple-expression additive-expression relop additive-expression relop|=|=|!=additive-expression term(+|-)term term factor(*|/)factor factor(expression)|ID|call|NUMcall 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 processorpublic int ax;/累加器AXpublic int bx;/BXpublic int cx;public int pc;/程序计数器public int bp;/基址指针bppublic int sp;/堆栈指针sppublic int hp;public int zf;/标志flag；/其它详细内容将会在以后解释,2.2存储器组织,线性组织，Mem0MemmaxAddr,0,1,2,3,maxaddr,低,高,功能分区：代码区元数据区栈（运行时存储空间）堆假定每一个功能存储区的地址都是由0开始,2.3目标机器模型,代码区存储代码,堆存储动态分配空间,栈存储函数运行栈,CPU（寄存器组）,元数据存放符号表等运行信息,简单的栈式存储分配,数据结构,class VM processor cpu;/虚拟机的cpusymtable；/符号表DataTable code;/代码存储空间 int stack=new intSTACKSIZE;/栈 int heap=new intHEAPSIZE;/堆,2.4指令系统,目标程序形式有以下几种：绝对机器代码可再定位机器代码汇编语言程序我们采用汇编语言的形式表示目标代码格式如下：,指令集举例,MOV ax,bx;bx axMOV addr,ax;ax addr所表示的地址空间中JMP 21;无条件跳转指令CMP ax,bx;比较ax与bx寄存器的值,设置标志寄存器JZ 21;根据标志寄存器的值有条件跳转,目标代码数据结构,根据目标代码的结构，不难设计它的数据结构如下：class Codeprivate 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 Tokenstring 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-stmtparams int ID,int ID|void|emptycompound-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-expressionsimple-expression additive-expression relop additive-expression relop|=|=|!=additive-expression term(+|-)term term factor(*|/)factor factor(expression)|ID|call|NUMcall 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-stmtcompound-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,抽象语法树 节点表示,=+-,IDNUM,IDNUM,表达式：expression ID=expression|simple-expressionsimple-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 TreeNodeint lineno;/行号TreeNode child=null,null,null,null;/子节点;TreeNode sibling;/兄弟节点NodeType ntype;/节点类型string nodestr;/保存标识符的名称，便于在语法树中显示string vartype;/用于标明变量类型int char floatstring rettype;/函数返回类型void int char float/other property info,语法分析器的实现,class ParserToken curtoken;void parse()curtoken=getNextToken();/取得第一个tokenTreeNode 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/VarInfopublic class VarInfopublic string var_name;public string var_type;public int isarray;/0:simplevar 1:array(一维数组)public int arraysize;public int rva;/offsetpublic Place place;/参数变量？局部变量？全局变量？,符号表设计函数信息,/FunInfopublic class FunInfopublic string fun_name;public string ret_type;/0:void 1:int 2:user_defined_typepublic 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 Codeprivate 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 _MAINline1:HALT line2:f1:F1 PROC NEARline3:ADD SP 4line4:MOV BP+2 0line5:MOV BP+3 0line6:MOV AX BPline7:ADD AX 4line8:MOV BP+4 AXline9:MOV BP+5 SPline10:MOV AX 1line11:MOV BP-1-0+0 AXline12:MOV AX 2line13:MOV BP-1-1+0 AXline14:RET line15:F1 ENDP,line16:main:MAIN PROC NEARline17:ADD SP 6line18:MOV BP+2 0line19:MOV BP+3 1line20:MOV AX-1line21:MOV BP+4 AXline22:MOV BP+5 SPline23:MOV AX BP+6+1+0line24:PUSH AX line25:MOV AX BP+6+0+0line26:PUSH AX line27:CALL NEAR PTR _F1line28:SUB SP 2line29: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;/虚拟机的cpuDataGrid symtable；/符号表DataGrid asmcode;/代码存储空间 const int STACKSIZE=200;int stack=new intSTACKSIZE;/栈/int heap=new intHEAPSIZE;/堆,public struct processorpublic int ax;/累加器AXpublic int bx;/BXpublic int cx;public int pc;/程序计数器public int bp;/基址指针bppublic int sp;/堆栈指针sppublic int hp;public int zf;/标志flag；/其它,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 Push(string arg)/入栈 PUSH AX int val=0;switch(arg)case AX:val=cpu.ax;break;case BX:val=cpu.bx;break;case BP:val=cpu.bp;break;case“SP:val=cpu.sp;break;this.Stackcpu.sp=val;cpu.sp+;,/eg:MOV AX 1void Mov(string des,string source)int val=ArgValue(source);/取得源操作数的值switch(des)case AX:cpu.ax=val;break;case BX:cpu.bx=val;break;case BP:cpu.bp=val;break;case SP:cpu.sp=val;break;,/eg:ADD SP 4void Add(string des,string source)int val=ArgValue(source);switch(des)case AX:cpu.ax+=val;break;case BX:cpu.bx+=val;break;case SP:cpu.sp+=val;break;default:break;,/eg:Haltvoid Halt()MessageBox.Show(代码执行完毕);Init();,目标代码的生成？,前面详细介绍了代码在目标机器上的运行；接下来重点介绍目标代码的生成！,目标代码的生成！,如何从中间表示（语法树）得到目标代码呢？示例：赋值语句If语句 while语句函数调用与返回,回顾,本小节主要介绍了整个系统的构架一些主要的数据结构（单词符号，语法节点，中间表示形式，目标代码结构）目标代码的运行为后面的内容奠定基础,作业,1 列举不同的中间表示形式；比较其优缺点（特点）2 枚举语义分析过程需要做的所有工作,