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

《编译器设计与实现Lcc原理剖析》由会员分享，可在线阅读，更多相关《编译器设计与实现Lcc原理剖析（65页珍藏版）》请在装配图网上搜索。

1、编译器设计与实现Lcc原理剖析华中科技大学计算机学院张 德2023/9/18一、概述1、编译器各阶段2023/9/18词法分析器语法分析器语义分析器中间代码生成器代码优化器代码生成器错误处理器符号表管理器源程序目标程序2、编译器各阶段的分组前端：依赖于语言并很大程度上独立于目标机器。一般包括语法分析、词法分析、符号表的建立、语义分析、中间代码生成以及相关错误处理。后端：依赖于目标机器的阶段或某些阶段的某些部分。一般来说，后端完成的任务不依赖于源语言而只依赖于中间语言。主要包括代码优化、代码生成以及相关的错误处理和符号表操作。2023/9/18二、符号表符号表是编译器保存信息的中心库，编译器的各

2、部分通过符号表进行交互，并访问符号表中的数据符号。符号表把各种名字映射到符号集合。常量、标识符和标号都是名字，不同名字有不同的属性。符号管理不仅要处理符号本身，还管理符号的作用域。2023/9/181、符号的表示struct symbol char*name;/名称int scope;/作用域Coordinate src;/在源程序中位置Symbol up;/连接符号表中上一个符号List uses;/可保存一个Coordinate列表，表示使用情况int sclass;/扩展存储类型/符号标记Type type;/如变量、函数、常量、结构或联合等信息floatref;/被引用的粗略次数uni

3、on/联合u为标号、结构、联合、枚举、常量、全局/和静态变量提供附加信息 u;/Xsymbol x;/由后端处理，如为变量分配寄存器/为调试器产生数据信息2023/9/181、符号的表示scope域：enum CONSTANTS=1,LABELS,GLOBAL,PARAM,LOCAL;第k层中声明的局部变量其scope域等于LOCAL+k。src域：typedef struct coord char*file;unsigned x,y;Coordinate;file指名包含该符号定义文件名，y和x表示出现的行号及行中位置。sclass域：符号扩展类型可以是AUTO、REGISTER、STATI

4、C或EXTERN等首字母大写的类型表示全小写类型的指针，如Symbol。2023/9/182、符号表的表示externTableconstants;externTableexternals;externTableglobals;externTableidentifiers;externTablelabels;externTabletypes;struct table intlevel;/同symbol中scope域Table previous;/符号表链表，指向level-1的表struct entry struct symbol sym;struct entry *link;*buckets

5、256;/这是一个哈希链数组，方便插入、查找Symbol all;/指向当前及其外层所有符号列表的表头;2023/9/183、符号表举例、符号表举例int x,y;f(int x,int a)int b;y=x+a*b;if(y 5)int a;y=x+a*b;2023/9/182023/9/183045600000a b x y4、符号表的相关操作查找和建立标识符Symbol install(const char*name,Table*tpp,int level,int arena);Symbol lookup(const char*name,Table tp);标号:与标识符相似，但不涉及

6、作用域常量：这些符号保存在constants表中产生变量：用于产生静态变量保存字符串等2023/9/18三、代码生成接口这一章内容定义了与目标机器无关的前端和与目标机器相关的后端之间的接口。Lcc接口包括一些共享数据结构、18个函数和包括36个操作符的语言。该语言用于将可执行代码从源程序生成dag（有向无环图）。共享数据结构可供前后端共享，但某些域为一端私有。symbol就是一个共享数据结构。2023/9/181、类型度量typedef struct metrics unsigned char size,align,outofline;Metrics;size:类型的大小；align：对齐字节

7、数；outofline：控制相关类型的常量的放置。为1时，不出现在dag中，存于静态变量中。Metrics charmetric;Metrics shortmetric;Metrics intmetric;Metrics floatmetric;Metrics doublemetric;Metrics structmetric;2023/9/182、接口记录typedef struct interface Xinterfacex;Interface;lcc为每一种目标机器形成一个独有的接口实例。x域是对interface的扩展，后段使用它存放与目标及其相关的接口数据和函数，对后端私有。2023

