一个简单的C语言编译器

一个简单的C语言编译器一．小组成员朱嘉俊（）计算机996王筱（）计算机996朱杭（）计算机996朱林（）计算机994二．运行方式在DOS环境下运行:Cminus.exe <filename> -h三．概述经过一段时间的学习，我们在初步掌握了编译器的基本原理以后，设计了一个具有基本编译功能的编译器。

该编译器接受类C语言语法的源代码输入，输出结果是PC机的汇编源代码。

在捆绑了宏汇编编译器Masm后，即可直接生成MSDOS下的二进制可执行文件。

为方便起见，以下简称为C—语言编译器。

本编译器实现了基本高级语言所必须的语法要素，包括简单变量声明、函数的实现、整数和字符串运算、条件判断语句和循环语句及跳转语句、基本代数运算、赋值等，还支持汇编语言嵌入。

本编译器是利用编译器生成器Parse Generator和VC6.0在Windows平台上实现的，并开发了一个基于Windows平台的32位编译集成开发环境CompilerMan，提供了关键字彩色提示、出错同屏提示、出错代码跳转等较为完善方便的功能。

由于编译程序本身涉及到词法分析、语法分析、代码生成、错误恢复和优化等诸多模块，要在实验中做到面面俱到不太可能，所以本编译器不可避免的会存在各种问题，但作为一个具有基本功能的、可扩充的系统，完全达到了巩固编译原理的理论知识，并将其运用于实践的目的。

四．背景编译程序，就是一种具有编撰和翻译功能的程序。

人们要用计算机来解决问题，首先面临的一个问题，就是要告诉计算机解决什么问题，或者告诉计算机如何解决这个问题。

这就涉及到用什么样的语言来描述的问题，人所习惯的自然语言和计算机认识的机器语言有很大的差别，用机器语言来描述人想解决的问题十分不便，因而，计算机科学家设计一些人们比较习惯的语言来描述要解决的问题，称之为高级语言。

用语言来描述的问题，统称为程序。

然而，用高级语言写的程序，不能被计算机所直接认识和理解，必须经过等价的转换，变成机器能理解并执行的机器语言的程序。

进行这种等价转换工作的工具，就是编译程序。

1．编译程序的结构编译程序是很复杂的，但它可被分为相对独立的几个部分，每个部分承担专门的工作，各部分间互相共享传送数据。

把编译程序分解成较小的部分，不仅便于开发、调试，而且便于编译程序的移植。

一个典型的编译程序通常具有如图1的结构。

图1 编译器基本结构1.1 词法分析词法分析负责对源程序的字符串进行扫描和分解，根据构词法将字符流(Character Stream)转化成单词流(Token Stream)。

例如对于C--语句：x = y + z – m * 10;词法分析的结果是：ID ASSIGN ID ADD ID SUB ID MUL NUM SEMI构词的规则就是词法，例如标识符(ID)可定义为以字母开头，后面跟零个或任意个字母或数字的序列。

词法分析程序就根据词法构造有限自动机来识别每一个单词，将产生的单词交给语法分析程序。

1.2 语法分析语法分析模块的任务是根据文法规则把单词序列分解成各类语法单位，识别出一个一个句子，例如对前面的语句进行语法分析可得到如图2的分析树。

如果输入单词不能构成语法树，则说明有语法错误。

常见的语法分析方法分为自顶向下分析和自底向上分析两大类。

在C--编译器中采用了一种自底向上的方法，即LR方法。

1.3 语义分析这一阶段部分是根据前一阶段产生的语法树，按语言的语义进行翻译，产生四元式或三元式等中间语言。

中间语言可以很方便地转换成目标代码。

前面的语法树可能产生的四元式序列为：(*,_t0,10,m)(-,_t1,z,_t0)(+,_t0,y,_t1)(=,x,_t0)由于中间语言对后面的代码优化和目标代码生成有密切关系，又和目标机器的体系结构有关，所以中间语言的选择对于编译器的效率和质量有很大的影响。

1.4 代码优化代码优化是把中间代码进行变换，以产生更加高效的目标代码。

1.5 目标代码生成目标代码生成是编译最后一个阶段，它把中间代码转换成汇编指令或可重定位的目标代码。

例如对于前面生成的中间代码，可以产生IBM PC汇编指令为：mov ax, mmul ax, 10mov bx, zsub bx,axadd bx,ymov x, bx汇编代码经过Masm汇编器(Assembler)和连接器(Linker)处理，就产生了可在IBM PC机器上运行的二进制代码。

2．形式语言简介2.1 文法和语言文法是产生语言的规则，它可定义为：对于一个四元式G=(V N，V T，S，P)，其中(1) V N是非终结符号的有限集合(2) V T是终结符号的有限集合，且V T∩V N(3) 开始符号S，S∈V N(4) 一组产生式P，P中的每一个产生式都具有如下形式：u→v，u∈(V N∪V T)+且至少要有一个非终结符号，v∈(V N∪V T)*则G表示一个文法。

乔姆斯基(Noam Chmosky)把文法分成四类：0型文法又称无约束文法，产生式的形式为a→b，a、b是任意字符串。

1型文法又称上下有关文法，产生式形式为a→b，且|a|≥|b|。

2型文法又称上下文无关文法(Context-Free Grammar)，产生式形式为A→a，a∈(V N∪V T)*，A∈V N。

