AST是个什么东西？

Abstract Syntax Tree（抽象语法树），简称AST；是源代码的抽象语法结构的树状表现形式。

超级迷你编译器

今天，我们将一起编写一个编译器。但是不同于其他任何编译器…

这是一个超级小（迷你版）编译器！这个编译器有多小呢，如果您删除所有注释，此文件仅仅只有200行的实际代码。

我们将把一些类似Lisp的函数调用编译成一些类似C的函数函数调用。

如果您对其中一个或者多个不熟悉。我将会给您快速介绍。

LISP是什么？ Lisp（历史上拼写为LISP）是具有悠久历史的计算机编程语言家族，有独特和完全括号的前缀符号表示法。起源于公元1958年，是现今第二悠久而仍广泛使用的高端编程语言。只有FORTRAN编程语言比它更早一年。Lisp编程语族已经演变出许多种方言。现代最著名的通用编程语种是Clojure、Common Lisp和Scheme。

Lisp用来作为计算机程序实用的数学表达。因为是早期的高端编程语言之一，它很快成为人工智能研究中最受欢迎的编程语言。在计算机科学领域，Lisp开创了许多先驱概念，包括：树结构、自动存储器管理、动态类型、条件表达式、高端函数、递归、自主（self-hosting）编译器、读取﹣求值﹣输出循环（英语：Read-Eval-Print Loop，REPL）。

“LISP”名称源自“列表处理器”（英语：LISt Processor）的缩写。列表是Lisp的主要数据结构之一，Lisp编程代码也同样由列表组成。因此，Lisp程序可以把源代码当作数据结构进行操作，而使用其中的宏系统，开发人员可将自己定义的新语法或领域专用的语言，嵌入在Lisp编程中。 Lisp是第一个函数式程序语言，区别于C语言、Fortran等命令型程序语言和Java、C#、Objective-C等面向对象程序语言。由于历史的原因，Lisp长期以来被认为主要用于人工智能领域，但Lisp并不是只为人工智能而设计，而是一种通用的程序语言。

如果我们有两个函数如add和subtract，代码如下：

                   LISP                      C
    2 + 2          (add 2 2)                 add(2, 2)
    4 - 2          (subtract 4 2)            subtract(4, 2)
    2 + (4 - 2)    (add 2 (subtract 4 2))    add(2, subtract(4, 2))

是不是看上去很容易？

很好，因为这正是我们将要编译的内容。 虽然这既不是完整的LISP语法也不是C语法，但足以说明现代编译器的许多主要部分。

大多数编译器分为三个主要阶段：解析（Parsing），转换（Transformation），和代码生成（Code Generation）

1. 解析 就是让原始（源）代码并将其转换为更抽象的代码表示。
2. 转换 就是把这些抽象的代码表示，去进行操作，转变成编译器想要的、能够理解的东西。
3. 代码生成 把这些转换后的代码代码，重新将其转换为新的代码。

解析（parsing）

解析通常被分为两个阶段：词法分析和语法分析

1、词法分析就是把原始（源）代码通过词法分析器拆分成可标记的程序（Tokens或称为词法单元）

也就是将字符流(char stream)转换为记号流(token stream)

Tokens 是由微小的对象组成的一个数组，描述了一个孤立的片断的语法。它们可以是数字，标签，标点符号，运算符，等等。

2、语法分析就是把token stream 重新格式化为 可以描述每一个部分的语法和它们之间的关系，这种被称为中间表示或者叫抽象语法树。

抽象语法树，简称AST，是一个深层嵌套的对象，以易于使用和表达的方式表示代码之间的关系，并告诉我们很多信息。

 * For the following syntax:
 *
 *   (add 2 (subtract 4 2))
 *
 * Tokens might look something like this:
 * Tokens 可能看起来像如下的形式：
 *
 *   [
 *     { 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',
 *         }]
 *       }]
 *     }]
 *   }

转换（Transformation）

编译器的下一个阶段类型就是转换，同样，这只是从最后一步获取AST并对其进行更改。它可以用同一种语言操作AST，也可以将其翻译成一种全新的语言。

让我们看看如何转换AST。

您可能会注意到，我们的AST中有一些看起来非常相似的元素。这些对象具有type属性。每个节点都称为AST节点。这些节点上定义了描述树的一个独立部分的属性。

我们有一个“NumberLiteral”的一个节点：

{
    type: 'NumberLiteral',
    value: '2',
}

或者是一个“CallExpression”节点：

