抽象語法樹在 JavaScript 中的應用

抽象語法樹是什麼

在電腦科學中，抽象語法樹（abstract syntax tree 或者縮寫為 AST），或者語法樹（syntax tree），是原始碼的抽象語法結構的樹狀表現形式，這裡特指程式語言的原始碼。樹上的每個節點都表示原始碼中的一種結構。之所以說語法是「抽象」的，是因為這裡的語法並不會表示出真實語法中出現的每個細節。

果然比較抽象，不如先看幾個例子：

抽象語法樹舉例

foo = ‘hello world’;

/*

+————-+

| assign(=) |

+————-+

X X

X X

+——-+ +—————–+

| foo | | ‘hello world’ |

+——-+ +—————–+

*/

if (foo === true) {

bar = ‘hello world’;

alert(bar);

}

/*

+——+

| if |

+——+

X X

X X

+————–+ +————-+

| equal(===) | | if_body |

+————–+ +————-+

X X X X

X X X X

+——-+ +——–+ +————-+ +————+

| foo | | true | | assign(=) | | alert() |

+——-+ +——–+ +————-+ +————+

X X X

X X X

+——-+ +—————–+ +——-+

| bar | | ‘hello world’ | | bar |

+——-+ +—————–+ +——-+

*/

從上述兩個例子可以看出，抽象語法樹是將原始碼根據其語法結構，省略一些細節（比如：括號沒有生成節點），抽象成樹形表達。

抽象語法樹在電腦科學中有很多應用，比如編譯器、IDE、壓縮最佳化程式碼等。下麵介紹一下抽象語法樹在 JavaScript 中的應用。

JavaScript 抽象語法樹

構造 JavaScript 抽象語法樹有多種工具，比如 v8、SpiderMonkey、UglifyJS 等，這裡重點介紹 UglifyJS。

UglifyJS

UglifyJS 是使用最廣的 JavaScript 壓縮工具之一，而且自身也是用 JavaScript 寫的，使用它的方法很簡單（需要 nodejs 環境）：

首先全域性安裝：

[sudo ]npm install -g uglify-js

然後就可以使用了：

uglifyjs -m srcFileName.js -o destFileName.min.js

關於 UglifyJS 的用法這裡就不多介紹了，我們要做的是一些更有趣的事情。

UglifyJS Tools

UglifyJS 提供了一些工具用於分析 JavaScript 程式碼，包括：

• parser，把 JavaScript 程式碼解析成抽象語法樹

• code generator，透過抽象語法樹生成程式碼

• mangler，混淆 JavaScript 程式碼

• scope analyzer，分析變數定義的工具

• tree walker，遍歷樹節點

• tree transformer，改變樹節點

生成抽象語法樹

使用 UglifyJS 生成抽象語法樹很簡單：

首先安裝 UglifyJS 為 npm 包：

npm install uglify-js –save-dev

然後使用 parse 方法即可：

var UglifyJS = require(‘uglify-js’);

var ast = UglifyJS.parse(‘function sum(foo, bar){ return foo + bar; }’);

這樣生成的 ast 即為那一段程式碼的抽象語法樹。那麼我們怎麼使用呢？

使用 mangler 壓縮程式碼

使用 mangler 可以透過將區域性變數都縮短成一個字元來壓縮程式碼。

var UglifyJS = require(‘uglify-js’);

var ast = UglifyJS.parse(‘function sum(foo, bar){ return foo + bar; }’);

ast.figure_out_scope();

ast.mangle_names();

console.log(ast.print_to_string());

// function sum(a,b){return a+b}

使用 walker 遍歷抽象語法樹

使用 walker 可以遍歷抽象語法樹，這種遍歷是深度遍歷。

var UglifyJS = require(‘uglify-js’);

var ast = UglifyJS.parse(‘function sum(foo, bar){ return foo + bar; }’);

ast.figure_out_scope();

ast.walk(new UglifyJS.TreeWalker(function(node) {

console.log(node.print_to_string());

}));

/*

function sum(foo,bar){return foo+bar}

function sum(foo,bar){return foo+bar}

sum

foo

bar

return foo+bar

foo+bar

foo

bar

*/

UglifyJS 已經提供了直接壓縮程式碼的指令碼，walker 看上去貌似也沒啥用，那麼這些工具有什麼使用場景呢？

抽象語法樹的應用

利用抽象語法樹重構 JavaScript 程式碼

假如我們有重構 JavaScript 的需求，它們就派上用場啦。

下麵考慮這樣一個需求：

我們知道，parseInt 用於將字串變成整數，但是它有第二個引數，表示以幾進位制識別字串，若沒有傳第二個引數，則會自行判斷，比如：

parseInt(‘10.23’);

// 10 轉換成正整數

parseInt(’10abc’);

// 10 忽略其他字元

parseInt(’10’, 10);

// 10 轉換成十進位制

parseInt(’10’, 2);

// 2 轉換成二進位制

parseInt(‘0123’);

// 83 or 123 不同瀏覽器不一樣，低版本瀏覽器會轉換成八進位制

parseInt(‘0x11’);

// 17 轉換成十六進位制

因為有一些情況是和我們預期不同的，所以建議任何時候都加上第二個引數。

