GlacJAY 的学习笔记

原文链接：http://www.hokstad.com/writing-a-compiler-in-ruby-bottom-up-step-6.html

既然上次已经提到说，我们其实是在从 Lisp、Scheme 还有类似的其他语言中借鉴各种要实现的功能（我没想过要把这个项目做成原创的⋯⋯或者至少也要等到以后再说吧），那么现在也是时候实现一些更加强大的功能了。

那就来做延迟求值以及匿名函数吧

Lambda，又名匿名函数，可以像普通的数值或者字符串类型那样被当作函数参数来到处传递，也可以在需要的时候才调用（当然不调也可以）。同时，外层函数（也就是定义匿名函数的函数）作为它们的运行环境，在其中定义的局部变量可以被这些匿名函数所访问。这就形成了一个闭包。我们这次并不是要实现完整的闭包功能，只是开头的一小步而已，完整的实现要等到再后面了。

其实说到底，正如编程语言中的其他很多功能一样，闭包也只是又一种语法糖而已。比如说，你可以认为这样其实是定义了一个类，这个类中有唯一一个需要被调用的方法，还有一些作为运行环境的成员变量（或者你也可以反过来用闭包来实现面向对象系统 - 这是由 Wouter van Oortmerssen 所提出来的观点。自从我发现 Amiga E 这个项目之后，作为作者的他就成了我的偶像。如果你是一个编程语言方面的极客的话，那你就一定要去看看 Wouter 所做过的东西）- 有很多功能其实都是相互正交的。

（blah blah blah ⋯⋯这个人在说自己很啰嗦之类的，就不翻了）

那么，为了避免定义很多具名小函数的麻烦，同时降低函数重名的概率，lambda 允许你在任何需要它们的地方进行定义，并且返回一个表示所定义函数的值。

我们现在所要增加的是像下面这样的东西：

第一个表达式会返回所定义的函数（目前来说，其实就是这个函数的起始地址），而不是去执行这个函数。而 call，当然就是以指定的参数列表，来调用传给它的那个函数地址。

那么，这跟“真正”的闭包又有什么区别呢？

最重要的一点就是，当你在 lambda 中引用了外层作用域中的某个变量后，那么，当以后对同一个 lambda 进行调用时，这个变量还是可以访问的。这样的变量与 lambda 绑定在了一起。当然，只是得到一个函数的地址的话，肯定是实现不了这个功能的。让我们来看一种实现闭包的技术吧，这样你就能够了解大概所要做的工作了（工作量不大，但也不小）：

• 我们可以创建一个“环境”，一个存放那些被引用到的外部变量的地方，以使得当外层函数返回之后，它们也可以继续存在。这个环境必须是在堆中，而且每次对外层函数的调用，都需要创建一个新的环境。
• 我们必须返回一个可以用来访问这个环境的东西。你可以返回一个对象，其中的成员变量就是被 lambda 引用到的那些变量。或者你也可以用一个 thunk（中文叫啥呢？），也就是自动生成出来的一个包含有指向这个对象指针的小函数，它会在调用我们的 lambda 之前将这个对象加载到预先指定的地方。或者你也可以用什么其他的办法。
• 你必须决定有哪些变量需要放入这个环境中。可以是外层函数中的所有局部变量，当然也可以只是那些被引用到的变量。后一种作法可以节省一定的内存空间，但是需要作更多的工作。

好吧，还是让我们先来把匿名函数本身给弄出来吧。就像以前一样，我会一步一步地说明所要做的修改，但我同时也会对之前的代码做一些整理。这些整理的部分我就不一一说明了。

首先是对 lambda 表达式本身进行处理的方法：

这个实现应该是很容易理解的吧。我们在这里做的，就是给要定义的匿名函数，生成一个形如“lambda__[number]"的函数名，然后就把它当作一个普通函数来处理了。虽然你也可以就把它生成到外层函数的函数体中，但我发现那样做的话，就会显得很乱的样子，所以我现在还是就把它作为单独的函数来处理了。然后我们调用 #compile_defun 方法来处理这个函数，这样的话，这个函数其实也就只有对用户来说，才是真正匿名的了。然后我们把这个函数的地址保存在寄存器 %eax 中，这里同时也是我们存放子表达式结果的地方。当然，这是一种很懒的作法啦，我们迟早需要为复杂的表达式，实现更加强大的处理机制的。但寄存器分配果然还是很麻烦的一件事情，所以现在就先这样吧（将所有的中间结果压入栈中也是一种可行的作法啦，不过那样比较慢）。

