第1章 开始制作编译器

本章先讲述本书以及编译器的概要，之后说明本书的示例程序C♭的安装方法。

1.1 本书的概要

这节将对本书的概要进行说明。

本书的主题

本书的主题是编译器。编译器（compiler）是将编程语言的代码转换为其他形式的软件。这种转换操作就称为编译（compile）。

实际的编译器有C语言的编译器GCC（GNU Compiler Collection）、Java语言的编译器javac（Sun公司）等。

像编译器这样复杂的软件，仅仅笼统地介绍一下是很难让人理解的，所以本书将从头开始制作一门语言的编译器。通过实际地设计、制作编译器，使读者对编译器产生具体、深刻的认识。这样通过实践获得的知识，在其他语言的编译器上也是通用的。

本书制作的编译器

本书将从头开始制作C♭这门语言的编译器。

C♭是笔者为本书设计的语言，基本上可以说是C语言的子集。它在C语言的基础上进行了简化，并加入了一些时兴的功能，使得与之配套的编译器制作起来比较容易。笔者最初想直接使用C语言的，但是C语言的编译器无论写起来还是读起来都非常难，所以最终放弃了。关于C♭的标准，第2章会详细说明。

使用本书的C♭编译器编译出的程序是在PC的Linux平台上运行的。最近，借助虚拟机以及KNOPPIX等，Linux环境已经很容易搭建了。请读者一定要实际用C♭编译器编译程序，并尝试运行一下。

编译示例

接着让我们赶紧进入编译器的正题。

首先我们来思考一下编译究竟是一种什么样的处理。这里以使用GCC处理代码清单1.1中的C语言程序为例进行说明。实际编译下面的程序时，需要重新安装GCC。

代码清单1.1 hello.c

#include <stdio.h>
int
main（int argc, char ＊＊argv）
{
    printf（"Hello, World! \n"）;  /＊ 打个招呼 ＊/
    return 0;
}

本书的读者对象是已经掌握C语言知识的人，所以理应编译过C语言程序。但保险起见，还是确认一下编译的步骤。使用GCC处理上述程序，需要输入如下命令。

$ gcc hello.c -o hello

这样便生成了名为hello的文件，这是个可执行文件（executable file）。

接着输入下面的命令，运行刚才生成的hello命令。

$ ./hello
Hello, World!

通过这样操作来运行程序本身没有问题，但从过程来看，还是有一些不明确的地方。

●可执行文件是怎样的文件

●gcc命令是如何生成可执行文件的

●可执行文件hello是经过哪些步骤运行起来的

让我们依次看一下上述疑问。

可执行文件

首先从GCC生成的可执行文件是什么说起。

说到现代的Linux上的可执行文件，通常是指符合ELF（Executable and Linking Format）这种特定形式的文件。ls、cp这些命令（command）对应的实体文件都是可执行文件，例如/bin/ls和/bin/cp等。

使用file命令能够查看文件是否符合ELF的形式。例如，要查看/bin/ls文件是不是ELF，在shell中输入如下命令即可。

$ file /bin/ls
/bin/ls: ELF 32-bit LSB executable, Intel 80386, version 1（SYSV）, for GNU/Linux
2.4.1, dynamically linked（uses shared libs）, for GNU/Linux 2.4.1, stripped

如果像这样显示ELF......executable，就表示该文件为ELF的可执行文件。根据所使用的Linux机器的不同，可能显示ELF 64-bit，也可能显示ELF 32-bit MSB，这些都是ELF的可执行文件。

ELF文件中包含了程序（代码）以及如何运行该程序的相关信息（元数据）。程序（代码）就是机器语言（machine language）的列表。机器语言是唯一一种CPU能够直接执行的语言，不同种类的CPU使用不同的机器语言。

例如，现在基本上所有的个人计算机使用的都是Intel公司的486这款CPU的后续产品，486有着自己专用的机器语言。Sun公司的SPARC系列CPU使用的是其他机器语言。IBM公司的PowerPC系列CPU使用的又是不一样的机器语言。486的机器语言不能在SPARC上运行，反过来SPARC的机器语言也不能在486上运行。这点在SPARC和PowerPC、486和PowerPC上也一样。

