第16期 - 外白渡桥

封面图来源于外白渡桥，一个看东方明珠特别的位置，人少较为清静，漫步苏州河畔，有一丝丝的惬意。

技术笔记-AST

AST 全称 abstract syntax tree (抽象语法树)。它是源代码语法结构的一种抽象表示。

AST 的使用场景

应用于浏览器引擎、打包工具、代码转译、静态分析和代码格式化等场景。

解析 JavaScript

浏览器 js 引擎（如 V8）拿到 js 的第一件事就是解析 js 生成 AST。随后进行解释执行，通过 AST js 引擎可以理解代码的结构并逐行解释执行。再编译优化执行，在生成 AST 后 js 引擎会进行各种代码优化，然后将优化后的 AST 转换为字节码或机器码执行。

webpack

解析代码：使用 AST 来解析代码的模块依赖关系，通过分析 AST，可以识别出模块的导入和导出语句。 代码分割和树摇（Tree Shaking）：利用 AST 进行代码分割，按需加载代码。通过 AST 分析代码，删除未使用的部分，减小打包后的文件体积。 插件和 Loader：Webpack 的插件和 Loader 可以基于 AST 修改代码。如 Babel Loader 使用 Babel 转换 ES6+ 代码为兼容的 ES5 代码。

ESLint

代码检查和规范：使用 AST 进行静态代码分析，检测代码中潜在错误和不符合规范的部分

Prettier

根据预定义的规则和配置文件自动重新排版代码，从而使代码风格统一。无论是缩进、换行还是空格，Prettier 都会按照规范进行调整 通过解析代码生成 AST，然后基于 AST 重新排版代码，以确保代码的一致性和可读性。通过 AST，可以忽略原始代码的格式，仅关注代码的语法结构，生成标准化的代码格式。

AST 相关库

ts-morph
https://ts-morph.com/navigation/

babel解析生成ast
https://babeljs.io/docs/babel-parser
babel遍历ast
https://babeljs.io/docs/babel-traverse

实用的在线AST工具

https://ts-ast-viewer.com/#
https://astexplorer.net/
https://esprima.org/demo/parse.html#

AST 结构

AST（抽象语法树）只有一个顶级节点——Program，它代表了整个程序的语法结构，Program 节点是所有代码片段的根节点，从这个节点出发可以访问程序的所有部分。 在 Program 节点之下，AST 会根据代码的结构将不同的代码片段区分开来，作为 Program 节点的子节点来处理。AST 的子节点类型包括 函数声明（FunctionDeclaration）、变量声明（VariableDeclaration）、表达式（ExpressionStatement）、块语句（BlockStatement）等。

function greet(name) {
  let greeting = "Hello, " + name;
  console.log(greeting);
}

{
  "type": "Program",  // 根节点，表示整个程序
  "body": [
    {
      "type": "FunctionDeclaration",  // 函数声明
      "id": {
        "type": "Identifier",
        "name": "greet"  // 函数名为 greet
      },
      "params": [
        {
          "type": "Identifier",
          "name": "name"  // 函数参数名为 name
        }
      ],
      "body": {
        "type": "BlockStatement",  // 函数体为块语句
        "body": [
          {
            "type": "VariableDeclaration",  // 变量声明语句
            "declarations": [
              {
                "type": "VariableDeclarator",  // 变量声明器
                "id": {
                  "type": "Identifier",
                  "name": "greeting"  // 变量名为 greeting
                },
                "init": {
                  "type": "BinaryExpression",  // 二元表达式，表示字符串拼接
                  "operator": "+",
                  "left": {
                    "type": "Literal",
                    "value": "Hello, ",  // 左操作数为字符串 "Hello, "
                    "raw": "\"Hello, \""  // 原始字符串表示
                  },
                  "right": {
                    "type": "Identifier",
                    "name": "name"  // 右操作数为参数 name
                  }
                }
              }
            ],
            "kind": "let"  // 使用 let 关键字声明变量
          },
          {
            "type": "ExpressionStatement",  // 表达式语句
            "expression": {
              "type": "CallExpression",  // 调用表达式
              "callee": {
                "type": "MemberExpression",  // 成员表达式，调用 console.log 方法
                "computed": false,
                "object": {
                  "type": "Identifier",
                  "name": "console"  // 对象部分，名称为 console
                },
                "property": {
                  "type": "Identifier",
                  "name": "log"  // 属性部分，名称为 log
                }
              },
              "arguments": [
                {
                  "type": "Identifier",
                  "name": "greeting"  // 传递 greeting 变量作为参数
                }
              ]
            }
          }
        ]
      },
      "generator": false,
      "expression": false,
      "async": false
    }
  ],
  "sourceType": "script"  // 源代码类型为脚本
}