最后，我们返回一个 [:subexpr] ，来告拆调用者到哪边可以得到这个 lambda 的值。

之后是一些重构。你也许已经注意到了，#compile_exp 中的代码有点乱，因为要处理不同类型的参数。让我们把这部分代码给提取出来：

要注意的是，这里又出现了一个新的 :atom 类型。借助于此，我们就可以把一个 C 函数的地址传给 :call 指令了。反正实现起来也很简单。当然，我们还要在 #get_arg 方法中加上如下代码，以使其生效：

然后，作为重构的一部分，对 :call 的处理被分离了出来，成为一个单独的方法：

看起来很熟悉对不对？因为它就是原来的 #compile_exp 方法，只不过是用 #compile_eval_arg 替换掉了其中的一些代码。另外有改动的地方，就是同时也用 #compile_eval_arg 方法来得到要调用的函数，并对可能得到的 %eax 做了些手脚，在前面加了个星号。

如果你知道这是怎么回事的话，你也许已经开始寻思其他的点子了，而不管那是真正的好事，还只是开枪打自己的脚。上面的代码其实就相当于，你把任意一个表达式的值当作指向一段代码的指针，然后也不做任何的检查，就直接跳过去执行它。如果是往一个随机的地址进行跳转的话，你最有可能得到的就是一个段错误了。当然，你也可以很容易地通过这项技术，来实现面向对象系统中的虚函数跳转表，或者其他的什么东西。因此，安全性将会是以后必须要考虑的东西。还有就是，要实现对一个地址（而不是函数名）的间接调用，你必须要在这个地址前面加上星号。

那么，现在的 #compile_exp 方法变成什么样子了呢？简单来说就是，变得整齐多了：

看起来很不错，不是吗？#compile_call 几乎跟之前的 #compile_exp 一模一样，只不过是把一些代码给提取出来，成为了辅助方法而已。

那么就来简单地测试一下吧：

（看起来也没那么糟不是吗？）

编译运行之：

这篇的代码在这里。

之后的部分

因为我合并了几篇文章，下面就列一下更新过后的，“已经写完但还需要整理的”文章列表。因为我肯定还会合并下面的某些部分的，所以我想我需要找时间开始写一些新的部分了（为了完成我所定下的 30 篇的计划）。

• 步骤七：再看用匿名函数实现循环，以及对函数参数的访问
• 步骤八：实现赋值语句以及简单的四则运算
• 步骤九：一个更简洁的 while 循环语句
• 步骤十：测试这个语言：实现一个简单的输入转换模块
• 步骤十一：重构代码生成器，分离架构相关的部分
• 步骤十二：对某些功能点的讨论，以及未来的前进方向
• 步骤十三：实现数组
• 步骤十四：局部变量以及多重作用域
• 步骤十五：访问变长参数列表
• 步骤十六：再看输入转换模块，重构以支持新功能，并用其解析它自己
• 步骤十七：总结实现自举所需要的功能点
• 步骤十八：开始实现真正的解析器

原文链接：http://www.hokstad.com/writing-a-compiler-in-ruby-bottom-up-step-5.html

上次我承诺会发布的更快一些，不过还是失败了⋯⋯作为补偿，这章的内容将会是原计划中的第 5，6，7 章内容的合并，因为这三章确实都很短。闲话少叙：

处理数字常量

到目前为止，我们只处理了一些实现所必须的数字常量，也就是当一个外部函数的返回值是数字的情况，而且没有做任何形式的类型检查。

那么，就让我们来看一下 gcc 在 C 语言中是怎样处理各种类型（包括 long long 等）的整数的吧。当然，这次还是针对 32 位的 x86 架构：

我略掉了大部分 gcc 所生成的代码，如果愿意，你可以自己执行 gcc -S 命令来看。有趣的部分是对各个函数的调用，其生成的代码如下：

换句话说，至少在处理函数调用的时候，gcc 都会把各种整数类型统一作为 32 位的整型来处理，除了 long long 类型之外。因此，我们可以暂时忘掉 long long 类型，而只处理 32 位以内的整数值，这样我们就可以忽略类型处理相关的东西了。

懒惰还真是一种病啊。

我们同时也会略过浮点型。为什么呢？因为只要有整数运算，你就可以实现一个完整的编译器了，所以现在就加入对浮点型的支持完全只是浪费时间而已。当然这个东西以后总归是要做的。

另外，当我还年轻时，我们连 FPU 是啥都还不知道呢。尽管如此，我们依然可以用整数来模拟各种定点运算，一样可以完成很多事情。

