七的博客
使用JavaScript语言实现迷你版本的编译器(三)-抽象语法树转换
使用JavaScript语言实现迷你版本的编译器(三)-抽象语法树转换
构建编译器的一个重要环节是将一种编程语言的抽象语法树 ( AST) 转换为另一种语言的 AST。
1. AST 转换的基本概念
1.1 转换的目的
AST 转换的主旨在于将一种编程语言的表达逻辑映射到另一种编程语言的语法规则上。 在这个章节中，我们将 Lisp 语言的抽象语法树转成 JavaScript 语言的抽象语法树。 这种转换主要是为了满足 JavaScript 语言的语法要求，这是一个转换代码的中间步骤，以确保代码在目标编程语言中具有正确的语法形式。
1.2 转换过程的类比
为了更好地理解 AST 转换的流程，我们可以将这个过程比作是方言之间的翻译。 中国国内有很多种方言，基本每个地方都会有自己独特的语言。假如 Lisp 语言是北京话， JavaScript 语言是广东话，尽管这两种语言的表达习惯跟语法结构可能不太一样，但是最终沟通的目的都是一样的。
但是如果没有翻译的话，说这两种语言的人大概率是无法理解对方想表达的意思。AST 转换其实就有点类似于这样的一个翻译。
Lisp 语言抽象语法树：
{
"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"
}
]
}
]
}
]
}
转换后的 JavaScript 抽象语法树：
{
type: 'Program',
body: [{
type: 'ExpressionStatement',
expression: {
type: 'CallExpression',
callee: {
type: 'Identifier',
name: 'add'
},
arguments: [{
type: 'NumberLiteral',
value: '2'
}, {
type: 'CallExpression',
callee: {
type: 'Identifier',
name: 'subtract'
},
arguments: [{
type: 'NumberLiteral',
value: '4'
}, {
type: 'NumberLiteral',
value: '2'
}]
}]
}
}]
};
2. 实现 AST转换
2.1 转换逻辑梳理
逻辑梳理的文字描述可能比较抽象，如果不能理解可以直接跳到代码区域进行阅读，然后再回过来看文字描述。
在转换开始之前，我们先设计梳理下转换逻辑。 我们需要先编写一个函数，它接受 Lisp AST 作为输入参数， 并输出 JavaScript AST。 函数使用遍历器 ( traverser ) 以及访问者 ( visitor ) 模式来构造新的 AST。伪代码如下：
// 遍历器是用来遍历抽象语法树的每一个节点，由于 AST 是一个嵌套的数据结构，通常表示为树，包含源代码的结构以及语法信息。
function traverser(){
//... 这里实现遍历抽象语法树的每一个节点
}
function transformer(lispAst) {
let javaScriptAst = {};
traverser(lispAst,visitor)
return javaScriptAst;
}
2.2 转换策略
针对这几种 Lisp 抽象语法树的节点，我们需要分别做不同的处理策略：
NumberLiteral 类型的节点，我们直接向父节点的 _context 中添加一个新的 NumberLiteral 节点即可。
StringLiteral 类型的节点，我们直接向父节点的 _context 中添加一个新的 StringLiteral 节点即可。
CallExpression 类型的节点，这种类型处理比较复杂，因为是处理一个函数调用表达式。我们需要把原先的 Lisp 语言的 CallExpression 转换成 JavaScript 语言的 CallExpression 。在 **JavaScript **语言的抽象语法树中，函数调用也需要有 CallExpression ，但是它的结构会有所不同。 它需要包含一个表示调用函数的 callee 属性以及一个数组 arguments 来包含所有传递给函数的参数。
3. 编写 AST 转换器
3.1 构建新的 AST 结构
首先我们先创建一个新的 JavaScript AST 对象，其根节点为 Program 类型。
let newAst = {
"type": "Program",
"body": []
};
3.2 实现节点转换逻辑
接下来将根据 Lisp AST 中不同的节点类型实现对应的转换逻辑，确保能够添加到新的 JavaScript AST 中。
3.2.1 转换字面量
对于 NumberLiteral 以及 StringLiteral 节点，我们直接将其复制到新的 AST 中即可。
NumberLiteral: {
enter(node, parent) {
parent._context.push({
type: 'NumberLiteral',
value: node.value
});
}
},
StringLiteral: {
enter(node, parent) {
parent._context.push({
type: 'StringLiteral',
value: node.value
});
}
},
3.2.2 函数调用处理
处理函数调用表达式时，需要创建新的 JavaScript 表达式节点，还需要判断是否需要包装在一个 ExpressionStatement 中。
CallExpression: {
enter(node, parent) {
// 创建一个新的 CallExpression 节点,包含 Identifier
let 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 中
// 因为在 JavaScript 中, 顶层的 CallExpression 通常是语句
expression = {
type: "ExpressionStatement",
expression: expression
};
}
// 将可能被包装的 CallExpression 节点推入父节点的 context 中
parent._context.push(expression);
}
}
3.2.3 完整的转换代码
function transformer(ast) {
// 这里传入一个 list 的 AST 节点信息
// 创建一个新的 AST 节点, 有一个类型为 Program 的节点
let newAst = {
"type": "Program",
"body": []
};
// 这里有一个技巧, 通过在旧节点上添加一个 context 属性来引用新的 AST 节点
// context 是旧 AST 到新 AST 的一个引用
ast._context = newAst.body;
// 调用遍历器, 传入 AST 以及访问者对象
traverser(ast, {
// 对于NumberLiteral和StringLiteral节点，它们被直接复制到新AST中，类型不变。
// visitor 处理 NumberLiteral 类型节点
NumberLiteral: {
enter(node, parent) {
// 创建一个新的 NumberLiteral 节点, 压入 父节点的 context 中
parent._context.push({
"type": "NumberLiteral",
value: node.value
})
}
},
// 处理 StringLiteral 类型节点
StringLiteral: {
enter(node, parent) {
parent._context.push({
"type": "StringLiteral",
"value": node.value
})
}
},
// 处理 CallExpression 类型节点
// 对于CallExpression节点，转换更复杂。每个CallExpression都被转换成一个新的CallExpression节点，但是如果它不是另一个CallExpression的子节点（即它是顶层调用），则会被包装在一个ExpressionStatement中，因为在JavaScript中，独立的函数调用需要是一个语句。
CallExpression: {
enter(node, parent) {
// 创建一个新的 CallExpression 节点,包含 Identifier
let 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 中
// 因为在 JavaScript 中, 顶层的 CallExpression 通常是语句
expression = {
type: "ExpressionStatement",
expression: expression
};
}
// 将可能被包装的 CallExpression 节点推入父节点的 context 中
parent._context.push(expression);
}
}
})
// 函数结束时返回新创建的 AST
return newAst;
}
function traverser(ast, visitor) {
// traverseArray 函数允许我们遍历一个数组,调用 traverseNode
function traverseArray(array, parent) {
array.forEach(child => {
traverseNode(child, parent)
})
}
// 接受一个节点以及它的父节点
function traverseNode(node, parent) {
// 尝试从 visitor 对象中找出对应类型的方法集合
let methods = visitor[node.type];
// 如果存在 enter 方法, 递归进行子节点前调用它
if (methods && methods.enter) {
methods.enter(node, parent);
}
// 根据当前的节点类型, 选择不同的遍历策略
switch (node.type) {
// Program 节点则遍历它的 body 属性中的每一个节点
case 'Program':
traverseArray(node.body, node);
break;
// CallExpression节点就直接遍历它的params属性中的每一个节点。
case 'CallExpression':
traverseArray(node.params, node);
break;
// NumberLiteral 以及 StringLiteral 没有子节点,直接不做处理
case 'NumberLiteral':
case 'StringLiteral':
break
default:
throw new TypeError(node.type);
}
// 如果存在 exit 方法, 就在完成子节点的递归后调用它
if (methods && methods.exit) {
methods.exit(node, parent);
}
}
// 最开始调用 traverseNode 来遍历, 顶层 AST 父节点是 null
traverseNode(ast, null);
}
4. 代码测试
在 test.js 函数中添加如下代码：
const {
transformer,
} = require('./tiny-js-compiler');
const assert = require('assert');
const 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'
}]
}]
}]
};
const newAst = {
type: 'Program',
body: [{
type: 'ExpressionStatement',
expression: {
type: 'CallExpression',
callee: {
type: 'Identifier',
name: 'add'
},
arguments: [{
type: 'NumberLiteral',
value: '2'
}, {
type: 'CallExpression',
callee: {
type: 'Identifier',
name: 'subtract'
},
arguments: [{
type: 'NumberLiteral',
value: '4'
}, {
type: 'NumberLiteral',
value: '2'
}]
}]
}
}]
};
assert.deepStrictEqual(transformer(ast), newAst, 'Transformer should turn `ast` into a `newAst`');
console.log('Test case Passed!');
执行运行命令：
node test.js
如果看到 Test case Passed! 则说明测试通过，编写的 parser() 函数达到了我们想要的效果。
5.总结
在这个章节，我们实现了 AST 转换的基本概念以及基本的转换步骤。使用 JavaScript 实现了一个简单的转换器，将 Lisp语言的 AST 转换成了 JavaScript 语言的 AST。在这个过程中，还包括了对遍历器以及访问者模式的使用。 下一章节我们将进行目标代码生成。