Home > Article > Web Front-end > Detailed introduction to the sample code of writing an ultra-small compiler in JavaScript
Detailed introduction to the sample code of writing an ultra-small compiler in JavaScript
- 黄舟Original
- 2017-03-06 15:06:411198browse
This is a compiler written in JavaScript. Although it is a very small and useless compiler, it can show us many things about the compiler. Today I translated it for everyone to learn and discuss.
/**
* 今天让我们来写一个编译器，一个超级无敌小的编译器！它小到如果把所有注释删去的话，大概只剩
* 200行左右的代码。
*
* 我们将会用它将 lisp 风格的函数调用转换为 C 风格。
*
* 如果你对这两种风格不是很熟悉，下面是一个简单的介绍。
*
* 假设我们有两个函数，`add` 和 `subtract`，那么它们的写法将会是下面这样：
*
* 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 的全部语法，但它足以向我们
* 展示现代编译器很多要点。
*
*/
/**
* 大多数编译器可以分成三个阶段：解析（Parsing），转换（Transformation）以及代码
* 生成（Code Generation）
*
* 1. *解析*是将最初原始的代码转换为一种更加抽象的表示（译者注：即AST）。*
*
* 2. *转换*将对这个抽象的表示做一些处理，让它能做到编译器期望
* 它做到的事情。
*
* 3. *代码生成*接收处理之后的代码表示，然后把它转换成新的代码。
*/
/**
* 解析（Parsing）
* -------
*
* 解析一般来说会分成两个阶段：词法分析（Lexical Analysis）和语法分析（Syntactic Analysis）。
*
* 1. *词法分析*接收原始代码，然后把它分割成一些被称为 Token 的东西，这个过程是在词法分析
* 器（Tokenizer或者Lexer）中完成的。
*
* Token 是一个数组，由一些代码语句的碎片组成。它们可以是数字、标签、标点符号、运算符，
* 或者其它任何东西。
*
* 2. *语法分析* 接收之前生成的 Token，把它们转换成一种抽象的表示，这种抽象的表示描述了代
* 码语句中的每一个片段以及它们之间的关系。这被称为中间表示（intermediate representation）
* 或抽象语法树（Abstract Syntax Tree， 缩写为AST）
*
* 抽象语法树是一个嵌套程度很深的对象，用一种更容易处理的方式代表了代码本身，也能给我们
* 更多信息。
*
* 比如说对于下面这一行代码语句：
*
* (add 2 (subtract 4 2))
*
* 它产生的 Token 看起来或许是这样的：
*
* [
* { 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'
* }]
* }]
* }]
* }
*/
/**
* 转换（Transformation）
* --------------
*
* 编译器的下一步就是转换。它只是把 AST 拿过来然后对它做一些修改。它可以在同种语言下操
* 作 AST，也可以把 AST 翻译成全新的语言。
*
* 下面我们来看看该如何转换 AST。
*
* 你或许注意到了我们的 AST 中有很多相似的元素，这些元素都有 type 属性，它们被称为 AST
* 结点。这些结点含有若干属性，可以用于描述 AST 的部分信息。
*
* 比如下面是一个“NumberLiteral”结点：
*
* {
* type: 'NumberLiteral',
* value: '2'
* }
*
* 又比如下面是一个“CallExpression”结点：
*
* {
* type: 'CallExpression',
* name: 'subtract',
* params: [...nested nodes go here...]
* }
*
* 当转换 AST 的时候我们可以添加、移动、替代这些结点，也可以根据现有的 AST 生成一个全新
* 的 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'
* }]
* }]
* }]
* }
*
* So for the above AST we would go:
* 对于上面的 AST 的遍历流程是这样的：
*
* 1. Program - 从 AST 的顶部结点开始
* 2. CallExpression (add) - Program 的第一个子元素
* 3. NumberLiteral (2) - CallExpression (add) 的第一个子元素
* 4. CallExpression (subtract) - CallExpression (add) 的第二个子元素
* 5. NumberLiteral (4) - CallExpression (subtract) 的第一个子元素
* 6. NumberLiteral (4) - CallExpression (subtract) 的第二个子元素
*
* 如果我们直接在 AST 内部操作，而不是产生一个新的 AST，那么就要在这里介绍所有种类的抽象，
* 但是目前访问（visiting）所有结点的方法已经足够了。
*
* 使用“访问（visiting）”这个词的是因为这是一种模式，代表在对象结构内对元素进行操作。
*
* 访问者（Visitors）
* --------
*
* 我们最基础的想法是创建一个“访问者（visitor）”对象，这个对象中包含一些方法，可以接收不
* 同的结点。
*
* var visitor = {
* NumberLiteral() {},
* CallExpression() {}
* };
*
* 当我们遍历 AST 的时候，如果遇到了匹配 type 的结点，我们可以调用 visitor 中的方法。
*
* 一般情况下为了让这些方法可用性更好，我们会把父结点也作为参数传入。
*/
/**
* 代码生成（Code Generation）
* ---------------
*
* 编译器的最后一个阶段是代码生成，这个阶段做的事情有时候会和转换（transformation）重叠，
* 但是代码生成最主要的部分还是根据 AST 来输出代码。
*
* 代码生成有几种不同的工作方式，有些编译器将会重用之前生成的 token，有些会创建独立的代码
* 表示，以便于线性地输出代码。但是接下来我们还是着重于使用之前生成好的 AST。
*
* 我们的代码生成器需要知道如何“打印”AST 中所有类型的结点，然后它会递归地调用自身，直到所
* 有代码都被打印到一个很长的字符串中。
*
*/
/**
* 好了！这就是编译器中所有的部分了。
*
* 当然不是说所有的编译器都像我说的这样。不同的编译器有不同的目的，所以也可能需要不同的步骤。
*
* 但你现在应该对编译器到底是个什么东西有个大概的认识了。
*
* 既然我全都解释一遍了，你应该能写一个属于自己的编译器了吧？
*
* 哈哈开个玩笑，接下来才是重点 : P
*
* 所以我们开始吧...
*/
/**
* ============================================================================
* (/^▽^)/
* 词法分析器（Tokenizer）!
* ============================================================================
*/
/**
* 我们从第一个阶段开始，即词法分析，使用的是词法分析器（Tokenizer）。
*
* 我们只是接收代码组成的字符串，然后把它们分割成 token 组成的数组。
*
* (add 2 (subtract 4 2)) => [{ type: 'paren', value: '(' }, ...]
*/
// 我们从接收一个字符串开始，首先设置两个变量。
function tokenizer(input) {
// `current`变量类似指针，用于记录我们在代码字符串中的位置。
var current = 0;
// `tokens`数组是我们放置 token 的地方
var tokens = [];
// 首先我们创建一个 `while` 循环， `current` 变量会在循环中自增。
//
// 我们这么做的原因是，由于 token 数组的长度是任意的，所以可能要在单个循环中多次
// 增加 `current`
while (current < input.length) {
// 我们在这里储存了 `input` 中的当前字符
var char = input[current];
// 要做的第一件事情就是检查是不是右圆括号。这在之后将会用在 `CallExpressions` 中，
// 但是现在我们关心的只是字符本身。
//
// 检查一下是不是一个左圆括号。
if (char === '(') {
// 如果是，那么我们 push 一个 type 为 `paren`，value 为左圆括号的对象。
tokens.push({
type: 'paren',
value: '('
});
// 自增 `current`
current++;
// 结束本次循环，进入下一次循环
continue;
}
// 然后我们检查是不是一个右圆括号。这里做的时候和之前一样：检查右圆括号、加入新的 token、
// 自增 `current`，然后进入下一次循环。
if (char === ')') {
tokens.push({
type: 'paren',
value: ')'
});
current++;
continue;
}
// 继续，我们现在检查是不是空格。有趣的是，我们想要空格的本意是分隔字符，但这现在
// 对于我们储存 token 来说不那么重要。我们暂且搁置它。
//
// 所以我们只是简单地检查是不是空格，如果是，那么我们直接进入下一个循环。
var WHITESPACE = /\s/;
if (WHITESPACE.test(char)) {
current++;
continue;
}
// 下一个 token 的类型是数字。它和之前的 token 不同，因为数字可以由多个数字字符组成，
// 但是我们只能把它们识别为一个 token。
//
// (add 123 456)
// ^^^ ^^^
// Only two separate tokens
// 这里只有两个 token
//
// 当我们遇到一个数字字符时，将会从这里开始。
var NUMBERS = /[0-9]/;
if (NUMBERS.test(char)) {
// 创建一个 `value` 字符串，用于 push 字符。
var value = '';
// 然后我们循环遍历接下来的字符，直到我们遇到的字符不再是数字字符为止，把遇到的每
// 一个数字字符 push 进 `value` 中，然后自增 `current`。
while (NUMBERS.test(char)) {
value += char;
char = input[++current];
}
// 然后我们把类型为 `number` 的 token 放入 `tokens` 数组中。
tokens.push({
type: 'number',
value: value
});
// 进入下一次循环。
continue;
}
// 最后一种类型的 token 是 `name`。它由一系列的字母组成，这在我们的 lisp 语法中
// 代表了函数。
//
// (add 2 4)
// ^^^
// Name token
//
var LETTERS = /[a-z]/i;
if (LETTERS.test(char)) {
var value = '';
// 同样，我们用一个循环遍历所有的字母，把它们存入 value 中。
while (LETTERS.test(char)) {
value += char;
char = input[++current];
}
// 然后添加一个类型为 `name` 的 token，然后进入下一次循环。
tokens.push({
type: 'name',
value: value
});
continue;
}
// 最后如果我们没有匹配上任何类型的 token，那么我们抛出一个错误。
throw new TypeError('I dont know what this character is: ' + char);
}
// 词法分析器的最后我们返回 tokens 数组。
return tokens;
}
/**
* ============================================================================
* ヽ/❀o ل͜ o\ﾉ
* 语法分析器（Parser）!!!
* ============================================================================
*/
/**
* 语法分析器接受 token 数组，然后把它转化为 AST
*
* [{ type: 'paren', value: '(' }, ...] => { type: 'Program', body: [...] }
*/
// 现在我们定义 parser 函数，接受 `tokens` 数组
function parser(tokens) {
// 我们再次声明一个 `current` 变量作为指针。
var current = 0;
// 但是这次我们使用递归而不是 `while` 循环，所以我们定义一个 `walk` 函数。
function walk() {
// walk函数里，我们从当前token开始
var token = tokens[current];
// 对于不同类型的结点，对应的处理方法也不同，我们从 `number` 类型的 token 开始。
// 检查是不是 `number` 类型
if (token.type === 'number') {
// 如果是，`current` 自增。
current++;
// 然后我们会返回一个新的 AST 结点 `NumberLiteral`，并且把它的值设为 token 的值。
return {
type: 'NumberLiteral',
value: token.value
};
}
// 接下来我们检查是不是 CallExpressions 类型，我们从左圆括号开始。
if (
token.type === 'paren' &&
token.value === '('
) {
// 我们会自增 `current` 来跳过这个括号，因为括号在 AST 中是不重要的。
token = tokens[++current];
// 我们创建一个类型为 `CallExpression` 的根节点，然后把它的 name 属性设置为当前
// token 的值，因为紧跟在左圆括号后面的 token 一定是调用的函数的名字。
var node = {
type: 'CallExpression',
name: token.value,
params: []
};
// 我们再次自增 `current` 变量，跳过当前的 token
token = tokens[++current];
// 现在我们循环遍历接下来的每一个 token，直到我们遇到右圆括号，这些 token 将会
// 是 `CallExpression` 的 `params`（参数）
//
// 这也是递归开始的地方，我们采用递归的方式来解决问题，而不是去尝试解析一个可能有无限
// 层嵌套的结点。
//
// 为了更好地解释，我们来看看我们的 Lisp 代码。你会注意到 `add` 函数的参数有两个，
// 一个是数字，另一个是一个嵌套的 `CallExpression`，这个 `CallExpression` 中
// 包含了它自己的参数（两个数字）
//
// (add 2 (subtract 4 2))
//
// 你也会注意到我们的 token 数组中有多个右圆括号。
//
// [
// { 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: ')' } <<< 右圆括号
// ]
//
// 遇到嵌套的 `CallExpressions` 时，我们将会依赖嵌套的 `walk` 函数来
// 增加 `current` 变量
//
// 所以我们创建一个 `while` 循环，直到遇到类型为 `'paren'`，值为右圆括号的 token。
while (
(token.type !== 'paren') ||
(token.type === 'paren' && token.value !== ')')
) {
// 我们调用 `walk` 函数，它将会返回一个结点，然后我们把这个节点
// 放入 `node.params` 中。
node.params.push(walk());
token = tokens[current];
}
// 我们最后一次增加 `current`，跳过右圆括号。
current++;
// 返回结点。
return node;
}
// 同样，如果我们遇到了一个类型未知的结点，就抛出一个错误。
throw new TypeError(token.type);
}
// 现在，我们创建 AST，根结点是一个类型为 `Program` 的结点。
var ast = {
type: 'Program',
body: []
};
// 现在我们开始 `walk` 函数，把结点放入 `ast.body` 中。
//
// 之所以在一个循环中处理，是因为我们的程序可能在 `CallExpressions` 后面包含连续的两个
// 参数，而不是嵌套的。
//
// (add 2 2)
// (subtract 4 2)
//
while (current < tokens.length) {
ast.body.push(walk());
}
// 最后我们的语法分析器返回 AST
return ast;
}
/**
* ============================================================================
* ⌒(❀>◞౪◟<❀)⌒
* 遍历器!!!
* ============================================================================
*/
/**
* 现在我们有了 AST，我们需要一个 visitor 去遍历所有的结点。当遇到某个类型的结点时，我们
* 需要调用 visitor 中对应类型的处理函数。
*
* traverse(ast, {
* Program(node, parent) {
* // ...
* },
*
* CallExpression(node, parent) {
* // ...
* },
*
* NumberLiteral(node, parent) {
* // ...
* }
* });
*/
// 所以我们定义一个遍历器，它有两个参数，AST 和 vistor。在它的里面我们又定义了两个函数...
function traverser(ast, visitor) {
// `traverseArray` 函数允许我们对数组中的每一个元素调用 `traverseNode` 函数。
function traverseArray(array, parent) {
array.forEach(function(child) {
traverseNode(child, parent);
});
}
// `traverseNode` 函数接受一个 `node` 和它的父结点 `parent` 作为参数，这个结点会被
// 传入到 visitor 中相应的处理函数那里。
function traverseNode(node, parent) {
// 首先我们看看 visitor 中有没有对应 `type` 的处理函数。
var method = visitor[node.type];
// 如果有，那么我们把 `node` 和 `parent` 都传入其中。
if (method) {
method(node, parent);
}
// 下面我们对每一个不同类型的结点分开处理。
switch (node.type) {
// 我们从顶层的 `Program` 开始，Program 结点中有一个 body 属性，它是一个由若干
// 个结点组成的数组，所以我们对这个数组调用 `traverseArray`。
//
// （记住 `traverseArray` 会调用 `traverseNode`，所以我们会递归地遍历这棵树。）
case 'Program':
traverseArray(node.body, node);
break;
// 下面我们对 `CallExpressions` 做同样的事情，遍历它的 `params`。
case 'CallExpression':
traverseArray(node.params, node);
break;
// 如果是 `NumberLiterals`，那么就没有任何子结点了，所以我们直接 break
case 'NumberLiteral':
break;
// 同样，如果我们不能识别当前的结点，那么就抛出一个错误。
default:
throw new TypeError(node.type);
}
}
// 最后我们对 AST 调用 `traverseNode`，开始遍历。注意 AST 并没有父结点。
traverseNode(ast, null);
}
/**
* ============================================================================
* ⁽(◍˃̵͈̑ᴗ˂̵͈̑)⁽
* 转换器!!!
* ============================================================================
*/
/**
* 下面是转换器。转换器接收我们在之前构建好的 AST，然后把它和 visitor 传递进入我们的遍历
* 器中 ，最后得到一个新的 AST。
*
* ----------------------------------------------------------------------------
* 原始的 AST | 转换后的 AST
* ----------------------------------------------------------------------------
* { | {
* type: 'Program', | type: 'Program',
* body: [{ | body: [{
* type: 'CallExpression', | type: 'ExpressionStatement',
* name: 'add', | expression: {
* params: [{ | type: 'CallExpression',
* type: 'NumberLiteral', | callee: {
* value: '2' | type: 'Identifier',
* }, { | name: 'add'
* type: 'CallExpression', | },
* name: 'subtract', | arguments: [{
* params: [{ | type: 'NumberLiteral',
* type: 'NumberLiteral', | value: '2'
* value: '4' | }, {
* }, { | type: 'CallExpression',
* type: 'NumberLiteral', | callee: {
* value: '2' | type: 'Identifier',
* }] | name: 'subtract'
* }] | },
* }] | arguments: [{
* } | type: 'NumberLiteral',
* | value: '4'
* ---------------------------------- | }, {
* | type: 'NumberLiteral',
* | value: '2'
* | }]
* (那一边比较长/w\) | }]
* | }
* | }]
* | }
* ----------------------------------------------------------------------------
*/
// 定义我们的转换器函数，接收 AST 作为参数
function transformer(ast) {
// 创建 `newAST`，它与我们之前的 AST 类似，有一个类型为 Program 的根节点。
var newAst = {
type: 'Program',
body: []
};
// 下面的代码会有些奇技淫巧，我们在父结点上使用一个属性 `context`（上下文），这样我们就
// 可以把结点放入他们父结点的 context 中。当然可能会有更好的做法，但是为了简单我们姑且
// 这么做吧。
//
// 注意 context 是一个*引用*，从旧的 AST 到新的 AST。
ast._context = newAst.body;
// 我们把 AST 和 visitor 函数传入遍历器
traverser(ast, {
// 第一个 visitor 方法接收 `NumberLiterals`。
NumberLiteral: function(node, parent) {
// 我们创建一个新结点，名字叫 `NumberLiteral`，并把它放入父结点的 context 中。
parent._context.push({
type: 'NumberLiteral',
value: node.value
});
},
// 下一个，`CallExpressions`。
CallExpression: function(node, parent) {
// 我们创建一个 `CallExpression` 结点，里面有一个嵌套的 `Identifier`。
var expression = {
type: 'CallExpression',
callee: {
type: 'Identifier',
name: node.name
},
arguments: []
};
// 下面我们在原来的 `CallExpression` 结点上定义一个新的 context，它是 expression
// 中 arguments 这个数组的引用，我们可以向其中放入参数。
node._context = expression.arguments;
// 然后来看看父结点是不是一个 `CallExpression`，如果不是...
if (parent.type !== 'CallExpression') {
// 我们把 `CallExpression` 结点包在一个 `ExpressionStatement` 中，这么做是因为
// 单独存在（原文为top level）的 `CallExpressions` 在 JavaScript 中也可以被当做
// 是声明语句。
//
// 译者注：比如 `var a = foo()` 与 `foo()`，后者既可以当作表达式给某个变量赋值，也
// 可以作为一个独立的语句存在。
expression = {
type: 'ExpressionStatement',
expression: expression
};
}
// 最后我们把 `CallExpression`（可能是被包起来的） 放入父结点的 context 中。
parent._context.push(expression);
}
});
// 最后返回创建好的新 AST。
return newAst;
}
/**
* ============================================================================
* ヾ（〃＾∇＾）ﾉ♪
* 代码生成器!!!!
* ============================================================================
*/
/**
* 现在只剩最后一步啦：代码生成器。
*
* 我们的代码生成器会递归地调用它自己，把 AST 中的每个结点打印到一个很大的字符串中。
*/
function codeGenerator(node) {
// 对于不同 `type` 的结点分开处理。
switch (node.type) {
// 如果是 `Program` 结点，那么我们会遍历它的 `body` 属性中的每一个结点，并且递归地
// 对这些结点再次调用 codeGenerator，再把结果打印进入新的一行中。
case 'Program':
return node.body.map(codeGenerator)
.join('\n');
// 对于 `ExpressionStatements`,我们对它的 expression 属性递归调用，同时加入一个
// 分号。
case 'ExpressionStatement':
return (
codeGenerator(node.expression) +
';' // << (...因为我们喜欢用*正确*的方式写代码)
);
// 对于 `CallExpressions`，我们会打印出 `callee`，接着是一个左圆括号，然后对
// arguments 递归调用 codeGenerator，并且在它们之间加一个逗号，最后加上右圆括号。
case 'CallExpression':
return (
codeGenerator(node.callee) +
'(' +
node.arguments.map(codeGenerator)
.join(', ') +
')'
);
// 对于 `Identifiers` 我们只是返回 `node` 的 name。
case 'Identifier':
return node.name;
// 对于 `NumberLiterals` 我们只是返回 `node` 的 value
case 'NumberLiteral':
return node.value;
// 如果我们不能识别这个结点，那么抛出一个错误。
default:
throw new TypeError(node.type);
}
}
/**
* ============================================================================
* (۶* ‘ヮ’)۶”
* !!!!!!!!!!!!编译器!!!!!!!!!!!
* ============================================================================
*/
/**
* 最后！我们创建 `compiler` 函数，它只是把上面说到的那些函数连接到一起。
*
* 1. input => tokenizer => tokens
* 2. tokens => parser => ast
* 3. ast => transformer => newAst
* 4. newAst => generator => output
*/
function compiler(input) {
var tokens = tokenizer(input);
var ast = parser(tokens);
var newAst = transformer(ast);
var output = codeGenerator(newAst);
// 然后返回输出!
return output;
}
/**
* ============================================================================
* (๑˃̵ᴗ˂̵)و
* !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!你做到了!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
* ============================================================================
*/
// 现在导出所有接口...
module.exports = {
tokenizer: tokenizer,
parser: parser,
transformer: transformer,
codeGenerator: codeGenerator,
compiler: compiler
};The above is a detailed introduction to the sample code for writing an ultra-small compiler using JavaScript. For more related content, please pay attention to the PHP Chinese website (www.php.cn)!
Statement：
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Previous article：Detailed introduction to implementing a countdown timer using JS code in 18 lines of codeNext article：Detailed introduction to implementing a countdown timer using JS code in 18 lines of code
Related articles
See more- An in-depth analysis of the Bootstrap list group component
- Detailed explanation of JavaScript function currying
- Complete example of JS password generation and strength detection (with demo source code download)
- Angularjs integrates WeChat UI (weui)
- How to quickly switch between Traditional Chinese and Simplified Chinese with JavaScript and the trick for websites to support switching between Simplified and Traditional Chinese_javascript skills