乐趣区

关于javascript:译超级微型编译器

引子

在看 babel 文档的时候,接触到 The Super Tiny Compiler,其中的正文感觉解释的蛮容易了解,翻译记录一下。

  • Origin
  • My GitHub

为什么要关注编译器

大部分的人在他们的日常工作中,实际上没有必要去思考编译器相干的货色,不关注编译器很失常。然而,编译器在你的身边很常见,你应用的很多工具,都是借鉴了编译器的概念。

编译器很可怕

编译器确实很可怕。然而这是咱们(那些写编译器的人)本人的谬误,咱们舍弃了简略正当,并且让它变得如此简单可怕,以至于大部分的人认为是齐全无奈靠近的事件,只有书呆子能够明确。

该从那里开始?

从编写一个最简略的编译器开始。这个编译器十分的小,如果你移除所有的正文,也只有 200 行代码。

咱们筹备写一个编译器,它的作用是将一些 LISP 办法调用的模式转换成 C 语言外面办法调用的的模式。

如果你对其中的语言不太熟悉,我将会简略介绍一下。

如果咱们有两个办法 addsubtract,它们会像上面这样书写:

example LISP C
2 + 2 (add 2 2) add(2, 2)
4 – 2 (subtract 4 2) subtract(4, 2)
2 + (4 – 2) (add 2 (subtract 4 2)) add(2, subtract(4, 2))

很容易,对吧?很好,这正是咱们筹备要编译的。尽管这个不是残缺的 LISP 或 C 语法,但它的语法足以演示大部分古代编译器的次要局部。

编译的三个阶段

大部分的编译能够划分为 3 个次要阶段:解析 (Parsing), 转换 (Transformation), 代码生成(Code Generation)。

  • 解析:获取每一行代码,并将其变成更加形象的代码。
  • 转换:获取形象的代码,依照编译器的用意进行操作。
  • 代码生成:获取转换后体现的代码,并将其变换成新的代码。

解析(Parsing)

解析通常分为两个阶段:词法剖析 (Lexical Analysis)和 语法分析(Syntactic Analysis)。

  • 词法剖析:获取代码,并且用 分词器 (tokenizer)将其分解成独自的 记号(tokens)。记号是一个数组,外面是形容语法各个局部的对象。它们可能是数字、文本、标点符号、操作符等等。
  • 语法分析:获取那些记号,并将其转换为另外一种表现形式,这种表现形式形容了本人的语法和互相分割。这被称为两头示意或 形象语法树(Abstract Syntax Tree 或 AST)。形象语法树是一个深层嵌套的对象,代表代码运行的一种形式,它提供给咱们很多信息。

例如上面的语法:

(add 2 (subtract 4 2))

记号看起来可能像这样:

[{ 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: ')'        },
]

形象语法树看起来可能像这样:

{
  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',
      }]
    }]
  }]
}

转换(Transformation)

编译的下一个阶段就是转换。这一步只是获取上一步的 AST 并且再一次扭转它。能够用雷同的语言操作 AST,或者把 AST 转换成一个齐全新的语言。

让咱们看看如果转换一个 AST。

你可能发现咱们的 AST 外面有些元素很类似。这里有一些领有 type 属性的对象,每一个这样的对象被称为 AST 节点(AST Node)。这些节点定义了树上每个独自局部的属性。

咱们有一个 NumberLiteral 节点:

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

或者可能是一个 CallExpression 节点:

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

当转换 AST 时,咱们能够对节点的属性进行增加 / 移除 / 替换操作,咱们能够增加新的节点,移除节点,或者基于已存在的 AST 创立一个齐全新的 AST。

因为咱们的指标是一个新的语言,所以咱们将要针对新的语言,创立一个齐全新的 AST。

遍历(Traversal)

为了可能找到所有的节点,咱们须要遍历它们。这个遍历的过程要达到 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'
      }]
    }]
  }]
}

下面的 AST,咱们将这样遍历:

  1. Program – 从 AST 最顶层级开始
  2. CallExpression (add) – 挪动到 Program 的 body 外面的第一个元素
  3. NumberLiteral (2) – 挪动到 CallExpression(add) 的 params 的第一个元素
  4. CallExpression (subtract) – 挪动到 CallExpression(add) 的 params 的第二个元素
  5. NumberLiteral (4) – 挪动到 CallExpression(subtract) 的 params 的第一个元素
  6. NumberLiteral (2) – 挪动到 CallExpression(subtract) 的 params 的第二个元素

如果间接操作这个 AST,这里可能要介绍各种形象。然而咱们正在尝试做的事件,拜访到树的每个节点就足够了。

访问者(Visitors)

这里根本的思路是,创立一个“visitor”对象,它领有的办法能够承受不同类型的节点。

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

当咱们遍历 AST 时,只有“进入(enter)”到一个匹配的类型节点,咱们将调用这个 visitor 的办法。

为了让这个想法可行,咱们将传入一个节点和其父节点的援用。

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

而后,这里还存在“退出(exit)”的可能性。设想一下咱们这样的树结构:

- Program
  - CallExpression
    - NumberLiteral
    - CallExpression
      - NumberLiteral
      - NumberLiteral

当咱们遍历上来,最终会达到一个死胡同。所以当咱们实现树每个分支的遍历,咱们就“退出(exit)”。因而,向下遍历树,“进入(enter)”到树节点,返回的时候,咱们就“退出(exit)”。

-> Program (enter)
  -> CallExpression (enter)
    -> Number Literal (enter)
    <- Number Literal (exit)
    -> Call Expression (enter)
      -> Number Literal (enter)
      <- Number Literal (exit)
      -> Number Literal (enter)
      <- Number Literal (exit)
    <- CallExpression (exit)
  <- CallExpression (exit)
<- Program (exit)

为了反对这种性能,最初咱们的 visitor 看起来会像是这样:

var visitor = {
  NumberLiteral: {enter(node, parent) {},
    exit(node, parent) {},}
};

代码生成(Code Generation)

编译的最初一个阶段就是代码生成。有些时候编译器在这个阶段,会做跟转换重叠的事件,然而大部分的代码生成只是意味着获取 AST 并且转换成字符串代码。

代码生成有几种不同的运行形式,一些编译器会重用之前的记号(tokens),有些会创立一个独自的代码示意,这样他们就能够线性打印节点,然而从我理解到的状况,大部分会应用咱们方才创立的 AST,也是咱们将要关注的。

咱们的代码生成器将无效地晓得如何“打印(print)”AST 的所有不同节点类型,并且它将递归地调用本人来打印嵌套的节点,直到将所有内容打印成一长串代码。

就这样!这些就是编译器所有不同的局部。并不是每一个编译器都像我这里形容的那样。编译器用于不同的目标,它们可能须要比我形容的更多的步骤。然而,当初你应该对于大部分编译器是什么样的,有一个更高的意识。

当初,我曾经解释了这么多,你应该都能很好的写出本人的编译器,对吧?只是开个玩笑,这就是我要帮忙的。那么就让咱们开始吧!

编译器示例

见 the-compiler-js。

参考资料

  • the-super-tiny-compiler
  • Let’s Build A Simple Interpreter
退出移动版