歡迎光臨
每天分享高質量文章

抽象語法樹在 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

贊(0)

分享創造快樂