编译器设计和实现

编译器设计与实现——Lcc原理剖析华中科技大学计算机学院张德2020/4/23一、概述1、编译器各阶段2020/4/23词法分析器语法分析器语义分析器中间代码生成器代码优化器代码生成器错误处理器符号表管理器源程序目标程序2、编译器各阶段的分组前端：依赖于语言并很大程度上独立于目标机器。一般包括语法分析、词法分析、符号表的建立、语义分析、中间代码生成以及相关错误处理。后端：依赖于目标机器的阶段或某些阶段的某些部分。一般来说，后端完成的任务不依赖于源语言而只依赖于中间语言。主要包括代码优化、代码生成以及相关的错误处理和符号表操作。2020/4/23二、符号表符号表是编译器保存信息的中心库，编译器的各部分通过符号表进行交互，并访问符号表中的数据——符号。符号表把各种名字映射到符号集合。常量、标识符和标号都是名字，不同名字有不同的属性。符号管理不仅要处理符号本身，还管理符号的作用域。2020/4/231、符号的表示structsymbol{char*name;//名称intscope;//作用域Coordinatesrc;//在源程序中位置Symbolup;//连接符号表中上一个符号Listuses;//可保存一个Coordinate列表，表示使用情况intsclass;//扩展存储类型symbolflag//符号标记Typetype;//如变量、函数、常量、结构或联合等信息floatref;//被引用的粗略次数union{//联合u为标号、结构、联合、枚举、常量、全局appendentinfo//和静态变量提供附加信息}u;//Xsymbolx;//由后端处理，如为变量分配寄存器debuggerextension//为调试器产生数据信息}2020/4/231、符号的表示scope域：enum{CONSTANTS=1,LABELS,GLOBAL,PARAM,LOCAL};第k层中声明的局部变量其scope域等于LOCAL+k。src域：typedefstructcoord{char*file;unsignedx,y;}Coordinate;file指名包含该符号定义文件名，y和x表示出现的行号及行中位置。sclass域：符号扩展类型可以是AUTO、REGISTER、STATIC或EXTERN等首字母大写的类型表示全小写类型的指针，如Symbol。2020/4/232、符号表的表示externTableconstants;externTableexternals;externTableglobals;externTableidentifiers;externTablelabels;externTabletypes;structtable{intlevel;//同symbol中scope域Tableprevious;//符号表链表，指向level-1的表structentry{structsymbolsym;structentry*link;}*buckets[256];//这是一个哈希链数组，方便插入、查找Symbolall;//指向当前及其外层所有符号列表的表头};2020/4/233、符号表举例intx,y;f(intx,inta){intb;y=x+a*b;if(y5){inta;y=x+a*b;}}2020/4/232020/4/233045600000abxy4、符号表的相关操作查找和建立标识符Symbolinstall(constchar*name,Table*tpp,intlevel,intarena);Symbollookup(constchar*name,Tabletp);标号:与标识符相似，但不涉及作用域常量：这些符号保存在constants表中产生变量：用于产生静态变量保存字符串等2020/4/23三、代码生成接口这一章内容定义了与目标机器无关的前端和与目标机器相关的后端之间的接口。Lcc接口包括一些共享数据结构、18个函数和包括36个操作符的语言。该语言用于将可执行代码从源程序生成dag（有向无环图）。共享数据结构可供前后端共享，但某些域为一端私有。symbol就是一个共享数据结构。2020/4/231、类型度量typedefstructmetrics{unsignedcharsize,align,outofline;}Metrics;size:类型的大小；align：对齐字节数；outofline：控制相关类型的常量的放置。为1时，不出现在dag中，存于静态变量中。Metricscharmetric;Metricsshortmetric;Metricsintmetric;Metricsfloatmetric;Metricsdoublemetric;Metricsstructmetric;2020/4/232、接口记录typedefstructinterface{metricsinterfaceflagsinterfacefunctionsXinterfacex;}Interface;lcc为每一种目标机器形成一个独有的接口实例。x域是对interface的扩展，后段使用它存放与目标及其相关的接口数据和函数，对后端私有。2020/4/233、dag操作可执行代码用dag来描述。函数体是用dag组成的序列或森林。每个dag都可以同过gen函数传给后端。dag节点structnode{shortop;shortcount;Symbolsyms[3];Nodekids[2];Nodelink;Xnodex;};2020/4/233、dag操作op域存放dag操作符。dag操作符后缀表示操作数类型：enum{F=FLOAT,I=INT,U=UNSIGNED,P=POINTER,V=VOID,B=STRUCT};如CNST，有变体CNSTI、CNSTU、CNSTP等。CNST=14；CNSTC=CNST+F；CNSTI=CNST+I；……2020/4/232020/4/232020/4/233、dag操作举例：inti,*p;f(){i=*p++;}2020/4/233CNSTI45ASGNP1ADDRGPp7INDIRI6ADDRGPi8ASGNI4ADDP2INDIRP4、接口标志unsignedlittle_endian:1;目标机器存储是低位优先还是高位优先unsignedmulops_calls:1;有硬件实现乘、除和求余，mulopes_calls应等于0unsignedwants_callb:1;通知前端产生CALLB节点以调用返回结构的函数unsignedwants_argb:1;通知前端节点产生ARGB节点以产生结构参数unsignedleft_to_right:1;告诉前端按照从左到右的顺序计算和提交参数给后端unsignedwants_dag:1;告诉前端传递dag给后端2020/4/235、函数前端将函数编译为私有数据结构。将函数的任意部分传递给后端之前，前端必须先对每个函数进行完整的分析。函数的处理：function函数包括前端过程gencode遍历前端的私有数据结构，将dag的每个森林传给后端过程gen。gen选择代码，在dag上添加注释并将返回一个dag指针。gencode还可以调用local宣告新的局不变量。前端过程emitcode再次遍历，将gen返回的指针传递给emit函数发送代码。2020/4/236、上行调用前段调用后端以执行代码生成和发送。后端调用前端完成输出、分配存储空间、查询类型等功能。上行调用即后端调用前端。allocate分配空间，保证对齐方式符合机器多数类型newnode分配新的dag节点newconst符号表中创建新的常量newtemp符号表中创建新的变量……2020/4/23四、词法分析词法分析器读入源程序，产生语言的基本词法单元。例：*prt＝56；2020/4/23单词编码附加值‘*’ID“prt”‘＝’ICON“56”1、输入2020/4/23bufferbuffer+MAXLINEbuffer+MAXLINE＋MAXSIZE\ncplimit当limit-cp小于某一个固定值时，调用fillbuf函数填充buffer2、单词识别部分文法：token:keywordidentifierconstantoperatorpunctuatorpunctuator:oneof[](){}*,:=;…2020/4/23定义：ID标识符FCON浮点常量ICON整型常量SCON…INCRDECRDEREF……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)……2020/4/233、关键字的识别可以通过查表完成，也可以通过硬编码方式识别。例如，当起始小写字母为i时由gettok函数中switch语句的case‘i’处理。2020/4/23case'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;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-rcpMAXLINE){cp=rcp-1;fillbuf();rcp=++cp;}2020/4/23assert(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;检查是否需要填充buffer5、其他另外还有：数字识别字符常量和字符串识别都是有gettok函数实现，实现方法相似。词法分析器可以有象LEX这样的工具实现。Lcc手工实现了词法分析器，体积更小。2020/4/23五、语法分析根据语言的文法分析，以确认输入是否符合语言规则，并建立输入源程序的内部表示。Lcc采用递归下降的语法分析。语法分析以形式语言理论为基础，采取语法制导翻译方法，处理程序中的错误。2020/4/231、表达式表达式的表示：(a+b)+b*(a+b)2020/4/23ADD+IADDRG+PaMUL