什么是抽象語(yǔ)法樹
抽象語(yǔ)法樹（abstract syntax tree，AST，或者簡(jiǎn)稱語(yǔ)法樹）是源代碼的抽象語(yǔ)法結(jié)構(gòu)的樹狀表現(xiàn)形式，它以樹狀的形式表現(xiàn)編程語(yǔ)言的語(yǔ)法結(jié)構(gòu)，樹上的每個(gè)節(jié)點(diǎn)都表示源代碼中的一種結(jié)構(gòu)。
之所以說是抽象的，是因?yàn)檫@里的語(yǔ)法并不會(huì)表示出真實(shí)語(yǔ)法中出現(xiàn)的每個(gè)細(xì)節(jié)，比如嵌套括號(hào)被隱含在樹結(jié)構(gòu)中，并不會(huì)以節(jié)點(diǎn)的形式呈現(xiàn)出來(lái)。而類似于if...else這樣的條件語(yǔ)句，可以使用兩個(gè)分支的節(jié)點(diǎn)來(lái)表示。
比如下面這段代碼：
while (b !== 0) {
if (a > b) {
a = a - b
} else {
b = b - a
}
}
return a;
它的對(duì)應(yīng)的抽象語(yǔ)法樹如下：
可以通過astexplorer這個(gè)網(wǎng)站，將我們輸入的代碼轉(zhuǎn)換為AST展示出來(lái)，可以展示為書結(jié)構(gòu)，也可以直接以JSON格式展示，比如在左側(cè)輸入let a = 123;，對(duì)應(yīng)的語(yǔ)法樹：
也可以直接輸入JSON：
{
"type": "Program",
"start": 0,
"end": 12,
"body": [
{
"type": "VariableDeclaration",
"start": 0,
"end": 12,
"declarations": [
{
"type": "VariableDeclarator",
"start": 4,
"end": 11,
"id": {
"type": "Identifier",
"start": 4,
"end": 5,
"name": "a"
},
"init": {
"type": "Literal",
"start": 8,
"end": 11,
"value": 123,
"raw": "123"
}
}
],
"kind": "let"
}
],
"sourceType": "module"
}
語(yǔ)法樹中每個(gè)元素可以成為一個(gè)節(jié)點(diǎn)（node），類型包括：
(parameter) node:
Identifier | SimpleLiteral | RegExpLiteral | Program | FunctionDeclaration | FunctionExpression |
ArrowFunctionExpression | SwitchCase | CatchClause | VariableDeclarator | ExpressionStatement |
BlockStatement | EmptyStatement | DebuggerStatement | WithStatement | ReturnStatement |
LabeledStatement | BreakStatement | ContinueStatement | IfStatement | SwitchStatement | ThrowStatement |
TryStatement | WhileStatement | DoWhileStatement | ForStatement | ForInStatement | ForOfStatement |
VariableDeclaration | ClassDeclaration | ThisExpression | ArrayExpression | ObjectExpression |
YieldExpression | UnaryExpression | UpdateExpression | BinaryExpression | AssignmentExpression |
LogicalExpression | MemberExpression | ConditionalExpression | SimpleCallExpression | NewExpression |
SequenceExpression | TemplateLiteral | TaggedTemplateExpression | ClassExpression | MetaProperty |
AwaitExpression | Property | AssignmentProperty | Super | TemplateElement | SpreadElement |
ObjectPattern | ArrayPattern | RestElement | AssignmentPattern | ClassBody | MethodDefinition |
ImportDeclaration | ExportNamedDeclaration | ExportDefaultDeclaration | ExportAllDeclaration |
ImportSpecifier | ImportDefaultSpecifier | ImportNamespaceSpecifier | ExportSpecifier
使用場(chǎng)景
平時(shí)我們好像從來(lái)沒有接觸過AST，但是實(shí)際上它的適用場(chǎng)景一直相伴左右，比如：
- JS反編譯，語(yǔ)法解析
- Babel編譯ES6語(yǔ)法
- 代碼高亮
- 關(guān)鍵字匹配
- 作用域判斷
- 代碼壓縮
AST分析
使用剛才提到的astexplorer這個(gè)網(wǎng)站，解析1 + 2 * 3，得到的AST語(yǔ)法樹
從語(yǔ)法樹我們開出來(lái)，body里面的exporession（表達(dá)式）是BinaryExpress（二院表達(dá)式），start和end標(biāo)識(shí)了我們這個(gè)表達(dá)式字符的起止位置，operator是+，然后left屬性的值是一個(gè)Literal字面量，value是2，right屬性的值又是另外一個(gè)BinaryExpress，left的值是2，operator是*，right右側(cè)值是3
這樣，通過一個(gè)樹狀結(jié)構(gòu)，將我們輸入的表達(dá)式明明白白展示出來(lái)了。
將表達(dá)式添加一個(gè)括號(hào)，變成(1 + 2) * 3，得到的新的語(yǔ)法樹：
可以看出來(lái)，left值變?yōu)榱艘粋€(gè)BinaryExpress，operator是*，right值是3。
比較兩個(gè)表達(dá)式的語(yǔ)法樹，可以發(fā)現(xiàn)：
- 在確定類型為
ExpressionSatatement后，會(huì)按照代碼執(zhí)行的先后順序，將表達(dá)式BinaryExpression分解為left、operator、right三部分 - 每部分都標(biāo)明了類型、起止位置、值等信息
- 標(biāo)明了操作符類型
再來(lái)看一下常用的箭頭函數(shù)：
const fn = (a, b) => {
return a + b
};
AST的JSON結(jié)果：
{
"type": "Program",
"start": 0,
"end": 40,
"body": [
{
"type": "VariableDeclaration",
"start": 0,
"end": 40,
"declarations": [
{
"type": "VariableDeclarator",
"start": 6,
"end": 39,
"id": {
"type": "Identifier",
"start": 6,
"end": 8,
"name": "fn"
},
"init": {
"type": "ArrowFunctionExpression",
"start": 11,
"end": 39,
"id": null,
"expression": false,
"generator": false,
"params": [
{
"type": "Identifier",
"start": 12,
"end": 13,
"name": "a"
},
{
"type": "Identifier",
"start": 15,
"end": 16,
"name": "b"
}
],
"body": {
"type": "BlockStatement",
"start": 21,
"end": 39,
"body": [
{
"type": "ReturnStatement",
"start": 25,
"end": 37,
"argument": {
"type": "BinaryExpression",
"start": 32,
"end": 37,
"left": {
"type": "Identifier",
"start": 32,
"end": 33,
"name": "a"
},
"operator": "+",
"right": {
"type": "Identifier",
"start": 36,
"end": 37,
"name": "b"
}
}
}
]
}
}
}
],
"kind": "const"
}
],
"sourceType": "module"
}
耐下性子，仔細(xì)讀一下語(yǔ)法樹，其實(shí)也不難理解，首先body的type變?yōu)榱?code>VariableDeclaration，declarations是一個(gè)數(shù)組，首先聲明了fn這個(gè)變量，然后在init里面是一個(gè)type為ArrowFunctionExpression的節(jié)點(diǎn)，里面有params、body、ReturnStatement等各種用來(lái)標(biāo)識(shí)箭頭函數(shù)的屬性值，
實(shí)現(xiàn)
從上面可以看出來(lái)，抽象語(yǔ)法樹其實(shí)就是將一類標(biāo)簽轉(zhuǎn)化成通用標(biāo)識(shí)符，從而歸納出的一個(gè)類似于樹形結(jié)構(gòu)的語(yǔ)法樹。
那么這個(gè)過程是如何實(shí)現(xiàn)的呢？
簡(jiǎn)單學(xué)習(xí)了一下，首先需要幾個(gè)工具包用來(lái)解析JS語(yǔ)法、遍歷樹結(jié)構(gòu)以及生成新的樹結(jié)構(gòu)：
const esprima = require('esprima'); // 解析js的語(yǔ)法的包
const estraverse = require('estraverse'); // 遍歷樹的包
const escodegen = require('escodegen'); // 生成新的樹的包
let code = `function getAST(){}`;
//解析js的語(yǔ)法
let tree = esprima.parseScript(code);
//遍歷樹
estraverse.traverse(tree, {
enter(node) {
console.log('enter: ' + node.type);
},
leave(node) {
console.log('leave: ' + node.type);
}
});
//生成新的樹
let r = escodegen.generate(tree);
console.log(r);
通過遍歷、修改抽象語(yǔ)法樹，我們可以去改變?nèi)魏屋敵鼋Y(jié)果，也就是說，在編譯的過程中，借助抽象語(yǔ)法樹，我們可以去改變?cè)瓉?lái)的輸入，得到想要的結(jié)果。
這也就是Babel轉(zhuǎn)義JavaScript代碼的原理。
關(guān)于Babel
Babel使用一個(gè)基于ESTree并修改過的AST，它的內(nèi)核說明文檔可以在這里找到。
Babel的三個(gè)主要處理步驟分別是： 解析（parse），轉(zhuǎn)換（transform），生成（generate）。
（1）解析
接受代碼并輸出AST，這個(gè)步驟又分為兩個(gè)階段：詞法分析（Lexical Aanalysis）和語(yǔ)法分析（Syntactic Analysis）
詞法分析階段把字符串形式的代碼轉(zhuǎn)換為令牌流，可以將令牌看做一個(gè)扁平的語(yǔ)法片段數(shù)組
n * n;
↓
[
{ type: { ... }, value: "n", start: 0, end: 1, loc: { ... } },
{ type: { ... }, value: "*", start: 2, end: 3, loc: { ... } },
{ type: { ... }, value: "n", start: 4, end: 5, loc: { ... } },
...
]
其中每一個(gè)type都有一組數(shù)形來(lái)描述該令牌，和AST節(jié)點(diǎn)一樣也有start、end等屬性：
{
type: {
label: 'name',
keyword: undefined,
beforeExpr: false,
startsExpr: true,
rightAssociative: false,
isLoop: false,
isAssign: false,
prefix: false,
postfix: false,
binop: null,
updateContext: null
},
...
}
語(yǔ)法分析階段會(huì)吧一個(gè)令牌轉(zhuǎn)換成AST的形式，這個(gè)階段會(huì)使用令牌中的信息把他們轉(zhuǎn)換成一個(gè)AST的表述結(jié)構(gòu)，便于后續(xù)操作
（2）轉(zhuǎn)換
接受AST并對(duì)其進(jìn)行遍歷，此過程中對(duì)節(jié)點(diǎn)進(jìn)行添加、更新和移除等操作。這是Babel最復(fù)雜的過程，也是Babel插件接入工作的部分。
（3）生成
深度優(yōu)先遍歷將經(jīng)過一系列轉(zhuǎn)換后的AST，并將其轉(zhuǎn)換成字符串形式的代碼，同時(shí)還會(huì)創(chuàng)建源碼映射。
單元測(cè)試覆蓋率
JavaScript單元測(cè)試覆蓋率統(tǒng)計(jì)方法的核心思想，是在源代碼響應(yīng)的位置注入設(shè)定的統(tǒng)計(jì)代碼，當(dāng)執(zhí)行測(cè)試代碼的時(shí)候，代碼運(yùn)行到注入的地方，就會(huì)執(zhí)行對(duì)應(yīng)的統(tǒng)計(jì)代碼，生成覆蓋率統(tǒng)計(jì)報(bào)告。大概步驟如下：
（1）對(duì)源代碼進(jìn)行語(yǔ)法分析、解析，然后生成抽象語(yǔ)法樹
（2）在語(yǔ)法樹相應(yīng)的位置注入統(tǒng)計(jì)代碼。
在程序執(zhí)行到這個(gè)位置的時(shí)候?qū)ο鄳?yīng)的全局變量賦值，確保執(zhí)行之后能夠根據(jù)全局變量知道代碼的執(zhí)行流程。
（3）通過注入統(tǒng)計(jì)代碼的抽象語(yǔ)法樹，生成對(duì)應(yīng)的JavaScript代碼
（4）將生成好的JavaScript代碼交給執(zhí)行環(huán)境（Node或者瀏覽器）運(yùn)行
（5）執(zhí)行單元測(cè)試，產(chǎn)生的統(tǒng)計(jì)信息，放到全局變量里面。
（6）根據(jù)全局變量中的覆蓋率信息生成特定格式的報(bào)告。
總結(jié)
大致學(xué)習(xí)了一下AST的知識(shí)，并沒有很深入，只是了解到AST是對(duì)源代碼的一種樹狀結(jié)構(gòu)的表示形式，可以用來(lái)在編譯階段對(duì)代碼進(jìn)行處理。Babel之所以能夠?qū)崿F(xiàn)JavaScript的轉(zhuǎn)換，就是利用了AST，經(jīng)歷了解析、轉(zhuǎn)換、生成三個(gè)步驟，其中轉(zhuǎn)換是最復(fù)雜的步驟，各種Babel的插件也是在這個(gè)步驟中發(fā)揮作用。
