AST-抽象語法樹 · 架構面試題-第一季

## 1.抽象語法樹(Abstract Syntax Tree) `webpack`和`Lint`等很多的工具和庫的核心都是通過`Abstract Syntax Tree`抽象語法樹這個概念來實現對代碼的檢查、分析等操作的 * 通過了解抽象語法樹這個概念，你也可以隨手編寫類似的工具 ## 2.抽象語法樹用途 * 代碼語法的檢查、代碼風格的檢查、代碼的格式化、代碼的高亮、代碼錯誤提示、代碼自動補全等等 * 如JSLint、JSHint對代碼錯誤或風格的檢查，發現一些潛在的錯誤 * IDE的錯誤提示、格式化、高亮、自動補全等等 * 代碼混淆壓縮 * UglifyJS2等 * 優化變更代碼，改變代碼結構使達到想要的結構 * 代碼打包工具webpack、rollup等等 * CommonJS、AMD、CMD、UMD等代碼規范之間的轉化 * CoffeeScript、TypeScript、JSX等轉化為原生Javascript ## 3.抽象語法樹定義這些工具的原理都是通過`JavaScript Parser`把代碼轉化為一顆抽象語法樹（AST），這顆樹定義了代碼的結構，通過操縱這顆樹，我們可以精準的定位到聲明語句、賦值語句、運算語句等等，實現對代碼的分析、優化、變更等操作 > 在計算機科學中，抽象語法樹（abstract syntax tree或者縮寫為AST），或者語法樹（syntax tree），是源代碼的抽象語法結構的樹狀表現形式，這里特指編程語言的源代碼。 > Javascript的語法是為了給開發者更好的編程而設計的，但是不適合程序的理解。所以需要轉化為AST來使之更適合程序分析，瀏覽器編譯器一般會把源碼轉化為AST來進行進一步的分析等其他操作。 ![](https://img.kancloud.cn/12/26/12261a06023b7c01d5eecd92e09e72c2_678x363.png) ## 4.JavaScript Parser * JavaScript Parser，把js源碼轉化為抽象語法樹的解析器。 * 瀏覽器會把js源碼通過解析器轉為抽象語法樹，再進一步轉化為字節碼或直接生成機器碼。 * 一般來說每個js引擎都會有自己的抽象語法樹格式，Chrome的v8引擎，firefox的SpiderMonkey引擎等等，MDN提供了詳細SpiderMonkey AST format的詳細說明，算是業界的標準。 ### 4.1 常用的JavaScript Parser * esprima * traceur * acorn * shift ### 4.2 esprima * 通過[esprima](https://www.npmjs.com/package/esprima)把源碼轉化為AST * 通過[estraverse](https://www.npmjs.com/package/estraverse)遍歷并更新AST * 通過[escodegen](https://www.npmjs.com/package/escodegen)將AST重新生成源碼 * [astexplorer](https://astexplorer.net/)AST的可視化工具 ~~~ mkdir zhufengast cd zhufengast cnpm i esprima estraverse escodegen- S ~~~ ~~~ let esprima = require('esprima'); var estraverse = require('estraverse'); var escodegen = require("escodegen"); let code = 'function ast(){}'; let ast=esprima.parse(code); let indent=0; function pad() { return ' '.repeat(indent); } estraverse.traverse(ast,{ enter(node) { console.log(pad()+node.type); if(node.type == 'FunctionDeclaration'){ node.id.name = 'ast_rename'; } indent+=2; }, leave(node) { indent-=2; console.log(pad()+node.type); } }); let generated = escodegen.generate(ast); console.log(generated); ~~~ ~~~ Program FunctionDeclaration Identifier Identifier BlockStatement BlockStatement FunctionDeclaration Program ~~~ ~~~ let esprima = require('esprima');//源代碼轉成AST語法樹 let estraverse = require('estraverse');//遍歷語法樹 let escodegen = require('escodegen');//把AST語法樹重新生成代碼的工具 let sourceCode = 'function ast(){}'; let ast = esprima.parse(sourceCode);//源代碼轉成AST語法樹 let indent =0; function pad(){ return " ".repeat(indent); } estraverse.traverse(ast,{ enter(node){ console.log(pad()+node.type); indent+=2; }, leave(node){ indent-=2; console.log(pad()+node.type); } }); ~~~ ## 5.babel插件 * 訪問者模式Visitor 對于某個對象或者一組對象，不同的訪問者，產生的結果不同，執行操作也不同 * [@babel/core](https://www.npmjs.com/package/@babel/core)Babel 的編譯器，核心 API 都在這里面，比如常見的 transform、parse * [babylon](http://www.zhufengpeixun.cn/2020/html/26.webpack-5-AST.html)Babel 的解析器 * [babel-types](https://github.com/babel/babel/tree/master/packages/babel-types)用于 AST 節點的 Lodash 式工具庫, 它包含了構造、驗證以及變換 AST 節點的方法，對編寫處理 AST 邏輯非常有用 * [babel-traverse](https://www.npmjs.com/package/babel-traverse)用于對 AST 的遍歷，維護了整棵樹的狀態，并且負責替換、移除和添加節點 * [babel-types-api](https://babeljs.io/docs/en/next/babel-types.html) * [Babel 插件手冊](https://github.com/brigand/babel-plugin-handbook/blob/master/translations/zh-Hans/README.md#asts) * [babeljs.io](https://babeljs.io/en/repl.html)babel可視化編譯器 ### 5.1 轉換箭頭函數 * [babel-plugin-transform-es2015-arrow-functions](https://www.npmjs.com/package/babel-plugin-transform-es2015-arrow-functions) 轉換前 ~~~ const sum = (a,b)=>a+b ~~~ ![](https://img.kancloud.cn/81/05/810564ec5619fd626320c3ff3079e16d_631x804.png) 轉換后 ~~~ var sum = function sum(a, b) { return a + b; }; ~~~ ![](https://img.kancloud.cn/46/34/463444dd3380b2da563e3b9fc9228487_625x808.png) ~~~ npm i @babel/core babel-types -D ~~~ 實現 ~~~ let babel = require('@babel/core'); let t = require('babel-types'); const code = `const sum = (a,b)=>a+b`; let transformArrowFunctions = { visitor: { ArrowFunctionExpression: (path) => { let node = path.node; let id = path.parent.id; let params = node.params; let body=t.blockStatement([ t.returnStatement(node.body) ]); let functionExpression = t.functionExpression(id,params,body,false,false); path.replaceWith(functionExpression); } } } const result = babel.transform(code, { plugins: [transformArrowFunctions] }); console.log(result.code); ~~~ ### 5.2. 預計算babel插件 * path.parentPath 父路徑轉換前 ~~~ const result = 1 + 2; ~~~ ![](https://img.kancloud.cn/c0/67/c06784d7c7110e19d8559d5cc613c5fc_566x572.png) 轉換后 ~~~ const result = 3; ~~~ ![](https://img.kancloud.cn/56/da/56da831b77aaafd4643cc3ee61772314_566x463.png) ``` let babel = require('@babel/core'); let t=require('babel-types'); let preCalculator={ visitor: { BinaryExpression(path) { let node=path.node; let left=node.left; let operator=node.operator; let right=node.right; if (!isNaN(left.value) && !isNaN(right.value)) { let result=eval(left.value+operator+right.value); path.replaceWith(t.numericLiteral(result)); if (path.parent&& path.parent.type == 'BinaryExpression') { preCalculator.visitor.BinaryExpression.call(null,path.parentPath); } } } } } const result = babel.transform('const sum = 1+2+3',{ plugins:\[ preCalculator \] }); console.log(result.code); ``` ## 9\. AST ### 9.1 解析過程 AST整個解析過程分為兩個步驟 * 分詞：將整個代碼字符串分割成語法單元數組 * 語法分析：建立分析語法單元之間的關系 ### 9.2 語法單元 Javascript 代碼中的語法單元主要包括以下這么幾種 * 關鍵字：`const`、`let`、`var`等 * 標識符：可能是一個變量，也可能是 if、else 這些關鍵字，又或者是 true、false 這些常量 * 運算符 * 數字 * 空格 * 注釋 ### 9.3 詞法分析 ~~~ let jsx = `let element=<h1>hello</h1>`; function lexical(code) { const tokens=[]; for (let i=0;i<code.length;i++){ let char=code.charAt(i); if (char == '=') { tokens.push({ type: 'operator', value:char }); } if (char=='<') { const token={ type: 'JSXElement', value:char } tokens.push(token); let isClose = false; for (i++;i<code.length;i++){ char=code.charAt(i); token.value+=char; if (char=='>') { if (isClose) { break; } else { isClose=true; } } } continue; } if (/[a-zA-Z\$\_]/.test(char)) { const token={ type: 'Identifier', value:char } tokens.push(token); for (i++;i<code.length;i++){ char=code.charAt(i); if (/[a-zA-Z\$\_]/.test(char)) { token.value+=char; } else { i--; break; } } continue; } if (/\s/.test(char)) { const token={ type: 'whitespace', value:char } tokens.push(token); for (i++;i<code.length;i++){ char=code.charAt[i]; if (/\s/.test(char)) { token.value+=char; } else { i--; break; } } continue; } } return tokens; } let result=lexical(jsx); console.log(result); ~~~ ~~~ [ { type: 'Identifier', value: 'let' }, { type: 'whitespace', value: ' ' }, { type: 'Identifier', value: 'element' }, { type: 'operator', value: '=' }, { type: 'JSXElement', value: '<h1>hello</h1>' } ] ~~~ ### 9.4 語法分析 * 語義分析則是將得到的詞匯進行一個立體的組合，確定詞語之間的關系 * 簡單來說語法分析是對語句和表達式識別，這是個遞歸過程 ~~~ // babylon7 https://astexplorer.net/ // babylon7 https://astexplorer.net/ function parse(tokens) { const ast={ type: 'Program', body: [], sourceType:'script' } let i=0;//標示當前位置 let currentToken;//當前的符號 while ((currentToken = tokens[i])) { if (currentToken.type == 'Identifier' && (currentToken.value == 'let'||currentToken.value == 'var')) { const VariableDeclaration={ type: 'VariableDeclaration', declarations:[] } i+=2; currentToken=tokens[i]; let VariableDeclarator = { type: 'VariableDeclarator', id: { type: 'Identifier', name:currentToken.value } }; VariableDeclaration.declarations.push(VariableDeclarator); i+=2; currentToken=tokens[i]; if (currentToken.type=='JSXElement') { let value=currentToken.value; let [,type,children]=value.match(/([^<]+?)>([^<]+)<\/\1>/); VariableDeclarator.init={ type: 'JSXElement', openingElement:{ type:'JSXOpeningElement', name:{ type:'JSXIdentifier', name:'h1' } }, closingElement:{ type:'JSXClosingElement', name:{ type:'JSXIdentifier', name:'h1' } }, name: type, children:[ { type:'JSXText', value:'hello' } ] } } else { VariableDeclarator.init={ type: 'Literal', value:currentToken.value } } ast.body.push(VariableDeclaration); } i++; } return ast; } let tokens=[ {type: 'Identifier',value: 'let'}, {type: 'whitespace',value: ' '}, {type: 'Identifier',value: 'element'}, {type: 'operator',value: '='}, {type: 'JSXElement',value: '<h1>hello</h1>'} ]; let result = parse(tokens); console.log(result); console.log(JSON.stringify(result)); ~~~ ~~~ { "type": "Program", "body": [{ "type": "VariableDeclaration", "declarations": [{ "type": "VariableDeclarator", "id": { "type": "Identifier", "name": "element" }, "init": { "type": "JSXElement", "openingElement": { "type": "JSXOpeningElement", "name": { "type": "JSXIdentifier", "name": "h1" } }, "closingElement": { "type": "JSXClosingElement", "name": { "type": "JSXIdentifier", "name": "h1" } }, "name": "h1", "children": [{ "type": "JSXText", "value": "hello" }] } }] }], "sourceType": "script" } ~~~ ``` letutil\=require('util'); functionparse(tokens){ letast\=?{?type:'Program',body:\[\],sourceType:'module'}; leti\=0;//當前的索引 letcurrToken;//當前的token while(currToken\=tokens\[i\]){ //第一次的時候?currToken?=?{?type:?'Keyword',?value:?'let'?} if(currToken.type\=='Keyword'&&currToken.value\=='let'){ letVariableDeclaration\=?{type:'VariableDeclaration',declarations:\[\]}; ast.body.push(VariableDeclaration); i+=2;//i=2 currToken\=tokens\[i\];//{?type:?'Identifier',?value:?'element'?}, letvariableDeclarator\=?{ type:'VariableDeclarator', id:{type:'Identifier',name:currToken.value} ???????????} VariableDeclaration.declarations.push(variableDeclarator); i+=2;//i=4 currToken\=tokens\[i\];//?{?type:?'String',?value:?'hello'?} if(currToken.type\=='String'){ variableDeclarator.init\=?{type:'StringLiteral',value:currToken.value}; ??????????}elseif(currToken.type\=='JSXElement'){ letvalue\=currToken.value; //type=h1?children=hello let?\[,type,children\]?\=value.match(/\]+?)>(\[^/);??//hello variableDeclarator.init\=?{ type:'JSXElement',//類型JSX元素 openingElement:{ type:'OpeningElement', name:{type:'JSXIdentifier',name:type} ?????????????????}, closingElement:{ type:'ClosingElement', name:{type:'JSXIdentifier',name:type} ?????????????????}, children:\[ ?????????????????????{type:'JSXText',value:children} ?????????????????\] ?????????????} ??????????} ???????} i++; ???} returnast; } lettokens\=?\[ ??{?type:?'Keyword',?value:?'let'?}, ??{?type:?'WhiteSpace',?value:?'?'?}, ??{?type:?'Identifier',?value:?'element'?}, ??{?type:?'Equal',?value:?'='?}, ???{type:"JSXElement",value:'hello'} \]; //{?type:?'JSXElement',?value:?'hello'?} letast\=parse(tokens); ast.body\[0\].declarations\[0\].init\=??{ "type":?"ExpressionStatement", "expression":?{ "type":?"CallExpression", "callee":?{ "type":?"MemberExpression", "computed":?false, "object":?{ "type":?"Identifier", "name":?"React", ??????????}, "property":?{ "type":?"Identifier", "name":?"createElement", ??????????} ????????}, "arguments":?\[ ??????????{ "type":?"Literal", "value":?"h1", "raw":?"\\"h1\\"" ??????????}, ??????????{ "type":?"Literal", "value":?null, "raw":?"null" ??????????}, ??????????{ "type":?"Literal", "value":?"hello", "raw":?"\\"hello\\"" ??????????} ????????\] ??????} ????} console.log(JSON.stringify(ast)) ```