AST簡介
在平時的開發中,經常會遇到對JavaScript代碼進行檢查或改動的工具,例如ESLint會檢查代碼中的語法錯誤;Prettier會修改代碼的格式;打包工具會將不同文件中的代碼打包在一起等等。這些工具都對JavaScript代碼本身進行了解析和修改。這些工具是如何實現對代碼本身的解析呢?這就要用到一種叫做AST抽象語法樹的技術。
抽象語法樹(Abstract Syntax Tree, 縮寫為AST),是將代碼抽象成一種樹狀結構,樹上的每個節點表示代碼中的一種語法,包括標識符,字面量,表達式,語句,模塊等等。將代碼形成抽象語法樹AST之后,還可以通過這棵樹還原成代碼。在AST的形成過程中會丟棄注釋和空白符等無意義的內容。
將代碼抽象成AST需要兩個步驟:1.詞法分析,是掃描代碼并將其中的內容標識為token數組。2.語法分析,是將詞法分析的token數組轉化為樹狀的形式,也就形成了抽象語法樹。下面我們分別看一下每個步驟。
?
詞法分析
詞法分析是生成AST的第一個步驟,它將代碼的內容轉換為一個一個的標識token,忽略空白符號,識別標識符的類型,最終形成一個tokens數組。這里使用Esprima,一個ECMAScript解析器來生成tokens。本來想用babel,但是babel沒有拋出獨立生成tokens的方法。
const esprima = require("esprima");
const code = "const a = 2 + 1;";
const tokens = esprima.tokenize(code);
console.log(tokens);/* 生成的tokens
[{ type: 'Keyword', value: 'const' },{ type: 'Identifier', value: 'a' },{ type: 'Punctuator', value: '=' },{ type: 'Numeric', value: '2' },{ type: 'Punctuator', value: '+' },{ type: 'Numeric', value: '1' },{ type: 'Punctuator', value: ';' }
]
*/
在Node.js中執行這段代碼,命令行中就打印出了生成的tokens,放在上面的注釋中了。可以看到,代碼中除了空白之外,全都被生成token了,value為實際的內容,type為這個內容的類型,其中Keyword為JavaScript的關鍵字,Numeric為數字,Punctuator是符號,Identifier指的是標識符,例如變量名等。
我們再看一個代碼中包含多行與函數的場景,與上面的代碼相比,只有code不一樣,因此其它代碼就省略了:
// 準備解析的代碼
const fun = function (a) {const b = 2;return a + b;
}/* 生成的tokens
[{ type: 'Keyword', value: 'const' },{ type: 'Identifier', value: 'fun' },{ type: 'Punctuator', value: '=' },{ type: 'Keyword', value: 'function' },{ type: 'Punctuator', value: '(' },{ type: 'Identifier', value: 'a' },{ type: 'Punctuator', value: ')' },{ type: 'Punctuator', value: '{' },{ type: 'Keyword', value: 'const' },{ type: 'Identifier', value: 'b' },{ type: 'Punctuator', value: '=' },{ type: 'Numeric', value: '2' },{ type: 'Punctuator', value: ';' },{ type: 'Keyword', value: 'return' },{ type: 'Identifier', value: 'a' },{ type: 'Punctuator', value: '+' },{ type: 'Identifier', value: 'b' },{ type: 'Punctuator', value: ';' },{ type: 'Punctuator', value: '}' }
]
*/
這個例子復雜很多,通過結果可以看到函數雖然作為一個整體,但是被拆分成了多個token。而且這個例子中雖然有多行,但生成的tokens是沒有換行標志的。事實上對于Esprima,可以配置保留注釋和以及展示每個token在源碼中的位置(從而可以判斷是否有換行)。更多配置可以看Esprima文檔。
const esprima = require("esprima");
// 準備解析的代碼
const code = `// 打印輸出
console.log(value);`;
const tokens = esprima.tokenize(code, { loc: true, comment: true });
console.log(JSON.stringify(tokens));/* 生成的tokens
[{type: "LineComment",value: " 打印輸出",loc: { start: { line: 1, column: 0 }, end: { line: 1, column: 7 } },},{type: "Identifier",value: "console",loc: { start: { line: 2, column: 0 }, end: { line: 2, column: 7 } },},{type: "Punctuator",value: ".",loc: { start: { line: 2, column: 7 }, end: { line: 2, column: 8 } },},{type: "Identifier",value: "log",loc: { start: { line: 2, column: 8 }, end: { line: 2, column: 11 } },},{type: "Punctuator",value: "(",loc: { start: { line: 2, column: 11 }, end: { line: 2, column: 12 } },},{type: "Identifier",value: "value",loc: { start: { line: 2, column: 12 }, end: { line: 2, column: 17 } },},{type: "Punctuator",value: ")",loc: { start: { line: 2, column: 17 }, end: { line: 2, column: 18 } },},{type: "Punctuator",value: ";",loc: { start: { line: 2, column: 18 }, end: { line: 2, column: 19 } },},
];
*/
可以看到結果中打印了每一個token的起始位置和最終位置,注釋也保留了,使用LineComment類型。另外注意看console.log這個對象方法,在數組中被分解為了標識符+符號+標識符三個。另外這個被解析的代碼我故意放了一個錯誤(value未定義就被使用值),但這里僅僅是識別token,代碼是否可以被執行與生成tokens無關。
語法分析
詞法分析結束之后,對生成tokens進一步分析,最后形成一個語法樹,就是抽象語法樹AST了。這里我們還是使用Esprima生成。(本想嘗試利用詞法分析結果來生成AST,但暫時沒有找到相關的API,因此只能從代碼直接生成AST了)。
const esprima = require("esprima");
// 準備生成的代碼
const code = "const a = 2 + 1;";
const ast = esprima.parse(code);
console.log(JSON.stringify(ast));/* 生成的AST
{type: "Program",body: [{type: "VariableDeclaration",declarations: [{type: "VariableDeclarator",id: { type: "Identifier", name: "a" },init: {type: "BinaryExpression",operator: "+",left: { type: "Literal", value: 2, raw: "2" },right: { type: "Literal", value: 1, raw: "1" },},},],kind: "const",},],sourceType: "script",
}
*/
可以看到代碼被解析成了一個JSON結構,這個JSON結構即描述了代碼本身。我們從外向內試著分析一下這個結構:
- Program 表示一個程序
- VariableDeclaration 表示變量聲明,kind表示了是const
- VariableDeclarator 表示變量聲明的標識符,是名稱為a的Identifier標識符
- BinaryExpression 二元運算符表達式,其中操作符是+號
- Literal 加號的左右都是字面量,值為數字1和2
因此,一段代碼就被分析成了這樣一顆AST樹。這里我們再看一個例子:
// 準備解析的代碼
const fun = function (a) {const b = 2;return a + b;
}/* 生成的AST
{type: "Program",body: [{type: "VariableDeclaration",declarations: [{type: "VariableDeclarator",id: { type: "Identifier", name: "fun" },init: {type: "FunctionExpression",id: null,params: [{ type: "Identifier", name: "a" }],body: {type: "BlockStatement",body: [{type: "VariableDeclaration",declarations: [{type: "VariableDeclarator",id: { type: "Identifier", name: "b" },init: { type: "Literal", value: 2, raw: "2" },},],kind: "const",},{type: "ReturnStatement",argument: {type: "BinaryExpression",operator: "+",left: { type: "Identifier", name: "a" },right: { type: "Identifier", name: "b" },},},],},generator: false,expression: false,async: false,},},],kind: "const",},],sourceType: "script",
}
*/
這個例子增加了FunctionExpression,表示函數;BlockStatement表示塊級語句;ReturnStatement表示return語句等。與前面詞法分析將函數拆分成多個token不一樣,這次函數是一個整體,且內部包含了params,BlockStatement和ReturnStatement等,確實是做到了對語法本身的分析。
與tokenize方法一樣,語法分析的parse方法也有很多選項,例如解析注釋,列出在代碼中的位置等等,這里就不描述了。除了通過代碼之外,還有AST explorer網站可以將代碼在線轉換為AST,并且可以在線標黃AST結點對應的代碼。
抽象語法樹規范ESTree
前面生成的AST樹的結構中,我們看到了很多AST結點,這些節點有type表示結點類型,以及其他屬性。Javascript有這么多語法規則,而且在不停的更新,如何知道這些語法規則的類型和屬性定義呢?
ESTree就提供了Javascript語法到AST結點的屬性定義的規則。ESTree并不是AST轉換工具,它是一份文檔,提供了ECMAScript標準中的語法到AST結點定義的規則。生成AST的工具,需要遵守這個規則,這樣不同工具生成的抽象語法樹就是通用的,我們也只需要寫一套代碼來解析即可。ESTree維護在GitHub,通過查看ESTree的目錄結構和規則示例,可以看到不僅包含了每年的最新語法,甚至還包含了一些還在stage中的語法。
// 目錄結構(部分)
├── experimental/
├── extensions/
├── stage3/
├── deprecated.md
├── es2015.md
├── es2016.md
├── es2017.md
├── es2018.md
├── es2019.md
├── es2020.md
├── es2021.md
├── es2022.md
├── es2025.md
├── es2026.md
├── es5.md
└── ...// 規則實例
interface Function <: Node {id: Identifier | null;params: [ Pattern ];body: FunctionBody;
}
A function declaration or expression.
ESTree最早是由Mozilla工程師在開發Javascript引擎SpiderMonkey時定義的,后來被大家接受并形成了事實的標準,現在由Babel,ESlint和Acorn維護。ESTree并不是一個強制規則,因此也有部分AST轉換工具沒有使用這個標準。下面的工具介紹中會提到這一點。
AST工具列表
首先列舉一下目前社區中流行的AST生成工具,以及它們是否支持ESTree和輸出Tokens。
工具名稱 | 支持ESTree | 支持輸出Tokens | 簡介 |
---|---|---|---|
Esprima | 是 | 是 | 很早的AST工具,支持最新語法的進度較慢 |
Acorn | 是 | 是 | 流行的AST工具,支持插件 |
Espree | 是 | 是 | ESLint(JS語法檢查工具)的AST工具,最初基于Esprima開發,后來基于Acorn |
@babel/parser | 是 | 否 | Babel(JS編譯器)的AST工具,fork于Acorn |
UglifyJS | 否 | 否 | UglifyJS(JS壓縮工具)中提供的AST工具,獨立格式不支持ESTree |
其中Esprima是非常早的AST工具,也很好用,但由于ES6開始,ECMAScript標準中語法的數量增多速度變快,導致Esprima無法即使更新,因此出現了更多AST生成工具。其中Acorn是流行的工具之一,具有插件機制,現在很多JavaScript工具都采用了Acorn或者在它的基礎上繼續開發。下面我們簡單列舉下這些工具的代碼使用方式示例:
/*code 被解析的代碼tokens 詞法分析結果ast 生成的抽象語法樹
*/
const code = "const a = 2 + 1;";// --- Esprima ---
const esprima = require("esprima");
const tokens = esprima.tokenize(code);
const ast = esprima.parse(code);// --- Acorn ---
const acorn = require("acorn");
// it是個js遍歷器
const it = acorn.tokenizer(code);
const tokens = [...it];
const ast = acorn.parse(code, { ecmaVersion: "latest" });// --- Espree ---
const espree = require("espree");
const tokens = espree.tokenize(code);
const ast = espree.parse(code, { ecmaVersion: "latest" });// --- @babel/parser ---
const babelParser = require("@babel/parser");
const ast = babelParser.parse(code);// --- UglifyJS ---
const UglifyJS = require("uglify-js");
const ast = UglifyJS.minify(code, {parse: {}, compress: false, mangle: false,output: { ast: true, code: false }
});
通過代碼示例可以看到,雖然API細節個別有區別,但使用方式是基本一致的。還有一些社區工具雖然有解析AST的能力,但卻沒有拋出API,比如Terser;還有一些工具是直接集成了上面的工具作為解析AST的方法,例如recast。這些工具我們就不在表格中列出了。
AST的應用Demo
AST在Javascript的工具中應用非常廣泛:代碼編譯構建,混淆壓縮,語法高亮,錯誤檢查,格式修改,ES版本兼容等等,應用實在是太多了。可以說在前端工程化領域中絕大部分工具都需要AST的能力。但其中大部分工具都不僅只是生成語法樹,它們還會對AST進行修改,最后再生成代碼。我們再用一個流程圖來表示:
?
從圖中可以看到,大部分工具利用AST的方式是,先把代碼生成AST,然后再對AST進行遍歷和修改,生成一顆新的AST。最后將AST生成代碼作為輸出結果。這里我們嘗試一個最簡單的例子,其中遍歷AST使用的是Estraverse,從AST生成代碼使用的是Escodegen。
const esprima = require("esprima");
const estraverse = require("estraverse");
const escodegen = require("escodegen");const code = `
let fun = function (letter) {let b = 2;console.log(" let letter");return b + letter;
};
`;
// 生成AST
const ast = esprima.parse(code);
// 遍歷
estraverse.traverse(ast, {enter: (node) => {if (node.type === "VariableDeclaration" && node.kind === 'let') {// 修改ASTnode.kind = "const";}},
});
// 生成新代碼
const newCode = escodegen.generate(ast);
console.log(newCode);/* 生成結果
const fun = function (letter) {const b = 2;console.log(' let letter');return b + letter;
};
*/
上面代碼的作用是,將輸入代碼中的let變量聲明修改為const。這僅僅是個最簡單的Demo,沒有考慮變量存在修改不能使用const的場景。有些人可能對于AST的作用有疑惑,認為對代碼為用字符串替換或者正則的方式也能實現。但當代碼內容復雜時,例如變量名和字符串常量中都可能包含let,這時使用常規的正則方式難度是比較高的。
CST具體語法樹
前面我們介紹的都是AST抽象語法樹,它是忽略注釋,分號等無意義內容之后的組成的一顆樹。那么有沒有一種語法樹可以保留這些內容呢?有的,它就是具體語法樹CST(Concrete Syntax Tree)。具體語法樹是代碼的完整表示,在代碼高亮,代碼格式化等方面非常有用。這里我們使用Tree-sitter工具,嘗試對代碼生成具體語法樹。
const Parser = require('tree-sitter');
const JavaScript = require('tree-sitter-javascript');const parser = new Parser();
parser.setLanguage(JavaScript);
const sourceCode = 'let x = 2;';
const tree = parser.parse(sourceCode);console.log(tree.rootNode.toString());
console.log(tree.rootNode.children[0].toString());
console.log(tree.rootNode.children[0].children);
console.log(tree.rootNode.children[0].children[1].toString());
console.log(tree.rootNode.children[0].children[1]);/* 輸出
(program (lexical_declaration (variable_declarator name: (identifier) value: (number))))
(lexical_declaration (variable_declarator name: (identifier) value: (number)))
[SyntaxNode {type: let,startPosition: {row: 0, column: 0},endPosition: {row: 0, column: 3},childCount: 0,},VariableDeclaratorNode {type: variable_declarator,startPosition: {row: 0, column: 4},endPosition: {row: 0, column: 9},childCount: 3,},SyntaxNode {type: ;,startPosition: {row: 0, column: 9},endPosition: {row: 0, column: 10},childCount: 0,}
]
(variable_declarator name: (identifier) value: (number))
VariableDeclaratorNode {type: variable_declarator,startPosition: {row: 0, column: 4},endPosition: {row: 0, column: 9},childCount: 3,
}
*/
Tree-sitter本身是用C語言編寫的,但提供了JavaScript語言的npm包供使用。同時它也支持解析多種語言,不同的語言引入不同的解析器即可。Tree-sitter并不使用ESTree作為解析格式,而是使用S表達式,如我們輸出的第一行tree.rootNode.toString()
。S表達式(S-Expression)類似于前綴表達式,在Lisp語言中使用較多。這里舉一個簡單的例子:
- 原表達式: 1 * (2 + 3)
- S表達式: (* 1 (+ 2 3))
從例子中可以簡單理解為,在中間的操作符需要提到最前面。然后我們再來看輸出的第一行,其中每個節點的含義如下:
- program 程序根節點
- lexical_declaration 聲明語句
- variable_declarator 聲明器
- name(identifier) 變量名
- value:(number) 數字值
然后將它們組合起來:
- (program (lexical_declaration (variable_declarator name: (identifier) value: (number))))
- (程序根節點 (聲明語句 (聲明器 變量名 數字值)))
詳細含義和解析方法可以查看Tree-sitter文檔。不過細心看雖然用了S表達式的形式,但這依然是一顆AST而不是CST,因為樹中并沒有分號等無意義符號。我們仔細看輸出的子節點中,發現了分號的存在,這一類無意義結點被稱作匿名節點,在S表達式中并不會展示,但是遍歷子節點時,是可以遍歷到的。另外Tree-sitter也能解析存在錯誤的語法:
const sourceCode = 'let x = 2qwe;';
/*
(program (lexical_declaration (variable_declarator name: (identifier) (ERROR (number)) value: (identifier))))
*/
在代碼有錯誤的情況下,依然生成了S表達式,且表達式中可以看到ERROR結點。這種能力對語法錯誤提示等功能有幫助。
總結
這篇文章僅僅是對語法樹(AST CST)做了一個簡單的介紹,并沒有對原理和細節做深入的了解。事實上,解析與生成代碼是計算機學科中一個專門的領域,也是一門大學的課程,叫做編譯原理。像是龍書《編譯原理》中就有講到詞法分析,語法分析,語法樹生成等等,其中的復雜程度遠遠超過了一篇博客的內容。
對于語法樹的生成工具來說,AST和CST的界限也并不是完全區分的(一般默認是AST模式),很多工具就可以在語法樹中保留注釋等無意義內容,有些也可以解析包含錯誤的代碼。具體用AST還是CST還是自定義的樹,要看使用場景。
前端除了JavaScript之外,還有JSX代碼,TS代碼,CSS代碼等等,都有工具可以做到解析語法樹。
有一個前端非常常用的編譯器,叫做babel,包含了很多編譯相關的工具。關于babel相關的內容,會在后面單獨文章介紹。同時也將會嘗試關于AST更復雜一點的應用。
參考
- AST 抽象語法樹知識點
https://mp.weixin.qq.com/s/KaIaCjRGC55UB6px15M1kw - CST vs AST 以及 biome 和 Oxc 各自的選擇理由
https://juejin.cn/post/7504168956594683943 - Babel文檔
https://babeljs.io/ - 前端工程化基石 – AST(抽象語法樹)以及AST的廣泛應用
https://juejin.cn/post/7155151377013047304 - Esprima 文檔
https://esprima.org/ - 快來享受AST轉換的樂趣
https://zhuanlan.zhihu.com/p/617125984 - ESTree Github
https://github.com/estree/estree - AST explorer JavaScript代碼在線轉換為AST語法樹
https://astexplorer.net/ - 【轉譯器原理 parser 篇】實現 js 新語法并編譯到 css
https://juejin.cn/post/6959502530745204772 - JS AST 原理揭秘
https://zhaomenghuan.js.org/blog/js-ast-principle-reveals.html - Acorn Github
https://github.com/acornjs/acorn - Espree Github
https://github.com/eslint/js/tree/main/packages/espree - UglifyJS Github
https://github.com/mishoo/UglifyJS - UglifyJS — why not switching to SpiderMonkey AST
https://lisperator.net/blog/uglifyjs-why-not-switching-to-spidermonkey-ast/ - Terser Github
https://github.com/terser/terser - Estraverse Github
https://github.com/estools/estraverse - Escodegen Github
https://github.com/estools/escodegen - Tree-sitter 文檔
https://tree-sitter.github.io/tree-sitter/ - Node Tree-sitter 文檔
https://tree-sitter.github.io/node-tree-sitter/ - 利用 Tree-sitter 進行語法樹分析
https://juejin.cn/post/7407278157449052186