3型文法又称正规文法，它的产生式左部是一个非终结符号，右部最多只有一个非终结符号且在右部的最左端或最右端。

通常程序设计语言的文法属于2型文法，可被下推机(Pushdown Automaton)识别。

语言定义为L(G)={w|S=>*w,w∈V T*}，可见，文法G中的V T相当于产生语言的字母表，G中的一组产生式是产生语言的一组规则；语言L(G)中的每一个句子w，是由G的开始符号S经推导得到的，完全由终结符号组成的字。

非终结符号是引起推导继续进行的中间符号，在推导进行到某一步时，如果再没有非终结符号留在推导的结果中，则称推导成功。

在语言的设计和编译器的编写方面，文法都提供了极大的优点：a) 文法给出了精确的，也易于理解的语言语法说明。

b) 对于某些文法类，可以自动产生高效的分析器。

额外的好处是，分析器的构造过程可以揭露出语法的二义性和其它难于分析的结构，这些问题在语言和它的编译器的最初设计阶很可能没有发现。

c) 设计得漂亮的文法，把结构加于程序设计语言，这些结构对把源程序翻译成为正确的目标代码和错误诊断都是有用的。

把以文法为基础的翻译的描述转变成程序的开发工具也是存在的。

d) 语言也是逐渐完善的，需要补充新的结构和完成附加的任务。

如果存在以文法为基础的语言的实现，这些新结构的加入就更方便。

2.2巴科斯范式（BNF）巴科斯范式(Backus Normal Form,BNF)是描述语法规则的一种形式方法，在该方法中，使用如下符号：< > 非终结号::= 定义符| 或者{ } 括号内的成份可以重复出现多次，也可以不出现[ ] 括号内的成份为任选项，可以出现一次或不出现例如C语言中IF－THEN语句可以表示成：<IF语句> ::= IF <布尔表达式> THEN <语句> [<ELSE语句>]用巴科斯范式的形式表示文法的优点是简洁、清楚并容易被理解。

3．编译程序的实现环境Parse Generator简介及其使用编译器生成工具----Parse Generator 基于Windows平台，它集成了词法生成器ALEX和语法生成器AYACC，并提供了较为强大的类库。

其主要优点体现在以下几个方面：●可以视一个编译程序为一个Project，集成Alex和Ayacc文件的环境有利于整体调试和开发。

且编辑界面友好，利于初学者使用。

●.l文件（lex文件）和.y文件（yacc文件）可生成为标准的C原代码，也可生成Visual C++和Borland C++格式的原代码。

这对习惯与BC或VC编程的程序员，无疑是极大的方便。

●ALex和AYacc的表驱动代码隐藏在联接库中。

库在程序LINK的时候连入系统中。

这在程序编译的效率和灵活性两个方面都有较大贡献。

●ALex和AYacc的原代码和和生成的目标代码（C或C++）可以建立语句的对应，这对生成代码的调试提供很大方便。

实验中的编译程序采用将ALex和AYacc文件转化为Visual C++格式的代码。

现将程序中使用的联接库中主要类和函数作一介绍。

●类yylexer ---- 所有词法分析器类的基类yylexer类提供由Alex生成的C++词法分析器的一切基本功能。

yylexer是一个抽象类，要使用它，必须继承出自己的类，并实现抽象函数yylex 和yyaction。

C--编译器程序中的词法分析器类是其子类C_Lexer类。

●类yyparser ---- 所有语法分析器类的基类yyparser类提供由AYacc生成的C++语法分析器的一切基本功能。

yyparser是一个抽象类，要使用它，必须继承出自己的类，并实现抽象函数yywork 和yyparseaction。

C--编译器程序中的语法分析器类是其子类C_Parser类。

五．详细设计1．功能说明输入：类C语言纯文本源程序。

输出：·目标机为具有8086+处理器的MSDOS系统下的二进制可执行代码。

·PC Assembly Language汇编语言源代码以供分析使用。

本编译程序实现的主要功能如下表所示：2．词法分析器（lexer）2．1 正规式和DFA·ε和φ都是Σ上的正规式，它们所表示的正规集分别为{ε}和φ·任何a∈Σ，a是Σ上的一个正规式，它所表示的正规集为{a}·假定U和V都是Σ上的正规式，它们所表示的正规集分别记为L(U)和L(V)，那么，(U|V)、(U.V)和(U)*也都是正规式，它们所表示的正规集分别为L(U)∪L(V)、L(U)L(V)和(L(U))*。

仅由有限次使用上述三步骤而定义的表达式才是Σ上的正规式，仅由这些正规所表示的字集才是Σ上的正规集。

正规式可以有效地描述词法，而确定的有限自动机(DFA)能准确地识别正规集，执行词法分析的功能。

2．2 利用有限自动机进行词法分析词法分析是整个编译过程的第一阶段，它将字符序列转化为单词序列。

识别单词的基本方法是根据词法定义构造有限自动机即描述语言结构特征的状态转换图。

例如对于十进制整数正规定义：[1-9]+[0-9]*可以构造如图3所示的有限自动机。

图 3 识别十进制整数的有限自动机其中状态2为接收态，若对于一个字符序列有限自动机可以到达2状态，则说明一个整数已被识别出来。

词法分析器构造程序LEX正是根据这一原理工作的。

构造词法分析器的主要任务是设计词法的正规定义和相关的动作。