那么，我们真正要做的修改有哪些呢？

在方法 #get_arg 中，在处理字符串常量之前，加入如下代码：

在方法 #compile_exp 中，我们用如下代码来处理 #get_arg 的返回值：

然后，就完事了。就这么简单。

然后就是测试啦：

插曲：针对原生数据类型的一些思考

”纯“面向对象类型的语言很棒，但并不是对底层的代码生成器而言的，我想。不管你是否想要实现一个纯的面向对象语言，我仍然坚信，首先实现原生的数据类型和其操作，是非常有价值的。你可以在后面的阶段再来考虑是否要对用户隐藏它们，或者是让它们看起来像是对象，或者是透明地在它们和对象之间执行自动转换的操作，等等。

要注意的是，Matz 的 Ruby 解释器（Matz Ruby Interpreter，简称MRI）就是这样实现的：里面的数字就跟“真正的”对象神马的完全不一样，但是解释器本身却尽其所能的对用户隐藏这一事实。不过我个人认为 MRI 做的还是不够。

If ... then ... else

如果没有某种形式的条件逻辑支持的话，我们的语言是没有太大用处的。几乎所有有用的语言都支持某种形式的 if .. then .. else 构造。现在，我们要实现的是像 [:if, condition, if-arm, else-arm] 这样的构造，而且是以 C 语言的形式来实现。也就是说，0 和空指针都表示假，其他值则都为真。

仍然是一个简单的例子：

相关的汇编输出：

对于大多数的语言和架构来说，这都是一个编译 if .. then .. else 时会采用的通用模板：

• 计算条件表达式。
• 对结果进行测试（这里用的是 testl 指令 - 在其他架构中比较通用的还有 cmp 指令，或者对寄存器进行自减）。testl 指令比较它的左右两个操作数，并进行相应的标志位设置。
• 然后，条件跳转到 else 语句处。这里，我们检查条件表达式的值是否不为真。在这种情况下我们用的是 je 指令，即“相等时跳转”（jump on equal），也就是当结果相等时跳转（要注意的是，在大多数的 CPU 架构中，很多指令都会设置条件码，而不仅仅是显示的测试指令）。
• 然后执行 then 子句。
• 跳过 else 子句，继续执行整个 if 语句之后的部分。
• 生成 else 子句的标号，以及其中的指令序列。
• 生成 if 语句的结束标号。

其他还有很多不同的变种，比如根据条件表达式取值的概率，或者某个架构中是否跳转的执行代价，进而调整两个子句的顺序等。不过就目前来说，上面的方法已经足够了。

总之，编译的方法还是很简单的，应该说就是以上所述流程的直译：

这段代码应该很易懂的，其实就是对所有子句 - 条件，then 子句，以及 else 子句 - 分别调用 #compile_exp 方法，并在其间插入所需的辅助指令，同时用 @seq 成员来生成所需的标号。

为了使其生效，我们在 #compile_exp 方法中的 return defun ... 之后插入如下代码：

下面是一个简单的测试：

这里是最终结果。

如往常般，执行的方法如下：

有关循环的一些思考

非条件循环是很容易实现的，不过我们需要实现它吗？显然不需要。我们已经可以用递归来实现循环了，又何必要乱加东西呢？

不过，要令它工作良好，我们还需要实现尾递归优化，可是我现在还没有做好准备。尾递归优化，或者更一般的形式 - 尾调用优化 - 所说的情况是，在一个函数的末尾，调用了一个需要相同或者更少个数参数的函数，并返回它所返回的值。在这种情况下，你可以将当前函数的调用栈，复用给被调用的函数来使用，并且是通过 jmp 而不是 call 来调用这个函数。jmp 指令不会在堆栈中压入一个新的返回地址，因此当这个被调用的函数返回，返回到的就是当前函数的调用者那里，而不是当前的这个函数。

这就同时完成了几件事情：首先，也是最重要的，就是堆栈不再会随着调用而增长了。其次，我们能够省掉几个指令周期。有了尾调用优化，再配合其他几个优化之后，你就可以这样来写循环，而不用担心堆栈溢出的问题了：

换句话说，尾调用优化意味着，对任何形如 (defun foo () (do bar foo)) 的函数来说，堆栈的使用率都会从原来的成比例增长减少为定值了。

当前的版本已经可以编译上面的代码了，不过它会很快用完堆栈并且崩溃掉的。不是很令人满意啊。

果然（原文：I sense a disturbance in the force），两位读到这篇文章的极客都指出了堆栈增长的问题。

