• 下载我的编译器 - 175.75 KB

引言

这是我学士学位课程期间的项目。我设计了部分 C 编译器。虽然它是 C 编译器，但所有编译器的概念几乎相同。我使用了 LEX 和 YACC 工具来生成词法和语法分析。我也做了代码优化阶段。并且我在 X86 机器中生成了最终代码，并使用 MASM 汇编器运行了代码。它非常成功。

编译器是一种程序，它读取用一种语言（称为源语言）编写的程序，并将其翻译成另一种等效语言（称为目标语言）的程序。它报告在将源代码翻译成目标代码期间检测到的错误。源程序可以是任何编程语言。这里我们的源程序是 ANSI C 程序。目标程序可以是汇编语言代码或机器代码。这里我们为给定源代码生成了 8086 汇编级代码。编译器的第一个阶段，词法分析器，是使用 Linux 提供的 LEX 工具实现的。第二个阶段，语法分析器，是使用 Linux 提供的 Yacc 工具实现的。第三个阶段，语义分析器，和第四个阶段，中间代码生成，是作为解析器中生产规则对应动作的一部分执行的。由此产生的中间代码是 8086 汇编代码，它通过使用 MASM 转换为可执行文件。

编译器的阶段

编译器主要有六个阶段。前四个阶段：词法分析、语法分析、语义分析和中间代码生成是分析阶段的一部分，它们是与机器无关的阶段。而另外两个阶段：代码优化和代码生成是合成阶段的一部分，它们是高度依赖于机器的阶段。

编译器的阶段是

一）词法分析

词法分析，或称线性分析，或扫描，是指源程序组成的字符流从左到右读取，并分组为具有集体意义的“词法单元”（token）。分隔词法单元字符的空格和程序中出现的注释语句通常会在词法分析期间被消除。将编译的分析阶段分为词法分析和解析有几个原因。

1) 简洁的设计也许是最重要的考虑因素。将词法分析与语法分析分离通常可以简化其中一个或两个阶段。

例如，一个包含注释和空白约定解析器比一个可以假设注释和空白已经被词法分析器移除的解析器要复杂得多。如果我们正在设计一种新语言，分离词法和语法约定可以导致更清晰的整体语言设计。

2) 编译器效率得到提高。单独的词法分析器允许我们为任务构建一个专用且可能更高效的处理器。大量时间
花费在读取源程序并将其划分为词法单元上。用于读取输入字符和处理词法单元的专用缓冲技术可以显著加快编译器的性能。

3) 编译器可移植性得到增强。输入字母的特殊性和其他特定于设备的异常可以限制在词法分析器中。特殊或非标准符号的表示可以隔离在词法分析器中。

当词法分析器和解析器分离时，已经设计了专门的工具来帮助自动化它们的构建。LEX 是一种广泛使用的工具，用于为各种语言指定词法分析器。我们称该工具为 LEX 编译器，其输入规范为 LEX 语言。LEX 通常以词法分析器的方式使用，通过创建 LEX 语言的程序 lex.l 来准备。然后，lex.l 通过 LEX 编译器运行以生成 C 程序 lex.yy.c。程序 lex.yy.c 由从 lex.l 的正则表达式构建的转换图的表格表示组成，以及一个使用该表识别词法单元的标准例程。lex.l 中与正则表达式相关的动作是 C 代码片段，并直接传递到 lex.yy.c。最后，lex.yy.c 通过编译器运行以生成目标程序 a.out，它是一个词法分析器，将输入流转换为词法单元序列。

请参考图：lex_interaction 和 lexical_analyzer

LEX 规范

一个 LEX 程序由三部分组成

声明
    %%
转换规则
    %%
辅助过程

声明部分包括变量、显式常量和正则表达式的声明。（显式常量是声明用于表示常量的标识符。）正则表达式用作转换规则中出现的正则表达式的组成部分。LEX 程序的转换规则是 P1 {action1} 形式的语句
P2 {action2}
….. ………..
Pn {actionn}
   
其中每个 P1 是一个正则表达式，每个 action1 是一个程序片段，描述词法分析器在模式 P1 匹配词素时应采取的动作。在 Lex 中，动作是用 C 编写的；然而，一般来说，它们可以是任何实现语言。
 

二）语法分析（我已附上我们的语法分析器规则和 YACC 用法）

语法分析，或称层次分析，其中字符或词法单元被层次化地分组为具有集体意义的嵌套集合。层次分析也称为解析，涉及将源程序的词法单元分组为语法短语，这些短语被编译器用于合成输出。通常，源程序的语法短语由解析树表示。

三）语义分析

语义分析，在此阶段执行某些检查以确保程序的组件有意义地组合在一起。语义分析阶段检查源程序的语义错误，并为后续的代码生成阶段收集类型信息。它使用语法分析阶段确定的层次结构来识别表达式和语句的运算符和操作数。

