My-Notes

Search

SearchSearch

002.抽象语法树

Mar 21, 2024, 7 min read

抽象语法树（AST）是一个非常重要、非常常见的知识点，弄清楚抽象语法树有助于后面的学习。

什么是抽象语法树？当遇到一个难以理解的词的时候，最简单的方式就是拆词，针对抽象语法树就可以拆解为三个部分：抽象、语法、树，接下来就是针对这三个词逐个击破，只要把这三个词搞懂了，那么抽象语法树整体的概念也就理解了。

树

树实际上是一种数据结构，树这种非线性的数据结构在解决某些问题的时候，具有如下的优点：

  1. 层次关系：树结构可以非常自然地表示数据之间的层次关系，如文件系统中的目录结构、组织结构、语法分析树等。通过树结构，可以清晰地展示数据的从属关系和分层结构。
  2. 搜索效率：对于某些类型的树（如二叉搜索树、AVL 树、红黑树等），在保持某种顺序或平衡条件的情况下，搜索效率比线性数据结构（如链表、数组）要高得多。在平衡二叉搜索树中，搜索、插入和删除操作的时间复杂度通常为 ，其中 为树中节点的数量。
  3. 动态数据集合：与数组等固定大小的数据结构相比，树结构可以方便地添加、删除和重新组织节点。这使得树结构非常适合用于动态变化的数据集合。
  4. 有序存储：在二叉搜索树等有序树结构中，数据按照一定的顺序进行组织。这允许我们在 时间内完成有序数据集合的操作，如查找最大值、最小值和前驱、后继等。
  5. 空间优化：在某些应用场景中，树结构可以有效地节省空间。例如，字典树（Trie）可以用于存储大量字符串，同时节省空间，因为公共前缀只存储一次。
  6. 分治策略：树结构天然地适应分治策略，可以将复杂问题分解为较小的子问题并递归求解。许多高效的算法都基于树结构，如排序算法（归并排序、快速排序）、图算法（最小生成树、最短路径等）。

正因为“树”这种数据结构有上述的优点，所以很多地方都用到了它：DOM 树、CSSOM 树、Vue 模板树、语法树。

语法树

简单来讲，语法树就是将代码转为树的结构。

假设有如下的代码：

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

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

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

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 数据，形成一颗语法树：

JavaScript AST 可视化

抽象

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

  • 现实生活中“抽象”的有“很模糊”的意思。
  • 在计算机科学里面，抽象是一种思维方式，具体指的是从一个具体事物中提取出本质特征、概念和规律，忽略不相关的细节。

这是一种非常重要的方式，可以将某个复杂的问题分解成更简单更纯粹的小问题，从而更容易的解决复杂问题。

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

抽象语法树

抽象语法树（Abstract Syntax Tree，简称 AST）是编程语言中一种树形的数据结构，用于表示源代码的语法结构。

在 AST 中，每个节点代表源代码中的一个语法元素（如变量、表达式、语句等），并且描述了这些元素之间的层次关系。在从源代码转为语法树的过程中，会采用到抽象的思想，只关注代码的结构和语法，忽略具体的字符、空格、换行等表达细节。通过这种抽象表示，可以更方便地理解、分析和操作源代码，而无需直接处理文本格式的代码。

抽象语法树在编译器和解释器设计、代码分析、代码转换等领域具有广泛的应用。使用 AST 可以简化代码处理过程，提高代码操作的精确性和可扩展性，并有助于实现高效的代码优化和转换算法。

Graph View

Backlinks