8、/9/183、dag操作可执行代码用dag来描述。函数体是用dag组成的序列或森林。每个dag都可以同过gen函数传给后端。dag节点struct node short op;short count;Symbol syms3;Node kids2;Node link;Xnode x;2023/9/183、dag操作op域存放dag操作符。dag操作符后缀表示操作数类型：enum F=FLOAT,I=INT,U=UNSIGNED,P=POINTER,V=VOID,B=STRUCT;如CNST，有变体CNSTI、CNSTU、CNSTP等。CNST=1u.sym;return INT;goto id

9、;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=6&prect=11&prect=13)int

10、op=t;t=gettok();if(operop=ASGN)p=asgntree(ASGN,p,value(expr1(0);else return p2023/9/18条件表达式：conditonal-expression:binary-expression?expression:conditional-expressionstatic Tree expr2(void)Tree p=expr3(4);if(t=?)Tree l,r;Coordinate pts2;if(Aflag 1&isfunc(p-type)warning(%s used in a conditional expres

11、sionn,funcname(p);p=pointer(p);t=gettok();pts0=src;l=pointer(expr(:);pts1=src;r=pointer(expr2();return p;2023/9/18另有二元表达式、一元表达式、后缀表达式和基本表达式。表达式分析多是用递归和大量switch语句实现。在编译领域用一个分析函数代替n个函数处理n级优先是非常流行的。关于表达式的分析还包括表达式语义的分析，如类型检查转换、函数调用分析等各种操作。2023/9/182、语句分析代码的表示：表达式首先被编译为分析树然后转化为dag。每个函数的dag在代码表中被串起来，代码表表示

12、了函数的代码。code结构：struct code enum Blockbeg,Blockend,Local,Address,Defpoint,Label,Start,Gen,Jump,Switch kind;Code prev,next;union u;2023/9/18语句的识别：void statement(int loop,Swtch swp,int lev)float ref=refinc;if(Aflag=2&lev=15)warning(more than 15 levels of nested statementsn);switch(t)case IF:ifstmt(genla

13、bel(2),loop,swp,lev+1);break;case WHILE:whilestmt(genlabel(3),swp,lev+1);break;case DO:dostmt(genlabel(3),swp,lev+1);expect(;);break;refinc=ref;expect(;)break;2023/9/18if语句的识别：if expression=0 goto Lstatement1 goto L+1L:statement2L1：static void ifstmt(int lab,int loop,Swtch swp,int lev)t=gettok();exp

14、ect();/判断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);2023/9/18在循环、switch、got

15、o语句中都用到了标号和跳转，标号使通过definelab函数定义的，而跳转通过branch函数生成。除语句识别外，还有声明的识别。声明的识别非常复杂，c语言中声明的形式很多，处理时大量的相互递归调用。经过前端的分析后，将源程序转化为dag，并添加进代码表。2023/9/183、小结六、中间代码生成编译器的后端通过function接口函数调用gencode和emitcode来遍历代码表。walk和listnodes函数操作处理dag森林。newnode函数为节点分配内存并用它的参数只来初始化节点的域。listnode还负责删除公共子表达式。2023/9/181、构建节点Node listnode

16、s(Tree tp,int tlab,int flab)Node p=NULL,l,r;int op;if(tp=NULL)return NULL;if(tp-node)/node标识listnode访问过的树return tp-node;if(isarray(tp-type)op=tp-op+sizeop(voidptype-size);elseop=tp-op+sizeop(tp-type-size);switch(generic(tp-op)tpnode p;return p;2023/9/182、控制流最简单的一元和二元操作加入结点表，但是并不会出现在根中。赋值等操作可以用这种情况解决

17、。要改变控制流需要跳转。case JUMP:l=listnodes(tp-kids0,0,0);list(newnode(JUMP+V,l,NULL,NULL);reset();break;2023/9/18static void list(Node p)if(p&p-link=NULL)if(forest)p-link=forest-link;forest-link=p;elsep-link=p;forest=p;2023/9/18forest是一个循环链表，不为空则指向链表最后一个节点，为空则将其初始化，link域可以表示根结点。case LT:/LT代表大于转移，是接口dag标识符 l=

18、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);else if(flab)switch(generic(tp-op)case EQ:op=NE;break;case NE:op=EQ;break;case GT:op=LE;break;case LT:op=GE;break;case GE:op=LT;break;case LE:op=GT;break;default:assert(0);list(newn

19、ode(op+opkind(l-op),l,r,findlabel(flab);if(forest&forest-syms0)forest-syms0-ref+;break;2023/9/182023/9/18ai&ai+bi0&ai+bikids1作为一个addr。最后emitasm生成一个换行符。2023/9/183、寄存器的分配从上节我们可以看出，代码发送器可以生成汇编代码，但是汇编代码中的寄存器是如何分配的？寄存器分配包括两个内容：分配：决定哪些值占用寄存器指派：为每个值指派特定的寄存器2023/9/182023/9/18例程名例程名作用作用 linearize为输出一棵指令树排序 r

20、alloc为一条指令释放和分配寄存器 putreg释放一个忙寄存器 getreg发现和分配一个寄存器 askreg发现和分配一个空寄存器 askfixedreg尝试分配一个制定的寄存器 spillee标记一个最远使用寄存器溢出 spill溢出一个或多个寄存器 spillr溢出一个寄存器 genspill产生代码溢出一个寄存器 genreload产生代码重载一个被溢出的寄存器 reprune当genreload更新x.kids后，更新kids在后端选择指令并将子指令从树中分离出来，linearize采用前序遍历分离的树，并按照最后执行的顺序链接指令。gen再将每条指令传递给ralloc函数，ra

21、lloc一般首先调用putreg来释放不再被其子节点使用的寄存器，然后调用getreg函数为自身分配一个寄存器。对于临时变量，ralloc在首次赋值的时候为它分配一个寄存器，在最后一次使用的时候释放该机存器。2023/9/18寄存器状态的跟踪unsigned freemask2;unsigned usedmask2;用掩码表示寄存器的状态对于寄存器r：int n=r-set;r-mask&freemaskn 为0表示寄存器忙2023/9/18寄存器分配：寄存器分配器对森林进行三遍扫描:第一遍对所有使用临时变量的节点建立一个表。该列表指名了临时变量节点的最后一次使用。第二遍对森林的扫描删去一些用

22、于寄存器复制的指令，把计算源寄存器的表达式重定向，使用目的寄存器。最后一遍扫描为每个节点分配寄存器。2023/9/18寄存器的溢出：寄存器溢出是指寄存器分配器用完寄存器时需要生成代码来空出一个忙寄存器，将其值存储回存储器中，并将那些未被处理的使用该寄存器的节点替换成存储器结点。存储器分配用完时最有选择是把最远使用的寄存器存回存储器。这类似于操作系统中的内存调度，原理相同。2023/9/18八、总结lcc是构造编译器的一种方法。在设计过程中对数以百计的技术策略进行了选择，这些策略很多都是可行的方法。lcc中运用了许多编程技巧，使的很多方法得以巧妙的实现，减小了代码的体积。lcc中的各个部分还可单

23、独拿出做其他的应用，如语法分析可用于处理电子数据表，lburg可处理各种树的模式匹配问题。2023/9/181、数据结构由于lcc的共享数据结构不多，因此可以很好的处理前端与代码生成之间的数据结构共享。这样也有不足之处：比较其它简单的设计方法，这些结构更为复杂。有些人认为是c语言导致这种复杂性，用定义单独结构的方法可以减少这些复杂程度。例如用面向对象语言将结构分割。2023/9/182、接口lcc剔除了许多冗余部分并做了简单性假定，一次是的代码很紧凑，但是这些假定限制了接口在其他语言和机器上的应用能力。lcc接口假定符号和无符号整数以及长整数都具有相同的长度。假定所有指针表示相同。2023/9/183、语法和语义分析lcc的语法和语义分析穿插进行。lcc采用一遍扫描的策略，与AST相比她的开销更小，速度更快。2023/9/184、代码生成和优化代码生成需要综合平衡各种因素。功能强大的优化器可以产生更好的代码。但是他的速度太慢了。就每棵树来说，lcc的指令选择是最佳的。但相邻数的代码边界处就差一些。lcc可以在最后使用窥孔优化解决。lcc的寄存分配器比较原始，目前可以采用图的着色方法分配能力更为出色，但这样做会使代码多出很多。2023/9/18