编译器设计与实现-Lcc原理剖析.ppt

编译器设计与实现,Lcc原理剖析,华中科技大学计算机学院张德,2019/12/2,一、概述,1、编译器各阶段,2019/12/2,2、编译器各阶段的分组,前端：依赖于语言并很大程度上独立于目标机器。一般包括语法分析、词法分析、符号表的建立、语义分析、中间代码生成以及相关错误处理。后端：依赖于目标机器的阶段或某些阶段的某些部分。一般来说，后端完成的任务不依赖于源语言而只依赖于中间语言。主要包括代码优化、代码生成以及相关的错误处理和符号表操作。,2019/12/2,二、符号表,符号表是编译器保存信息的中心库，编译器的各部分通过符号表进行交互，并访问符号表中的数据符号。符号表把各种名字映射到符号集合。常量、标识符和标号都是名字，不同名字有不同的属性。符号管理不仅要处理符号本身，还管理符号的作用域。,2019/12/2,1、符号的表示,structsymbolchar*name;/名称intscope;/作用域Coordinatesrc;/在源程序中位置Symbolup;/连接符号表中上一个符号Listuses;/可保存一个Coordinate列表，表示使用情况intsclass;/扩展存储类型/符号标记Typetype;/如变量、函数、常量、结构或联合等信息floatref;/被引用的粗略次数union/联合u为标号、结构、联合、枚举、常量、全局/和静态变量提供附加信息u;/Xsymbolx;/由后端处理，如为变量分配寄存器/为调试器产生数据信息,2019/12/2,1、符号的表示,scope域：enumCONSTANTS=1,LABELS,GLOBAL,PARAM,LOCAL;第k层中声明的局部变量其scope域等于LOCAL+k。src域：typedefstructcoordchar*file;unsignedx,y;Coordinate;file指名包含该符号定义文件名，y和x表示出现的行号及行中位置。sclass域：符号扩展类型可以是AUTO、REGISTER、STATIC或EXTERN等首字母大写的类型表示全小写类型的指针，如Symbol。,2019/12/2,2、符号表的表示,externTableconstants;externTableexternals;externTableglobals;externTableidentifiers;externTablelabels;externTabletypes;structtableintlevel;/同symbol中scope域Tableprevious;/符号表链表，指向level-1的表structentrystructsymbolsym;structentry*link;*buckets256;/这是一个哈希链数组，方便插入、查找Symbolall;/指向当前及其外层所有符号列表的表头;,2019/12/2,3、符号表举例,intx,y;f(intx,inta)intb;y=x+a*b;if(y5)inta;y=x+a*b;,2019/12/2,2019/12/2,4、符号表的相关操作,查找和建立标识符Symbolinstall(constchar*name,Table*tpp,intlevel,intarena);Symbollookup(constchar*name,Tabletp);标号:与标识符相似，但不涉及作用域常量：这些符号保存在constants表中产生变量：用于产生静态变量保存字符串等,2019/12/2,三、代码生成接口,这一章内容定义了与目标机器无关的前端和与目标机器相关的后端之间的接口。Lcc接口包括一些共享数据结构、18个函数和包括36个操作符的语言。该语言用于将可执行代码从源程序生成dag（有向无环图）。共享数据结构可供前后端共享，但某些域为一端私有。symbol就是一个共享数据结构。,2019/12/2,1、类型度量,typedefstructmetricsunsignedcharsize,align,outofline;Metrics;size:类型的大小；align：对齐字节数；outofline：控制相关类型的常量的放置。为1时，不出现在dag中，存于静态变量中。Metricscharmetric;Metricsshortmetric;Metricsintmetric;Metricsfloatmetric;Metricsdoublemetric;Metricsstructmetric;,2019/12/2,2、接口记录,typedefstructinterfaceXinterfacex;Interface;lcc为每一种目标机器形成一个独有的接口实例。x域是对interface的扩展，后段使用它存放与目标及其相关的接口数据和函数，对后端私有。,2019/12/2,3、dag操作,可执行代码用dag来描述。函数体是用dag组成的序列或森林。每个dag都可以同过gen函数传给后端。dag节点structnodeshortop;shortcount;Symbolsyms3;Nodekids2;Nodelink;Xnodex;,2019/12/2,3、dag操作,op域存放dag操作符。dag操作符后缀表示操作数类型：enumF=FLOAT,I=INT,U=UNSIGNED,P=POINTER,V=VOID,B=STRUCT;如CNST，有变体CNSTI、CNSTU、CNSTP等。CNST=11,2019/12/2,另有二元表达式、一元表达式、后缀表达式和基本表达式。表达式分析多是用递归和大量switch语句实现。在编译领域用一个分析函数代替n个函数处理n级优先是非常流行的。关于表达式的分析还包括表达式语义的分析，如类型检查转换、函数调用分析等各种操作。,2019/12/2,2、语句分析,代码的表示：表达式首先被编译为分析树然后转化为dag。每个函数的dag在代码表中被串起来，代码表表示了函数的代码。code结构：structcodeenumBlockbeg,Blockend,Local,Address,Defpoint,Label,Start,Gen,Jump,Switchkind;Codeprev,next;unionu;,2019/12/2,语句的识别：voidstatement(intloop,Swtchswp,intlev)floatref=refinc;if(Aflag=2,2019/12/2,if语句的识别：ifexpression=0gotoLstatement1gotoL+1L:statement2L1：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，tlabif(t=ELSE)branch(lab+1);t=gettok();definelab(lab);statement(loop,swp,lev);if(findlabel(lab+1)-ref)definelab(lab+1);elsedefinelab(lab);,2019/12/2,在循环、switch、goto语句中都用到了标号和跳转，标号使通过definelab函数定义的，而跳转通过branch函数生成。除语句识别外，还有声明的识别。声明的识别非常复杂，c语言中声明的形式很多，处理时大量的相互递归调用。经过前端的分析后，将源程序转化为dag，并添加进代码表。,2019/12/2,3、小结,六、中间代码生成,编译器的后端通过function接口函数调用gencode和emitcode来遍历代码表。walk和listnodes函数操作处理dag森林。newnode函数为节点分配内存并用它的参数只来初始化节点的域。listnode还负责删除公共子表达式。,2019/12/2,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);elseop=tp-op+sizeop(tp-type-size);switch(generic(tp-op)tpnodep;returnp;,2019/12/2,2、控制流,最简单的一元和二元操作加入结点表，但是并不会出现在根中。赋值等操作可以用这种情况解决。要改变控制流需要跳转。caseJUMP:l=listnodes(tp-kids0,0,0);list(newnode(JUMP+V,l,NULL,NULL);reset();break;,2019/12/2,staticvoidlist(Nodep)if(p,2019/12/2,forest是一个循环链表，不为空则指向链表最后一个节点，为空则将其初始化，link域可以表示根结点。,caseLT:/LT代表大于转移，是接口dag标识符l=listnodes(tp-kids0,0,0);r=listnodes(tp-kids1,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,2019/12/2,2019/12/2,aiunsignedusedmask2;用掩码表示寄存器的状态对于寄存器r：intn=r-set;r-mask&freemaskn为0表示寄存器忙,2019/12/2,寄存器分配：寄存器分配器对森林进行三遍扫描:第一遍对所有使用临时变量的节点建立一个表。该列表指名了临时变量节点的最后一次使用。第二遍对森林的扫描删去一些用于寄存器复制的指令，把计算源寄存器的表达式重定向，使用目的寄存器。最后一遍扫描为每个节点分配寄存器。,2019/12/2,寄存器的溢出：寄存器溢出是指寄存器分配器用完寄存器时需要生成代码来空出一个忙寄存器，将其值存储回存储器中，并将那些未被处理的使用该寄存器的节点替换成存储器结点。存储器分配用完时最有选择是把最远使用的寄存器存回存储器。这类似于操作系统中的内存调度，原理相同。,2019/12/2,八、总结,lcc是构造编译器的一种方法。在设计过程中对数以百计的技术策略进行了选择，这些策略很多都是可行的方法。lcc中运用了许多编程技巧，使的很多方法得以巧妙的实现，减小了代码的体积。lcc中的各个部分还可单独拿出做其他的应用，如语法分析可用于处理电子数据表，lburg可处理各种树的模式匹配问题。,2019/12/2,1、数据结构,由于lcc的共享数据结构不多，因此可以很好的处理前端与代码生成之间的数据结构共享。这样也有不足之处：比较其它简单的设计方法，这些结构更为复杂。有些人认为是c语言导致这种复杂性，用定义单独结构的方法可以减少这些复杂程度。例如用面向对象语言将结构分割。,2019/12/2,2、接口,lcc剔除了许多冗余部分并做了简单性假定，一次是的代码很紧凑，但是这些假定限制了接口在其他语言和机器上的应用能力。lcc接口假定符号和无符号整数以及长整数都具有