现在，让我们先忽略这个问题吧，同时注意下对堆栈空间的使用好了。之后，我们会实现一个专门的循环结构的。目前就这样吧 - 如果以后我实现了尾调用优化的话，我们还可以重新考虑在运行时库中实现一个循环构造的方案。

不管怎样，我们现在可以写出一个无限循环了⋯⋯不是太有用，不是吗？

当然，我们其实也已经可以写 while 循环了：

看起来不是太好，不过确实可以工作。但看起来总归还是太丑了，所以我们总归还是要实现一个正尔八经的 while 循环的。

我不是一个 Lisp 程序员。我没办法处理那么多的括号⋯⋯不过 Lisp 的语法确实很适合于一门还没有语法的语言。到了一定的阶段之后，我会实现一个完整的解析器的。也许是出于偶然，我已经实现的和将要实现的很多东西在某种程度上来说都是取自于 Lisp 的，至少看起来是这样的。如果你能适应 Lisp 的语法的话，这个语言还是非常强大的。就算你不打算用它来开发你的程序，好好地学一下这门语言也是非常值得的。

在我想来，很多看起来像是从 Lisp 中得来的点子，大概都是来自于我花在学习 Lisp 的有限经验。

下一篇：匿名函数，也许不止。

原文链接：http://www.hokstad.com/writing-a-compiler-in-ruby-bottom-up-step-4.html

抱歉，又拖了很长时间。要忙的事情实在很多。正如上一篇文章末尾提到的那样，这次要讲的是自定义函数，以及一个简单的“运行时库”。

自定义函数

一门编程语言如果连函数和方法都没有的话，那也就不能算是一门语言了。而且，实践表明，一门面向对象语言中的所有特性都可以通过过程式的语言要素来实现：一个方法也只不过是以一个对象为额外参数的函数而已。因此，增加对函数的支持就是实现一门语言的核心所在。

其实，这个东东也是很简单的啦。跟以前一样，还是让我们来看一下 C 语言中的函数是怎么实现的吧：

gcc 生成的汇编代码是这个样子滴：

其中的函数调用现在应该很容易认了吧。剩下的就是简单的样板代码了：

在函数的开头，首先是将寄存器 %ebp 压入堆栈，然后拷贝寄存器 %esp 到 %ebp。而在函数的最后，leave 指令就是前面两条指令的逆操作，而 ret 指令则是从堆栈中弹出要返回到的指令地址（也就是调用该函数的那条指令的下一条指令）并跳转。为什么在这里要将 %esp（也就是堆栈指针）拷到 %ebp 呢？嘛，一个很明显的好处就是你可以尽情的申请堆栈空间，然后在完事时简单地将 %ebp 拷回给 %esp 就行了。从上面就可以看到，GCC 已经充分利用了这一点，直接用 leave 指令来处理调用函数时对参数所申请的空间 - 反正手工释放也只是浪费时间而已。

这么说来的话，要做的事情应该就很简单了啊。

首先需要修改方法 Compiler#initialize，创建一个用来保存所有函数定义的哈希：

然后增加一个输出所有函数定义的方法：

可以看到，这里也同时包括了 .globl 与 .type 与 .size 之类的东西。.globl 的意思就是你想让这个函数也能够从其他文件（也就是编译单元）中调用，这在链接多个目标文件的时候是很重要的。我想 .type 和 .size 主要是用在调试的时候，分别用来表示一个符号对应的是一个函数，以及这个函数的大小。

除了这些之外，这个方法就很简单啦 - 它会通过调用 #compile_exp 方法来完成实际的工作。

我们再来增加一个用来定义函数的辅助方法：

然后在方法 #compile_exp 中增加如下的几行代码：

之所以要增加第一行代码，一方面是出于健壮性的考虑，同时这也允许我们用 nil 和空数组来表示“啥也不做”的意思，当你要定义一个空函数的时候就会用到这一点了。这样一来，第二行代码就不需要去检查将要定义的是不是一个空函数了。

不知道你注意到了没有，我们其实已经实现了对函数的递归定义。像 [:defun,:foo,[:defun, :bar, []]] 这样的代码完全是合法的。同时你也许会注意到，这个实现会导致两个函数其实都是可以从别处调用的。好吧，现在是没关系的啦，我们以后会处理这个的（要么不允许编写这样的代码，要么就只允许外层函数来调用内层函数 - 我还没有决定到底要做哪个啦）。

剩下的事情就是输出这些函数的定义了，因此我们在方法 #compile 中对 #output_constants 的调用之前增加如下的一行：

