動態

詳情 返回 返回

抽象語法樹AST必知必會 | 京東物流技術團隊 - 動態 詳情

1 介紹 AST

打開前端項目中的 package.json，會發現眾多工具已經佔據了我們開發日常的各個角落，例如 JavaScript 轉譯、CSS 預處理、代碼壓縮、ESLint、Prettier 等。這些工具模塊大都不會交付到生產環境中，但它們的存在於我們的開發而言是不可或缺的。

Babel，Webpack，Vue-cli 和 EsLint 等很多的工具和庫的核心都是通過 Abstract Syntax Tree 抽象語法樹這個概念來實現對代碼的檢查、分析等操作的。在前端當中 AST 的使用場景非常廣，比如在 Vue.js 當中，我們在代碼中編寫的 template 轉化成 render function 的過程當中第一步就是解析模版字符串生成 AST。

AST 的官方定義：

抽象語法樹 (Abstract Syntax Tree，AST)，是源代碼語法結構的一種抽象表示。以樹狀的形式表現編程語言的語法結構，每個節點都表示源代碼中的一種結構。

JS 的許多語法為了給開發者更好的編程體驗，並不適合程序的理解。所以需要把源碼轉化為 AST 來更適合程序分析，瀏覽器的編譯器一般會把源碼轉化為 AST 來進行進一步的分析來進行其他操作。通過了解 AST 這個概念，對深入瞭解前端的一些框架和工具是很有幫助的。

那麼 AST 是如何生成的？為什麼需要 AST ？

瞭解過編譯原理的同學知道計算機想要理解一串源代碼需要經過“漫長”的分析過程：

  1. 詞法分析 (Lexical Analysis)
  2. 語法分析 (Syntax Analysis)
  3. …
  4. 代碼生成 (Code Generation)

這是在線的 AST 轉換器：AST轉換器。可以在這個網站上，親自嘗試下轉換。點擊語句中的詞，右邊的抽象語法樹節點便會被選中，如下圖：

代碼轉化成 AST 後的格式大致如下圖所示：

為了方便大家理解抽象語法樹，來看看具體的例子。

var tree = 'this is tree'

js 源代碼將會被轉化成下面的抽象語法樹：


{
  "type": "Program",
  "start": 0,
  "end": 25,
  "body": [
    {
      "type": "VariableDeclaration",
      "start": 0,
      "end": 25,
      "declarations": [
        {
          "type": "VariableDeclarator",
          "start": 4,
          "end": 25,
          "id": {
            "type": "Identifier",
            "start": 4,
            "end": 8,
            "name": "tree"
          },
          "init": {
            "type": "Literal",
            "start": 11,
            "end": 25,
            "value": "this is tree",
            "raw": "'this is tree'"
          }
        }
      ],
      "kind": "var"
    }
  ],
  "sourceType": "module"
}

可以看到一條語句由若干個詞法單元組成。這個詞法單元就像 26 個字母。創造出個十幾萬的單詞，通過不同單詞的組合又能寫出不同內容的文章。

字符串形式的 type 字段表示節點的類型。比如”BlockStatement”，”Identifier”，”BinaryExpression”等。 每一種類型的節點定義了一些屬性來描述該節點類型，然後就可以通過這些節點來進行分析其他操作。

2 AST 如何生成

看到這裏，你應該已經知道抽象語法樹大致長什麼樣了。那麼AST又是如何生成的呢？

以上面var tree = ‘this is tree’為例：

詞法分析

其中詞法分析階段掃描輸入的源代碼字符串，生成一系列的詞法單元 (tokens)，這些詞法單元包括數字，標點符號，運算符等。詞法單元之間都是獨立的，也即在該階段我們並不關心每一行代碼是通過什麼方式組合在一起的。

大致可以看出轉換之前源代碼的基本構造。

語法分析階段——老師教會我們每個單詞在整個句子上下文中的具體角色和含義。

  • 代碼生成

