编程语言如何实现？

今天的主题是 AST （抽象语法树），AST 听起来好像是个很新的东西，实际上我们平常用的 SQL执行器、语言编译器、解释器都在大量使用，是词法语法解析的基础，掌握了对于理解编程语言非常有帮助。

我们简单将这个词拆分抽象、语法、树，如果我们能够顺利将这个词拆分，那么我们也就掌握了其核心所在

  • 抽象：抽象的反义词是具象，也就说明抽象的事物关注点不在于细节，而在于整体
  • 语法：语法一组词法的表达式，具备某种指定的规则，具有某种特定的意义，比如 1+1
  • 树：树是一种一对多的结构，通过根节点往下递生，可以存在多个子树，当然这不是我们这篇讨论的主题，但却是重点

我们接下来通过几个例子更加清楚了解一下什么是树

一、什么是树？

1）算数表达式

5 * 4 / 2 + 3 * 6 这是一个简单的算法运算，但是如果我们要通过树形的方式表达它的话，结果可能是以下这样：

图片

我们通过分析这张树形图，我们可以发现有哪几个结构 ？

  • 一部分是数字：5,4,2,3,6
  • 一部分是操作符：*, /, +, *

我们从中抽取出了 + 符号，并将其作为该树的根节点，这个时候又可以分为左右两个子树，我们从中提取出一棵子树来看

图片

观察发现子树又变成了一棵树，那么可以得出一个结论：任何一棵子树都可以独立成为一棵完整的树，多个子树可以组合成一棵完整的树。至此，我们就完成了一棵树的定义，接下来我们再看一个其他例子

2）XML 文件

XML文件也是我们日常中比较常用到的文件结构

1
2
3
4
5
6
7
8
<person>
 <name>
  张三
 </name>
 <label>
  法外狂徒
 </label>
</person>

图片

我们将文件结构转成属性结构后，就可以很直观的看出数据层级与内容

二、树的转换

树的有点是很直观，可以直接看出数据层级与内容，但是我们平时操作的时候只能是操作客观上的树形结构，而不是以上主观的树形结构。因此当我们得到上述树形结构后，我们就需要对该树进行扁平化操作，那问题来了，如何扁平化呢？

我们一样拿上述算数运算为例

图片

红色的框框代表一棵树，而绿色和黄色框框则表示该树的两棵子树，当然 5 * 4 当然也可以框起来作为绿色框的子树。每棵树似乎都表示着一个算数运算

1）规则定义

转换需要建立在一定的规则基础上.我们需要先定义下规则，如果遇到一个运算，我们就以 BinaryExpression 来表示，而 运算 中的结构自然就包含着 字符 和 运算符 ，比如 5 * 4 这是一个运算，我们将整体标识为一个 BinaryExpression。

而这个运算中存在三个元素，分别是：5, 4, *。那么其中 5 和 4 我们就可以称之为 字符， * 可以称之为 运算符。由此我们可以再定一个规则，字符 的类型我们可以用 Identifier 来标识，运算符 的类型我们就以 Operator 来表示。

到这步我们就已经简单地定义好了一个 规则，接下来我们要做的事情就是利用我们的规则将上述树形结构扁平化

2）小试牛刀

图片

我们先拿上述例子来做操作，首先这是一个表达式，我们利用 BinaryExpression 进行标识

1
2
BinaryExpression
  type: BinaryExpression

从运算中我们 以运算符 可以拆分为左右两部分，也就是 5 和 4，我们继续进行标识

1
2
3
4
5
6
left: Identifier
  type: Identifier
  value: 5
right: Identifier
  type: Identifier
  valuer: 4

定义好两部分后我们该如何将两部分链接起来呢？那就得用到我们的运算符了 *，我们先利用规则定义好运算符的表示

1
operator: *

然后将两部分链接起来

1
2
3
4
5
6
7
8
9
BinaryExpression
  type: BinaryExpression
  left: Identifier
    type: Identifier
    value: 5
  operator: *
  right: Identifier
    type: Identifier
    valuer: 4

3）成品展示

图片

很好，到这里我们就完成了第一块里程碑了！

4）趁热打铁

上面我们才完成了一小部分的规则转换定义，接下来我们继续将树形结构进行转换：

图片

到这里我们已经从树形结构图转到了我们定义的层级结构了，但我们可以发现，以上的层级结构图依然是不够完整的

目前为止我们才定义了上述表达式中左边的部分，还缺少右边的定义，这个时候就需要大家来帮个忙， 帮我补充一下右边的部分，结构体已经在下述文本中贴出，大家可以复制到自己的文本编辑器中进行填空补充，将__ 内容替换补充即可

1
2
3
4
5
6
7
8
9
right: __
  type: __
  left: __
   type: __
   value: __
  operator: __
  right: __
   type: __
   value: __

