Micro C 　一个C编译器的 设计与实现

1、Micro C一个C编译器的 设计与实现 本次演讲以设计、实现C语言的一个子集的编译程序（MICROC）为主题，介绍本编译器的原理，一些具体的数据结构和设计上的独到之处。 主要性能整体设计 主 要 性 能源语言：C语言子集目标代码：80 x86汇编语言1）文法：整数C文法2）支持的数据类型：void,char, int以及数组。忽略unsigned 和 signed。 忽略auto,register,const。能够识别extern, static, long （extern 为函数，不支持extern 变量。 static 和 long 都忽略）。对double 和float 作int处理。

2、3)支持的运算符： 算术运算符：+，-，*，/，% ，? :（三目），sizeof 。 关系运算符： , =, =, ! = ， = = 逻辑运算符：&, |, ! 位运算 ： &，|，, , , 赋值运算 ： ，+ =, - =, * =, / =, % = &=, ! =, =, =, =4)支持typedef5)支持函数，main当作普通函数处理。 6)支持预编译 #include7 )支持的语句： 条件语句：if . else 循环语句：while ， do.while ， for(;) 转移语句：goto ，return， continue ，break 分支语句：switch()

3、case8)支持两种类型的注释 ANSI C风格的注释 /* */ 不支持注释的嵌套，位于/* 和 */ 之间的字符串 将被忽略。 C+行注释 / C源程序词法分析语法分析与代码生成汇编源程序符号表管理出错处理 MicroC 总 体 设 计 符号表的设计与实现 MicroC的符号表用堆栈和二叉树的形式实现。 MicroC的符号是以Compound Statement为单位进行组织的，把处于同一 Compound Statement中的符号放在一个二叉树上。 全局变量的处理方式： 在MicroC中，全局变量是作为最外层的Compound State- ment挂在第一个被压入堆栈的指针上。直到程

4、序结束，此指 针才被退栈。这样，全局变量始终是可见的。 函数的符号表 在MicroC中，函数由于其特殊性，并不与一般的变量 作同样的处理，而是放在一个称为sg_function_symtab的全 局表中。此sg_function_symtab用二叉树的形式实现，使得 查找方式得到统一，并提高查找的效率。 Label的符号表 在MicroC中，当前函数中出现的label放在头节点为 sg_goto_label_symtab的二叉树中。源程序可以使用goto label语句，但label的范围限定在当前函数中。也就是说，不 能通过goto跳到另外一个函数中，每个函数可以看作是一个 只有单一入口的基

5、本块，这样有利于程序的结构化。数据结构：Typedef struct _symbol_char nameNAME_LEN;char rnameLABEL_LEN;unsigned is_symtab;unsignedis_function;unsignedis_declaration;unsignedis_array;unsignedis_argument;unsignedis_assign;unsignedis_cl;unsignedis_rvalue;unsignedis_pushed;intnum_ele;specifierbasetype;intoffset;struct _symbo

6、l_ *next;struct _symbol_ *args;struct _symbol_ * lchild,*rchild; symbol; symbol结构的几个关键域的具体含义解释如下：char nameNAME_LEN 是标识符的名称；char rnameNAME_LEN 是标识符在汇编代码中的名称;unsigned is_symtab=1 表示此Symbol是某个二叉树的根；unsigned is_function =1 表示此标识符是一个函数；unsigned is_declaration=1若此标识符为一个标号或函数，则 此标号或函数为声明，而不是定义；unsigned is_

7、array=1 表明此标识符是一个数组；unsigned is_argument =1表明此标识符表示函数的一个参数；ununsigned is_assign =1表示此标识符是一个变量，并且已 经被赋予了初值；unsigned is_cl =1 表示此symbol是一个常量；unsigned is_rvalue =1 表示此标识符是一个右值；unsigned is_pushed =1 表示此标识符所代表的expression的值已经压入栈；int num_ele 标识符表示数组时，用来表示数组元素的个数；specifier basetype 用来表示此标识符的类型，若是函数，则用来 表示函数

8、 的返回类型；int offset 用来表示变量的偏移量（为了区别具有相同名称的全 局变量和局部变量，需要用offset来区分）；struct _symbol_ *next 符号表中的下一个元素，如果是函数的 参数，则指向它的下一个参数；struct _symbol_ *args 若此标识符表示一个函数，则用来表示函 数的第一个参数，表示变量，则表示此变 量的初始化值，另外，若此标识符表示一 个数组，则此项用来表示数组的下标值；struct _symbol_ *lchild,*rchild用于二叉树的构造。 分析过程中发现语法或语义错误时，打印出错信息，释放空间，删除临时文件后退出。 对源程序

9、中一些符合语法规范但不常用的写法给出警告信息。如：int ; “warning : ignored on left of specifier when no variable isdeclared”char c; “warning : compound statement has only declaration, no statements出 错 处 理文法设计 表达式文法设计中，通过改造文法消除歧义，使文 法本身就体现了各个操作符的优先级，如： （为了便于演示，作了适当简化） additive_expression: multiplicative_expression| additive_

10、expression oPLUS multiplicative_expression| additive_expression oMINUS multiplicative_expression; multiplicative_expression: unary_expression| multiplicative_expression oMUL cast_expression| multiplicative_expression oDIV cast_expression| multiplicative_expression oMOD cast_expression;IF ELSE 语句的设计

11、我们采用的文法本身没有消除歧义，在LR分析中存在移入/归约冲突。根据yacc的消除歧义规则选择移入，正好符合C语言的else就近原则。selection_statement : kIF oLP expression oRP statementelse_clause ;else_clause :kELSE statement |;语法制导的翻译 变量的声明与定义：主要工作是建立一个符号表项，基本上不进行实际代码的生成工作。如果是全局变量，就为此标识符在汇编文件的Data 段中通过存储器分配伪操作为它分配空间，并增加相应的符号表项。若是局部变量，则在汇编文件中通过调整栈指针为它分配空间，只是建立相

12、应的符号表项，记录此标识符的信息。若变量进行了初始化，则全局变量通过存储器分配伪操作为它分配初值，而局部变量通过MOV语句为它赋初值。若是一个常变量，则忽略const 关键字。 函数的声明与定义：如果只是一个函数的声明，则只是为它生成符号表项，记录它相应的信息。如果函数定义的后面有函数体，则先为它加入被调用者的动作，然后根据函数体的代码，为它生成相应的汇编代码，然后加入返回动作。main()函数的处理：在MicroC中，main函数的处理大致与其它的函数作相同的处理，但是MicroC编译器会在main函数的开头加入一段代码，使得程序从main函数返回之后，能够正确地退回到DOS。标号的声明与定

13、义： 如果遇到的是一个标号，若此标号在goto语句后面，并且此前没有出现过，则此标号也为一个声明，为它产生相应的符号表项，加入到符号表中去。否则，既是声明，又是定义。typedef 的处理： 为typedef后面的标识符产生一个符号表项，并把它的specifier中的sclass置为TYPEDEF，并记录它的类型信息，加入到符号表中。当此标识符用来定义其它的变量时，词法分析器会到符号表中去找，从而进一步得到它的类型信息，这样就能够正确地进行变量的定义。表达式的翻译采用类似逆波兰式的处理方式，通过push,pop来实现表达式结果的传递。下面以双目运算为例：(x+y)*(1+2), 这儿的x,y都为类型为int 的变量。由此产生如下代码：movdx,word ptr bp-4movax,word ptr bp-2addax,dxpushaxpopdxmovax,3imuldx语句与控制流的翻译 参照了编译课本的设计方法进行设计。对头文件的支持 我们支持#include 预编译，每当分析