GCC将C语言的程序转化为用机器语言（例如486的机器语言）描述的程序。将机器语言的程序按照ELF这种特定的文件格式注入文件，得到的就是可执行文件。

编译

那么gcc命令是如何将hello.c转换为可执行文件的呢？

由hello.c这样的单个文件来生成可执行文件时，虽然只需要执行一次gcc命令，但实际上其内部经历了如下4个阶段的处理。

1．预处理

2．（狭义的）编译

3．汇编

4．链接

上述处理也可以统称为编译，但严谨地说第2阶段进行的狭义的编译才是真正意义上的编译。本书中之后所提到的编译，指的就是狭义的编译。这4个阶段的处理我们统称为build。

下面对这4个阶段的处理的作用进行简单的说明。

预处理

C语言的代码首先由预处理器（preprocessor）对#include和#define进行处理。具体来说，读入头文件，将所有的宏展开，这就是预处理（preprocess）。预处理的英文是pre-process，就是前处理的意思。这里的“前”是在什么之前呢？当然是编译之前了。

预处理的内容近似于sed命令和awk命令这样的纯文本操作，不考虑C语言语法的含义。

狭义的编译

接着，编译器对预处理器的输出进行编译，生成汇编语言（assemble language）的代码。一般来说，汇编语言的代码的文件扩展名是“.s”。

汇编语言是由机器语言转换过来的人类较易阅读的文本形式的语言。机器语言是以CPU的执行效率为第一要素设计的，用二进制代码表示，每一个bit都有自己的含义，人类很难理解。因此，一般要使用与机器语言直接对应的汇编语言，以方便人们理解。

汇编

然后，汇编语言的代码由汇编器（assembler）转换为机器语言，这个处理过程称为汇编（assemble）。

汇编器的输出称为目标文件（object file）。一般来说，目标文件的扩展名是“.o”。

Linux中，目标文件也是ELF文件。既然都是ELF文件，那么究竟是目标文件还是可执行文件呢？这不是区分不了了吗？这个不用担心。ELF文件中有用于提示文件种类的标志。例如，用file命令来查看目标文件，会像下面这样显示ELF...relocatable，据此就能够将其和可执行文件区分开。

$ file t.o
t.o: ELF 32-bit LSB relocatable, Intel 80386, version 1（SYSV）, not stripped

链接

目标文件本身还不能直接使用，无论是直接运行还是作为程序库（library）文件调用都不可以。将目标文件转换为最终可以使用的形式的处理称为链接（link）。使用程序库的情况下，会在这个阶段处理程序库的加载

例如，假设Hello, World！程序经过编译和汇编生成了目标文件hello.o，链接hello.o即可生成可执行文件。生成的可执行文件的默认文件名为a.out，可以使用gcc命令的-o选项来修改输出的文件名。

顺便提一下，通过链接处理生成的并不一定是可执行文件，也可以是程序库文件。程序库文件相关的话题将在第19章中详细说明。

build过程总结

如上所述，C语言的代码经过预处理、编译、汇编、链接这4个阶段的处理，最终生成可执行文件。图1-1中总结了各个阶段的输出文件，我们再来确认一下。

图1-1 生成可执行文件的过程

本书将对这4个处理阶段中除预处理之外的编译、汇编和链接进行说明。

程序运行环境

build的过程以链接为终点，但本书并不仅仅局限于build的过程，还会涉及build之后的程序运行环境相关的话题。从代码的编写、编译、运行到运行结束，理解上述全部过程是我们的目标。换言之，从编写完程序到该程序被运行，所有环节本书都会涉及（图1-2）。

图1-2 程序运行的全过程

为何除了build的过程之外，本书还要涉及程序运行的环节呢？这是因为在现代编程语言的运行过程中，运行环境所起的作用越来越大。

首先，链接的话题并非仅仅出现在build的过程中。如果使用了共享库，那么在开始运行程序时，链接才会发生。最近广泛使用的动态加载（dynamic load），就是一种将所有链接处理放到程序运行时进行的手法。