接下来就到了公布答案的环节了！

1
2
3
4
5
6
7
8
9
right: BinaryExpression
  type: BinaryExpression
  left: Identifier
   type: Identifier
   value: 3
  operator: *
  right: Identifire
   type: Identifier
   value: 6

大家可以进行比对下答案是否正确，然后我们将两部分内容进行组装

图片

到这里，我们就已经得到了一个完整的层级结构了，那么这部分内容跟我们今天将的 AST 有什么关系呢？

我们先来看下真正的 AST（抽象语法树）长啥样

我们转换一个简单的函数：

1
2
3
function add(n, m){
  return n + m
}

图片

左边是我们平时编写的代码，而右侧便是通过代码转换得到的 AST 树

图片

我们通过观察这棵 AST 树有什么发现？没错！这棵 AST 树的结构基本和我们刚刚共同完成的层级结构图一致，这意味着我们刚刚自己手撸了一棵 AST 树出来

三、揭露 AST 面纱

1）AST 定义

1. 它是什么？

AST（抽象语法树）并没有我们所想的那么神秘，它是源代码语法结构的一种抽象表示，它以树状的形式表现编程语言的语法结构，树上的每个节点都表示源代码中的一种结构。

2. 它有什么特征？

首先它是抽象的，它无关语法结构，不会记录源语言真实语法中的每个细节，比如分隔符，空白符，注释等，它都会进行移除。

3. 它有什么用？

通过以上的实践，我们也认识到了转换AST 是一项繁琐的过程，但为什么要去转换呢？现在各种语言语法种类繁多，虽然最终落到计算机的眼中都是 0 和 1，但是编译器需要识别语言，这个时候就需要使用一种通用的数据结构来描述，而 AST 就是那个东西，因为 AST 是真实存在且存在一定逻辑规则的。

4. 它是如何进行转换的？

它转换的过程中也是运用到了我们刚刚所说的几种方式：

  • 词法分析器
  • 语法分析器
  • 解释器

图片

比如我们写个简单的代码：

1
const name = '张三'
  • 词法分析

第一步就是 词法分析 ，它的任务就是一个一个字母地读取代码，当它遇到 空格、操作符、特殊符号 的时候，就表示自己第一活已经扫描结束了，我们上述的代码这经过 词法分析 后就会被解析为 [const, name, =, '张三'] 这几个值

  • 语法分析

经过上层的分析，我们已经拿到了各个 token， 也就是 token流 ，也就是接下来我们就可以对 token流 进行语法分析，比如我们第一个遇到的 token 是 const ，语法分析器通过分析，判断它是一个 声明参数 ，就会标记为 VariableDeclaration，以此类推，后面的几个 token 都会进行分析，直到生成了一棵 AST 抽象语法树

图片

当生成树的时候，解析器 会删除一些没必要的标识tokens（比如不完整的括号），因此AST不是100%与源码匹配的，但是已经能让我们知道如何处理了

2）AST 应用

AST 查看辅助工具：点我

解析并转换 AST 的这个步骤比较繁琐，当然我们不必重复造轮子，已经有人替我们造好了轮子，比如解析服Java文件，我们可以应用 Javaparser 进行 AST 转换，解析 Js / Ts 文件，可以应用 Babelparser 进行 AST 转换。当然，尽管轮子已经为我们准备好了，我们还需要如何运用，那就是得了解规则，下面附上一些常用的节点类型含义对照表，也就是 AST 转换的规则：

类型名称 中文译名 描述
Program 程序主体 整段代码的主体
VariableDeclaration 变量声明 声明变量，比如 let const var
FunctionDeclaration 函数声明 声明函数，比如 function
ExpressionStatement 表达式语句 通常为调用一个函数，比如 console.log(1)
BlockStatement 块语句 包裹在 {} 内的语句，比如 if (true) { console.log(1) }
BreakStatement 中断语句 通常指 break
ContinueStatement 持续语句 通常指 continue
ReturnStatement 返回语句 通常指 return
SwitchStatement Switch 语句 通常指 switch
IfStatement If 控制流语句 通常指 if (true) {} else {}
Identifier 标识符 标识，比如声明变量语句中 const a = 1 中的 a
ArrayExpression 数组表达式 通常指一个数组，比如 [1, 2, 3]
StringLiteral 字符型字面量 通常指字符串类型的字面量，比如 const a = ‘1’ 中的 ‘1’
NumericLiteral 数字型字面量 通常指数字类型的字面量，比如 const a = 1 中的 1
ImportDeclaration 引入声明 声明引入，比如 import

