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

1、MicroC：一个编译器的设计与实现Micro C一个C编译器的设计与实现摘 要编译程序是把高级语言编写的源程序翻译成机器语言表示的目标程序的转换程序，是程序员接触最多的系统软件之一。C、PASCAL、BASIC等高级语言具有功能强大、结构化好、可移植性好、可读性好等众多优点，基本取代了汇编语言，而更先进的语言，如C+,SmallTalk，Ada,Java等面向对象的语言也是层出不穷。这就对编译器的理论、技术提出了一个挑战。一个好的语言，势必需要一个高效、功能强大的编译器。编译理论，在计算机科学中是比较成熟的学科，它建立在形式语言和自动机理论的基础之上。形式语言是对程序设计语言形式化的描述，它

2、一方面涉及产生形式语言的规则文法；另一方面涉及识别形式语言的装置自动机。运用这些理论可以构造词法分析和语法分析的有力工具有限自动机和下推自动机。编译理论还包括语法制导翻译方法、存储空间组织、错误处理、代码优化等内容。自己动手设计一个编译器是学习编译理论的一个好方法。本文以设计、实现C语言的一个子集的编译程序（MICROC）为主题，介绍本编译器的原理，一些具体的数据结构以及X86汇编语言等内容。本编译器的目标是把C语言的源代码翻译成X86汇编代码，再由MASM或TASM汇编成目标代码，再由连接程序连接成可执行代码。C语言是BELL实验室的Dennis Ritchie在B语言的基础设计并实现的一种

3、高级语言，它是一种结构化语言，具有语句简洁、紧凑，易于移植等特点，因此选择它作为编译器的源语言。由于目前实验室基于Intel体系的机器较多，因此选择8086汇编语言为目标语言。同时也能在开发中使用现成的汇编器（Assembler）和调试器（Debugger）。MicroC编译器简介1、 主要性能源语言：C语言子集目标代码：80x86汇编语言1）文法：整数C文法2）支持的数据类型：void,char,int以及数组。忽略unsigned 和 signed。能够识别extern, static, long（extern 为函数，不支持extern 变量。static 和 long 都忽略）。对do

4、uble 和float 作int处理。忽略auto,register,const。支持函数，main当作普通函数处理。3） 支持的运算符： 算术运算符：+，-，*，/，% ，? :（三目），sizeof 。 关系运算符： , =, =, ! = ， = = 逻辑运算符：&, |, ! 位运算 ：&，|，, , , 赋值运算 ： ，+ =, - =, * =, / =, % =，&=, ! =, =, =, =4)支持typedef5)支持预编译 #include6 )支持的语句： 条件语句：if . else 循环语句：while ， do.while ， for(;) 转移语句：goto ，

5、return， continue ，break 分支语句：switch() case7)支持两种类型的注释 ANSI C风格的注释 /* */ 不支持注释的嵌套，位于/* 和 */ 之间的字符串 将被忽略。 C+行注释 /2、 基本结构MicroC由词法分析、语法分析、代码生成、符号表管理以及错误处理等部分组成，如图所示。C源程序词法分析出错处理符号表管理语法分析与代码生成C源程序3、 运行环境：Intel 80x86/1M MS-DOS 词法分析1、MicroC的词法特点1）保留字：保留字是编译器预定义的且不可重定义的、在程序中承担固定作用的字符序列。MicroC中的保留字有：auto, b

6、reak, case, char, const, continue , default, do, double, else,extern, float, for, goto, if, int, long, register，return, short,signed,sizeof, static, switch, typedef, unsigned, void, volatile，while，include。2）标识符：在程序中定义的表示常量、变量、过程以及函数名的字符序列。标识符由一个字母后面跟着数字和字母的任意组合，由于作用域规则的存在，标识符可以有条件地重新定义。在MicroC中，标识符中