其次，像Java和C#这种语言的运行环境中都有垃圾回收（Garbage Collection, GC）这一强大的功能，该功能对程序的运行有着很大的影响。

再次，在Sun的Java VM等具有代表性的Java的运行环境中，为了提高运行速度，采用了JIT编译器（Just In Time compiler）。JIT编译器是在程序运行时进行处理，将程序转换为机器语言的编译器。也就是说，Java语言是在运行时进行编译的。

既然涉及了这样的话题，仅了解build的过程是不够的，还必须了解程序的运行环境。不掌握包含运行环境在内的整个流程，就不能说完全理解了程序的动作。今后，无论是理解程序还是制作编译器，都需要了解从build到运行环境的整体流程。

1.2 编译过程

这一节将对狭义的编译的内部处理过程进行介绍。

编译的4个阶段

狭义的编译大致可分为下面4个阶段。

1．语法分析

2．语义分析

3．生成中间代码

4．代码生成

下面就依次对这4个阶段进行说明。

语法分析

一般我们所说的编写程序，就是把代码写成人类可读的文本文件的形式。像C和Java这样，以文本形式编写的代码对人类来说的确易于阅读，但并不是易于计算机理解的形式。因此，为了运行C和Java的程序，首先要对代码进行解析，将其转换为计算机易于理解的形式。这里的解析（parse）也称为语法分析（syntax analyzing）。解析代码的程序模块称为解析器（parser）或语法分析器（syntax analyzer）。

那么“易于计算机理解的形式”究竟是怎样的形式呢？那就是称为语法树（syntax tree）的形式。顾名思义，语法树是树状的构造。将代码转化为语法树形式的过程如图1-3所示。

图1-3 语法树

语义分析

通过解析代码获得语法树后，接着就要解析语法树，除去多余的内容，添加必要的信息，生成抽象语法树（Abstract Syntax Tree, AST）这样一种数据结构。上述处理就是语义分析（semantic analysis）。

语法分析只是对代码的表象进行分析，语义分析则是对表象之外的部分进行分析。举例来说，语义分析包括以下这些处理。

●区分变量为局部变量还是全局变量

●解析变量的声明和引用

●变量和表达式的类型检查

●检查在引用变量之前是否进行了初始化

●检查函数是否按照定义返回了结果

上述处理的结果都会反映到抽象语法树中。语法分析生成的语法树只是将代码的构造照搬了过来，而语义分析生成的抽象语法树中还包含了语义信息。例如，在变量的引用和定义之间添加链接，适当地增加类型转换等命令，使表达式的类型一致。另外，语法树中的表达式外侧的括号、行末的分号等，在抽象语法树中都被省略了。

生成中间代码

生成抽象语法树后，接着将抽象语法树转化为只在编译器内部使用的中间代码（Intermediate Representation, IR）。

之所以特地转化为中间代码，主要是为了支持多种编程语言或者机器语言。

例如，GCC不仅支持C语言，还可以用来编译C++和Fortran。CPU方面，不仅是Intel的CPU，还可以生成面向Alpha、SPARC、MIPS等各类CPU的机器语言。如果要为这些语言和CPU的各种组合单独制作编译器，将耗费大量的时间和精力。Intel CPU用的C编译器、Intel CPU用的C++编译器、Intel CPU用的Fortran编译器、Alpha用的C编译器……要制作的编译器的数量将非常庞大（图1-4）。

图1-4 不使用中间代码的情况

而如果将所有的编程语言先转化为共同的中间代码，那么对应一种语言或一种CPU，只要添加一份处理就够了（图1-5）。因此支持多种语言或CPU的编译器使用中间代码是比较合适的。例如GCC使用的是一种名为RTL（Register Transfer Languange）的中间代码。

图1-5 使用中间代码的情况

根据编译器的不同，也存在不经过中间代码，直接从抽象语法树生成机器语言的情况。本书制作的C♭编译器最初并没有使用中间代码，后来发现使用中间代码的话，代码的可读性和简洁性都要更胜一筹，所以才决定使用中间代码。

解析代码转化为中间代码为止的这部分内容，称为编译器的前端（front-end）。

代码生成