为了快速了解，我们这篇以 JavaScript 文件为例，那么解析与操作 JavaScript 文件，已经有了比较好用的轮子 – jscodeshift，我们下面就利用 jscodeshift 来操作 AST

1、查找

这里是一段十分简易的代码：

1
2
import React from 'react';
import { Button } from 'antd';

我们对比上面的 节点类型含义对照表 ，可以看出这是两个 ImportDeclaration 语句

然后我们将这段代码放到 AST 可视化工具中查看转换成 AST 后的样子：

图片

这个时候我们有个小小的需求，那就是我想要获取下面代码块中的导包源，也就是 from 后面的内容

1
2
3
import React from "react";
import { Button } from "antd";
import { moment } from "moment";

我们来看这段话的含义，代码中我们通过引入 jscodeshift 来帮助我们解析和操作 AST 文件，然后在 API 中声明了我们要查找元素的类型

图片

这个时候我们可以打开控制台运行 node find.js 来运行该脚本内容，可以看到控制台成功的输出了我们想要的结果！

1
2
3
react
antd
moment

接下来我们玩法进阶，我们在下面代码块中除了看到有 import 语法，还定义了 name 属性，那我们这个时候需求又来了， 我想获取该 name 的值！这个时候要怎么办呢？

图片

第一步我们需要查看 AST 结构，我们可以将文件体复制到我们的 AST 查看辅助工具上进行 AST 结构概览：

图片

可以看到我们想要的内容在 ArrayExpression 中的 elements中，那么接下来我们在代码中该如何操作呢？大家可以先进行尝试~

答案如下：

图片

我们先要找到 ArrayExpression 类型的元素，然后访问该元素下的 elements 属性，就会得到我们想要的值了！

1
2
3
张三
李四
王五
2、修改

我们上面已经实现了通过 AST 结构来查找我们想要的元素，下面我们就可以开始进行操作节点元素了！

首先先看如何修改，这时来了个需求，我们的 Button 组件名称变了，换成了 Button01 ，那我们就得做出相应的修改

接下来我们继续看以下文件，通过查看可以发现有些不同，这个时候多了 find API，而且这个API可以增加参数 { source: { value: "antd" } } 。

这个 API 的目的是只查找 source = antd 的 ImportDeclaration 元素，然后进行替换，Button 命名的所在位置在 imported.name，因此我们相应修改该值即可

图片

我们通过运行 node modify.js 便可以看到我们修改后的文件内容，想要使之生效，我们还需要将修改后的内容写会该文件中，我们可以在文件最下方补上下面一段代码：

1
fs.writeFileSync('./code/demo.js', root.toSource(), 'utf-8')

然后运行代码，这个时候我们就可以发现 demo.js文件内容已经发生了修改。

1
2
3
4
5
import React from "react";
import { Button01 } from "antd";
import { moment } from "moment";

var name = ["张三", "李四", "王五"];
3、新增

有了查，改，接下来就轮到了增了，增的话会比上面复杂些，因为我们需要将我们要新增的内容构建成 AST 结构，然后再往已有的 AST 结构中插入

老样子，我们老朋友需求又来了，之前页面中只用到了 antd 的 Button 组件，那我们页面这个时候还需要用到 antd 的 Select 组件

我们第一步就是要将我们要插入的内容构建成 AST 元素，我们先分析已有的 Button AST 结构长啥样，然后依葫芦画瓢构建即可。

我们分析得到该结构的组成部分由 ImportSpecifier 和 Identifier 组成，ImportSpecifier 中包着 Identifier

图片

那么我们就可以得出我们要插入的内容结构为：

图片

接下来就交给 jscodeshift 帮我们生成

1
$.importSpecifier($.identifier("Select"))

得到 AST 结构后我们还需要查看我们要插入的位置，回到之前的 AST 结构中

图片

我们发现导入的资源组件内容都放在了 specifiers 属性中，那我们就可以动手操作了，我们在项目中找到 create.js 文件

图片

通过运行代码，可以发现结果已经变成了我们修改后的内容。

1
2
3
4
5
import React from "react";
import { Button, Select } from "antd";
import { moment } from "moment";

var name = ["张三", "李四", "王五"];
4、删除

讲完查，改，增，最后就剩下我们拿手的删了

需求它又来了，页面这个时候不需要 antd 组件了，也就是将 import { Button } from "antd"; 这句话移除

那就老规则，先找到 antd 这个元素所在的 AST，然后将它置为空即可

图片

这个时候通过运行，就可以发现打印出来的内容已经没有了关于antd 的引入信息了

1
2
3
4
import React from "react";
import { moment } from "moment";

var name = ["张三", "李四", "王五"];

到这里我们就讲完了关于 AST 的增删改查操作

AST 是个很有用的工具，会在编译原理词法语法分析等常见被大量用到，大家可以学习一下~