编译原理
我只看了龙书的前两章，主要目的是对编译原理有个大概的认知。然后对着大佬开源的 the-super-tiny-compiler，虽然只有几百行代码，麻雀虽小五脏俱全，将书里面抽象的理论和具体的实践结合起来能更好的理解。
编译简介
抽象语法树是一个嵌套程度很深的对象，用一种更容易处理的方式代表了代码本身，也能给我们更多信息。
如 10+3*(7-2)-4 可以表示为
-
|
+<---+--->4
|
10<---+--->*
|
3<---+--->-
|
7<---+--->2
符号表管理：编译器可以在编译期间记录源程序中使用的标识符并收集与标识符相关的各种属性信息。标识符的属性信息标明了该标识符的存储位置、类型、作用域。
- 中间代码生成
- 除赋值外，每个三地址指令最多只有一个操作符，所以编译器必须确定完成操作的顺序，如乘除的优先级大于加减
- 代码优化，改进中间代码，产生执行速度更快的机器代码
- 代码生成，生成可重定位的机器代码或者汇编代码
预处理器，编译器的输入可能由一个或者多个预处理器产生。如 c 语言能用 \
汇编器，某些编译器产生汇编代码，汇编代码需要交给汇编器作进一步的处理，产生机器代码，交给装配器（loader）或者连接编辑器（link-editor）处理。
装配器，完成程序的装入和连接编辑两项功能。 连接编辑器允许我们将多个可重定位机器代码的文件组装成一个程序。
the-super-tiny-compiler
作者只用了几百行的 js 代码实现了一个很小的编译器，可以将 lisp 风格的函数调用转换为 c 风格。主要目的是为了展示如何写一个编译器。
编译器通常分成三个阶段：
- 解析（Parsing）
- 词法分析（Lexical Analysis），词法分析 接收原始代码，然后把它分割成一些被称为 Token 的东西，这个过程是在词法分析器（Tokenizer 或者 Lexer）中完成的
- 语法分析（Syntactic Analysis），语法分析 接收之前生成的 Token，把它们转换成一种抽象的表示，这种抽象的表示描述了代码语句中的每一个片段以及它们之间的关系。这被称为中间表示（intermediate representation）或抽象语法树（Abstract Syntax Tree， 缩写为 AST）
- 转换（Transformation），编译器的目标是把输入的代码转换成一种新的语言，所以我们可以通过转换产生一个针对新语言的全新的 AST
- 创建一个访问者（Visitor） 对象，对 AST 里面不同的 type 来进行处理，
- 代码生成（Code Generation），根据转换后的 AST 来生成代码
具体实现：
- 词法分析器（Tokenizer），
input => tokenizer => tokens，将原始代码字符串拆分成 token 数组，[{ type: 'paren', value: '(' }, ...] - 语法分析器（Parser），
tokens => parser => ast，接受 token 数组，转换成 AST[{ type: 'paren', value: '(' }, ...] => { type: 'Program', body: [...] } - 遍历器
traverser(ast, visitor)，ast => transformer => newAst，使用深入优先算法遍历 node，然后根据 node type 选择对应的 visitor 来处理 - 转换器
function transformer(ast)，newAst => generator => output，定义好 visitor，调用遍历器来处理 - 代码生成
// lisp 函数
(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'
}]
}]
}]
}
function compiler(input) {
var tokens = tokenizer(input);
var ast = parser(tokens);
var newAst = transformer(ast);
var output = codeGenerator(newAst);
// 然后返回输出!
return output;
}