增加对一个运行时库的支持

首先，让我们将现在的 #compile 方法重命名为 #compile_main，然后重新定义 #compile 方法如下：

之后是对常量 DO_BEFORE 和 DO_AFTER 的定义（如果愿意的话，你也可以把它们放在一个单独的文件中，我现在就直接把它们放在开头好了）：

你得承认，你想看到的应该是更加高级一些的东东，但那样就违背我们最初的目标了。上面的代码对于实现一个运行时库来说已经足够了。当然，你也可以用一些只能通过 C 或者汇编才能实现的东西，只要把包含那些函数实现的目标文件给链接进来就可以了，因为我们一直都是在按照 C 语言的调用规则来办事的嘛。

让我们来测试一下吧。在 Compiler.new.compile(prog) 的前面加入下面的代码：

然后编译运行：

你可以在这里找到今天的成果。

对函数参数的访问吗？

今天还遗留了一个任务：实现对函数参数的访问。这个的工作量可是不小的。放心，我不会忘了这个的，这将会是第八篇文章的主题。我也不会让你等太久的啦，这次一定

原文链接：http://www.hokstad.com/writing-a-compiler-in-ruby-bottom-up---step-3.html

我本来是想要早点发表的，可是我这周又不行了 - 虽然整理一篇旧文只需要半个小时。不管怎样，这是第三章，而且我会在末尾大概列一下之后的大纲。由于我会试着把一些小的步骤组合成更有内容的章节（下面就有个这样的例子），因此原来的 30 篇文章已经被我给减到了 20 篇左右（当然，这只是我已经完成了的，后面还有新的呢）。

用 do 语句将表达式给串起来

到目前为止，上次的第二版程序只能编译一个单独的表达式。只是这样的话，并不是非常的有用啊。因此我决定实现一种支持顺序执行的结构，就像函数体那样的。当然，如你所想，这是很简单的。我会增加一个关键字 do，而其作用就是顺序执行传给它的每一个（个数不限哦，或者说，只受限于内存的大小）参数表达式。看起来就像这样：

要实现这个是非常简单的。我们只需要在函数 #compile_exp 的开头加入下列代码：

递归在这里的作用很重要哦 - 毕竟你是在处理一个树形结构，那也就需要在越来越深层的树结点之上调用实现编译的核心函数，而这当然也包括我们的下一个目标，即对子表达式的处理。

子表达式，步骤一

先来给出一个我们想要支持的用例：

第一个需要改变的地方，在函数 #get_arg 中，我们在其开头加入如下的代码：

如果你这时已经试着用上面的代码来编译测试用例了的话，gcc 会报错给你的，因为我们现在只处理了 #get_arg 的返回值是一个字符串常量对应的序列号的情况，而这对子表达式来说显然是不适用的。

子表达式，步骤二：返回值

那么 gcc 是怎么处理这个的呢。让我们来看看下面这段代码：

所产生的汇编吧（只截取 main 中相关的部分）：

应该说还是很直观的吧。gcc 首先会去调用子表达式（foo），并且希望这个函数能够把它的返回值放入寄存器 %eax 中，然后就会把这个值作为参数拷到堆栈上，而不是什么字符串常量的地址。

首先是要调整 #get_arg 函数：

唯一需要改动的地方就是返回值了，我们增加了一个表示返回值类型的标识 - 以后还会加入其他类型的。

剩下的工作就是改写 #compile_exp 函数中的相关部分了。这时就不能直接收集 #get_arg 的返回值了，而是需要对每个参数都做相应的处理并直接输出（而这同时也是 stack_adjustment 需要修改的原因，因为已经没有 args 数组了）：

如你所见，并不是什么复杂的更改。我们只是检查了 #get_arg 所返回的类型信息，并相应的输出字符串常量或者寄存器 %eax 而已。随着我们加入更多要处理的情况，这个部分代码还会继续扩充的。

你可以在这里找到最新版本的代码。

之后的计划

这里只列出的基本完成的部分。我的计划是，当我开始着手写新的部分时，我会将重心放在一个简单的解析器上，以尽快实现编译器的自举（即，编译它自己）。

