[翻译] 用 Ruby 写编译器之一:一个简单的 main 函数模板

原文链接: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 的汇编程序。

我是从允许内嵌的汇编代码片断开始[自举](http://en.wikipedia.org/wiki/Bootstrapping_(compilers))这个编译器的,并在此基础上逐步地增加所支持的语法结构。

首先我加入了对函数的定义以及调用的支持,并以此为基础构建我的整个编译器。然后我会增加基于寄存器的基本四则运算的支持,然后是局部变量,等等等等,但在同时也会解析汇编,以保证当遇到内嵌汇编代码片段中的寄存器时,还能够保持寄存器分配器的简洁(原文: 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 的某些细节存在疑问,但我所具备的基础汇编知识已经足够我理解那些个汇编代码了。虽然在此过程中,我很可能会犯一些很愚蠢的错误,但我同时也可以从中学到很多知识(而且那些非常相信能够从我这里学到相关知识的人们也请注意了 - 我在这方面也只是个初学者哦)。

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#!/bin/env ruby
class Compiler

  def compile(exp)
    # Taken from gcc -S output
    puts <<PROLOG
 .file "bootstrap.rb"
 .text
.globl main
 .type main, @function
main:
 leal 4(%esp), %ecx
 andl $-16, %esp
 pushl -4(%ecx)
 pushl %ebp
 movl %esp, %ebp
 pushl %ecx
PROLOG

    puts <<EPILOG
 popl %ecx
 popl %ebp
 leal -4(%ecx), %esp
 ret
EPILOG

    puts <<GLOBAL_EPILOG
 .size main, .-main
GLOBAL_EPILOG
  end
end

prog = [:puts,"Hello World"]

Compiler.new.compile(prog)

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

1
2
3
int main()
{
}

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

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

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

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

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


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

 
comments powered by Disqus