AST抽象語法樹
1.概念
抽象語法樹(abstract syntax code,AST) 是原始碼的 抽象語法結構的樹狀表示
。這裡特指程式語言的原始碼。
樹上的每個節點都表示原始碼中的一種結構,之所以說是抽象的,是因為 抽象語法樹並不會表示出真實語法出現的每一個細節
,比如說,巢狀括號被隱含在樹的結構中,並沒有以節點的形式呈現。
抽象語法樹
並不依賴於源語言的語法,也就是說 語法分析
階段所採用的上下文無文文法,因為在寫文法時,經常會對文法進行等價的轉換(消除左遞迴,回溯,二義性等),這樣會給文法分析引入一些多餘的成分,對後續階段造成不利影響,甚至會使合個階段變得混亂。因些,很多編譯器經常要獨立地構造語法分析樹,為前端,後端建立一個清晰的介面。
抽象語法樹在很多領域有廣泛的應用,比如瀏覽器,智慧編輯器,編譯器等。
2.為何需要抽象語法樹(抽象語法樹作用)
程式語言太多,需要一個統一的結構讓計算機識別。
作用:比如 typescript
的型別檢查,IDE的語法高亮,程式碼檢查,轉譯等等,都是需要先將程式碼轉化成AST在進行後續的操作。
3.抽象語法樹的生成過程(編譯)
js為例:
詞法分析(lexical analysis)
:進行詞法分析的程式或者函式叫作詞法分析器(Lexical analyzer,簡稱Lexer),也叫掃描器(Scanner,例如 typescript
原始碼中的 scanner.ts
), 字元流
轉換成對應的 Token流
。
tokenize:
tokenize就是按照一定的規則,例如token令牌(通常代表關鍵字,變數名,語法符號等),將程式碼分割為一個個的“串”,也就是語法單元)。涉及到詞法解析的時候,常會用到tokennize。
語法分析(parse analysis)
: 是編譯過程的一個邏輯階段。語法分析的任務是在詞法分析的基礎上將單詞序列組合成語法樹,如“程式”,“語句”,“表示式”等等.語法分析程式判斷源程式在結構上是否正確。源程式的結構由上下文無關文法描述。
例如:對
const a = 1; const b = a + 1; 複製程式碼
的編譯過程。
圖片地址: ofollow,noindex">www.processon.com/view/link/5…
詞法解析過程
:一邊掃描原始碼一邊進行分類,例如掃描到第一行 const a = 1
,首先掃描到 const
,會生成一個語法單元說這是關鍵字 const
,接著掃描到 a
,這是變數名 a
,接著操作符 =
,接著常量 1
,等等,構成一個個token流。
語法分析過程
:將token流轉化為一個有元素層級巢狀所組成的代表程式語法結構的樹,這個樹被叫做抽象語法樹AST。
4.擴充套件測試:如何將 const a = 1
轉化成 var a = 1
1. 新建一個 testAst
的工程
mkdir testAst複製程式碼
testAst
下新建 test.js
檔案
touch test.js複製程式碼
-
testAst
下安裝esprima
的npm模組,得到AST
npm iesprima --save複製程式碼
test.js
寫入程式碼
const esprima = require('esprima'); let code = 'const a = 1'; const ast = esprima.parseScript(code); console.log(ast); 複製程式碼
2.執行 test.js
node test.js複製程式碼
3.得到生成的AST
也可通過 esprima.org/demo/parse.… ,輸入程式碼,線上檢視AST
-
testAst
下安裝estraverse
的npm模組,遍歷更新AST
npm i estraverse--save 複製程式碼
4.修改程式碼如下:
const esprima = require('esprima'); const estraverse = require('estraverse'); let code = 'const a = 1'; const ast = esprima.parseScript(code); estraverse.traverse(ast, { enter: function (node) { node.kind = "var"; } }); console.log(ast);複製程式碼
5.執行 test.js
,得到更新過後的AST
-
testAst
下安裝escodegen
的npm模組,得到轉譯後的程式碼
npm i escodegen--save複製程式碼
6.修改程式碼如下:
const esprima = require('esprima'); const estraverse = require('estraverse'); const escodegen = require('escodegen'); let code = 'const a = 1'; const ast = esprima.parseScript(code); estraverse.traverse(ast, { enter: function (node) { node.kind = "var"; } }); const transformCode = escodegen.generate(ast); console.log(transformCode); 複製程式碼
7.執行 test.js
,得到轉譯後的程式碼
參考文件:
-
https://segmentfault.com/a/1190000012943992
- https://baike.baidu.com/item/語法分析/8853407?fr=aladdin
- baike.baidu.com/item/詞法分析
- blog.csdn.net/feng98ren/a…
- https://github.com/jamiebuilds/babel-handbook/blob/master/translations/zh-Hans/plugin-handbook.md#toc-asts