• 步骤四：运行时，以及函数的定义
• 步骤五：处理其他类型的常量值
• 步骤六：条件表达式 if ... then ... else
• 步骤七：循环语句
• 步骤八：匿名函数（lambda）
• 步骤九：用匿名函数来实现循环，以及对函数参数的处理
• 步骤十：赋值，以及简单的代数运算
• 步骤十一：更简结的 while 循环
• 步骤十二：测试我们的语言：开发一个简单的输入转换模块
• 步骤十三：重构代码生成模块，并抽象出平台相关的部分
• 步骤十四：对一些概念的讨论，以及今后的前进方向
• 步骤十五：数组
• 步骤十六：局部变量以及多种作用域
• 步骤十七：可变长参数列表
• 步骤十八：再看输入转换模块：测试新的功能点，以及自我转换
• 步骤十九：确定自举所需要实现的功能
• 步骤二十：开始实现真正的解析器

原文地址：http://www.hokstad.com/writing-a-compiler-in-ruby-bottom-up-step-2.html

我会选择 Ruby 来作为我的实现语言并没有什么特别的理由。在现阶段，语言的选择并不重要；不过，我确实很喜欢 Ruby。

在这之后，我会采取一系列的步骤令所实现的语言向其实现语言靠拢。我的意思是，我想将编译器实现为可以自举的，即它应该能够编译自身。

而这也就意味着，要么我的编译器需要至少支持 Ruby 语言的一个子集，要么就需要一个中间的翻译步骤，来将编译器中的实现翻译成它自己可以编译的语言。

虽然这一点并没有限制你所用的实现语言，但那至少意味着你用来实现的语言跟你要实现的语言之间很相似，除非你对实现编译器的自举没有什么兴趣。

这也同时意味着，如果你想实现编译器的自举，那你最好不要用实现语言中的什么复杂的特性。要记住，你得实现所有你用过的那些语言特性，不然，当你要开始做自举的时候，你就得对整个编译器的架构做大的调整了。那一点都不好玩。

话说回来，使用 Ruby 来作为实现语言的一大优点（同样对于其他某些语言来说也是这样，比如说 Lisp），就是你可以很容易地构建出一个树形的数据结构出来 - Ruby 的话就是用数组或者哈希，Lisp 的话就是用列表。

这也就是说，我可以用数组来手工构建抽象语法树，从而避免了实现一个语法分析器的工作。耶！代价就是很丑，不过也可以接受的语法啦。

Hello World

Hello World 的话看起来会是这个样子的：

这里，我们需要处理的东西非常简单：我们需要将一个参数压入堆栈，然后调用一个函数。

那么就让我们来看一下怎样用 x86 汇编来做这件事吧。我用“gcc -S”编译了下面的这段 C 程序：

然后看看输出会是什么样子的。下面给出的是真正相关的部分，是与上一次的输出比较之后的结果：

如果你懂一些汇编的话，就算以前没有写过 x86 的汇编程序，也应该可以很容易的看懂这段代码吧：

• 这里首先定义了一个字符串常量。
• 通过对堆栈指针的减 4 操作，在堆栈上申请了一段 4 个字节大小的空间。
• 然后将之前定义的字符串常量的地址，放入刚刚申请的那 4 个字节的空间中。
• 接着，我们调用了由 glibc 提供的 puts 函数（在这个系列中，我会假设你已经有了 gcc/gas + glibc；Linux 的话这些东东应该已经有了）。
• 最后，通过一个加 4 操作来释放堆栈空间。

那么，我们要怎样在我们的编译器中实现这一切呢？首先，我们需要一种方法来处理那些字符串常量，通过在上次的 Compiler 类的实现中添加下面的代码（我的所有 Ruby 代码都在这里，这样你就知道该做什么了）：

这段代码就是简单地将一个字符串常量映射到一个整数上，而这个整数则对应着一个标号。相同的字符串常量会对应到相同的整数上，因此也只会被输出一次。用哈希而不是数组来保证这种唯一性是一种很常用的优化手段，不过也不一定非要这样做。

下面这个函数是用来输出所有的字符串常量的：

最后剩下的就是编译函数调用的代码了：

也许你已经注意到这里的不一致性了：上面的代码虽然好像是可以处理多参数调用的样子，但却只从堆栈中减掉了一个 4，而不是按照实际的参数个数而进行相应的调整，从而导致了不同参数间的相互覆盖。

我们马上就会处理这个问题的。对于我们简单的 Hello World 程序来说，目前这样已经足够了。

在这段代码中还有几点需要注意：

• 我们甚至都还没有检查被调用的函数到底存不存在 - gcc/gas 会帮我们处理这个问题的，虽然这也意味着没啥帮助的错误信息。
• 我们可以调用任何一个可以连接的函数，只要这个函数只需一个字符串作为参数。
• 这段代码目前还有很多需要被抽像出去的地方，比如说得到被调函数地址的方法，还有所有那些硬编码进来的 x86 汇编等。相信我，我会（慢慢）解决这些问题的。

