微型编译器
大多数编译器分为三个主要阶段：解析，转换，和代码生成
- 解析正在获取原始代码并将其转换为更抽象的代码代码的表示形式。
- 转换接受此抽象表示并进行操作编译器想要的任何东西。
- 代码生成采用代码的转换表示形式，将其转换为新代码。
解析通常分为两个阶段：词法分析和语法分析。
词法分析提取原始代码并将其拆分为一个个有效标识，它们是由微小的小物体组成的数组，描述了一个孤立的片断的语法。它们可以是数字，标签，标点符号，运算符，
语法分析将标记重新格式化为描述语法的每个部分及其关系的表示形式彼此。这称为中间表示或抽象语法树。
抽象语法树，简称AST，是一个深层嵌套的对象，以易于使用的方式表示代码，并告诉我们很多信息。
例如：
(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: ')' },
]
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',
* }]
* }]
* }]
* }
实战目标：
编写一个函数 compiler 使得 input 转换为 output,
const input = "(add 3 (div 8 2))";
//转换为下面代码
const output = "add(3, div(8, 2))";
词法分析 - Tokenizer
词法分析，目标将一段代码分割成一个个的单词和标点符号。
词法分析的函数也叫做扫描 scanner。扫描器读取代码后，依据预定的规则合并生成成一个个的标识 tokens（移除空白符，注释）。生成 tokens 列表。
数据结构如下：
[
{ type: "paren", value: "(" },
{ type: "name", value: "add" },
{ type: "number", value: "3" },
{ type: "paren", value: "(" },
{ type: "name", value: "div" },
{ type: "number", value: "8" },
{ type: "number", value: "2" },
{ type: "paren", value: ")" },
{ type: "paren", value: ")" }
];
语法分析 - Parser
语法分析，主要目的在于通过分析词法分析生成的词法单元流，构建出一个代表当前程序的抽象语法树 ast。
由上面的 tokenizer 进行分词后，其实并没有表达出语法。此时需要设计一个 parser 将 tokens 转换为 ast。parser 指针将逐个解析 token，在以上简化的 tokens 列表中，parser 在解析到左括号 “(” 此 token 时，进入递归，只要下一个 token 不是右括号 “)”，就不会结束递归。
最终指针移至 tokens 列表尾部，消费完成所有 tokens，此时生成完整的 ast。
数据结构如下：
{
"type": "Program",
"body": [
{
"type": "CallExpression",
"name": "add",
"params": [
{
"type": "NumberLiteral",
"value": "3"
},
{
"type": "CallExpression",
"name": "div",
"params": [
{
"type": "NumberLiteral",
"value": "8"
},
{
"type": "NumberLiteral",
"value": "2"
}
]
}
]
}
]
}
因此，通过递归生成了以上的 CallExpression 嵌套的模块。
代码转换 - Transformer
这里主要的工作，通过语法映射，将 haskell 的抽象语法树转成 javascript 的抽象语法树。这里有一个很重要的概念就是 traverser。这是一个可以通过匹配类型从而遍历访问 ast 某个节点的工具函数。
traverse(ast, {
Program: {
enter(node, parent) {
// ...
},
exit(node, parent) {
// ...
}
},
CallExpression: {
enter(node, parent) {
// ...
},
exit(node, parent) {
// ...
}
},
NumberLiteral: {
enter(node, parent) {
// ...
},
exit(node, parent) {
// ...
}
}
});
traverse 的第一个参数是 ast，第二个参数我们称作 visitor（访问器）。我们定义了每个 type 的 visitor。在 traverse 递归遍历每个节点的时候，都会在对应的时机执行 enter、exit 回调函数。
有了上述的 traverse 工具后，我们可以在访问每个节点的时候，不断生成、并调整我们的新语法树。
最终经过 transformer 转换后的 javascript 的 ast 语法树数据结构如下：
{
"type": "Program",
"body": [
{
"type": "ExpressionStatement",
"expression": {
"type": "CallExpression",
"callee": {
"type": "Identifier",
"name": "add"
},
"arguments": [
{
"type": "NumberLiteral",
"value": "3"
},
{
"type": "CallExpression",
"callee": {
"type": "Identifier",
"name": "div"
},
"arguments": [
{
"type": "NumberLiteral",
"value": "8"
},
{
"type": "NumberLiteral",
"value": "2"
}
]
}
]
}
}
]
}
代码生成 - Generator
代码生成器主要的职责是将转换后的 ast 通过特定规则组合为新的代码。
在得到通过 transformer 转换后的新语法树后，代码生成器同样递归的调用自己打印 ast 中的每一个节点，最终生成一个长长的代码字符串。也就是我们目标的：output。
小结
本文是本人在进行这方面学习的时候看其他的一些大佬的技术博客做的一些笔记类的转载型文章，还有很多细节尚未触及，在今后的学习中会陆续添加进来。