最後是代碼生成階段，該階段是一個非常自由的環節，可由多個步驟共同組成。在這個階段我們可以遍歷初始的 AST，對其結構進行改造，再將改造後的結構生成對應的代碼字符串。

代碼生成階段——我們已經弄清楚每一條句子的語法結構並知道如何寫出語法正確的英文句子，通過這個基本結構我們可以把英文句子完美地轉換成一箇中文句子。

3 AST 的基本結構

拋開具體的編譯器和編程語言，在 “AST 的世界”裏所有的一切都是節點 (Node)，不同類型的節點之間相互嵌套形成一顆完整的樹形結構。

{
  "program": {
    "type": "Program",
    "sourceType": "module",
    "body": [
      {
        "type": "FunctionDeclaration",
        "id": {
          "type": "Identifier",
          "name": "foo"
        },
        "params": [
          {
            "type": "Identifier",
            "name": "x"
          }
        ],
        "body": {
          "type": "BlockStatement",
          "body": [
            {
              "type": "IfStatement",
              "test": {
                "type": "BinaryExpression",
                "left": {
                  "type": "Identifier",
                  "name": "x"
                },
                "operator": ">",
                "right": {
                  "type": "NumericLiteral",
                  "value": 10
                }
              }
            }
          ]
        }
        ...
       }
       ...
    ]
}

AST 的結構在不同的語言編譯器、不同的編譯工具甚至語言的不同版本下是各異的，這裏簡單介紹一下目前 JavaScript 編譯器遵循的通用規範 —— ESTree 中對於 AST 結構的一些基本定義，不同的編譯工具都是基於此結構進行了相應的拓展。

4 AST 的應用場景和用法

瞭解 AST 的概念和具體結構後，你可能不禁會問：AST 有哪些使用場景，怎麼用？
代碼語法的檢查、代碼風格的檢查、代碼的格式化、代碼的高亮、代碼錯誤提示、代碼自動補全等等

  • 如 JSLint、JSHint 對代碼錯誤或風格的檢查，發現一些潛在的錯誤。
  • IDE 的錯誤提示、格式化、高亮、自動補全等等。

代碼混淆壓縮。

  • UglifyJS2 等。

優化變更代碼，改變代碼結構使達到想要的結構。

  • 代碼打包工具 webpack、rollup 等等。
  • CommonJS、AMD、CMD、UMD 等代碼規範之間的轉化。
  • CoffeeScript、TypeScript、JSX 等轉化為原生 Javascript。

至於如何使用 AST ，歸納起來可以把它的使用操作分為以下幾個步驟：

  1. 解析 (Parsing)：這個過程由編譯器實現，會經過詞法分析過程和語法分析過程，從而生成 AST。
  2. 讀取/遍歷 (Traverse)：深度優先遍歷 AST ，訪問樹上各個節點的信息（Node）。
  3. 修改/轉換 (Transform)：在遍歷的過程中可對節點信息進行修改，生成新的 AST。
  4. 輸出 (Printing)：對初始 AST 進行轉換後，根據不同的場景，既可以直接輸出新的 AST，也可以轉譯成新的代碼塊。

通常情況下使用 AST，我們重點關注步驟2和3，諸如 Babel、ESLint 等工具暴露出來的通用能力都是對初始 AST 進行訪問和修改。

這兩步的實現基於一種名為訪問者模式的設計模式，即定義一個 visitor 對象，在該對象上定義了對各種類型節點的訪問方法，這樣就可以針對不同的節點做出不同的處理。例如，編寫 Babel 插件其實就是在構造一個 visitor 實例來處理各個節點信息，從而生成想要的結果。

const visitor = {

    CallExpression(path) {

        ...

    }

    FunctionDeclaration(path) {

        ...

    }   

    ImportDeclaration(path) {

        ...

    }

    ...

}

traverse(AST, visitor)

5 AST 的轉化流程

利用 babel-core (babel 核心庫，實現核心的轉換引擎) 和 babel-types (可以實現類型判斷，生成 AST 節點等)和 AST 來將

let sum = (a, b) => a + b

改成為：

let sum = function(a, b) {
  return a + b
}

實現代碼如下：

// babel核心庫，實現核心的轉換引擎
let babel = require('babel-core');
// 可以實現類型判斷，生成AST節點等
let types = require('babel-types');

let code = `let sum = (a, b) => a + b`;
// let sum = function(a, b) {
//   return a + b
// }

// 這個訪問者可以對特定類型的節點進行處理
let visitor = {
  ArrowFunctionExpression(path) {
    console.log(path.type);
    let node = path.node;
    let expression = node.body;
    let params = node.params;
    let returnStatement = types.returnStatement(expression);
    let block = types.blockStatement([
        returnStatement
    ]);
    let func = types.functionExpression(null,params, block,false, false);
    path.replaceWith(func);
  }
}

let arrayPlugin = { visitor }
// babel內部會把代碼先轉成AST， 然後進行遍歷
let result = babel.transform(code, {
  plugins: [
    arrayPlugin
  ]
})
console.log(result.code);

分詞將整個代碼字符串分割成最小語法單元數組，生成 AST 抽象語法樹，經過轉化 transformer 生成新的 AST 樹，遍歷生成最終想要的結果 genrator：

AST 的三板斧：

  • 通過 esprima 生成 AST
  • 通過 estraverse 遍歷和更新 AST
  • 通過 escodegen 將 AST 重新生成源碼

我們可以來做一個簡單的例子：
1.先新建一個 test 的工程目錄。
2.在 test 工程下安裝 esprima、estraverse、escodegen 的 npm 模塊

npm i esprima estraverse escodegen --save

3.在目錄下面新建一個 test.js 文件，載入以下代碼：

const esprima = require('esprima');
let code = 'const a = 1';
const ast = esprima.parseScript(code);
console.log(ast);

將會看到輸出結果：

Script {
  type: 'Program',
  body:
   [ VariableDeclaration {
       type: 'VariableDeclaration',
       declarations: [Array],
       kind: 'const' } ],
  sourceType: 'script' }

4.再在 test 文件中，載入以下代碼：

const estraverse = require('estraverse');

estraverse.traverse(ast, {
    enter: function (node) {
        node.kind = "var";
    }
});

console.log(ast);

5.最後在 test 文件中，加入以下代碼：

const escodegen = require("escodegen");
const transformCode = escodegen.generate(ast)

console.log(transformCode);

輸出的結果：

var a = 1;

通過這三板斧：我們將const a = 1轉化成了var a = 1

6 實際應用

利用 AST 實現預計算的 Babel 插件，實現代碼如下：

// 預計算簡單表達式的插件
let code = `const result = 1000 * 60 * 60`;
let babel = require('babel-core');
let types= require('babel-types');

let visitor = {
  BinaryExpression(path) {
    let node = path.node;
    if (!isNaN(node.left.value) && ! isNaN(node.right.value)) {
      let result = eval(node.left.value + node.operator + node.right.value);
      result = types.numericLiteral(result);
      path.replaceWith(result);
      let parentPath = path.parentPath;
      // 如果此表達式的parent也是一個表達式的話，需要遞歸計算
      if (path.parentPath.node.type == 'BinaryExpression') {
        visitor.BinaryExpression.call(null, path.parentPath)
      }
    }
  }
}

let cal = babel.transform(code, {
  plugins: [
    {visitor}
  ]
});

作者：京東物流 李瓊

來源：京東雲開發者社區 自猿其説Tech

Javascript , 抽象語法樹 , ast , 前端 , html5
user avatar yushang_66b0e8718bd85 頭像 immerse 頭像 tingzhu_guo 頭像 fabarta 頭像 oukai 頭像 chenzhuodeyagao 頭像 zengjingdeshaonian 頭像 xinchengkuaikayuan 頭像 54r9rxzy 頭像 taozi_60b0b3c71b1a8 頭像 libin9iai 頭像
點贊 11 用戶, 點贊了這篇動態!
點贊

Add a new 評論

Some HTML is okay.