抽象语法树AST的一些学习笔记

抽象语法树先进行拆词理解：抽象语法树

先理解树再理解什么是语法树。最后结合什么是抽象语法树

树的优势

1. 层次关系：树结构可以非常自然地表示数据之间的层次关系，如文件系统中的目录结构、组织结构、语法分析树等。通过树结构，可以清晰地展示数据的从属关系和分层结构。

2. 搜索效率：对于某些类型的树（如二叉搜索树、AVL树、红黑树等），在保持某种顺序或平衡条件的情况下，搜索效率比线性数据结构（如链表、数组）要高得多。在平衡二叉搜索树中，搜索、插入和删除操作的时间复杂度通常为 O(log n)，其中 n 为树中节点的数量。

3. 动态数据集合：与数组等固定大小的数据结构相比，树结构可以方便地添加、删除和重新组织节点。这使得树结构非常适合用于动态变化的数据集合。

4. 有序存储：在二叉搜索树等有序树结构中，数据按照一定的顺序进行组织。这允许我们在 O(log n) 时间内完成有序数据集合的操作，如查找最大值、最小值和前驱、后继等。

5. 空间优化：在某些应用场景中，树结构可以有效地节省空间。例如，字典树（*Trie*）可以用于存储大量字符串，同时节省空间，因为公共前缀只存储一次。

6. 分治策略：树结构天然地适应分治策略，可以将复杂问题分解为较小的子问题并递归求解。许多高效的算法都基于树结构，如排序算法（归并排序、快速排序）、图算法（最小生成树、最短路径等）。

语法树

什么是语法树呢？简单来讲，就是将我们所写的代码转为树的结构。

假设有如下的代码：

JavaScript

var a = 42;

var b = 5;

function addA(d) {

return a + d;

}

var c = addA(2) + b;

对于上面的这段代码，编译器或者解释器是看不懂的，对于它们来讲，就是一段连续的字符串：

JavaScript

'var a = 42;var b = 5;function addA(d) {return a + d;}var c = addA(2) + b;'

编译器或者解释器会对上面的代码进行整体的扫描分析，分析出来上面的字符串中哪些是关键字、哪些是标志符，哪些是运算符，形成一个一个的 token（最小的不可再拆分的单位）

例如上面的那一段代码，分析出来的结果如下：

JavaScript

Keyword(var) Identifier(a) Punctuator(=) Numeric(42) Punctuator(;) Keyword(var)

Identifier(b) Punctuator(=) Numeric(5) Punctuator(;) Keyword(function)

Identifier(addA) Punctuator(() Identifier(d) Punctuator()) Punctuator({)

Keyword(return) Identifier(a) Punctuator(+) Identifier(d) Punctuator(;)

Punctuator(}) Keyword(var) Identifier(c) Punctuator(=) Identifier(addA)

Punctuator(() Numeric(2) Punctuator()) Punctuator(+) Identifier(b) Punctuator(;)

最终，会采用“树”这种数据结构来存储上面的 token 数据，最终形成一颗语法树

有一个在线的网站，大家可以将自己的源码放上去，能够看到对应源码所生成的语法树：

https://www.jointjs.com/demos/abstract-syntax-tree

抽象

最后解释一下“抽象”。

需要注意一下，在计算机科学里面的“抽象”这个词和现实生活中“抽象”这个词的含义是不太相同的，现实生活中“抽象”的含义是指“很模糊”的意思。

在计算机科学里面，抽象是一种思维方式，具体指的是从一个具体事物中提取出 本质特征、概念和规律，忽略 不相关的细节。这个实际上是一种非常非常重要的方式，通过这种方式，我们可以将某个复杂的问题分解成更简单的，更纯粹的小问题，从而帮助我们更容易的解决复杂问题。

在将源代码转换为树结构的时候，只会关注代码的结构和语法，会忽略具体的字符、空格、换行这些表达细节，像这些不重要的表达细节，在形成树结构的时候通通会被丢弃掉