概念

抽象语法树 (Abstract Syntax Tree)，简称 AST，它是源代码语法结构的一种抽象表示。它以树状的形式表现编程语言的语法结构，树上的每个节点都表示源代码中的一种结构

Abstract Syntax Tree抽象语法树（通常被简写成AST）实际上只是一个解析树(parse tree)的一个精简版本。一棵解析树是包含代码所有语法信息的树型结构，它是代码的直接翻译。所以解析树，也被成为具象语法树（Concret Syntax Tree, 简称CST）;而抽象语法树，忽略了一些解析树包含的一些语法信息，剥离掉一些不重要的细节

应用

• 编辑器的错误提示、代码格式化、代码高亮、代码自动补全；

• elint、pretiier 对代码错误或风格的检查；

• webpack 通过 babel 转译 javascript 语法；

AST 如何生成

js 执行的第一步是读取 js 文件中的字符流，然后通过词法分析生成 token，之后再通过语法分析( Parser )生成 AST，最后生成机器码执行

词法分析

词法分析，也称之为扫描（scanner），简单来说就是scanner会从左到右扫描文本，把文本拆成一些单词。然后，这些单词传入分词器，经过一系列的识别器（关键字识别器、标识符识别器、常量识别器、操作符识别器等），确定这些单词的词性，这一过程的产物是token序列

token在机内一般用<type, value>形似的二元组来表示，type表示一个单词种类，value为属性值

例如 var 这三个字符，它只能作为一个整体，语义上不能再被分解，因此它是一个 Token，它的type本身就可表示这个关键字，不再需要属性值， 用二元组表示就是<VAR, ->

词法分析器里，每个关键字是一个 Token ，每个标识符是一个 Token，每个操作符是一个 Token，每个标点符号也都是一个 Token。除此之外，还会过滤掉源程序中的注释和空白字符（换行符、空格、制表符等)

最终，整个代码将被分割进一个tokens列表

语法分析

token序列会经过我们的解析器，由解析器识别出代码中的各类短语，会根据语言的文法规则(rules of grammar)输出解析树，同时，验证语法，语法如果有错的话，抛出语法错误

解析树（具象语法树）

文法可表示为:

G=(T,N,P,S)

• T表示终结符的集合（如little、girl等，即词法分析中提到的token）

• N表示非终结符的集合（如<>里包括的部分，表示了语法成分， 因为它们可以推导出其他句子成分，所以称为非终结符）

• P表示产生式集合（上面分析英语句子的每一条规则都是一个产生式，如<动词短语> -> <动词> <名词短语>， 就是一个产生式）

• S表示开始符号（S属于N的子元素，是一个特殊的非终结符）

5 + (12 * 1)根据对应的文法生成的解析树

解析树的一些性质

• 解析树的根节点为文法开始符号

• 解析树内部节点表示一个产生式的应用

• 叶节点既可以是非终结符也可以是终结符。从左到右的叶节点得到的符号串成为这颗树的产出(yield)

抽象语法树（AST）

上文可见，根据文法规则生成的解析树会非常冗余。例如EXP->1这种结点，看上去有点冗余，我们把这种结点叫做单继承节点，实际上我们并不会关心EXP是什么，只会关心继承它的那个值，这里即1；再例如我们发现括号似乎也是冗余的，可以隐藏在树的结构中

把冗余的层修剪掉，我们可以得到一颗AST树

解析树和抽象语法树的不同之处:

1. AST不含有语法细节，比如冒号、括号、分号

2. AST会压缩单继承节点

3. 操作符会变成内部节点，不再会以叶子节点出现在树的末端

AST虽然小而美，生成并不容易。生成解析树相反会容易很多，它直接包含了语言的文法推导细节。很多解析器生成AST前会先生成解析树，这意味着多的步骤；也有一些编译器一步到位，跳过解析树，直接生成AST。

它之所以被称为抽象，也是与CST中的Concret一词相对的，它不会表达出真实语法中的每一个细节，仅仅只是浓缩了语法中的必要结构成分

AST会出现在大量的代码工具中，正是因为它比CST提供更清晰、简洁的接口，为开发人员操作源代码提供了便捷的渠道

实战：用AST修改源码

下面我们就来完成一个在调用 console.log(xx) 时候给前面加一个函数名

// 源代码
function getData() {
  console.log("data")
}
-------------------------------------------------------
// 转化为下面代码
function getData() {
  console.log("getData", "data");
}

1、创建 js 文件, 编写大致布局如下 使用babel

// @babel/parser : 将 js 代码 ---> AST 抽象语法树
// @babel/traverse 对 AST 节点进行递归遍历；
// @babel/types 对具体的 AST 节点进行进行修改；
// @babel/generator : AST 抽象语法树 ---> 新的 js 代码；
​
const generator = require("@babel/generator");
const parser = require("@babel/parser");
const traverse = require("@babel/traverse");
const types = require("@babel/types");
​
function compile(code) {
  // 1.parse 将代码解析为抽象语法树（AST）
  const ast = parser.parse(code);
​
  // 2,traverse 转换代码
  traverse.default(ast, {});
​
  // 3. generator 将 AST 转回成代码
  return generator.default(ast, {}, code);
}
​
const code = `
function getData() {
  console.log("data")
}
`;
const newCode = compile(code)
​