语义分析的一个重要组成部分是类型检查。在这里，编译器检查每个运算符是否具有源语言规范允许的操作数。

此外，编译器必须检查源程序是否遵循源语言的语法和语义约定。这种检查，称为静态检查，确保
某些类型的编程错误将被检测并报告。在目标程序运行时进行的检查称为动态检查。原则上，任何检查都可以动态完成，如果目标代码将元素的类型与元素的值一起携带。健全的系统消除了对类型错误进行动态检查的需要，因为它允许我们静态地确定这些错误在目标程序运行时不会发生。也就是说，如果一个健全的系统为一个程序部分分配了除 type_error 之外的类型，那么当该程序部分的目标代码运行时，就不会发生类型错误。如果编译器能够保证它接受的程序将无类型错误地执行，则该语言是强类型的。
  

静态检查包括

1. 类型检查：如果将运算符应用于不兼容的操作数，编译器应报告错误。
2. 控制流检查：导致控制流离开构造的语句必须有某个地方可以转移控制流。
3. 唯一性检查：在某些情况下，对象必须只定义一次。
4. 名称相关检查：有时，相同的名称必须出现两次或多次。编译器必须检查两个地方都使用了相同的名称。
 

四）中间代码生成

在语法和语义分析之后，一些编译器会生成源程序的显式中间表示。我们可以将这种中间表示视为抽象机器的程序。这种中间表示应该具有两个重要的特性：它应该易于生成，并且易于翻译成目标程序。

中间表示可以有多种形式。我们考虑8086汇编语言的一种中间形式，它类似于三地址码。这种中间形式具有几个特性
1) 除了赋值之外，每条指令最多只有一个运算符。因此，生成这些指令时，编译器必须决定操作的执行顺序。
2) 编译器必须生成一个临时名称来保存每条指令计算的值。
3) 某些指令可能少于三个操作数。

在编译器的分析-合成模型中，前端将源程序翻译成中间表示，后端从该中间表示生成目标代码。

目标语言的细节尽可能地限制在后端。尽管源程序可以直接翻译成目标语言，但使用独立于机器的中间形式有一些好处：
1. 易于重新定位；通过将新机器的后端连接到现有的前端，可以为不同的机器创建编译器。
2. 可以对中间表示应用独立于机器的代码优化器。

五）代码优化

代码优化阶段试图改进中间代码，以便生成运行更快的机器代码。代码优化的程度存在很大差异
不同的编译器执行。在那些做得最多的编译器中，被称为“优化编译器”，编译器的大量时间都花在了这个阶段。然而，存在
一些简单的优化可以显著提高目标程序的运行时间，而不会过多地减慢编译速度。

六）机器代码生成

编译器的最后阶段是生成目标代码，通常包括可重定位机器代码或汇编代码。为程序使用的每个变量选择内存位置。然后，每条中间指令都转换为执行相同任务的机器指令序列。一个关键方面是将变量分配给寄存器。

符号表管理

编译器的基本功能是记录源程序中使用的标识符，并收集每个标识符各种属性的信息。这些属性可能提供有关为标识符分配的存储空间（如果适用）、其类型、其作用域的信息，以及对于过程名称，诸如参数的数量和类型、传递每个参数的方法以及函数返回值的类型（如果函数返回任何值）等信息。

符号表是一种数据结构，包含每个标识符的记录，其中包含标识符属性的字段。该数据结构允许我们快速查找每个标识符的记录，并快速存储或检索该记录中的数据。

当词法分析器检测到源程序中的标识符时，该标识符将被输入到符号表中。但是，标识符的属性通常无法在词法分析期间确定。其余阶段将有关标识符的信息输入到符号表中，然后以各种方式使用此信息。

错误检测与报告

每个阶段都可能遇到错误。但是，在检测到错误后，一个阶段必须以某种方式处理该错误，以便编译可以继续，从而检测源程序中的更多错误。一个在发现错误时就停止的编译器不如它可以提供帮助那么有用。
语法和语义分析阶段通常处理编译器可检测到的大部分错误。词法阶段可以检测到输入中剩余字符不构成语言中任何词法单元的错误。词法单元流违反语言结构规则（语法）的错误由语法分析阶段确定。在语义分析期间，编译器试图检测具有正确语法结构但对所涉及操作没有意义的构造。

来源

1. 编译器：原理、技术和工具，作者：
阿尔弗雷德·V·阿霍 (Alfred V. Aho)
拉维·塞西 (Ravi Sethi)
杰弗里·D·乌尔曼 (Jeffery D. Ullman)
2. C 语言编译器设计，作者：艾伦·I·霍卢布 (Allen I. Holub)
3. Linux LEX 和 Yacc 手册页