下麵希望有一個指令碼，檢視所有 parseInt 有沒有第二個引數，沒有的話加上第二個引數 10，表示以十進位制識別字串。

使用 UglifyJS 可以實現此功能：

#! /usr/bin/env node

var U2 = require(“uglify-js”);

function replace_parseint(code) {

var ast = U2.parse(code);

// accumulate `parseInt()` nodes in this array

var parseint_nodes = [];

ast.walk(new U2.TreeWalker(function(node){

if (node instanceof U2.AST_Call

&& node.expression.print_to_string() === ‘parseInt’

&& node.args.length === 1) {

parseint_nodes.push(node);

}

}));

// now go through the nodes backwards and replace code

for (var i = parseint_nodes.length; –i >= 0;) {

var node = parseint_nodes[i];

var start_pos = node.start.pos;

var end_pos = node.end.endpos;

node.args.push(new U2.AST_Number({

value: 10

}));

var replacement = node.print_to_string({ beautify: true });

code = splice_string(code, start_pos, end_pos, replacement);

}

return code;

}

function splice_string(str, begin, end, replacement) {

return str.substr(0, begin) + replacement + str.substr(end);

}

// test it

function test() {

if (foo) {

parseInt(‘12342’);

}

parseInt(‘0012’, 3);

}

console.log(replace_parseint(test.toString()));

/*

function test() {

if (foo) {

parseInt(“12342”, 10);

}

parseInt(‘0012’, 3);

}

*/

在這裡，使用了 walker 找到 parseInt 呼叫的地方，然後檢查是否有第二個引數，沒有的話，記錄下來，之後根據每個記錄，用新的包含第二個引數的內容替換掉原內容，完成程式碼的重構。

也許有人會問，這種簡單的情況，用正則匹配也可以方便的替換，幹嘛要用抽象語法樹呢？

答案就是，抽象語法樹是透過分析語法實現的，有一些正則無法（或者很難）做到的優勢，比如，parseInt() 整個是一個字串，或者在註釋中，此種情況會被正則誤判：

var foo = ‘parseInt(“12345”)’;

// parseInt(“12345”);

抽象語法樹在美團中的應用

在美團前端團隊，我們使用 YUI 作為前端底層框架，之前面臨的一個實際問題是，模組之間的依賴關係容易出現疏漏。比如：

YUI.add(‘mod1’, function(Y) {

Y.one(‘#button1’).simulate(‘click’);

Y.Array.each(array, fn);

Y.mod1 = function() {

/**/

};

}, ”, {

requires: [

‘node’,

‘array-extras’

]

});

YUI.add(‘mod2’, function(Y) {

Y.mod1();

// Y.io(uri, config);

}, ”, {

requires: [

‘mod1’,

‘io’

]

});

以上程式碼定義了兩個模組，其中 mod1 模擬點選了一下 id 為 button1 的元素，執行了 Y.Array.each，然後定義了方法 Y.mod1，最後宣告了依賴 node 和 array-extras；mod2 執行了 mod1 中定義的方法，而 Y.io 被註釋了，最後宣告了依賴 mod1 和 io。

此處 mod1 出現了兩個常見錯誤，一個是 simulate 是 Y.Node.prototype 上的方法，容易忘掉宣告依賴 node-event-simulate3，另一個是 Y.Array 上只有部分方法需要依賴 array-extras，故此處多宣告了依賴 array-extras4；mod2 中新增註釋後，容易忘記刪除原來寫的依賴 io。

故正確的依賴關係應該如下：

YUI.add(‘mod1’, function(Y) {

Y.one(‘#button1’).simulate(‘click’);

Y.Array.each(array, fn);

Y.mod1 = function() {

/**/

};

}, ”, {

requires: [

‘node’,

‘node-event-simulate’

]

});

YUI.add(‘mod2’, function(Y) {

Y.mod1();

// Y.io(uri, config);

}, ”, {

requires: [

‘mod1’

]

});

為了使模組依賴關係的檢測自動化，我們建立了模組依賴關係檢測工具，它利用抽象語法樹，分析出定義了哪些介面，使用了哪些介面，然後查詢這些介面應該依賴哪些模組，進而找到模組依賴關係的錯誤，大致的過程如下：

1. 找到程式碼中模組定義（YUI.add）的部分

2. 分析每個模組內函式定義，變數定義，賦值陳述句等，找出符合要求（以 Y 開頭）的輸出介面（如 mod1 中的 Y.mod1）

3. 生成「介面 – 模組」對應關係

4. 分析每個模組內函式呼叫，變數使用等，找出符合要求的輸入介面（如 mod2 中的 Y.one，Y.Array.each，Y.mod1）

5. 透過「介面 – 模組」對應關係，找到此模組應該依賴哪些其他模組

6. 分析 requires 中是否有錯誤

使用此工具，保證每次提交程式碼時，依賴關係都是正確無誤的，它幫助我們實現了模組依賴關係檢測的自動化。

總結

抽象語法樹在計算機領域中應用廣泛，以上僅討論了抽象語法樹在 JavaScript 中的一些應用，期待更多的用法等著大家去嘗試和探索。

Reference

1. Wikipedia AST

2. UglifyJS

3. node-event-simulate

4. Y.Array.each

來自：美團技術部落格 – xcatliu

連結：http://tech.meituan.com/abstract-syntax-tree.html