JS编译器

本文内容基于仓库源码进行学习

最近在研究一些构建侧的东西，在翻 babel 官网的时候看到了这样一段话:

For an awesome tutorial on compilers, check out the-super-tiny-compiler, which also explains how Babel itself works on a high level.

出于学习的心态，去翻了一下这个仓库源码，以下是笔者的一些学习的记录，希望看完之后能对你理解 babel 的工作原理有一些帮助~

前言

the-super-tiny-compiler 是一个代码行数只有不到 200 行的超级小型的 compiler，但通过这个 compiler 能学习到最基础的 compile 原理，包括 babel 也是基于这样的原理来进行开发的。

仓库本身的例子是将一组 lisp 风格的函数语法编译成了 C 风格的函数语法，举例子来说:

这就大概是这次 compiler 需要完成的事情，可能看上去语法不是很完整，但是也能够演示现代编译器的主要部分思想了。

大多数的 Compilers 都会把编译过程分成三个主要的过程: parse、transform 以及 code generate：

• parse 主要是将源码转换成一种更抽象的代码表达
• transform 则是将上面抽象的表达进行任意 compiler 想进行的操作
• code generate 将 transform 处理之后的代码生成一种新的代码

Parse

parse 主要分为两个步骤: 词法分析以及语法分析。

• 词法分析将源码根据表达切分一个个的 tokens，tokens 是一组用来描述单独语法的对象，可以是 numbers、labels、punctuation、operators 等
• 语法分析则是将词法分析生成的 tokens 进行重新编排得到一个叫做抽象语法 树 (AST)的结构，AST 是一种易于使用且能展示完整信息的嵌套树状结构。

例如前面提到的 add 2 (subtract 4 2) 表达式被词法分析处理之后生成的 tokens 大概是:

[
  { type: 'paren',  value: '('        },
  { type: 'name',   value: 'add'      },
  { type: 'number', value: '2'        },
  { type: 'paren',  value: '('        },
  { type: 'name',   value: 'subtract' },
  { type: 'number', value: '4'        },
  { type: 'number', value: '2'        },
  { type: 'paren',  value: ')'        },
  { type: 'paren',  value: ')'        }
]

语法分析处理出来的 AST 结构为:

{
  type: 'Program',
    body: [
      {
        type: 'CallExpression',
        name: 'add',
        params: [
          {
          type: 'NumberLiteral',
          value: '2',
          },
         {
           type: 'CallExpression',
           name: 'subtract',
           params: [
            {
              type: 'NumberLiteral',
              value: '4',
            }, 
            {
              type: 'NumberLiteral',
              value: '2',
            }
           ]
         }]
      }]
}

Transform

transform 主要就是拿到 parse 得到的抽象语法树，并基于此做出一些修改。tranform 这个过程既可以基于当前语言的风格去修改 ast 也可以使用一种新的语言风格。

下面基于前面的 ast 结构来展示 transform 这个过程的工作流程。

可以看到，ast 里面的元素看起来都很相似，这些元素组成了 ast 的子结点，这些子结点的数据结构类型描述了代码中的一个单独的部分(例如变量、声明语句，表达式等等)。

例如上面提到的类型是  NumberLiteral 的节点:

{
  type: 'NumberLiteral',
  value: '2',
}

或者更复杂一点的子节点类型:

{
    type: 'CallExpression',
    name: 'substract',
    params: [...nested nodes here ...],
}

在 transfrom 这个过程中，我们可以通过增/删/改来操作抽象语法树结点，或者可以直接基于当前的抽象语法树创建一个新的出来。

既然这里我们的目标是将输入的代码转换成一种新的语言风格的代码(Lisp -> C)，所以这里会创建一个针对新语言的全新 AST 出来。

因此这里我们需要明确一下修改 AST 的操作:

Traversal(遍历)

为了能处理所有的结点，我们可以用深度优先搜索对其进行遍历:

{
  type: 'Program',
  body: [{
    type: 'CallExpression',
    name: 'add',
    params: [{
      type: 'NumberLiteral',
      value: '2'
    }, {
      type: 'CallExpression',
      name: 'subtract',
      params: [{
        type: 'NumberLiteral',
        value: '4'
      }, {
        type: 'NumberLiteral',
        value: '2'
      }]
    }]
  }]
}

遍历流程是这样的:

• Program - 从 AST 的顶结点开始
• CallExpression (add) - Program 的第一个子元素
• NumberLiteral (2) - CallExpression (add) 的第一个子元素
• CallExpression (subtract) - CallExpression (add) 的第二个子元素
• NumberLiteral (4) - CallExpression (subtract) 的第一个子元素
• NumberLiteral (2) - CallExpression (subtract) 的第二个子元素

如果直接在 ast 内部操作而不是产生一个新的 ast，可能就需要介绍所有的种类的抽象。但目前来看，访问所有结点的方法已经足够了。

访问(visiting) 这个词代表一种在对象结构内对元素进行操作的模式。

Visitors(访问)

这里我们可以创建一个 visitor 对象，这个对象包括一些方法用于接收不同的结点。

例如:

var visitor = {
  NumberLiteral() {},
  CallExpression() {}
};

因此当我们遍历 ast 的时候，如果匹配到了对应 type 的结点，可以调用 visitor 中的方法来处理。

Code generate

Compiler 的最后一个阶段就是 generate, 这个阶段做的事情可能会和 transformation 重叠，但是代码生成最主要的部分还是根据 AST 来输出代码。

Generate 有几种不同的工作方式，有些 Compilers 会重用之前生成的 token，有些则会创建独立的代码表示，以便于线性输出代码，但接下来我们还是着重于使用之前生成好的 AST。

我们的生成器需要知道如何打印 AST 中的所有类型结点，然后递归调用自身，知道所有的代码都被打印到一个很长的字符串中。

代码实现