AST (Abstract Syntax Tree)

AST 定義

• AST(Abstract Syntax Tree)抽象語法樹，簡稱AST，它是源代碼(也就是説它不僅僅是應用於JavaScript，同時還應用於其他語言，例如: Python，Rust等)語法結構的一種抽象表示。
• 它以樹狀的形式表現編程語言的語法結構，樹上的每個節點都表示源碼中的一種結構。
• 語法【抽象】: 指的是這裏的語法並不會表示出真實語法中出現的每個細節。

AST使用方式

• 我們常見的詞法分析器以及語法解析器(它可以將JavaScript源碼轉換成AST)，比如下面實例中的esprima，當然還有其他的，例如: acorn、shift、traceur等

用途

• AST 抽象語法樹的用途是非常廣泛的，比如:
• vscode、atom、sublime中的代碼高亮、代碼格式化、錯誤提示、代碼自動補全；
• eslint、prettier對代碼錯誤或者風格的檢查；
• babel轉譯ES6到ES5
  ...
• 所以説如果你想優化JavaScript的編譯和運行速度，AST的瞭解是必不可少的。

AST原理

編譯流程

• JavaScript執行的過程首先是讀取JavaScript文件中的字符流，其次通過詞法分析器生成token，之後再通過語法分析器(Parser)生成AST樹，最後轉換為機器碼執行。

var name = "jackdan";

• 第一步就先讀取上面的字符流'var name = "jackdan"'；
• 第二步分詞: 將'var name = "jackdan"'整個代碼字符串分割成最小的語法單元數組；如下:

[
  { type: 'Keyword', value: 'var' },
  { type: 'Identifier', value: 'name' },
  { type: 'Punctuator', value: '=' },
  { type: 'String', value: '"jackdan"' }
]

• 第三步語法分析: 在分詞的基礎上建立分析語法單元之間的關係；如下:

- Program
  type: "Program"
  - body: [
    - VariableDeclaration {
      type: "VariableDeclaration"
      - declarations: [
        - VariableDeclarator {
          type: "VariableDeclarator"
          - id: Identifier {
            type: "Identifier"
            name: "name"
          }
          - init: Literal {
            type: "Literal"
            value: "jackdan"
            raw: "jackdan"
          }
        }
      ]
      kind: "var"
    }
  ]

• 我們重點梳理一下原理中的詞法分析和語法分析，接觸過這兩者的應該不會太過於陌生。

詞法分析

• 詞法分析：同時也稱為掃描(scanner)，簡單來説就是調用
  next()方法，一個一個字母的來讀取字符，然後與定義好的JavaScript關鍵字符做比較，生成對應的Token。Token是一個不可分割的最小單元。例如:

var name = "jackdan";
// 先讀取v，然後繼續讀取a,最後讀取r組成一個var
// var這三個字符就識別為JavaScript中的關鍵字，作為一個整體，語義上就不能再被分解了，因此我們也視為一個Token

• 從上面的代碼實例中不難得出，詞法分析器裏，每個關鍵字是一個Token，每個標識符是一個Token，每個操作符是一個Token，每個標點符號也都是一個Token。除此之外，還會過濾掉程序中的註釋和空白字符（換行符、空格、製表符等）。
• 最終，我們看到整個代碼都被分割進了一個tokens列表（或者説一維數組）。

[
  { type: 'Keyword', value: 'var' },
  { type: 'Identifier', value: 'name' },
  { type: 'Punctuator', value: '=' },
  { type: 'String', value: '"jackdan"' }
]

語法分析

• 語法分析就是將詞法分析的tokns列表轉化成有語法含義的抽象語法樹結構。同時去驗證語法(高亮、自動補全等)，語法如果有錯的話，拋出語法錯誤。

- Program
  type: "Program"
  - body: [
    - VariableDeclaration {
      type: "VariableDeclaration"
      - declarations: [
        - VariableDeclarator {
          type: "VariableDeclarator"
          - id: Identifier {
            type: "Identifier"
            name: "name"
          }
          - init: Literal {
            type: "Literal"
            value: "jackdan"
            raw: "jackdan"
          }
        }
      ]
      kind: "var"
    }
  ]

AST 實例

// 源代碼
var name = "jackdan";

// AST 抽象語法樹
/**
 * 
 *      +-----------+
 *      | assign(=) |
 *      +-----------+
 *      /            \
 *     /              \
 * +----+        +---------+
 * |name|        |"jackdan"|
 * +----+        +---------+
 * 
*/

// 運行輸出的結構代碼
- Program
  type: "Program"
  - body: [
    - VariableDeclaration {
      type: "VariableDeclaration"
      - declarations: [
        - VariableDeclarator {
          type: "VariableDeclarator"
          - id: Identifier {
            type: "Identifier"
            name: "name"
          }
          - init: Literal {
            type: "Literal"
            value: "jackdan"
            raw: "jackdan"
          }
        }
      ]
      kind: "var"
    }
  ]

> var esprima = require('esprima');
> var program = 'var name = "jackdan"';

> esprima.tokenize(program);
[
  { type: 'Keyword', value: 'var' },
  { type: 'Identifier', value: 'name' },
  { type: 'Punctuator', value: '=' },
  { type: 'String', value: '"jackdan"' }
]

> esprima.parse(program);
Script {
  type: 'Program',
  body: [
    VariableDeclaration {
      type: 'VariableDeclaration',
      declarations: [Array],
      kind: 'var'
    }
  ],
  sourceType: 'script'
}

Thinking in JackDan