实现一个编译器需要实现哪些流程？

时间：2024-03-12 12:04:20    点击量：

实现一个编译器需要实现哪些流程？

http://book.douban.com/subject/3296317/

有本书叫编译原理，可以看看。

实现编译器可大可小，而根据语言的不同，其复杂度也是不尽相同，甚至于说区别很大。而对于一个普通的编译器来说，按照编译原理来说，你需要考虑的是以下几大块。

1. 词法分析器

将输入的字符流转换为特定的单词。这一步是识别组合字符的过程，识别出数字，标识符，关键字等过程就在于此。若我们这里设计的编译器不包含预处理器，那么，在这里还需要做一些预处理的过程，如识别出注释，并将其忽略掉。这一步的输入是字符，输出是单词。

2. 语法分析器

将输入的单词流转换为特定的语句。这里面需要做的就是组合单词，并按照特定的语法规则去匹配出合法的语句。如 if （ bool-expression ）{ statement }就是简单的if 语句，而所需要的就有关键字 if ，符号 ( ，表达式，符号 ）， 符号 ｛ ， 合法的语句， 符号 ｝。而这里的表达式与合法语句则又有合法的单词流组成。而我们把这一步处理完毕后，我们流下我们所需要关注的核心内容。如if 语句，我们传递下去后，我们就不需要符号 （ ） ｛ ｝等了。而表示这样的核心内容则是抽象语法树（Abstract Syntax Tree ，简称AST）。

3. 语义分析

在进行下一步前，我们往往会对AST进行分析。如类型匹配，这样的语意是否正确等。如简单的int i="hello"; 那么我们在遍历AST的时候，则会识别出来类型问题。而在这里我们往往需要一个符号表来记录变量以及对应的类型，然后分析AST的时候来进行查询与处理等。这一步的输入是AST，输出依然是AST。

4. 代码生成

这一步处于来编译器前端与后端的交界处。一般来说，我们会设计一个抽象于机器平台的中间语言( Intermediate Representation，简称IR ) 以便于进行后续机器无关的优化（如死代码消除，函数内联优化，for循环展开等）以及生成多机器平台的底层代码。在这一方面，往往有两个选择，一个是基于栈的IR，一个是基于寄存器的IR。前者易于编程与操作，而后者则性能更好。一般来说，很多编译型语言的IR都是基于寄存器的，如LLVM IR，微软编译器的中间语言等，而一些虚拟机平台的则是基于栈的。然而凡是也有例外，如在鲸书曾写道了我司编译器的WCode，则是基于栈的，而里面也提到了很多编译器有不止一个中间语言，这一个就不细谈了。对于鲸书，虽然有一些内容信息已经过时了，但是依然是神书。而这一步，就如今来说，我们往往也不自己来设计IR了，因为若走上这一条路，我们就会投入到无边无尽的后端工作中。那么，感谢伟大的LLVM，我们可以让我们的AST生成LLVM IR，避免掉繁琐的后端工作。我们所需要做的尽只是在AST中添加一个codeGen方法，然后利用LLVM IR API来生成LLVM IR。这一步的输入是AST，输出为IR。

5.代码优化

这一步则是来让代码更加的高效。一般来说，我们分为了机器无关优化与机器相关优化。机器无关的优化则是前面提到的一些内容，而若选择LLVM，我们可以轻易利用LLVM的各种优化pass来帮我们做到这一点。而机器相关优化，则是与硬件平台相关，我们往往需要利用一些硬件平台的特性来帮助优化。这一步输入是IR, 输出依然是IR。而若编译器有多套的IR，那么可能输入的IR与输出的IR是不一样格式的IR，但是如LLVM这样的则是同一套IR。

6. 目标代码生成

这一步则是生成目标平台代码。如若是编译型语言，则往往是产生.o文件，到这一步的时候，其实编译器的真正意义工作已经结束了。

7＊. Driver驱动器

在很多编译器中，我们不仅是到达.o文件，我们还可以调用链接器，汇编器然后生成可执行文件，而这样的工作其实是在一个driver中完成。而driver不仅完成工具链的调用工作，往往也会处理编译选项。如gcc -std=c++11 a.C 那么-std=c++11这一个选项的识别则是在driver中完成。

8＊. 错误信息机制

对于一个编译器来说，其还有一项则是错误的提示。而这一个耗时耗力，也是往往是编译器开发人员不太在意的，大家都想去做高大上的实现，体力活都不想做。这一步却往往是与用户最直接相关的，所以如何设计一个好的错误信息机制也是很重要的一点。

9 ... （如何支持多个源文件的编译？等）

之前也实现过一个较为简单的编译器，用c语言实现，目标代码是mips汇编。结合之前的一些经验教训，在这里说一下吧。

首先，第一步是词法分析。主要工作就是把源代码从左到右扫一遍，简单分析各个单词的种类譬如保留字、标识符等，对于非法字符保存，然后将分析结果存起来，最简单的就是存在数组里。这时候源代码文件就已经可以丢弃了，毕竟从内存中读取更快更方便嘛。

接下来，是语法分析。这一个很好理解，就是判断是否符合文法定义的结构。如果遇到错误，要及时准确报错，而且一般地不要停下来，而是采取合适的策略跳过错误，继续往下扫描，尽可能多得报错。

然后是语义分析。其实，语法分析和语义分析很类似，所以你也可以同时进行语法分析和语义分析，这个没有严格的规定。语义分析的作用是什么呢？就是进一步分析语句的含义，比如遇见int a就知道定义了一个int类型的变量a，在这一过程中会生成符号表，在接下来会详细讲。此外，还有进一步的错误检查，比如函数需要三个变量你却只传递了两个。

刚才说了，在语义分析的时候有一个构建符号表的过程，这个是干嘛的呢？其实我们人类在处理事情的时候也会有这么一个习惯，比如阅读一本特别复杂的书，里面人物关系特别乱，为了读懂它我们就会画一个表有某某人，他的性别，是什么国家的，性格特征之类的，符号表就是充当这个作用。我们分析变量的类型，函数的参数个数等等之类的，也方便了我们检查错误。符号表的结构可复杂也可简单，复杂的话可以用散列表，简单的话可以上数组，我使用的树，我觉得还是很好用的，结构简单，层次也清晰，效率也不错。

接下来就是中间代码生成，中间代码生成就是把源代码转化成一个尽可能简单易处理的简单语句，中间代码的形式由你自己决定，比如可能是四元式。以a=b+c这一句为例，你可以如下定义你的四元式:add b c a。借助中间代码，你可以更方便的生成目标代码，也更方便移植。

下面就是目标代码生成和代码优化了。代码优化是在目标代码生成之前，但是实际中是先写目标代码生成，后写代码优化。

先歇一会儿，再补全。

建议从设计编程语言与用最小代价实现入手研究学习。

木兰编程语言/mulan-rework 是个好参考。相关专栏：木兰编程语言

用类似技术可以方便 设计实现中文编程语言 如：

创建读者表，编号为自动递增的整数主键，邮箱为不重复不为空的文本，出生年为整数。将昵称为“喵喵”的读者记录的出生年改为2001。删除出生年小于2000的读者记录。删除读者表。
获取出生年大于2000的读者的邮箱、昵称，按出生年倒序排列。