从具体到抽象
Abstract Syntax Tree抽象语法树（通常被简写成AST）实际上只是一个解析树(parse tree)的一个精简版本。在编译器设计的语境中，"AST" 和 "语法树"(syntax tree)是可以互换的。
什么是解析树呢？我们知道一棵解析树是包含代码所有语法信息的树型结构，它是代码的直接翻译。所以解析树，也被成为具象语法树（Concret Syntax Tree, 简称CST）;而抽象语法树，忽略了一些解析树包含的一些语法信息，剥离掉一些不重要的细节，所以它看起并不像解析树那么事无巨细，这也是AST名字中抽象一词的由来。
在继续下一步之前，我们先统一一下文中的概念表达形式，以便更好的理解内容
解析树 = Parse Tree = CST 抽象语法树 = Syntax Tree = AST
我们先分析一段简短的代码js代码：5 + (1 x 12), 回忆一下编译器的工作过程
词法分析
编译的第一个阶段是扫描源代码文本，scanner会从左到右扫描文本，把文本拆成一些单词。然后，这些单词传入分词器，经过一系列的识别器（关键字识别器、标识符识别器、常量识别器、操作符识别器等），确定这些单词的词性，这一过程的产物是token序列。token在机内一般用<type, value>形似的二元组来表示，type表示一个单词种类，value为属性值，比如var这个单词，在js语言里是一个关键字，一种语言的关键字集合是事先可以确定的，所以它的type本身就可表示这个关键字，不再需要属性值， 用二元组表示就是<VAR, ->；再看我们的示例5 + (1 x 12)中， 12也是其中的一个单词, 它实际上是一个常量，用二元组表示就是<CONST, 12>。分词和所使用的语言种类密切相关，分解后的token序列为5, +, (, 1, x, 12, )。
<CONST, 5>
<OPT, +>
<SLP, ->
<CONST, 1>
<OPT, *>
<CONST, 12>
<RLP, ->scanner和分词器所做的工作，构成了编译器的词法分析阶段。
语法分析
分词阶段完成以后，token序列会经过我们的解析器，由解析器识别出代码中的各类短语，会根据语言的文法规则(rules of grammar)输出解析树，这棵树是对代码的树形描述。文法是什么呢？想想我们学英语的过程中，老师是如何教我们划分句子解构的，比如一个简单的英文自然语言例子：
Little girl ate apple
它由【名词短语】和【动词短语】组成, 再往下【名词短语】由【形容词】和【名词构成】，【动词短语】由【动词】和【名词短语】构成。【动词】和【名词】又可以由具体的单词构成。
我们会觉得语言描述冗长，而且并不直观，可以借助一些符号进行描述:
<句子> -> <名词短语><动词短语>
<名词短语> -> <形容词><名词>
<动词短语> -> <动词> <名词短语>
<形容词> -> little
<名词> -> girl | apple
<动词> -> ate用<>包裹起来的部分称为语法规则，未用<>包括起来的部分(如little、girl等)，就是该语言的基本符号。
用更抽象的形式化语言定义，文法可表示为:
- T表示终结符的集合（如little、girl等，即词法分析中提到的token）
- N表示非终结符的集合（如<>里包括的部分，表示了语法成分， 因为它们可以推导出其他句子成分，所以称为非终结符）
- P表示产生式集合（上面分析英语句子的每一条规则都是一个产生式，如<动词短语> -> <动词> <名词短语>， 就是一个产生式）
- S表示开始符号（S属于N的子元素，是一个特殊的非终结符）
可以看出，文法用简单的符号解决了无穷语言的有穷表述问题。
那么解析树具体长什么样呢？
2 + (12 * 1)根据对应的文法生成的解析树
解析树
你可能会非常疑惑为什么会有EXP->1这种形式的存在，是不是感觉非常冗余？
我们来从文法的角度来解释这个问题，2 + (12 * 1)是一个四则运算的表达式，根据我们小学学过的内容，大家都会很轻易的知道它的运算规则，那我们可以根据前面提到的文法规则公式，用形式语言把这些规则简写出来：
// 每条产生式前面的序号只为了更好的在下文引用，并不是产生式的一部分
1） E -> E + E
2） E -> E * E
3） E -> (E)
4） E -> number你很快会发现，上图的分析树就是根据这些规则生成的，而EXP->1这种形式正是第四条产生式的一个应用。
总结一下解析树的一些性质
- 解析树的根节点为文法开始符号
- 解析树内部节点表示一个产生式的应用
- 叶节点既可以是非终结符也可以是终结符。从左到右的叶节点得到的符号串成为这颗树的产出(yield)。
精简一棵解析树
我们现在知道具象语法树和抽象语法树的概念，而且知道AST是CST的精简版本，那么AST它是如何生成的呢？
我们现在知道，根据文法规则生成的解析树会非常冗余。我们有过疑问，EXP->1这种结点，是不是看上去有点冗余？我们把这种结点叫做单继承节点，实际上我们并不会关心EXP是什么，只会关心继承它的那个值，这里即1。
压缩单继承节点
另外，我们发现括号似乎也是冗余的，可以隐藏在树的结构中。
去掉括号
甚至，我们可以看到，蓝色方框中的内部结点也不含有关键信息，可以用操作符号(在这里是 + 和 *)把它们替换掉。
将操作符压进内部节点
继续把冗余的层修剪掉，我们可以得到一颗AST树
一颗抽象语法树
我们已经自己压缩了一棵解析树，通过上面几个步骤的精简，可以总结一些解析树和抽象语法树的不同之处:
- AST不含有语法细节，比如冒号、括号、分号
- AST会压缩单继承节点
- 操作符会变成内部节点，不再会以叶子节点出现在树的末端。
有了抽象语法树，我们基于它可以建立清晰的代码描述，非常有利于后续阶段的修改、变换。
