在看 babel 文档的时候,接触到 The Super Tiny Compiler,其中的注释感觉解释的蛮容易理解,翻译记录一下。
大部分的人在他们的日常工作中,实际上没有必要去思考编译器相关的东西,不关注编译器很正常。然而,编译器在你的身边很常见,你使用的很多工具,都是借鉴了编译器的概念。
编译器的确很可怕。但是这是我们(那些写编译器的人)自己的错误,我们舍弃了简单合理,并且让它变得如此复杂可怕,以至于大部分的人认为是完全无法接近的事情,只有书呆子可以明白。
从编写一个最简单的编译器开始。这个编译器非常的小,如果你移除所有的注释,也只有 200 行代码。
我们准备写一个编译器,它的作用是将一些 LISP 方法调用的形式转换成 C 语言里面方法调用的的形式。
如果你对其中的语言不太熟悉,我将会简单介绍一下。
如果我们有两个方法 add
和 subtract
,它们会像下面这样书写:
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)。
解析通常分为两个阶段:词法分析(Lexical Analysis)和语法分析(Syntactic Analysis)。
例如下面的语法:
(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',
}]
}]
}]
}
编译的下一个阶段就是转换。这一步只是获取上一步的 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,我们将这样遍历:
如果直接操作这个 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) {},
}
};
编译的最后一个阶段就是代码生成。有些时候编译器在这个阶段,会做跟转换重叠的事情,但是大部分的代码生成只是意味着获取 AST 并且转换成字符串代码。
代码生成有几种不同的运行方式,一些编译器会重用之前的记号(tokens),有些会创建一个单独的代码表示,这样他们就可以线性打印节点,但是从我了解到的情况,大部分会使用我们刚才创建的 AST,也是我们将要关注的。
我们的代码生成器将有效地知道如何“打印(print)” AST 的所有不同节点类型,并且它将递归地调用自己来打印嵌套的节点,直到将所有内容打印成一长串代码。
就这样!这些就是编译器所有不同的部分。并不是每一个编译器都像我这里描述的那样。编译器用于不同的目的,它们可能需要比我描述的更多的步骤。但是,现在你应该对于大部分编译器是什么样的,有一个更高的认识。
现在,我已经解释了这么多,你应该都能很好的写出自己的编译器,对吧?只是开个玩笑,这就是我要帮助的。那么就让我们开始吧!
背景 在公司参与一个原生APP和h5混合开发的项目,本人在项目中负责h5部分,现将...
作者:Joe Seifi 译者:前端小智 移动: https://mp.weixin.qq.com/s/p5... 有梦...
一、虽然有的属性是boolean类型,但仍旧建议按照XHTML书写(属性名=属性值)格式...
在默认情况之下,如果在Canvas之中将某个物体(源)绘制在另一个物体(目标)之...
简介: 6月4日,以“开启分布式云新时代”为主题2021云边协同大会在北京举行,本...
本文没有咬文嚼字的地方,只是一个配色技巧的分享,十分简单,简单到流泪,但或...
1、纯工具操作步骤,懂代码更容易 划线就是不符合国人的审美观念,看着就别扭,...
1.先瞧瞧效果: 2.代码是这样的: img src=images/circle.png alt= id=circle/@m...
前言 Canvas绘制多变形非常简单,只要懂得Canvas路径 + 简单的初中数学知识即可...
折叠式卡片布局在PC版网站中可能不常见,但是在手机版,小屏幕的网页浏览会大发...