现在我们可以来试着运行一下这个编译器了。你应该会得到下面这样的输出：

下面来测试一下：

[vidarh@dev compiler]$ ruby step2.rb >hello.s
[vidarh@dev compiler]$ gcc -o hello hello.s
[vidarh@dev compiler]$ ./hello
Hello World
[vidarh@dev compiler]$ 

那么，要怎么处理多个参数的情况呢？

我不会再展示用来说明的 C 代码和对应的汇编代码了 - 进行不同参数个数的调用并查看其输出对你来说应该不难。相反，我就直接给出对 compile_exp 函数所做的修改了（完整的代码在这里）：

这里做了什么呢？改动的地方没几个：

• 这里不再是申请固定大小的堆栈空间了（上一个版本中是 4 个字节），而是根据实际参数的个数来相应的调整堆栈指针。我得承认，我不知道 gcc 为什么会做这样的调整 - 而且原因并不重要，虽然我猜这是为了堆栈的对齐。优化和清理以后再说，并且，当你不知道某事的运行机理时，那就不要去改变它。
• 这之后，如你所见，参数被一个一个地放到堆栈上了。我们还是假定它们全都是相同大小的指针（因此在 x86 上就是 4 个字节）。
• 同时你还可以看到，第一个参数是被放在堆栈中最靠下的位置的。如果你还没有写过汇编程序，并且无法想象出这是怎么回事的话，那就把它们画出来吧；还要记住，这里的堆栈是向下扩展的。当申请空间时，我们是将堆栈指针向下移动的，而拷贝参数时则是从下往上（用越来越大的索引来访问 %esp，就像你访问数组时一样）。

这个编译器现在已经可以编译下面这样的代码了：

至于以后嘛

这就是我们踏出的第一步，而且我保证之后的步骤会越来越实际的，因为只要实现很少的几个功能点，我们就可以编译实际的程序了。而且我会努力令这些步骤更加精炼，更多的说明这样做的原因，而不是仅仅解释做了什么。

下面我会处理多个参数的调用（译者：我们不是才处理过嘛），然后是语句序列、子表达式，以及对返回值的处理，等等。

大约十二个这样难度的步骤之后，我们就会完成函数定义、参数传递、条件判断、运行时库，甚至是一个用来实现匿名函数的简单的 lambda（真正的闭包就要到后面了）。

再之后，我们会实现一个简单的文本处理程序，来对一个比 Ruby 的数组和符号更好一点的语法提供支持（只是某种程度啦，真正的语法分析得再多等等）。

原文链接：http://www.hokstad.com/writing-a-compiler-in-ruby-bottom-up-step-1.html

[译者抱怨：翻译好麻烦啊。]

我已经将这件事情搁置了很长时间了 - 这个系列中最早的文章甚至可以追溯到 2005 年的早期，而那时我还没有开始写这个博客呢。

我灰常喜欢编译器技术，而且我也已经写过好几个小型的编译器了。不久前我开始用 Ruby 语言写一个简单的编译器，而且我也以发表为目的记下了大量的笔记。问题在于，当我一步步地完成这个系列文章的时候，我的博客却渐渐地，没落了（？原文：Problem was I was that by the time I was finishing up the steps I have so far, my blog was languishing, and so it's been just gathering dust. 啊，我的英文好渣）。

我已经写完了大概 30 篇文章，并形成了一个简单但是可以工作的编译器。我也许要花上一段时间来发表它们，因为这些文章均需要一定程度的整理，而且我能花在写作上的时间不是很多。不过根据具体的时间安排，我也有可能一周就发表好几篇。

闲话少叙，第一篇参上：

有关一些背景，以及一小段代码

通常，在开始尝试编写一个编译器时，我会选择自顶向下的开发方式。换句话说就是，我会采取常见的策略，从设计一个语法分析器开始，而不管这个分析器是手写的，还是通过分析器生成器来生成。然后我会通过一系列的树形结构转换程序将 AST（即 Abstract Syntax Tree，抽象语法树）转化为符号表，同时进行错误检查，为树结点附加各类信息，并最终进行代码生成的步骤。在我转而使用 Linux 之后，我在这里就会选择生成 C 代码，前提是你的语言能够很好的契合 C 的语意。从这里也可以看出，C 是一门多么低层的语言了。

不过，我的第一个编译器是用 M68000 汇编语言写的，而且其输出也是 M68000 的汇编程序。