7、不能有 _字符。3）标点符号：在MicroC中，标点符号用于表示数学、逻辑运算的操作；定义数据结构；访问控制和分隔标识符。标点符号有：( ) + - * / % = | & | & ! = != =+= -= *= /= %= |= &= = = , ; : . ? + -4）数字、字符、字符串常量：整数可以用十进制、八进制、十六进制表示。如12, 0x5a, 036；实数可以用科学记数法或小数表示。如 1.2, 3.0e+2；字符是界于两个单引号之间的字符。如 a *；字符串常量是界于两个双引号之间的字符，如“hello”。4） MicroC支持两种类型的注释，第一种是ANSI C风格的注释

8、，不支持注释的嵌套，位于/* 和 */ 之间的字符串将被忽略。另一种是C+行注释，以/ 开头的行将被忽略。5） 其它：在MicroC中，由于只支持一种预编译，所以#include 整体作为一个标识符被识别。MicroC大小写敏感。 2、数据结构1） 关键字表：关键字表保存系统关键字的信息，其定义如下：typedefstruct char nameNAME_LEN; int key;/ keyword IDKEYENTRY;KEYENTRY Keytable =.；其中KEYENTRY中的name域用来保存关键字的名字，key域用来保存关键字的标识号，即词法分析器传递给语法分析器的终结符号。2）