{
    type: 'CallExpression',
    name: 'subtract',
    params: [...nested nodes go here...],
}

在转换AST时，我们可以通过“添加/删除/替换”属性来操作节点，我们可以添加新节点、移除节点，或者我们可以不使用现有的AST，并基于它创建一个全新的AST。

因为我们的目标是一种新的语言，所以我们将专注于创建一个全新的、特定于目标语言的AST。

遍历（Traversal）

为了浏览所有这些节点，我们需要能够遍历它们。This traversal process goes to each node in the AST depth-first.

 *   {
 *     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'
 *         }]
 *       }]
 *     }]
 *   }

因此，对于以上述所说的AST，我们可以得出：

1、Program - 一颗抽象语法树的最顶层
2、CallExpression（add）- Program主体 的第一个元素
3、NumberLiteral（2）-

如果我们直接操作这个AST，而不是创建一个单独的AST，我们可能会在这里引入各种抽象概念。但是只要访问树中的每个节点就足够了。

我之所以使用“访问”这个词是因为有这样一种模式来表示对象结构元素上的操作。

Visitors

这里的基本思路就是，我们将创建一个“visitor”对象，该对象中有可以接受不同的节点类型的方法。

 *   var visitor = {
 *     NumberLiteral() {},
 *     CallExpression() {},
 *   };

当我们遍历AST时，每当我们“进入”一个匹配类型的节点时，我们将调用这个访问者上的方法。
为了使其更加实用，便捷，我们也将传递当前节点和父节点之间的引用。

 *   var visitor = {
 *     NumberLiteral(node, parent) {},
 *     CallExpression(node, parent) {},
 *   };

 *   -> Program (enter)
 *     -> CallExpression (enter)
 *       -> Number Literal (enter)
 *       <- Number Literal (exit)
 *       -> Call Expression (enter)
 *          -> Number Literal (enter)
 *          <- Number Literal (exit)
 *          -> Number Literal (enter)
 *          <- Number Literal (exit)
 *       <- CallExpression (exit)
 *     <- CallExpression (exit)
 *   <- Program (exit)

为了支持以上观点，我们的Visitors最终的形式应该像：

 *   var visitor = {
 *     NumberLiteral: {
 *       enter(node, parent) {},
 *       exit(node, parent) {},
 *     }
 *   };

代码生成（Code Generation）

编译器的最后一个阶段是代码生成。有时编译器会做一些与转换重叠的事情，but for the most part code generation just means take our AST and string-ify code back out.

代码生成器有几种不同的工作方式，有些编译器会重用以前的词法单元（tokens），有些编译器会创建一个单独的代码表示（中间表示），以便可以线性地打印节点，但据我所知，大多数编译器将使用我们刚刚创建的同一个AST，这也是我们要关注的。

实际上我们的代码生成器知道如何去“打印”AST中的所有不同节点类型，它将递归地调用自己来打印嵌套节点，直到所有内容都打印成一个代码长串。

大概就是这样，这就是编译器所有不同的部分。

当然并不是说每个编译器看起来都和我在这里描述的完全一样。
编译器有许多不同的用途，它们可能比我描述的需要更多、更为详细的步骤。

但现在您应该对大多数编译器的外观有一个大致的了解。

既然我已经解释了所有这些，你们都可以自己编写编译器了吧？

开玩笑，这将是我要帮助你来完成的一件事；
So let’s begin…

参考文章：

• 抽象语法树简称 AST，是源代码的抽象语法结构的树状表现形式。通过这篇文章帮助读者了解JavaScript语言解析执行得过程。
• https://mp.weixin.qq.com/s/-pvoF4vd9jaUEdj0w2zOz（AST 团队-分享）
• Javascript抽象语法树上篇(基础篇)
• Javascript抽象语法树下篇(实践篇)
• JavaScript 语法解析、AST、V8、JIT
• Welcome to The Super Tiny Compiler!
• https://astexplorer.net/
• http://esprima.org/
• 为什么编译原理被称为龙书？
• 实现JavaScript语言解释器
• 编译器课程：https://www.infoq.cn/article/t184YFyd_VMEv0dIhpRd
• DSL（https://draveness.me/dsl/）
• https://zhuanlan.zhihu.com/p/107947462
• https://zhuanlan.zhihu.com/p/41710771

词法分析中的单词，其实应该叫做一个标记（token）比较合适，像let，var，while等，这些就可以叫做单词，因为他们具有特殊意义，像诸如=，==，&&和+等非字母连接起来的字符串，应该叫做标记比较合适（token）