时隔四个月的更新
其实后面的递归步骤只是借助 JS 的引用数据类型特性,模拟了类似 c 语言的指针功能 😐 ,就是简单的传递指针,不断生成类似链表的数据结构,填充数据,最终得到目标代码…而已..已.
起初
the-super-tiny-compiler 是 github 上的一个使用 js 编写的编译器,代码注释中称其可能是最小的编译器,可以将 lisp 风格的语言编写为 c 风格的语言
这个编译器项目可以说是麻雀虽小,五脏俱全
但是本人再阅读器源代码的时候,在生成新 ast 的过程中,对其递归过程产生了不解
所以从现在开始,要对源代码进行一下分析
编译器原理简单来说就是
词法分析
语法分析(生成 ast)
将 oldAst -> newAst
最后将产生的 newAst 生成目标语言语法进行输出
将 (add 2 (subtract 4 2))
作为输入,得到的 ast 结构如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| 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", }, ], }, ], }, ], };
|
得到这个结构后,执行了这样一个函数
1 2 3 4 5 6 7 8 9
| function transformer(ast) { let newAst = { type: "Program", body: [] }
ast._context = newAst.body }
|
给 ast 对象下添加了一个新属性,将该属性指向了 newAst 的 body 属性中
然后向下执行了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
| function transformer(ast) { let newAst = { type: "Program", body: [] }
ast._context = newAst.body
traverser(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, }); }, },
CallExpression: { enter(node, parent) { let expression = { type: 'CallExpression', callee: { type: 'Identifier', name: node.name }, arguments: [] }
node._context = expression.arguments;
if (parent.type !== "CallExpression") { expression = { type: 'ExpressionStatement', expression } }
parent._context.push(expression) } }
})
return newAst }
|
可以看到,newAst 的数据变化只执行了一个 traverser 函数就完成了,函数把刚刚的 ast 当作参数,以及根据不同类型对 newAst 中的 body 复制的行为,
这个函数的内部是这样子的
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| function traverser(ast, visitor) {
function traverseArray(array, parent) { }
function traverseNode(node, parent) { let methods = visitor[node.type]
if (methods && methods.enter) { methods.enter(node, parent) }
switch (node.type) { case "Program": traverseArray(node.body, node); break;
case "CallExpression": traverseArray(node.params, node) break;
case "NumberLiteral": case "StringLiteral": break;
default: throw new TypeError(node.type) } }
traverseNode(ast, null)
}
|
执行他的时候,主线为 traverser -> traverseNode ->
ast 作为 node 参数传入进去,这个函数的执行过程就进行了递归调用
第一次执行 methods 为 undefined 然后进入 switch 语句中
第一次的 ast type 是 Program 然后就将 ast 的 body 当作参数传递进去,然后 break;掉
至此,函数主线已经执行完毕了
之后的执行流程则是对 ast.body 进行的一个伪递归或者叫嵌套调用,函数每次根据其传入的 tree 参数,根据表达式,参数,去判断是否生成新的 ast
值得一提的是,在生成 newAst 的时候
有类似这样的语句
node._context = expression.arguments;
将传入节点的_context 属性指向当前对象下的某个属性,达到引用的效果,这时,使用 visitor 遍历语法数的时候,不管传入的对象是什么,因为已经在上层构建好了内存地址的引用关系,所以只需要给 parent._context 属性添加只就可以了
最后的最后就是将生成的新 ast 生成我们的目标语言,这个没什么好说的,递归生成字符串就好了。
总结,看似简单的小项目,如果自己去实现,不知到要考虑多少细节,所以说,前端深入之路,任重而道远!