生成 AST 的过程

生成 AST（抽象语法树）的过程主要包括两个步骤：词法分析（Lexical Analysis）和语法分析（Syntax Analysis）。

词法分析

词法分析器也叫 scanner（扫描器），顾名思义就是扫描我们的代码，遍历每个字符，使用预先定义好的规则将每个字符转换成 token(词法单元)。

词法分析阶段我们需要生成 token 列表, 核心思想就是遍历代码字符串，然后将字符串归类生成 token。

let name = "张三";

[
    {
        "type": "Keyword",
        "value": "let"
    },
    {
        "type": "Identifier",
        "value": "name"
    },
    {
        "type": "Punctuator",
        "value": "="
    },
    {
        "type": "String",
        "value": "\"张三\""
    },
    {
        "type": "Punctuator",
        "value": ";"
    }
]

自定义类型变量 constants.js

// token 类型
const TokenTypes = {
  Keyword: "Keyword", // 关键字
  Identifier: "Identifier", // 变量名标识符
  Punctuator: "Punctuator",  // 标点
  String: "String" // 字符串
}
// AST 节点类型定义
const AST_Types = {
  Literal: "Literal", // 字面量 就是值 如 let a = 1 1就是Literal
  Identifier: "Identifier", // 标识符 如 let a = 1 a就是Identifier
  AssignmentExpression: "AssignmentExpression", // 表示赋值表达式的节点类型
  VariableDeclarator: "VariableDeclarator", // 表示变量声明中的一个具体变量
  VariableDeclaration: "VariableDeclaration", // 表示变量声明语句
  Program: "Program" // Program 是顶层节点，表示整个 JavaScript 程序的根节点。它包含了程序中所有的语句和声明。
}

module.exports = {
  TokenTypes,
  AST_Types
}

词法分析生成 token // tokenizer.js

// 拿到刚才定义的类型变量
const customTokens = require("./constants")
const {TokenTypes } = customTokens

// 定义字符匹配规则
const KEYWORD = /let/ // 匹配关键字
const PUNCTUATOR = /[\=;]/ // 匹配"="、";"
const WHITESPACE = /\s/ // 匹配空格
const LETTERS = /[a-z]/i // 匹配字符