我是从允许内嵌的汇编代码片断开始自举这个编译器的，并在此基础上逐步地增加所支持的语法结构。

首先我加入了对函数的定义以及调用的支持，并以此为基础构建我的整个编译器。然后我会增加基于寄存器的基本四则运算的支持，然后是局部变量，等等等等，但在同时也会解析汇编，以保证当遇到内嵌汇编代码片段中的寄存器时，还能够保持寄存器分配器的简洁（原文：but parse the assembly so that the register allocator would stay clear of registers used in the assembler that was interspersed.）。

然后这个编译器就从编译汇编语言的语法，逐渐演变成编译我所设计的杂牌语言的语法，其中的汇编也越来越少。

我想再自举一个编译器出来。不过这次我就不打算用汇编来实现它了。这次我会从底层 - 也就是代码生成器 - 开始。并且我会完成如下几个目标：

• 实现的简洁性优先于其性能。要点在于，我希望能够将它重写为以其自身来实现。换句话说，我希望它能够实现自举（self hosted，跟 bootstrap 有啥区别呢？）。由于开始的代码最终会被替换掉，那么也就没有必要浪费时间在使它可以运行的更快上面。性能问题大可以以后再考虑。
• 不要做限制性能的决定。虽然性能并不是我们最初的目标，但也不能太大意，而导致今后不好对此进行改进。Ruby，说的就是你（Ruby的运行时非常的动态）。
• 实现的简洁性优先于惯例。不要仅仅因为一个特性很方便就去实现它，而仅实现那些可以帮助我们完成对编译器的自举的特性。而这就意味着，这些特性要能使我们的生活更加方便，而不仅仅是无谓地增加了实现编译器本身的难度。
• 不要急着设计语言，我们要设计的是特性。我想首先实现一个灵活而强大的代码生成器，以及一个可以支持各种功能的简洁的 AST 。我的意思是像 Lisp 语言那样极富表达能力的语法结构，并尽量用 Ruby 来达到相似的目标（这段翻的太渣了，请参考原文）。
• 我并不想深入学习 x86 的汇编语言，虽然我会以其作为我的目标语言。这样说有点夸张。我很熟悉 M68K 和 6510 的汇编语言，同时我也具备足够的知识来阅读 x86 的汇编程序。虽然我从来没有用它写过什么像样的代码，而且我也不打算这么做。我所需要知道的一切信息都来自于查看 gcc 产生的汇编输出。要善用“gcc -S”命令。虽然可能对 x86 的某些细节存在疑问，但我所具备的基础汇编知识已经足够我理解那些个汇编代码了。虽然在此过程中，我很可能会犯一些很愚蠢的错误，但我同时也可以从中学到很多知识（而且那些非常相信能够从我这里学到相关知识的人们也请注意了 - 我在这方面也只是个初学者哦）。

听起来之后貌似会抄很多的小道，同时也会遇到很多痛苦的地方，不是吗？但这同时也会非常有趣哦！

不管怎样，我们先从一段没什么实际用处的代码开始吧：

说实话，这段代码嘛也没做。它只是把用“gcc -S”命令将下面这段代码编译出来的结果拆吧拆吧之后给打印出来了而已：

这可是一个完整可工作的编译器哟 - 某种程度上来说吧。不幸地是，不管用它编译什么程序，得到的都只是一段毫无用处的代码，因些可以说它本身也是同样毫无用处的。但我们总要踏出这最初的一步。

你可以认为这个系列的文章是我的“意识流”。我做这件事仅仅是因为好玩而已。我并没打算坐下来，好好地完成一个多么赞的设计。我甚至会因为一时兴起而把一段代码给丢掉，或者之后又把它给找回来。

你在这里将要看到的其实已经是我第二次的代码了：我所做的每一个 SVN 提交都对应于我的一篇文章，不过我会在文章中做很多额外的讲解。有时这些讲解会令我中途改变主意 - 但我不会对代码做太大的修改，除非我认为这个修改能令我的讲解更清晰，或者我一开始完全就想错掉了。就算是这样，我也多半不会做出修改，除了在那边标注一下我会在之后解决。有些时候，我也会把几个我做起来很麻烦，但解释起来又很简单的步骤合而为一。

我在这里欢迎大家涌跃发言。不过要记住，虽然我会十分留意您的发言，但我已经完成了这个系列中的很大一部分，我不会因为某些意见而完全重写这些文章。不过我会留下一些笔记，并同时记住我之前都写了些什么内容。

下次我会让这个编译器真正去处理它的输入的，我保证。

[译者再次抱怨：翻译好麻烦啊。]