编译器设计与实现 ——lcc原理剖析.ppt

编译器设计与实现,——Lcc原理剖析,华中科技大学计算机学院 张 德,2018/10/14,一、概述,1、编译器各阶段,2018/10/14,2、编译器各阶段的分组,前端：依赖于语言并很大程度上独立于目标机器一般包括语法分析、词法分析、符号表的建立、语义分析、中间代码生成以及相关错误处理 后端：依赖于目标机器的阶段或某些阶段的某些部分一般来说，后端完成的任务不依赖于源语言而只依赖于中间语言主要包括代码优化、代码生成以及相关的错误处理和符号表操作2018/10/14,二、符号表,符号表是编译器保存信息的中心库，编译器的各部分通过符号表进行交互，并访问符号表中的数据——符号 符号表把各种名字映射到符号集合常量、标识符和标号都是名字，不同名字有不同的属性 符号管理不仅要处理符号本身，还管理符号的作用域2018/10/14,1、符号的表示,struct symbol {char *name; //名称int scope; //作用域Coordinate src; //在源程序中位置Symbol up; //连接符号表中上一个符号List uses; //可保存一个Coordinate列表，表示使用情况int sclass; //扩展存储类型//符号标记Type type; //如变量、函数、常量、结构或联合等信息float ref; //被引用的粗略次数union { //联合u为标号、结构、联合、枚举、常量、全局//和静态变量提供附加信息} u; //Xsymbol x; //由后端处理，如为变量分配寄存器// 为调试器产生数据信息 },2018/10/14,1、符号的表示,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、STATIC或EXTERN等 首字母大写的类型表示全小写类型的指针，如Symbol2018/10/14,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; //指向当前及其外层所有符号列表的表头 };,2018/10/14,,,,,3、符号表举例,int x, y; f(int x, int a){int b;y = x + a*b;if (y < 5){int a;y = x + a*b;} },2018/10/14,2018/10/14,4、符号表的相关操作,查找和建立标识符 Symbol install(const char * name, Table * tpp, int level, int arena); Symbol lookup(const char *name, Table tp); 标号:与标识符相似，但不涉及作用域 常量：这些符号保存在constants表中 产生变量：用于产生静态变量保存字符串等,2018/10/14,三、代码生成接口,这一章内容定义了与目标机器无关的前端和与目标机器相关的后端之间的接口。

Lcc接口包括一些共享数据结构、18个函数和包括36个操作符的语言该语言用于将可执行代码从源程序生成dag（有向无环图） 共享数据结构可供前后端共享，但某些域为一端私有symbol就是一个共享数据结构2018/10/14,1、类型度量,typedef struct metrics {unsigned char size, align, outofline; } Metrics; size:类型的大小； align：对齐字节数； outofline：控制相关类型的常量的放置为1时，不出现在dag中，存于静态变量中Metrics charmetric; Metrics shortmetric; Metrics intmetric; Metrics floatmetric; Metrics doublemetric; Metrics structmetric;,2018/10/14,2、接口记录,typedef struct interface {Xinterface x;} Interface;lcc为每一种目标机器形成一个独有的接口实例x域是对interface的扩展，后段使用它存放与目标及其相关的接口数据和函数，对后端私有。

2018/10/14,3、dag操作,可执行代码用dag来描述函数体是用dag组成的序列或森林每个dag都可以同过gen函数传给后端 dag节点struct node {short op;short count;Symbol syms[3];Node kids[2];Node link;Xnode x;};,2018/10/14,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；… …,2018/10/14,2018/10/14,2018/10/14,3、dag操作,举例： int i, *p; f() { i = *p++;},2018/10/14,4、接口标志,unsigned little_endian:1; 目标机器存储是低位优先还是高位优先unsigned mulops_calls:1; 有硬件实现乘、除和求余，mulopes_calls应等于0unsigned wants_callb:1; 通知前端产生CALLB节点以调用返回结构的函数unsigned wants_argb:1; 通知前端节点产生ARGB节点以产生结构参数unsigned left_to_right:1; 告诉前端按照从左到右的顺序计算和提交参数给后端unsigned wants_dag:1; 告诉前端传递dag给后端,2018/10/14,5、函数,前端将函数编译为私有数据结构。

将函数的任意部分传递给后端之前，前端必须先对每个函数进行完整的分析 函数的处理：function函数包括前端过程gencode遍历前端的私有数据结构，将dag的每个森林传给后端过程gengen选择代码，在dag上添加注释并将返回一个dag指针gencode还可以调用local宣告新的局不变量前端过程emitcode再次遍历，将gen返回的指针传递给emit函数发送代码2018/10/14,6、上行调用,前段调用后端以执行代码生成和发送后端调用前端完成输出、分配存储空间、查询类型等功能上行调用即后端调用前端 allocate分配空间，保证对齐方式符合机器多 数类型 newnode分配新的dag节点 newconst符号表中创建新的常量 newtemp符号表中创建新的变量 … …,2018/10/14,四、词法分析,词法分析器读入源程序，产生语言的基本词法单元 例：*prt ＝ 56；,2018/10/14,1、输入,2018/10/14,,\n,,,cp,limit,当limit-cp小于某一个固定值时，调用fillbuf函数填充buffer,2、单词识别,部分文法： token:keywordidentifierconstantoperatorpunctuator punctuator:one of [ ] ( ) { } * , : = ; …,2018/10/14,定义： ID 标识符 FCON 浮点常量 ICON 整型常量 SCON … INCR DECR DEREF ……,emun{ #define xx(a,b,c,d,e,f,g) a=b, #define yy(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“) … …,2018/10/14,3、关键字的识别,可以通过查表完成，也可以通过硬编码方式识别。

例如，当起始小写字母为i时由gettok函数中switch语句的case ‘i’处理2018/10/14,case 'i':if (rcp[0] == 'f',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;},2018/10/14,assert(cp == rcp);token = (char *)rcp - 1;while (map[*rcp],。