一个简单的 C 语言编译器一小组成员朱嘉俊（3991102161） 计算机 996王筱（3991102168） 计算机 996朱杭（3991102162） 计算机 996朱林（3991102094） 计算机 994 二运行方式在 DOS 环境下运行:Cminus.exe -h三概述经过一段时间的学习，我们在初步掌握了编译器的基本原理以后，设计了一个具有基本编译功能的编译器。该编译器接受类 C 语言语法的源代码输入，输出结果是 PC 机的汇编源代码。在捆绑了宏汇编编译器 Masm 后，即可直接生成 MSDOS下的二进制可执行文件。为方便起见，以下简称为 C语言编译器。本编译器实现了基本高级语言所必须的语法要素，包括简单变量声明、函数的实现、整数和字符串运算、条件判断语句和循环语句及跳转语句、基本代数运算、赋值等，还支持汇编语言嵌入。本编译器是利用编译器生成器 Parse Generator 和VC6.0 在 Windows 平台上实现的，并开发了一个基于 Windows 平台的 32 位编译集成开发环境 CompilerMan， 提供了关键字彩色提示、出错同屏提示、出错代码跳转等较为完善方便的功能。由于编译程序本身涉及到词法分析、语法分析、代码生成、错误恢复和优化等诸多模块，要在实验中做到面面俱到不太可能，所以本编译器不可避免的会存在各种问题，但作为一个具有基本功能的、可扩充的系统，完全达到了巩固编译原理的理论知识，并将其运用于实践的目的。四背景编译程序，就是一种具有编撰和翻译功能的程序。人们要用计算机来解决问题，首先面临的一个问题，就是要告诉计算机解决什么问题，或者告诉计算机如何解决这个问题。这就涉及到用什么样的语言来描述的问题，人所习惯的自然语言和计算机认识的机器语言有很大的差别，用机器语言来描述人想解决的问题十分不便，因而，计算机科学家设计一些人们比较习惯的语言来描述要解决的问题，称之为高级语言。用语言来描述的问题，统称为程序。然而，用高级语言写的程序，不能被计算机所直接认识和理解，必须经过等价的转换，变成机器能理解并执行的机器语言的程序。进行这种等价转换工作的工具，就是编译程序。1编译程序的结构编译程序是很复杂的，但它可被分为相对独立的几个部分，每个部分承担专门的工作，各部分间互相共享传送数据。把编译程序分解成较小的部分，不仅便于开发、调试，而且便于编译程序的移植。一个典型的编译程序通常具有如图 1 的结构。图 1 编译器基本结构1.1 词法分析词法分析负责对源程序的字符串进行扫描和分解，根据构词法将字符流(Character Stream)转化成单词流(Token Stream)。符号表管理词法分析器语法分析器语义分析器优化器代码生成器单词语法结构中间语言IRIR目标机器码出错处理例如对于 C-语句：x = y + z m * 10;词法分析的结果是：ID ASSIGN ID ADD ID SUB ID MUL NUM SEMI 构词的规则就是词法，例如标识符(ID)可定义为以字母开头，后面跟零个或任意个字母或数字的序列。词法分析程序就根据词法构造有限自动机来识别每一个单词，将产生的单词交给语法分析程序。1.2 语法分析语法分析模块的任务是根据文法规则把单词序列分解成各类语法单位，识别出一个一个句子，例如对前面的语句进行语法分析可得到如图 2 的分析树。如果输入单词不能构成语法树，则说明有语法错误。常见的语法分析方法分为自顶向下分析和自底向上分析两大类。在 C-编译器中采用了一种自底向上的方法，即 LR 方法。图 2 语法分析树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形式语言简介赋值语句变量 = 表达式项 + 表达式项 -IDID表达式*项ID项NUM2.1 文法和语言文法是产生语言的规则，它可定义为：对于一个四元式 G=(VN，V T，S ，P)，其中(1) VN 是非终结符号的有限集合(2) VT 是终结符号的有限集合，且 VTV N(3) 开始符号 S，SV N(4) 一组产生式 P，P 中的每一个产生式都具有如下形式：uv，u(V NV T)+且至少要有一个非终结符号， v(V NV T)*则 G 表示一个文法。乔姆斯基(Noam Chmosky)把文法分成四类：0 型文法又称无约束文法，产生式的形式为 ab，a 、b 是任意字符串。 1 型文法又称上下有关文法，产生式形式为 ab，且|a|b|。2 型文法又称上下文无关文法(Context-Free Grammar)，产生式形式为 Aa ，a (V NV T)*，AV N。3 型文法又称正规文法，它的产生式左部是一个非终结符号，右部最多只有一个非终结符号且在右部的最左端或最右端。通常程序设计语言的文法属于 2 型文法，可被下推机(Pushdown Automaton)识别。语言定义为 L(G)=w|S=*w,wV T*，可见，文法 G 中的 VT 相当于产生语言的字母表，G 中的一组产生式是产生语言的一组规则；语言 L(G)中的每一个句子w，是由 G 的开始符号 S 经推导得到的，完全由终结符号组成的字。非终结符号是引起推导继续进行的中间符号，在推导进行到某一步时，如果再没有非终结符号留在推导的结果中，则称推导成功。在语言的设计和编译器的编写方面，文法都提供了极大的优点：a) 文法给出了精确的，也易于理解的语言语法说明。b) 对于某些文法类，可以自动产生高效的分析器。额外的好处是，分析器的构造过程可以揭露出语法的二义性和其它难于分析的结构，这些问题在语言和它的编译器的最初设计阶很可能没有发现。c) 设计得漂亮的文法，把结构加于程序设计语言，这些结构对把源程序翻译成为正确的目标代码和错误诊断都是有用的。把以文法为基础的翻译的描述转变成程序的开发工具也是存在的。d) 语言也是逐渐完善的，需要补充新的结构和完成附加的任务。如果存在以文法为基础的语言的实现，这些新结构的加入就更方便。 2.2 巴科斯范式 （BNF）巴科斯范式(Backus Normal Form,BNF)是描述语法规则的一种形式方法，在该方法中，使用如下符号：非终结号:= 定义符| 或者 括号内的成份可以重复出现多次，也可以不出现 括号内的成份为任选项，可以出现一次或不出现例如 C 语言中 IFTHEN 语句可以表示成：:= IF THEN 用巴科斯范式的形式表示文法的优点是简洁、清楚并容易被理解。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 汇编语言源代码以供分析使用。本编译程序实现的主要功能如下表所示：功能 备注支持以下数据类型：int 整型char 字符型char 字符数组int 整型数组整型为有符号 16 位数。字符型为 8 位数。数组的下标允许为任何合法的表达式。经过简单扩充后，即可实现长整型，无符号整型。支持以下数据操作：+ 加法- 减法* 乘法/ 除法% 取余+ 自加 1- 自减 1* 乘方&, | 位与，位或 异或 位非&,| 逻辑与，逻辑或！ 逻辑非,= 关系比较运算=，！= 关系比较运算 算术移位+-*/%=，*=， 多达 12 种赋值=，&=， 语句|=，=，=支持以关键字_asm 前导的形式为_asm 的嵌入汇编代码(EMBEDED ASSEMBLY)。对嵌入汇编的支持大大提高的语言的可用性，一定程度弥补了系统函数较少的缺憾。提供系统级库函数：void print(/*表达式*/,% t)；支持字符串，字符，整型三种类型的变量输出，包括任何合法表达式的值。支持循环，转移，判断分支的程序设计，支持if, if.else,if.else if.forwhile, do.whilegoto .语句。支持 Label，允许在任何语句前定义Label 作为控制转移目的地。for 和 while 语句支持 break, continue 流程