最后把中间代码转换为汇编语言，这个阶段称为代码生成（code generation）。负责代码生成的程序模块称为代码生成器（code generator）。

代码生成的关键在于如何来填补编程语言和汇编语言之间的差异。一般而言，比起编程语言，汇编语言在使用上面的限制要多一些。例如，C和Java可以随心所欲地定义局部变量，而汇编语言中能够分配给局部变量的寄存器只有不到30个而已。处理流程控制方面也只有和goto语句功能类似的跳转指令。在这样的限制下，还必须以不改变程序的原有语义为前提进行转换。

优化

除了之前讲述的4个阶段之外，现实的编译器还包括优化（optimization）阶段。

现在的计算机，即便是同样的代码，根据编译器优化性能的不同，运行速度也会有数倍的差距。由于编译器要处理相当多的程序，因此在制作编译器时，最重要的一点就是要尽可能地提高编译出来的程序的性能。

优化可以在编译器的各个环节进行。可以对抽象语法树进行优化，可以对中间代码的代码进行优化，也可以对转换后的机器语言进行优化。进一步来说，不仅是编译器，对链接以及运行时调用的程序库的代码也都可以进行优化。

总结

经过上述4个阶段，以文本形式编写的代码就被转换为了汇编语言。之后就是汇编器和链接器的工作了。

本书中所制作的编译器主要实现上述4个阶段的处理。

1.3 使用C♭编译器进行编译

本节我们来了解一下C♭编译器的使用方法。

C♭编译器的必要环境

使用C♭编译器所需要的软件有如下3项。

1． Linux

2． JRE（Java Runtime Environment）1.5以上版本

3． Java编译器（非必需）

首先，要想运行C♭编译器build的程序，需要运行在Intel CPU（包括AMD等的同架构CPU）上的Linux。这里对Linux的发行版本没有特别的要求，大家可以选择喜欢的Linux发行版本来安装。本书不对Linux的安装方法进行说明。

另外，虽然这里以在32位版本的Linux上运行为前提，但通过使用兼容模式，64位的Linux也可以运行32位的程序。

运行C♭编译器需要JRE（Java运行时环境）。本书不对JRE的安装进行说明，请根据所使用的Linux发行版本的软件安装方法进行安装。

最后，本书制作的C♭编译器是用Java实现的。因此build C♭编译器本身需要Java的编译器。如果只是使用C♭编译器的话，则不需要Java编译器。

安装C♭编译器

接着说一下C♭编译器的安装方法，在此之前请先安装好Linux和Java运行环境。

首先下载C♭编译器的jar文件。

下载的文件是用tar和gzip打包压缩的，请使用如下命令进行解压。

$ tar xzf cbc-1.0.tar.gz

解压后会生成名为cbc-1.0的目录，进入该目录。接着，如下切换到超级用户（root），运行install.sh，这样安装就完成了。所有的文件都会被安装到/usr/local的目录下。

$ cd cbc-1.0
$ su
# ./install.sh

没有root权限的用户，也可以安装到自己的home目录下面。如下运行install.sh，就可以把文件安装到$HOME/cbc目录下面。

$ prefix=$HOME/cbc ./install.sh

C♭的Hello, World!

安装完C♭的编译器后，让我们来试着build一下C♭的Hello, World！程序吧。C♭的Hello, World！程序如代码清单1.2所示。

代码清单1.2 C♭的Hello, World!（hello.cb）

import stdio;
int
main（int argc, char ＊＊argv）
{
    printf（"Hello, World! \n"）;
    return 0;
}

build文件时，先进入hello.cb所在的目录，然后在shell中输入如下命令即可。

$ cbc hello.cb

和gcc不同的是，cbc不需要输入任何选项，输出的文件名就为hello。因此，只要cbc命令正常结束，应该就能生成可执行文件hello。确认hello已经生成后，如下运行该文件。

$ ./hello
Hello, World!

如果像这样显示了Hello, World!，就说明cbc编译器运行正常。并且上述hello命令是纯粹的Linux原生应用程序，在没有安装cbc的Linux机器上也可以正常运行。

下一章将对C♭语言和cbc进行说明。