使用 node 跑出结果，因为compile方法中并未做任何处理，此时输出的是原代码

2、完善compile方法

function compile(code) {
  // 1.parse
  const ast = parser.parse(code);
​
  // 2.traverse
  const visitor = {
    CallExpression(path) {
      // 拿到 callee 数据
      const { callee } = path.node;
      // 判断是否是调用了 console.log 方法
      // 1. 判断是否是成员表达式节点，上面截图有详细介绍
      // 2. 判断是否是 console 对象
      // 3. 判断对象的属性是否是 log
      const isConsoleLog =
        types.isMemberExpression(callee) &&
        callee.object.name === "console" &&
        callee.property.name === "log";
      if (isConsoleLog) {
        // 如果是 console.log 的调用 找到上一个父节点是函数
        const funcPath = path.findParent(p => {
          return p.isFunctionDeclaration();
        });
        // 取函数的名称
        const funcName = funcPath.node.id.name;
        // 将名称通过 types 来放到函数的参数前面去
        path.node.arguments.unshift(types.stringLiteral(funcName));
      }
    }
  };
  // traverse 转换代码
  traverse.default(ast, visitor);
​
  // 3. generator 将 AST 转回成代码
  return generator.default(ast, {}, code);
}
​

上面的 path.node 如下

{
  "type": "CallExpression",
  "start": 24,
  "end": 43,
  "loc": {
    "start": { "line": 3, "column": 2 },
    "end": { "line": 3, "column": 21 }
  },
  "callee": {
    "type": "MemberExpression",
    "start": 24,
    "end": 35,
    "loc": {
      "start": { "line": 3, "column": 2 },
      "end": { "line": 3, "column": 13 }
    },
    "object": {
      "type": "Identifier",
      "start": 24,
      "end": 31,
      "loc": {
        "start": { "line": 3, "column": 2 },
        "end": { "line": 3, "column": 9 },
        "identifierName": "console"
      },
      "name": "console"
    },
    "property": {
      "type": "Identifier",
      "start": 32,
      "end": 35,
      "loc": {
        "start": { "line": 3, "column": 10 },
        "end": { "line": 3, "column": 13 },
        "identifierName": "log"
      },
      "name": "log"
    },
    "computed": false
  },
  "arguments": [
    {
      "type": "StringLiteral",
      "start": 36,
      "end": 42,
      "loc": {
        "start": { "line": 3, "column": 14 },
        "end": { "line": 3, "column": 20 }
      },
      "extra": { "rawValue": "data", "raw": "'data'" },
      "value": "data"
    }
  ]
}
//方便阅读可以将不必要的位置信息（start, end, loc）等属性删除

此时再执行，输出结果为我们修改后的代码

总结

1. js 语法解析成 AST；

2. 修改 AST；

3. AST 转成 js 语法；

实现

以下是一个简化的步骤和思路：

1. 词法分析： 遍历源代码，将其分解成一系列的标记（tokens）。标记可以是关键字、运算符、变量名等。

2. 语法分析： 利用上下文无关文法（Context-Free Grammar，CFG）定义编程语言的语法规则，然后编写一个递归下降分析器（Recursive Descent Parser）。

   a. 定义文法规则： 将编程语言的语法规则翻译成一系列的产生式，其中每个产生式表示一个语法结构。

   b. 编写递归下降分析器： 对于每个非终结符（语法规则的左侧），编写一个相应的递归函数。这些函数可以递归地调用彼此，每个函数负责解析一个特定的语法结构，并返回相应的AST子树。

3. 构建抽象语法树： 在语法分析的过程中，递归下降分析器的每个函数都会返回一个AST子树。通过在这些函数中构造和连接这些子树，最终形成整个源代码的AST。

   a. 节点表示： 定义AST的节点类型，每个节点类型对应语法规则中的一个语法结构，如赋值语句、条件语句等。

   b. 构建过程： 在递归下降分析器的各个函数中，根据语法规则，创建相应的AST节点，并将其连接起来形成树状结构。

4. 语义分析： 在构建AST的过程中，可以执行一些简单的语义分析，例如检查变量的声明与引用是否匹配、类型检查等

本栏目推荐文章
• 盘点C#最有价值的10个语法糖
• 零基础入门Vue之梦开始的地方——插值语法
• SDC语法
• 微信小程序 WXML模板语法——事件绑定
• 微信小程序 WXML模板语法——数据绑定
• JS基础（一）引入方式，基本语法，数据类型，类型转换，原始类型和引用类型的区别
• 趣谈if语法
• markdown常用语法
• harmonyOS一：基本语法
• 第一篇博客————Markdown语法

语法 AST语法ast 语法125 ast 语法babel ast ast php-ast babel-ast 前端ast injection ast webpack ast php-ast方法linux ast