9、 保存终结符和非终结符属性的数据结构：%union/ note : NAME_LEN = 32charp_char32;intnum;intascii;symbol*p_symbol;；3、 实现：1） 终结符的命名规则：关键字：k+大写字符串，如kBREAK；标点符号为：o+大写字符串，如oPLUS；常数标识为：c+大写字符串，如cINT；其它：p+大写字符串，如pINCLUDE；2） 对注释的处理：MicroC处理两种注释，并跳过它们，程序段如下：/*while ( 1 )int i;i = input();/ or i = EOF, see input() source code for

10、 when file/ meet EOF return what?if ( !i )yyerror( End of file in commentn );user_exit(1);if ( i = * )if ( ( i = input() )= / )break;elseunput( i );/while ( 1 )intcurrlineno = yylineno;if ( !input() | currlineno != yylineno )break;3） 常数的处理：MicroC的词法分析器识别十进制、八进制、十六进制无符号整数，并转化成相应的数值形式。翻译规则如下：1-9+dec*y

11、ylval.num = stoi(yytext,10);return cINT;0oct*yylval.num = stoi(yytext,8); return cINT;0(x|X)hex+ yylval.num = stoi(yytext,16);return cINT;stoi函数将保存在yytext中的数字序列根据其8、10、16进制转化成相应的数值，并返回此数值。其原形为:int stoi(char *s, int radix ); s为数字序列，radix 指示相应的进制。4） 标识符的处理：对于标识符，首先将其复制到yylval中，然后调用id_or_keyword 查找其属性值

12、并返回。规则如下：letteralnum*strcpy(yylval.p_char,yytext); return id_or_keyword(yytext);函数int id_or_keyword(char *lex)完成以下操作：1）检查关键字表是否初始化，若否，则报错退出。2）用二分法在表格中查找是否有匹配的关键字，若找到，则返回表示其是关键字的标识号。3）若没有找到，则在sys_tab中查找是否有此标识符的类型定义，若是，则返回表示其为类型定义的标识号idTYPEDEF。否则返回的是表示其是标识符的标识号。注：由于本编译器支持typedef类型定义，所以就要到符号表中去查找，来决定此标

13、识符是否已经由typedef定义过。语法分析MicroC 采用LALR（1）文法，MicroC语法定义如下：translation_unit:external_declaration|translation_unit external_declaration;external_declaration:function_definition|declaration|control_line;control_line:pINCLUDE cSTRING|pINCLUDE pINCLDNAME;function_definition:declaration_specifiers declarator

14、compound_statement|declarator compound_statement;declaration:declaration_specifiers init_declarator_list oSEMI|declaration_specifiers oSEMI;declaration_list:declaration|declaration_list declaration;declaration_specifiers:storage_class_specifier declaration_specifiers|storage_class_specifier|type_spe

15、cifier declaration_specifiers|type_specifier|type_qualifier declaration_specifiers|type_qualifier;storage_class_specifier:kAUTO|kREGISTER|kSTATIC|kTYPEDEF|kEXTERN;type_specifier:kINT|kLONG|kSHORT|kCHAR|kVOID|kFLOAT|kDOUBLE|kSIGNED|kUNSIGNED|idTYPEDEF;type_qualifier:kCONST|kVOLATILE;init_declarator_l

16、ist:init_declarator|init_declarator_list oCOMMA init_declarator;init_declarator:declarator|declarator oASSIGN initializer;declarator:direct_declarator;direct_declarator:identifier|direct_declarator oLB constant_expression oRB|direct_declarator oLB oRB|direct_declarator oLP parameter_type_list oRP|di

17、rect_declarator oLP oRP;parameter_type_list:parameter_list|parameter_list oCOMMA oDOTDOTDOT;parameter_list:parameter_declaration|parameter_list oCOMMA parameter_declaration;parameter_declaration:declaration_specifiers declarator|declaration_specifiers abstract_declarator|declaration_specifiers;initi

18、alizer:assignment_expression|oLC initializer_list oRC|oLC initializer_list oCOMMA oRC;initializer_list:initializer|initializer_list oCOMMA initializer;abstract_declarator:direct_abstract_declarator;direct_abstract_declarator:oLB constant_expression oRB;identifier:yNAME;statement:labeled_statement|ex

19、pression_statement|compound_statement|selection_statement|iteration_statement|jump_statement;labeled_statement:identifier oCOLON |kCASE constant_expression oCOLON |kDEFAULT oCOLON ;expression_statement:expression oSEMIcompound_statement:oLC declaration_list statement_list oRC|oLC |oLC declaration_li

20、st oRC|oLC oRC;statement_list:statement|statement_list statement;selection_statement:kIF oLP expression oRP statement else_clause|kSWITCH oLP expression oRP statement;else_clause :kELSE statement | ;iteration_statement:kWHILE oLP expression oRP statement|kDO statement kWHILE oLP expression oRP oSEMI

21、|kFOR oLP expression oSEMI expression oSEMI expression oRP statement;jump_statement:kGOTO identifier oSEMI|kCONTINUE oSEMI|kBREAK oSEMI|kRETURN expression oSEMIexpression:assignment_expression|expression oCOMMA assignment_expression|;assignment_expression:conditional_expression|unary_expression oASS

22、IGN assignment_expression|unary_expression oPLUSASSIGN assignment_expression|unary_expression oMINUSASSIGN assignment_expression|unary_expression oMULASSIGN assignment_expression|unary_expression oDIVASSIGN assignment_expression|unary_expression oMODASSIGN assignment_expression|unary_expression oBIT

23、ORASSIGN assignment_expression|unary_expression oBITANDASSIGN assignment_expression|unary_expression oBITXORASSIGN assignment_expression|unary_expression oLFTSHTASSIGN assignment_expression|unary_expression oRITSHTASSIGN assignment_expression;sconditional_expression:logical_OR_expression|logical_OR_

24、expression oQUESTION expression oCOLON conditional_expression;constant_expression:conditional_expression;logical_OR_expression:logical_AND_expression|logical_OR_expression oOR logical_AND_expression;logical_AND_expression:inclusive_OR_expression|logical_AND_expression oAND inclusive_OR_expression;in

25、clusive_OR_expression:exclusive_OR_expression|inclusive_OR_expression oBITOR exclusive_OR_expression;exclusive_OR_expression:AND_expression|exclusive_OR_expression oBITXOR AND_expression;AND_expression:equality_expression|AND_expression oBITAND equality_expression;equality_expression:relational_expr

26、ession|equality_expression oEQUAL relational_expression|equality_expression oUNEQU relational_expression;relational_expression:shift_expression|relational_expression oLT shift_expression|relational_expression oGT shift_expression|relational_expression oLE shift_expression|relational_expression oGE s

27、hift_expression;shift_expression:additive_expression|shift_expression oLFTSHT additive_expression|shift_expression oRITSHT additive_expression;additive_expression:multiplicative_expression|additive_expression oPLUS multiplicative_expression|additive_expression oMINUS multiplicative_expression;multip

28、licative_expression:cast_expression|multiplicative_expression oMUL cast_expression|multiplicative_expression oDIV cast_expression|multiplicative_expression oMOD cast_expression;cast_expression:unary_expression;unary_expression:postfix_expression|oADDADD unary_expression|oSUBSUB unary_expression|oPLU

29、S cast_expression|oMINUS cast_expression|oBITNOT cast_expression|oNOT cast_expression|kSIZEOF unary_expression|kSIZEOF oLP unary_expression oRP|kSIZEOF oLP declaration_specifiers oRP;postfix_expression:primary_expression|postfix_expression oLB expression oRB|postfix_expression oLP argument_expressio

30、n_list oRP|postfix_expression oLP oRP|postfix_expression oADDADD|postfix_expression oSUBSUB;primary_expression:identifier|constant|cSTRING|oLP expression oRP;argument_expression_list:assignment_expression|argument_expression_list oCOMMA assignment_expression;constant:cINT|cCHAR|cREAL;语法分析实现的主要任务是设计Y

31、ACC程序中的语法规则及相应的语义分析子程序，然后由YACC自动生成语法分析程序。具体的实现请参阅“代码生成”。符号表严格的说，符号表是一个包含程序中的变量、子程序、类型定义、常数定义的信息的数据库。符号表的主要特点：.速度快.易使用.灵活.支持重复项目.快速删除MicroC符号表的实现：1、 组织方式：MicroC的符号表用堆栈和二叉树的形式实现。MicroC 的符号是以Compound Statement为单位进行组织的，把处于同一Compound Statement中的符号放在一个二叉树上。每遇到一个Compound Statement 就把指向一个树根的指针压入称为sg_compoun

32、d_stack的堆栈，然后把属于此Compound Statement的变量全都挂在这棵树上。这样，若在此Compound statement中遇到嵌套的Compound Statement，也将进行同样处理。当一个Compound statement结束以后，则此Compound Statement对应的二叉树也将被删除，这样，一个内部的Compound Statement中的变量对于其外部就不可见了。2、 全局变量的处理方式：在MicroC中，全局变量是作为最外层的Compound Statement挂在第一个被压入堆栈的指针上。直到程序结束，此指针才被退栈。这样，全局变量始终是可见的。3

33、、 函数的符号表：在MicroC中，函数由于其特殊性，并不与一般的变量作同样的处理，而是放在一个称为sg_function_symtab的全局表中。此sg_function_symtab用二叉树的形式实现，使得查找方式得到统一，并提高查找的效率。4、数据结构：1）const_value结构：typedef union _const_value_charv_c;unsigned charv_uc;intv_i;unsigned intv_ui;floatf;/ never useddoublelf;/ never usedconst_string*v_str; / pointer to the

34、string in table const_value;const_value结构是用来存放常量的值，根据常量类型的不同，把值放在不同的域中。2）symbol结构：typedef struct _symbol_char nameNAME_LEN;char rnameLABEL_LEN;unsigned is_symtab;unsigned is_function;unsigned is_declaration;unsignedis_array;unsignedis_argument;unsignedis_assign;unsignedis_cl;unsignedis_rvalue;unsign

35、edis_pushed;intnum_ele;specifierbasetype;intoffset;struct _symbol_ *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 表示此标识符是一个函数；unsigne

36、d is_declaration =1 若此标识符为一个标号或函数，则此标号或函数为声明，而不是定义；unsigned is_array=1 表明此标识符是一个数组；unsigned is_argument =1 表明此标识符用来表示一个函数的参数；unsigned is_assign =1 表示此标识符是一个变量，并且已经被赋予了初值；unsigned is_cl =1 表示此symbol是一个常量；unsigned is_rvalue =1 表示此标识符是一个右值；unsigned is_pushed =1 表示此标识符所代表的expression的值已经压入栈；int num_ele当此

37、标识符是一个数组的时候，用来表示数组的元素的个数；specifier basetype 用来表示此标识符的类型，若是函数，则用来表示函数的返回类型；int offset 用来表示变量的偏移量（为了区别具有相同名称的全局变量和局部变量，需要用offset来区分）；struct _symbol_ *next 符号表中的下一个元素，如果是函数的参数，则指向它的下一个参数；struct _symbol_ *args 若此标识符表示一个函数，则用来表示函数的第一个参数，若不是函数，则表示此变量的初始化值，另外，若此标识符表示一个数组名，则此项用来表示数组的下标值；struct _symbol_ *lch

38、ild,*rchild用于二叉树的构造。5、符号表维护函数：/单个符号的空间申请与释放：symbol*new_symbol();void del_symbol(symbol *p);/ 符号表头的维护函数：void remove_symtab(symbol *head);void remove_symtab_except_args(symbol *head);voidremove_function_symtab_include_args(symbol *func);symbol*create_symtab(const char *name);/Compound Statement Stack的

39、维护函数：void remove_symbol_list(symbol *p);symbol*search_symbol_in_symtab(symbol *tab, char *name);symbol*search_symbol_to_top(char *name);intadd_symbol_to_symtab(symbol *tab, symbol *p);intadd_symbol_to_current_symtab(symbol *p);intadd_symbol_list_to_current_symtab(symbol *p);symbol*link_symbol_list(s

40、ymbol *p1, symbol *p2);void union_specifier_symbol(symbol *p1, symbol *p2);void check_var_declarator(symbol *decl);void unoin_specifier_to_declarator(symbol *spec, symbol *decl);void unoin_specifier_to_declarator_list(symbol *spec, symbol *decl_list);symbol*new_symbol_from_typedef(symbol *def_sym);s

41、ymbol*find_symtab_typedef(char *name);symbol*new_compound_symtab();void del_compound_symtab();intget_symbol_size(symbol *p);void set_local_or_args_rname(symbol *p);char* get_asm_attri(symbol *p);void assign_parameters_rname(symbol *args_list);void assign_symbol_unusedname(symbol *p);symbol*clone_sym

42、bol(symbol *p);/函数定义表的维护：intcheck_args_type_in_function_call(symbol *p1,symbol *p2);intcheck_args_type(symbol *p1,symbol *p2);intcheck_func_args_type(symbol *func,symbol *decl);symbol*add_function_def_to_functab(symbol *func);void add_function_decl_to_functab(symbol *decl);void check_function_retval

43、(symbol *func);void set_func_offset(symbol *func);intget_function_args_size(symbol *func);/常数符号的处理：void cast_cl_type(symbol *c1, symbol *c2);intget_sym_value(symbol *c);/跳转语句的标号组织：void create_goto_label_symtab();void destory_goto_label_symtab();symbol*search_goto_label(char *name);void add_goto_labe

44、l(symbol *lb);/ 符号表的初始化与销毁：voidInitSymTab();voidDestorySymTab();/符号表的Dump（调试使用）：void dump_symbol(symbol *p);void dump_function(symbol *func);void dump_current_symtab();void dump_function_symtab();代码生成代码分析在MicroC中是比较核心的工作，也是我们工作的主要部分。比较普遍的做法是在代码生成阶段将产生一定形式的中间代码，如四元式、三元式或逆波兰记号等，然后由后端把中间代码转换成机器代码或汇编代码。

45、在我们的MicroC编译器中，我们直接生成80x86汇编代码，然后在借助已有的工具，tasm 和tlink，将此生成的汇编代码汇编、连接成为MS-DOS的可执行文件。这样，也能够在一定程度上验证编译器的正确性。1、 8086体系结构：Intel 8086芯片是16位微处理器，CPU的内外数据总线都是16位，有20条地址线，理论上可直接寻址2201M字节的主存空间，I/O端口的寻址范围为64K。 （1)寄存器 AX(Accumulator)作为累加器用，是算术运算的主要寄存器。 BX(Base)可作为通用寄存器使用，在计算存储器地址时，它经常用作基址寄存器。 CX(Count)可以作为通用寄存器

46、使用，在循环和串处理指令中作隐含的计数器。 DX(Data)可以作为通用寄存器使用，在作双字长运算时和AX组合使用，其中DX存 放高位字。 SP(Stack Pointer)是堆栈指针寄存器，BP(Base Pointer)是基址指针寄存器，它们者可以与SS寄存器组合使用来确定，SP用来指示栈顶，BP可指向栈中某一位置。 SI(Source Index)源变址寄存器和DI(Destination Index)目的变址寄存器与DS，ES联用，可达到在数据段和附加段寻址的目的。 CS(Code Segment)代码段寄存器，保存当前代码段首址高16位。DS(Data Segment)数据段寄存器，

47、保存当前数据段首址高16位。SS(Stack Segment)堆栈段寄存器，保存当前堆栈段首址高16位。ES(Extra Segment)附加段寄存器，存放当前附加段首址高16位。 (2)基本类型：字节(8位)、字(16位)、双字(32位) 字节类型的数值装入AL，字类型的数值装入AX，双字类型的数值装入DX:AX (3)在编译器中用到的部分寻址方式 a)立即寻址方式 操作数直接存放在指令中，紧跟在操作码之后，例如：MOVAL，5MOVAX，3064H b)寄存器寻址方式 操作数在寄存器中。例如：MOVAX，BX c)直接寻址方式 有效地址EA存放在指令中。在指令操作码之后。如操作数在数据段中

48、，则物理地址16d(DS)+EA，例如：MOVAX，2000H如(DS)=3000H,则(AX)=(32000H) d)寄存器间接寻址方式 操作数的有效地址在基址寄存器BX、BP或变址寄存器SI、DI中，操作数在存储器中。如寄存器是BX、SI、DI则操作数在数据段中，如寄存器是BP则操作数在堆栈段中。例如：MOVAX，BX如(DS)=2000H,(BX)=1000H则物理地址=21000H (4)用到的部分汇编指令 a)数据传送指令：MOV，PUSH，POP b)地址传送指令：LEA c)算术指令： ADD，INC，SUB，DEC，NEG，CMP，IMUL，IDIV， d)逻辑指令： AND，

49、OR，NOT，SHL，SAL，SHR，SAR e)串处理指令： MOVS，CMPS，REPE f)控制转移指令： JMP，JE，JLE，JG，JGE，JNE g)程序调用指令： CALL，RET2、 帧调用（Frame Call）的实现：当进行函数调用时，函数的调用者和被调用者执行如下的动作来进行建立一个调用帧。调用者（caller）执行的动作：1） 将实参压入栈中；2） 将返回地址（CS和IP）压入栈中；被调用者（callee）执行的动作：3） 保存帧指针BP；4） 使帧指针指向栈顶（MOV BP,SP）；5） 修改栈指针（SP），为局部变量分配空间。当调用完成后，被调用者（callee）将

50、执行如下动作，使得能从函数返回：1） 将返回值放在寄存器（AX）中；2） 将局部变量退栈；3） 恢复SP的值；4） 将BP退栈，恢复BP的值；5） 返回地址退栈。注：在MicroC编译器中，函数采用PASCAL的方式将参数压入栈，而非C语言的函数参数入栈方式。3、 语法制导的翻译MicroC的翻译主要分成3个部分，包括：1） 定义与声明(Definition and Declaration)的翻译；2） 表达式(Expression)的翻译；3） 语句(Statement)和控制流(Control Flow)的翻译。1） 定义与声明的翻译： 变量的声明与定义：主要工作是建立一个符号表项，基本上

51、不进行实际代码的生成工作。如果是全局变量，就为此标识符在汇编文件的Data 段中通过存储器分配伪操作为它分配空间，并增加相应的符号表项。若是局部变量，则在汇编文件中通过调整栈指针为它分配空间，只是建立相应的符号表项，记录此标识符的信息。若变量进行了初始化，则全局变量通过存储器分配伪操作为它分配初值，而局部变量通过MOV语句为它赋初值。若是一个常变量，则忽略const 关键字。 函数的声明与定义：如果函数定义后面没有函数体，则认为这只是一个函数的定义，则只是为它生成符号表项，记录它相应的信息。如果函数定义的后面有函数体，则先为它加入先前所讲的被调用者的动作，然后根据函数体的代码，为它生成相应的汇编代码，然后加入返回动作。main()函数的处理：在MicroC中，main函数的处理大致与其它的函数作相同的处理，但是MicroC编译器会在main函数的开