蔡不菜丶

V1

2022/11/20阅读:17主题:丘比特忙

AST 初探深浅,代码还能这样玩?!

大家好,这里是 菜农曰,欢迎来到我的频道。我们今天的主题是 AST (抽象语法树)

AST 听起来好像是个很新的东西,那么具体有什么用,好不好用就在这篇文章中找到答案吧~

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

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

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

一、什么是树?

1)算数表达式

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

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

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

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

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

2)XML 文件

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

<person>
 <name>
  张三
 </name>
 <label>
  法外狂徒
 </label>
</person>

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

二、树的转换

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

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

红色的框框代表一棵树,而绿色和黄色框框则表示该树的两棵子树,当然 5 * 4 当然也可以框起来作为绿色框的子树。

这个时候,聪明的小伙伴们看到这些树有没有什么发现,比如每棵树表示什么?

我们可以发现每棵树似乎都表示着一个算数运算

1)规则定义

转换需要建立在一定的规则基础上

我们需要先定义下规则,如果遇到一个运算,我们就以 BinaryExpression 来表示,而 运算 中的结构自然就包含着 字符运算符 ,比如 5 * 4 这是一个运算,我们将整体标识为一个 BinaryExpression

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

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

2)小试牛刀

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

BinaryExpression
  type: BinaryExpression

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

left: Identifier
  type: Identifier
  value: 5
right: Identifier
  type: Identifier
  valuer: 4

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

operator: *

然后将两部分链接起来

BinaryExpression
		type: BinaryExpression
		left: Identifier
				type: Identifier
				value: 5
		operator: *
		right: Identifier
				type: Identifier
				valuer: 4

3)成品展示

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

4)趁热打铁

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

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

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

right: __
  type: __
  left: __
   type: __
   value: __
  operator: __
  right: __
   type: __
   value: __

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

right: BinaryExpression
  type: BinaryExpression
  left: Identifier
   type: Identifier
   value: 3
  operator: *
  right: Identifire
   type: Identifier
   value: 6

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

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

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

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

function add(n, m){
  return n + m
}

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

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

三、揭露 AST 面纱

1)AST 定义

1. 它是什么?

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

2. 它有什么特征?

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

3. 它有什么用?

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

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

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

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

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

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、查找

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

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

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

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

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

import React from "react";
import { Button } from "antd";
import { moment } from "moment";

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

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

react
antd
moment

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

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

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

答案如下:

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

张三
李四
王五
2、修改

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

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

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

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

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

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

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

import React from "react";
import { Button01 } from "antd";
import { moment } from "moment";

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

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

老样子,我们老朋友需求又来了,之前页面中只用到了 antdButton 组件,那我们页面这个时候还需要用到 antdSelect 组件

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

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

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

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

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

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

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

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

import React from "react";
import { Button, Select } from "antd";
import { moment } from "moment";

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

讲完查,改,增,最后就剩下我们拿手的

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

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

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

import React from "react";
import { moment } from "moment";

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

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


好了,以上便是本篇的所有内容,AST 是个很有用的工具,如果觉得对你有帮助的小伙伴不妨点个关注做个伴,便是对小菜最大的支持。不要空谈,不要贪懒,和小菜一起做个吹着牛X做架构的程序猿吧~ 咱们下文再见!

今天的你多努力一点,明天的你就能少说一句求人的话!

我是小菜,一个和你一起变强的男人。 💋

微信公众号已开启,菜农曰,没关注的同学们记得关注哦!

分类:

后端

标签:

后端

作者介绍

蔡不菜丶
V1