the-super-tiny-compiler源码解析

一.目标

通过实现编译器来支持简单的表达式转换，把Lisp风格的函数调用转换成C风格的，例如：

即输入，要求输出

二.设计

把编译工作拆分成3部分：

解析：把代码字符串转成抽象表示

转换：把抽象表示修改成想要的样子

代码生成：把转换过的抽象表示转成新代码字符串

这里的解析包括词法分析及语法分析，由词法分析器把代码串转换成一系列词法单元（token），再由语法分析器生成能够描述语法结构（包括语法成分及其关系）的中间表示形式（Intermediate Representation）或抽象语法树（Abstract Syntax Tree）

从结构上看，词法单元是一组描述独立语法成分（比如数值，标签，标点符号，操作符等）的小对象，抽象语法树（简称AST）是个深层嵌套的对象，易于处理并且携带着语法结构信息，例如：

转换阶段要修改AST，也就是遍历上面生成的树结构，进行节点级操作（增/删/改节点）和属性级操作（增/删/改属性）。当然，也可以创建一棵新树

实现上，可以深度优先遍历，没什么特别的，逐节点处理倒是有点意思：

把访问节点的操作提出来作为层，遍历过程中按词法单元类型调用对应的方法即可，算是个小技巧

改完AST，就到了最后的代码生成环节，遍历收集，把AST还原成代码串就好了

三.实现

词法分析

遍历代码字符串，拆出各个词素，包成词法单元的形式

语法分析

为了应对函数调用嵌套的情况，改用递归来遍历token序列

遍历

递归遍历AST结构，遍历过程中通知，有点切面的意思

转换

由于遍历（）与修改（）操作分开成了2层，不太容易在遍历旧AST节点的同时明确知道对应的新AST父节点，这里采用了简单粗暴的方式，直接通过新增属性让旧AST节点的父节点持有待操作的新AST节点引用，能用，但污染了旧AST

代码生成

再把AST转回代码字符串，该加分号的加分号，该添括号的添括号……

流程串接

把上面所有环节串起来，构成简单的编译器，确实只有200行的样子，试玩一下：

四.优化

2个可优化点：

词法分析：逐字符匹配比较啰嗦，效率可接受的话，正则表达式更清晰

转换：生成新AST的方式比较脏，污染了旧AST，可以通过额外的数据结构记录新旧AST的联系，避免影响旧AST

更清晰的词法分析

比如各词素对应的正则表达式：

比较清晰了，如果想要提升扩展性的话，可以把词素相关的进一步配置化：

然后以统一的方式处理这些词素：

更干净的转换

生成新树要做两件事：

节点映射

创建树结构

节点映射好办，该把新节点往哪挂是个问题。与实现上是独立的两层，所以需要手动记录新旧两棵树的联系，比如上面转换部分源码中的：

这样就知道当前正在访问的旧节点对应的新节点应该挂到新树的哪个位置了，例如：

但这样实现比较脏（污染了传入的旧树）。更合理的做法是以非侵入的方式记录新树中当前活跃的节点容器，由于函数调用允许嵌套，需要用栈结构来记录：

并在递归遍历旧树过程中维持这种联系：

这样就不会再污染旧树了，并且代价不很高（一个额外的数据结构）

五.源码

Github地址：https://github.com/ayqy/the-super-tiny-compiler

P.S.包括带详细注释的原版，以及优化之后的实现

参考资料

The Super Tiny Compiler

jamiebuilds/the-super-tiny-compiler

联系ayqy