编译器设计与实现

编译器设计与实现第一页，共六十五页，2022年，8月28日一、概述1、编译器各阶段2023/3/31词法分析器语法分析器语义分析器中间代码生成器代码优化器代码生成器错误处理器符号表管理器源程序目标程序第二页，共六十五页，2022年，8月28日2、编译器各阶段的分组前端：依赖于语言并很大程度上独立于目标机器。一般包括语法分析、词法分析、符号表的建立、语义分析、中间代码生成以及相关错误处理。后端：依赖于目标机器的阶段或某些阶段的某些部分。一般来说，后端完成的任务不依赖于源语言而只依赖于中间语言。主要包括代码优化、代码生成以及相关的错误处理和符号表操作。2023/3/31第三页，共六十五页，2022年，8月28日二、符号表符号表是编译器保存信息的中心库，编译器的各部分通过符号表进行交互，并访问符号表中的数据——符号。符号表把各种名字映射到符号集合。常量、标识符和标号都是名字，不同名字有不同的属性。符号管理不仅要处理符号本身，还管理符号的作用域。2023/3/31第四页，共六十五页，2022年，8月28日1、符号的表示structsymbol{ char *name; //名称 int scope; //作用域 Coordinate src; //在源程序中位置 Symbol up; //连接符号表中上一个符号 List uses; //可保存一个Coordinate列表，表示使用情况 int sclass; //扩展存储类型 <symbolflag> //符号标记 Type type; //如变量、函数、常量、结构或联合等信息 float ref; //被引用的粗略次数 union{ //联合u为标号、结构、联合、枚举、常量、全局 <appendentinfo> //和静态变量提供附加信息 }u; // Xsymbol x; //由后端处理，如为变量分配寄存器 <debuggerextension>// 为调试器产生数据信息}2023/3/31第五页，共六十五页，2022年，8月28日1、符号的表示scope域： enum{CONSTANTS=1,LABELS,GLOBAL,PARAM,LOCAL};

第k层中声明的局部变量其scope域等于LOCAL+k。src域： typedefstructcoord{ char *file; unsigned

x,y; }

Coordinate; file指名包含该符号定义文件名，y和x表示出现的行号及行中位置。sclass域：符号扩展类型

可以是AUTO、REGISTER、STATIC或EXTERN等首字母大写的类型表示全小写类型的指针，如Symbol。2023/3/31第六页，共六十五页，2022年，8月28日2、符号表的表示extern Table constants;extern Table externals;extern Table globals;extern Table identifiers;extern Table labels;extern Table types;struct

table{ int level; //同symbol中scope域 Table

previous; //符号表链表，指向level-1的表 struct

entry{ struct

symbol

sym; struct

entry

*link; }*buckets[256]; //这是一个哈希链数组，方便插入、查找 Symbol

all; //指向当前及其外层所有符号列表的表头};2023/3/31第七页，共六十五页，2022年，8月28日3、符号表举例int x,y;f(intx,inta){ intb; y=x+a*b; if(y<5){ inta; y=x+a*b; }}2023/3/31第八页，共六十五页，2022年，8月28日2023/3/313045600000abxy第九页，共六十五页，2022年，8月28日4、符号表的相关操作查找和建立标识符Symbolinstall(constchar*name,Table*tpp,intlevel,intarena);Symbollookup(constchar*name,Tabletp);标号:与标识符相似，但不涉及作用域常量：这些符号保存在constants表中产生变量：用于产生静态变量保存字符串等2023/3/31第十页，共六十五页，2022年，8月28日三、代码生成接口这一章内容定义了与目标机器无关的前端和与目标机器相关的后端之间的接口。Lcc接口包括一些共享数据结构、18个函数和包括36个操作符的语言。该语言用于将可执行代码从源程序生成dag（有向无环图）。共享数据结构可供前后端共享，但某些域为一端私有。symbol就是一个共享数据结构。2023/3/31第十一页，共六十五页，2022年，8月28日1、类型度量typedefstructmetrics{ unsignedcharsize,align,outofline;}Metrics;size:类型的大小；align：对齐字节数；outofline：控制相关类型的常量的放置。为1时，不出现在dag中，存于静态变量中。Metrics

charmetric;Metrics

shortmetric;Metrics

intmetric;Metrics

floatmetric;Metrics

doublemetric;Metrics

structmetric;2023/3/31第十二页，共六十五页，2022年，8月28日2、接口记录 typedefstructinterface{ <metrics> <interfaceflags> <interfacefunctions> Xinterface x; } Interface;lcc为每一种目标机器形成一个独有的接口实例。x域是对interface的扩展，后段使用它存放与目标及其相关的接口数据和函数，对后端私有。2023/3/31第十三页，共六十五页，2022年，8月28日3、dag操作可执行代码用dag来描述。函数体是用dag组成的序列或森林。每个dag都可以同过gen函数传给后端。dag节点 struct

node{ short

op; short

count; Symbol

syms[3]; Node

kids[2]; Node

link; Xnode

x; };2023/3/31第十四页，共六十五页，2022年，8月28日3、dag操作op域存放dag操作符。dag操作符后缀表示操作数类型：enum{ F=FLOAT, I=INT, U=UNSIGNED, P=POINTER, V=VOID, B=STRUCT};如CNST，有变体CNSTI、CNSTU、CNSTP等。 CNST

=

1<<4； CNSTC=CNST+F； CNSTI=CNST+I； ……2023/3/31第十五页，共六十五页，2022年，8月28日2023/3/31第十六页，共六十五页，2022年，8月28日2023/3/31第十七页，共六十五页，2022年，8月28日3、dag操作举例：inti,*p;f(){i=*p++;}2023/3/313CNSTI45ASGNP1ADDRGPp7INDIRI6ADDRGPi8ASGNI4ADDP2INDIRP第十八页，共六十五页，2022年，8月28日4、接口标志 unsignedlittle_endian:1;目标机器存储是低位优先还是高位优先 unsignedmulops_calls:1;有硬件实现乘、除和求余，mulopes_calls应等于0 unsignedwants_callb:1;通知前端产生CALLB节点以调用返回结构的函数 unsignedwants_argb:1;通知前端节点产生ARGB节点以产生结构参数 unsignedleft_to_right:1;告诉前端按照从左到右的顺序计算和提交参数给后端 unsignedwants_dag:1;告诉前端传递dag给后端2023/3/31第十九页，共六十五页，2022年，8月28日5、函数前端将函数编译为私有数据结构。将函数的任意部分传递给后端之前，前端必须先对每个函数进行完整的分析。函数的处理：function函数包括前端过程gencode遍历前端的私有数据结构，将dag的每个森林传给后端过程gen。gen选择代码，在dag上添加注释并将返回一个dag指针。gencode还可以调用local宣告新的局不变量。前端过程emitcode再次遍历，将gen返回的指针传递给emit函数发送代码。2023/3/31第二十页，共六十五页，2022年，8月28日6、上行调用

前段调用后端以执行代码生成和发送。后端调用前端完成输出、分配存储空间、查询类型等功能。上行调用即后端调用前端。allocate分配空间，保证对齐方式符合机器多

数类型newnode分配新的dag节点newconst符号表中创建新的常量newtemp符号表中创建新的变量……2023/3/31第二十一页，共六十五页，2022年，8月28日四、词法分析词法分析器读入源程序，产生语言的基本词法单元。例：*prt＝56；2023/3/31单词编码附加值‘*’ID“prt”‘＝’ICON“56”第二十二页，共六十五页，2022年，8月28日1、输入2023/3/31bufferbuffer+MAXLINEbuffer+MAXLINE＋MAXSIZE\ncplimit当limit-cp小于某一个固定值时，调用fillbuf函数填充buffer第二十三页，共六十五页，2022年，8月28日2、单词识别部分文法：token: keyword identifier constant operator punctuatorpunctuator: oneof[](){}*,:=;…2023/3/31定义：ID标识符FCON 浮点常量ICON整型常量SCON…INCRDECRDEREF……第二十四页，共六十五页，2022年，8月28日emun{#definexx(a,b,c,d,e,f,g)a=b,#defineyy(a,b,c,d,e,f,g)#include“token.h”LAST}token.h文件：yy(0,0,0,0,0,0,0)xx(FLOAT,1,0,0,0,CHAR,"float")xx(DOUBLE,2,0,0,0,CHAR,"double")xx(CHAR,3,0,0,0,CHAR,"char")xx(SHORT,4,0,0,0,CHAR,"short")xx(INT,5,0,0,0,CHAR,"int")xx(UNSIGNED,6,0,0,0,CHAR,"unsigned")xx(POINTER,7,0,0,0,0,"pointer")xx(VOID,8,0,0,0,CHAR,"void")xx(STRUCT,9,0,0,0,CHAR,"struct")……2023/3/31第二十五页，共六十五页，2022年，8月28日3、关键字的识别可以通过查表完成，也可以通过硬编码方式识别。例如，当起始小写字母为i时由gettok函数中switch语句的case‘i’处理。2023/3/31case'i':if(rcp[0]=='f'&&!(map[rcp[1]]&(DIGIT|LETTER))){ cp=rcp+1; returnIF;}if(rcp[0]=='n'&&rcp[1]=='t'&&!(map[rcp[2]]&(DIGIT|LETTER))){ cp=rcp+2; tsym=inttype->u.sym; returnINT;}gotoid;第二十六页，共六十五页，2022年，8月28日4、标识符识别 case'h':case'j':case'k':case'm':case'n':case'o': case'p':case'q':case'x':case'y':case'z': case'A':case'B':case'C':case'D':case'E':case'F': case'G':case'H':case'I':case'J':case'K': case'M':case'N':case'O':case'P':case'Q':case'R': case'S':case'T':case'U':case'V':case'W':case'X': case'Y':case'Z': id: if(limit-rcp<MAXLINE){ cp=rcp-1; fillbuf(); rcp=++cp; }2023/3/31 assert(cp==rcp); token=(char*)rcp-1; while(map[*rcp]&(DIGIT|LETTER)) rcp++; token=stringn(token,(char*)rcp-token); tsym=lookup(token,identifiers); cp=rcp; returnID;检查是否需要填充buffer第二十七页，共六十五页，2022年，8月28日5、其他另外还有：数字识别字符常量和字符串识别都是有gettok函数实现，实现方法相似。

词法分析器可以有象LEX这样的工具实现。Lcc手工实现了词法分析器，体积更小。2023/3/31第二十八页，共六十五页，2022年，8月28日五、语法分析根据语言的文法分析，以确认输入是否符合语言规则，并建立输入源程序的内部表示。Lcc采用递归下降的语法分析。语法分析以形式语言理论为基础，采取语法制导翻译方法，处理程序中的错误。2023/3/31第二十九页，共六十五页，2022年，8月28日1、表达式表达式的表示：(a+b)+b*(a+b)2023/3/31ADD+IADDRG+PaMUL+IADD+IINDIR+IINDIR+IADD+IADDRG+PbADDRG+PbINDIR+IINDIR+IINDIR+IADDRG+PaADDRG+Pb第三十页，共六十五页，2022年，8月28日表达式的分析：c语言的小部分表达式语法: expr:term{+term} term:factor{*factor} factor:ID|‘(’expr‘)’T(expr)T(term{+term})T(term)T({+term})term();T({+term})term();while(t==‘+’){T(+term)}term();while(t==‘+’){T(+)T(term)}term();while(t==‘+’){t=gettok();T(term)}term();while(t==‘+’){t=gettok();term()}同理得分析函数term是：factor();while(t==‘*’){t=gettok();factor()}2023/3/31voidfactor(){if(t==ID)t=gettok();elseif(t==‘(’){t=gettok();expr();expect(‘)’);}}第三十一页，共六十五页，2022年，8月28日c语言表达式分析赋值表达式：assignment-expression: conditional-expression unary-expressionassign-operatorassignment-expressionTreeexpr1(inttok){ staticcharstop[]={IF,ID,0}; Treep=expr2(); if(t=='=‘||(prec[t]>=6&&prec[t]<=8) ||(prec[t]>=11&&prec[t]<=13)){ intop=t; t=gettok(); if(oper[op]==ASGN) p=asgntree(ASGN,p,value(expr1(0))); else<augmentedassignment> returnp}2023/3/31第三十二页，共六十五页，2022年，8月28日条件表达式：

conditonal-expression: binary-expression[?expression:conditional-expression]staticTreeexpr2(void){ Treep=expr3(4); if(t=='?'){ Treel,r; Coordinatepts[2]; if(Aflag>1&&isfunc(p->type)) warning("%susedinaconditionalexpression\n", funcname(p)); p=pointer(p); t=gettok(); pts[0]=src; l=pointer(expr(':')); pts[1]=src; r=pointer(expr2()); }<other> returnp;}2023/3/31第三十三页，共六十五页，2022年，8月28日另有二元表达式、一元表达式、后缀表达式和基本表达式。表达式分析多是用递归和大量switch语句实现。在编译领域用一个分析函数代替n个函数处理n级优先是非常流行的。关于表达式的分析还包括表达式语义的分析，如类型检查转换、函数调用分析等各种操作。2023/3/31第三十四页，共六十五页，2022年，8月28日2、语句分析代码的表示：表达式首先被编译为分析树然后转化为dag。每个函数的dag在代码表中被串起来，代码表表示了函数的代码。 code结构：structcode{ enum{Blockbeg,Blockend,Local,Address,Defpoint, Label,Start,Gen,Jump,Switch }kind; Codeprev,next; union{ <unions> }u;}2023/3/31第三十五页，共六十五页，2022年，8月28日语句的识别：voidstatement(intloop,Swtchswp,intlev){ floatref=refinc; if(Aflag>=2&&lev==15) warning("morethan15levelsofnestedstatements\n"); switch(t){ caseIF:ifstmt(genlabel(2),loop,swp,lev+1);break; caseWHILE:whilestmt(genlabel(3),swp,lev+1);break; caseDO:dostmt(genlabel(3),swp,lev+1);expect(';');break; …… } <check> refinc=ref;}expect(‘;’)break;2023/3/31第三十六页，共六十五页，2022年，8月28日if语句的识别：

ifexpression==0gotoL

statement1 gotoL+1L: statement2L＋1： staticvoidifstmt(intlab,intloop,Swtchswp,intlev){ t=gettok(); expect(‘(’); //判断if后的（ definept(NULL); walk(conditional(‘)’),0,lab);//包含listnode函数生成dag并加入 refinc/=2.0; //森林，把入口加入代码表.同时根 statement(loop,swp,lev); //据接过设置flab，tlab if(t==ELSE){ branch(lab+1); t=gettok(); definelab(lab); statement(loop,swp,lev); if(findlabel(lab+1)->ref) definelab(lab+1); }else definelab(lab); }2023/3/31第三十七页，共六十五页，2022年，8月28日在循环、switch、goto语句中都用到了标号和跳转，标号使通过definelab函数定义的，而跳转通过branch函数生成。除语句识别外，还有声明的识别。声明的识别非常复杂，c语言中声明的形式很多，处理时大量的相互递归调用。经过前端的分析后，将源程序转化为dag，并添加进代码表。2023/3/313、小结第三十八页，共六十五页，2022年，8月28日六、中间代码生成编译器的后端通过function接口函数调用gencode和emitcode来遍历代码表。walk和listnodes函数操作处理dag森林。newnode函数为节点分配内存并用它的参数只来初始化节点的域。listnode还负责删除公共子表达式。2023/3/31第三十九页，共六十五页，2022年，8月28日1、构建节点Nodelistnodes(Treetp,inttlab,intflab){ Nodep=NULL,l,r; intop; if(tp==NULL) returnNULL; if(tp->node)//node标识listnode访问过的树 returntp->node; if(isarray(tp->type)) op=tp->op+sizeop(voidptype->size); else op=tp->op+sizeop(tp->type->size); switch(generic(tp->op)){ <listnodescases> } tp－>node＝p; returnp;}2023/3/31第四十页，共六十五页，2022年，8月28日2、控制流最简单的一元和二元操作加入结点表，但是并不会出现在根中。赋值等操作可以用这种情况解决。要改变控制流需要跳转。

caseJUMP:{ l=listnodes(tp->kids[0],0,0); list(newnode(JUMP+V,l,NULL,NULL)); reset(); }break;2023/3/31第四十一页，共六十五页，2022年，8月28日staticvoidlist(Nodep){ if(p&&p->link==NULL){ if(forest){ p->link=forest->link; forest->link=p; }else p->link=p; forest=p; }}2023/3/31forest是一个循环链表，不为空则指向链表最后一个节点，为空则将其初始化，link域可以表示根结点。第四十二页，共六十五页，2022年，8月28日 caseLT:{//LT代表大于转移，是接口dag标识符 l=listnodes(tp->kids[0],0,0); r=listnodes(tp->kids[1],0,0); if(tlab) list(newnode(generic(tp->op)+opkind(l->op),l,r,findlabel(tlab))); elseif(flab){ switch(generic(tp->op)){ caseEQ:op=NE;break;caseNE:op=EQ;break; caseGT:op=LE;break;caseLT:op=GE;break; caseGE:op=LT;break;caseLE:op=GT;break; default:assert(0); } list(newnode(op+opkind(l->op),l,r,findlabel(flab))); } if(forest&&forest->syms[0]) forest->syms[0]->ref++;}break;2023/3/31第四十三页，共六十五页，2022年，8月28日2023/3/31a[i]&&a[i]+b[i]>0&&a[i]+b[i]<10的森林EQI2LEI2GEI2LABELV2INDIRICNSTI0ADDIADDPLSHIADDRGPaINDIRICNSTI2ADDRGPiINDIRIADDPADDRGPbCNSTI10第四十四页，共六十五页，2022年，8月28日七、代码生成器代码生成器：为编译前端提供接口函数，接口函数用与目标机器相关的指令来实现无关的中间代码。接口函数也为临时变量指派寄存器、固定的函数单元或栈空间。Lcc将大部分与机器无关的函数重组到一个大的与机器无关的程序中。2023/3/31第四十五页，共六十五页，2022年，8月28日例程名功能function产生函数的头代码和尾代码，调用gencodegencode解释代码表，并将数传递给gengen处理代码表中各个森林rewriteprelabel修改树，以适应寄存器变量和特殊的目标机器_label用所有可能的实现标记树reduce选择代价最小的实现prune从树中提出某些自指令linearize输出排序指令ralloc分配寄存器emitcode解释代码表，为每个森林调用emitemit追溯指令列表requate删除寄存器到寄存器的复制moveself删除寄存器复制到自身的指令emitasm解释汇编模版，输出大多数指令emit2输出过复杂不适于模版的指令2023/3/31第四十六页，共六十五页，2022年，8月28日1、选择和发送指令Lcc的指令选择器时由程序lburg根据紧缩规范自动生成的，lburg是代码生成器的生成器。lburg接收紧缩规范并产生一个用c语言编写的树分析程序，该程序为目标机器选择指令。树分析程序接受中间代码的主题树，并将它分割成与目标机器相对应的程序块，成为数覆盖。2023/3/31第四十七页，共六十五页，2022年，8月28日模式：ADDI(reg，con)表示如果ADDI的第一个子节点能递归的匹配reg，第二个子节点匹配con，那么该模式就在ADDI除匹配一棵树。规则：addr：ADDI（reg，con）规定了非终结符addr与上述模式相匹配规则：stmt：ASGNI（addr，reg）规定了ASGNI节点的每子节点递归的与addr和reg匹配非终结符stmt就与该ASGNI匹配。例：ASGNI(ADDP(INDIRP(ADDRLP(p)),CNSTI(4)),CNSTI(5))的覆盖2023/3/31ASGNIADDPINDIRPCNSTI4ADDRLPpCNSTI5addr：ADDP（addr，con）reg：INDIRP（addr）addr：ADDRLPcon：CNSTIreg：concon：CNSTIstmt：ASGNI（addr，reg）第四十八页，共六十五页，2022年，8月28日2023/3/31第四十九页，共六十五页，2022年，8月28日2023/3/31第五十页，共六十五页，2022年，8月28日2、发送器Lcc发送器（emitter）的作用是为目标机器输出代码。发送器并不依赖于目标机器，由两个描述与机器相关的数据的数组驱动。Lburg为每个BURM生成一些c语言代码，用来声明并初始化这两个数组。两个数组都是通过规则号索引。规则生成模板数组：staticchar*_template[];标记与指令对应的模板，以区别子指令（如寻址指令）：staticchar*_isinstruction[];2023/3/31第五十一页，共六十五页，2022年，8月28日 lburg从1开始为规则编号，并通过返回规则号来报告匹配情况，这样当需要的时候就可以找到响应的模板。如果模板以一个换行符为结尾表示它是一条指令，否则就必然是某条指令的一部分，比如是一个操作数。 rc:reg"%0" rc:con"%0" reg:ADDI4(reg,mrc1)"?mov%c,%0\nadd%c,%1\n"1 reg:ADDP4(reg,mrc1)"?mov%c,%0\nadd%c,%1\n"12023/3/31第五十二页，共六十五页，2022年，8月28日emitasm对规则结构及汇编程序代码模板进行了解释。emitasm递归调用自身，以处理地址计算之类的子指令。emitasm的遍历从一个指令开始，当递归到达为该指令提供值的指令时结束。emitasm由emit调用，emit确保emitasm以正确的顺序来处理这些指令，这样便可以处理指令间的顺序。2023/3/31第五十三页，共六十五页，2022年，8月28日例如：发送器解释字符串“lwr%c,%1\n”

先生成“lwr”，然后是目标寄存器的名字（通常是一个数字），接着是一个逗号。如果nts[1]中保存了表示非终结符addr的整数，那么递归生成p->kids[1]作为一个addr。最后emitasm生成一个换行符。2023/3/31第五十四页，共六十五页，2022年，8月28日3、寄存器的分配从上节我们可以看出，代码发送器可以生成汇编代码，但是汇编代码中的寄存器是如何分配的？寄存器分配包括两个内容：分配：决定哪些值占用寄存器指派：为每个值指派特定的寄存器2023/3/31第五十五页，共六十五页，2022年，8月28日2023/3/31例程名作用linearize为输出一棵指令树排序ralloc为一条指令释放和分配寄存器putreg释放一个忙寄存器getreg发现和分配一个寄存器askreg发现和分配一个空寄存器askfixedreg尝试分配一个制定的寄存器spillee标记一个最远使用寄存器溢出spill溢出一个或多个寄存器spillr溢出一个寄存器