function tokenizer(input) {
  const tokens = [] // token列表存储token，并最终返回
  let current = 0 // 标记遍历到字符串的什么位置

  // 用while循环遍历代码字符串，直到遍历完整个字符串
  while (current < input.length) {
    let char = input[current] // 暂存一下当前遍历到的字符

    // 判断当前字符串是否是关键字或变量名
    if (LETTERS.test(char)) {
      let value = ''
      // 遍历当前字符所连接的完整字符，存入 value
      while (LETTERS.test(char)) {
        value += char
        char = input[++current]
      }
      // 判断当前字符串是否是关键字
      if (KEYWORD.test(value)) {
        tokens.push({
           type: TokenTypes.Keyword, // 标记token类型
           value: value // 记录token值
        })
      }
      // 否则是变量名
      else {
         tokens.push({
           type: TokenTypes.Identifier, // 标记为字符类型
           value: value // 记录值
         })
       }
       continue
    }

语法分析

语法分析就是将遍历得到的 token 列表，根据语法规则将 token 关联起来，形成一棵树形结构，这棵树就是 AST。所以 AST 表示的是源代码的语法结构，树上的每个节点表示的是源代码中的一种结构。

先看结果：

{
  "type": "Program",
  "body": [
    {
      "type": "VariableDeclaration",
      "declarations": [
        {
          "type": "VariableDeclarator",
          "id": {
            "type": "Identifier",
            "name": "name"
          },
          "init": {
            "type": "Literal",
            "value": "张三",
            "raw": "\"张三\""
          }
        }
      ],
      "kind": "let" // 标识变量声明的类型
    }
  ],
  "sourceType": "script"
}

AST 生成

// 拿到刚才定义的token类型和AST类型
const customTokens = require("./constants")
const {TokenTypes, AST_Types } = customTokens

// 语法解析
function parser(tokens) { // 这里的tokens是指上面解析生成的tokens
  let current = 0
  function walk() {
      // 拿到解析生成的token
      const token = tokens[current]
      // 处理字符节点
      if (token.type === TokenTypes.String) {
        current++;
        // 返回一个新的 AST 结点
        return {
          type: AST_Types.Literal, // 赋予AST节点类型
          value: JSON.parse(token.value),
          row: token.value
        }
      }
      // 处理变量名
      if (token.type === TokenTypes.Identifier) {
      current++;
      return {
        type: AST_Types.Identifier,
        name: token.value,
      };
    }
    // 检查运算符关键字
    if (token.type === TokenTypes.Punctuator) {
      current++;
      if(/\=/.test(token.value)){ // 判断是否是=号， 这里 因为只是简单示例所以只有=的处理，实际情况更复杂些
        return {
          type: AST_Types.AssignmentExpression,
          operator: token.value
        }
      }
      // 忽略掉;号，不算入AST中
      else{
        return
      }
    }
    // 检查关键字
    // 处理赋值语句的时候存在递归调用。同时我们忽略了一些token的处理，比如"="、";"
    if ( token.type === TokenTypes.Keyword) {
      var value = token.value // 得到 'let'
      current++; // 紧跟声明语句的就是变量名，下一步walk就可以返回变量名
      const variable = walk() // 递归获取定义的变量 处理可能嵌套的结构
      current++ // 下一个应该是=号，略过不算入AST中
      const rightVar = walk()
      current++ // 下一个应该是;号，略过不算入AST中

      // 定义声明
      const declaration = {
        type: AST_Types.VariableDeclarator,
        id: variable, // 定义的变量
        init: rightVar // 赋予的值
      }
      // 定义要返回的节点
      return {
        type: AST_Types.VariableDeclaration,
        declarations: [declaration],
        kind: value,
      };
    }
    // 类型未知的结点，抛错误
    throw new TypeError(token.type);
    }
  // 创建 AST，定义根结点是一个类型为 `Program` 的结点。
  const ast = {
    type: AST_Types.Program,
    body: [],
    sourceType: "script"
  };
  // 遍历被解析字符执行 walk 函数，把结点值放入 ast.body 中。
  while (current < tokens.length) {
    ast.body.push(walk());
  }
  return ast;
}

module.exports = parser

AST 测试工具 https://esprima.org/demo/parse.html# 查看生成的 Token 和 AST

实现一个简单的 js 编译器

把 es6 的语法转换成 es5 的语法，其实就是 babel 干的事情

编译器一般分三步走： Parsing（解析）：负责将代码解析然后生成 AST
Transformation（转换）： 根据 AST 来对代码做一些增删改的操作
Code Generation （代码生成）：根据转换后 AST 重新生成新的代码

Parsing（解析）上述 AST 解析已讲

Transformation（转换） 将 let name = “张三”; 转换为 var name = “张三”; 即需要将 let 替换成 var，AST 转换成如下形式：

{
  "type": "Program",
  "body": [
    {
      "type": "VariableDeclaration",
      "declarations": [
        {
          "type": "VariableDeclarator",
          "id": {
            "type": "Identifier",
            "name": "name"
          },
          "init": {
            "type": "Literal",
            "value": "张三",
            "raw": "\"张三\""
          }
        }
      ],
      "kind": "var"
    }
  ],
  "sourceType": "script"
}

实现：首先我们需要一个可以遍历 ast 的 traverser（遍历器）ast 是一颗树形结构，采用深度优先进行遍历，再调用 traverser 生成新的 ast // traverser.js

// 获取AST节点类型
const constants = require("./constants")
const { AST_Types } = constants
// visitor 为自定义函数
function traverser(ast, visitor) {
  // 遍历解析 body 节点数组
  function traverseArray(array, parent) {
      array.forEach(function(child) {
        traverseNode(child, parent);
      });
    }
}
// 处理每个节点
function traverseNode(node, parent) {
   // 首先看看 visitor 中有没有对应 type 的处理函数。
    const method = visitor[node.type]
    // 如果有，调用处理方法 不同类型节点对应不同的方法 详见下文调用处
    if (method) {
      method(node, parent)
    }
    // 下面对每一个不同类型的结点分开处理。
    switch (node.type) {
      case AST_Types.Program: // 顶层的 Program 开始，body是数组所以调用traverseArray
        traverseArray(node.body, node)
        break
        // 以下类型不需要转换，直接退出
      case AST_Types.VariableDeclaration:
      case AST_Types.VariableDeclarator:
      case AST_Types.AssignmentExpression:
      case AST_Types.Identifier:
      case AST_Types.Literal:
        break
      // 同样，如果不能识别当前的结点，那么就抛出一个错误。
      default:
        throw new TypeError(node.type)
    }
  }
  // 触发遍历AST，根节点没有父节点所以这里传入null
  traverseNode(ast, null)
}
module.exports = traverser

// transformer.js
// 获取转换器和AST类型
const traverser = require("./traverser")
const constants = require("./constants")
const { AST_Types } = constants

// transformer接收 AST 作为参数
function transformer(ast) {
  // newAst用于存储新的AST
  const newAst = {
    type: AST_Types.Program,
    body: [],
    sourceType: "script"
  };
  // 保存当前修改过的节点
  ast._context = newAst.body
  // 将 AST 和 visitor 传入traverser中
  traverser(ast, {
    // 将let转换为var
    VariableDeclaration: function(node, parent) {
      const variableDeclaration = {
        type: AST_Types.VariableDeclaration,
        declarations: node.declarations,
        kind: "var"
      };
      // 把新的 VariableDeclaration 放入到 context 中。
      parent._context.push(variableDeclaration)
    }
  });
  // 最后返回新的AST
  return newAst
}

module.exports = transformer

Code Generation （代码生成）根据新的 AST 来重新生成代码

// 获取AST类型
const constants = require("./constants")
const { AST_Types } = constants

function codeGenerator(node) {
  // 处理不同类型的结点
  switch (node.type) {
  // 遍历 body 属性中的每一个结点并加入换行符号
  case AST_Types.Program:
      return node.body.map(codeGenerator)
        .join('\n')

    case AST_Types.VariableDeclaration: // 处理变量声明
      return (
        node.kind + ' ' + node.declarations.map(codeGenerator)
      )
    case AST_Types.VariableDeclarator: // 处理声明的变量和值
      return (
        codeGenerator(node.id) + ' = ' +
        codeGenerator(node.init)
      )
    case AST_Types.Identifier: // 变量名直接返回
      return node.name

    case AST_Types.Literal: // 字符串加上""、;返回
      return '"'+node.value+'"'+";"

    // 如果我们不能识别这个结点，那么抛出一个错误。
    default:
      throw new TypeError(node.type)
  }
}

module.exports = codeGenerator

完整的代码执行流

const transformer = require("./transformer")
const tokenizer = require("./tokenizer")
const parser = require("./parser")
const codeGenerator = require("./codeGenerator")

const tokens = tokenizer('let name = "张三";')
const ast = parser(tokens)
const newAst = transformer(ast)
const newCode = codeGenerator(newAst)

console.log(newCode) // var name = "张三";

附：AST 节点类型对照表

节点类型	描述
Identifier	变量、函数或属性的名称。
Literal	数字、字符串、布尔值等常量值。
ExpressionStatement	包含在语句中的表达式。
BinaryExpression	包含二元操作符及其两个操作数的表达式。
UnaryExpression	包含一元操作符及其操作数的表达式。
CallExpression	函数调用表达式，包括函数和参数。
MemberExpression	对象属性访问表达式，如 obj.prop。
AssignmentExpression	赋值表达式，如 variable = value。
FunctionDeclaration	函数声明节点，定义函数及其主体。
VariableDeclaration	变量声明节点，定义变量及其初始值。
IfStatement	条件语句，包含条件表达式和执行语句。
ForStatement	循环语句，包含初始化、条件和迭代语句。
WhileStatement	While 循环语句，包含条件和执行语句。
ReturnStatement	返回语句，用于从函数中返回值。
ObjectExpression	对象字面量表达式，表示 JavaScript 中的对象。
ArrayExpression	数组字面量表达式，表示 JavaScript 中的数组。
NewExpression	创建新对象实例的表达式，如 new Constructor()。

---