Javascript抽象語法樹上篇(基礎篇)
- 2019 年 12 月 16 日
- 筆記
一、基礎
為什麼要了解抽象語法樹
日常工作中，我們會碰到js程式碼解析的場景，比如分析程式碼中require了哪些包，有些什麼關鍵API調用，大部分情況使用正則表達式來處理，可一旦場景複雜，或者依賴於程式碼上下文時，正則就很難處理了，這時候就要用到抽象語法樹。常見的uglify、eslint、babel、webpack等等都是基於抽象語法樹來處理的，如此強大，有必要好好了解一下。
什麼是抽象語法樹
抽象語法樹即：Abstract Syntax Tree。簡稱AST，見下圖。
- 圖中code先經過parse轉換成一個樹狀數據結構
- 接著對樹中節點進行轉換，圖中將葉子節點對換位置
- 將樹狀結構通過generate再生成code
圖中樹狀數據結構即AST，從這個過程可以看到將程式碼轉成AST後，通過操作節點來改變程式碼。
如何獲得抽象語法樹
獲得抽象語法樹的過程為：程式碼 => 詞法分析 => 語法分析 => AST 詞法分析：把字元串形式的程式碼轉換為令牌（tokens）流。 語法分析：把一個令牌流轉換成 AST 的形式。這個階段會使用令牌中的資訊把它們轉換成一個 AST 的表述結構，這樣更易於後續的操作。
如下圖，程式碼為一個簡單的函數聲明。詞法分析階段，將程式碼作為字元串輸入獲得關鍵詞，圖中 function、 square、 (、 )、 {、 }等都被識別為關鍵詞(稍微回憶下編譯原理，字元挨個入棧，符合一定規則即出棧)。語法分析階段，對關鍵詞的組合形成一個個節點，如n*n這3個關鍵片語合成 二元表達式，關鍵詞return與二元表達式組合成 return語句。最後組合成一個 函數聲明語句。
二、規範
如何獲得AST已經簡單介紹了，那AST最終應該以什麼樣的數據結構存在呢，先看看上述函數聲明的AST結構
那解析的依據是什麼，為什麼要以上圖的結構出現，業界已經有了一套成熟的規範。
規範起源
在v8引擎之前，最早js引擎是SpiderMonkey，第一個版本由js作者Brendan Eich設計，後交給Mozilla組織維護。js引擎在執行js文件時，都會先將js程式碼轉換成抽象語法樹(AST)。有一天，一位Mozilla工程師在FireFox中公開了這個將程式碼轉成AST的解析器Api，也就是Parser_API[1]，後來被人整理到github項目estree[2]，慢慢的成了業界的規範。
規範解讀
上面提到的 Parser_API是規範的原文，中文版:Parser_API[3]，但讀起來並不太友好，推薦直接讀整理後的git項目estree，打開項目地址，如下圖
其中最下面的 es5.md為ES5規範，僅列出ES5的內容， es2015.md為ES6規範，但只列出了針對ES5新增的內容，依次類推，最後的 es2019.md即ES10是對ES9的補充，僅有一條規則。
打開最基礎的 es5.md，可以看到所有語法基礎，這裡跟大家一起讀一下大類，細分類別就略過了。讀規範時可以使用https://astexplorer.net/ 輔助閱讀，可以實時輸出AST。
- Node objects
- Programs
- Identifier
- Literal
- Functions
- Statements
- Declarations
- Expressions
- Patterns
Node objects
interface Node { type: string; loc: SourceLocation | null; }
定義AST中節點基本類型，其他所有具體節點都需要實現以上介面，即每個節點都必須包含type、loc兩個欄位
type欄位表示不同的節點類型，下邊會再講一下各個類型的情況，分別對應了 JavaScript 中的什麼語法。你可以從這個欄位看出這個節點實現了哪個介面 loc欄位表示源碼的位置資訊，如果沒有相關資訊的話為 null，否則是一個對象，包含了開始和結束的位置。介面如下
interface SourceLocation { source: string | null; start: Position; end: Position; }
每個 Position 對象包含了行（從1開始）和列（從0開始）資訊，介面如下
interface Position { line: number; // >= 1 column: number; // >= 0 }
Programs
interface Program <: Node { type: "Program"; body: [ Directive | Statement ]; }
一棵完整的程式程式碼樹，一般作為根節點
Identifier
interface Identifier <: Expression, Pattern { type: "Identifier"; name: string; }
標識符，我們寫程式碼時自定義的名稱，如變數名、函數名、屬性名。
Literal
interface Literal <: Expression { type: "Literal"; value: string | boolean | null | number | RegExp; }
字面量，如 「hello」、 true、 null、 100、 /d/這些，注意字面量本身也是一個表達式語句(ExpressionStatement)
Functions
interface Function <: Node { id: Identifier | null; params: [ Pattern ]; body: FunctionBody; }
一個函數聲明或者表達式，id是函數名，params是標識符數組，body是函數體，也是一個語句塊。
Statements
interface Statement <: Node { }
語句，子類有很多， 塊語句、 if/switch語句、 return語句、 for/while語句、 with語句等等
Declarations
interface Declaration <: Statement { }
聲明，子類主要有變數申明、函數聲明。
Expressions
interface Expression <: Node { }
表達式，子類很多，有二元表達式( n*n)、函數表達式(var fun = function(){})、數組表達式(var arr = [])、對象表達式(var obj = {})、賦值表達式( a=1)等等
Patterns
interface Pattern <: Node { }
模式，主要在 ES6 的解構賦值中有意義(let {name} = user，其中{name}部分為 ObjectPattern)，在 ES5 中，可以理解為和 Identifier 差不多的東西。
三、現狀
通過以上規範解讀，知道了最終要生成的AST以什麼樣的結構存在，對於javascript的解析，業界已經有很多成熟的解析器，可以將js程式碼轉換成符合規範的AST
- Esprima，比較經典，出現的比較早
- Acorn，fork自Esprima，程式碼更精簡。webpack使用acorn進行模組解析
- UglifyJS2，主要用於程式碼壓縮
- babylon，babel解析器，fork自Acorn，目前最新版本是babylon7,對應npm包@babel/parser
- Espree，eslint默認的解析器，由於遵循同一套規範，也可以使用babel的解析器替代
- flow、shift等等
AST基礎篇介紹完畢，下篇將從實踐的角度繼續介紹
References [1] ParserAPI：https://developer.mozilla.org/en-US/docs/Mozilla/Projects/SpiderMonkey/ParserAPI [2] estree：https://github.com/estree/estree [3] ParserAPI(中文)：https://developer.mozilla.org/zh-CN/docs/Mozilla/Projects/SpiderMonkey/ParserAPI
