A. 搞懂抽象語法書（AST）
【前端】搞懂抽象語法書（AST）什麼是AST?抽象語法樹（AbstractSyntaxTree，AST），或簡稱語法樹（Syntaxtree），是源代碼語法結構的一種抽象表示。它以樹狀的形式表現編程語言的語法結構，樹上的每個節點都表示源代碼中的一種結構--摘自維基網路
當寫下一段代碼的時候，其實寫的就是一段字元串，如何讓機器能夠理解代碼的邏輯，比如下面這段js代碼：
const?x?=?1?+?2;每一種編程語言都有其獨特的語法規則，而寫下的代碼是一個個的字元，為了讓機器讀懂書寫的代碼，需要一個個字元的去讀取，第一步就是把其中的所有關鍵詞提取出來，並且判斷這些關鍵詞屬於什麼類型，關系結構是怎麼樣。比如const是保留關鍵詞，+和=號是操作符等等，並且把不同欄位間的關系也表達出來，比如1+2是要賦值給x的等等。上述代碼的抽象語法樹如下：
//?採用?esprima?生成{??"type":?"Program",??"body":?[????{??????"type":?"VariableDeclaration",??????"declarations":?[????????{??????????"type":?"VariableDeclarator",??????????"id":?{?"type":?"Identifier",?"name":?"x"?},??????????"init":?{????????????"type":?"BinaryExpression",????????????"operator":?"+",????????????"left":?{?"type":?"Literal",?"value":?1,?"raw":?"1"?},????????????"right":?{?"type":?"Literal",?"value":?2,?"raw":?"2"?}??????????}????????}??????],??????"kind":?"const"????}??],??"sourceType":?"script"}這是用JSON的格式來表現了，不同的解析器其欄位名可能有些不同，但是其本質是一樣的。
如何生成AST生成AST的第一步就是讀取字元串，然後識別出一個個的token，比如下面這個JS的代碼片段，需要識別出const,a,=,19,1,2,-,a,/,10這些標識(token)，這些標識是有分類的，比如const是保留關鍵詞，a、b是變數，=、*、-、/這些的操作符。
const?a?=?10const?b?=?sum(1?*?2?-?a?/?10,?10)然後根據語言的語法規則來排列、分類這些token，從而形成一種樹狀結構（AST）。
Shunting-Yard演算法了解這個演算法前，先來復習一些概念，下面摘錄自wikipedia:
中綴表示法（Infixnotation，或中綴記法）是一個通用的算術或邏輯公式表示方法，操作符是以中綴形式處於操作數的中間。例：1*2-10/10
波蘭表示法（Polishnotation，或波蘭記法），是一種邏輯、算術和代數表示方法，其特點是操作符置於操作數的前面，因此也稱做前綴表示法。
逆波蘭表示法（ReversePolishnotation，RPN，或逆波蘭記法），是一種是由波蘭數學家揚·武卡謝維奇1920年引入的數學表達式方式，在逆波蘭記法中，所有操作符置於操作數的後面，因此也被稱為後綴表示法。例：12*1010/-
Shunting-Yard演算法就是把中綴表示法轉換為逆波蘭表示法。也就是把1*2-a/10轉換為12*1010/-的形式。這種形式非常易於計算機處理
為什麼要使用逆波蘭表示法？這種表示方法非常易於計算機處理，具體的解釋不是本文的重點，可以看這里：https://zh.wikipedia.org/wiki/逆波蘭表示法
這和抽象語法樹有什麼關系？把幾種表示方式放在一起比較一下
逆波蘭表示法：?1?2?*?10?10?/?-把?1?*?2?-?10?/?10?轉換為下面的樹形表示法，??????-??*????????/1???2???10???10//?再把上述的結構轉換為，JSON數據結構表示：{??"type":?"Program",??"body":?[????{??????"type":?"ExpressionStatement",??????"expression":?{????????"type":?"BinaryExpression",????????"operator":?"-",????????"left":?{??????????"type":?"BinaryExpression",??????????"operator":?"*",??????????"left":?{?"type":?"Literal",?"value":?1,?"raw":?"1"?},??????????"right":?{?"type":?"Literal",?"value":?2,?"raw":?"2"?}????????},????????"right":?{??????????"type":?"BinaryExpression",??????????"operator":?"/",??????????"left":?{?"type":?"Identifier",?"name":?"a"?},??????????"right":?{?"type":?"Literal",?"value":?10,?"raw":?"10"?}????????}??????}????}??],??"sourceType":?"script"}當把幾種方式放在一起比較的時候，發現其實是一致的，AST的數據結構只是給每一個token添加更多的屬性，以實現更加復雜的語法，其本質沒有變化。
演算法實現原理直接用一個例子來看看演算法的實現吧：
//?這里操作符的優先順序，默認為從小學的數學的操作符的優先順序，沒有什麼特殊哦1?*?2?+?(10?-?2)?*?5轉換為RPN和AST的過程Token演算法行為輸出操作符堆棧1把1輸出1*把*放入堆棧1*2把2輸出12*+把*出棧輸出12*+把+放入堆棧12*+(把(放入堆棧12*(+10把10輸出12*10(+-把-放入堆棧12*10-(+2把2輸出12*102-(+)把-出棧12*102-(+)把(出棧12*102-+*把*放入堆棧12*102-*+5把5輸出12*102-5*+結束把所有的操作符出棧12102-5+*+轉換為AST的過程和上述非常相似，最終的結果12*102-5*+
如果把這個放入一個堆棧，然後再一個個出棧就可以構建AST樹了，來試試看：
Token類型演算法行為+二元操作符（BinaryExpression）出棧，它就是樹的root，發現是二元操作符，所以會有左右兩個子節點*二元操作符出棧，它是root的右節點，本身是二元操作符，會有左右兩個節點5數字出棧，它是*的右節點-二元操作符出棧，*的左節點，本身是二元操作符，會有兩個子節點2數字出棧，-的右節點10數字出棧，-的左節點，-、*子節點都滿了，回到+節點*二元操作符出棧，它是+根節點的左節點，本身是二元操作符，創建兩個子節點2數字出棧，*的右節點1數字出棧，*的左節點這個例子中，只有數字和操作符，如果加入變數，那麼過程也是一樣的，只是類型不同罷了。
AST的一些應用場景AST的應用場景是非常廣泛的，在寫代碼的過程中，在不知覺中就用到了，代碼可以轉換為AST，AST也可以轉換為代碼。下面是一些應用場景的例子：
IDE
代碼高亮，糾錯等功能都是基於AST的
代碼轉譯
經常使用babel，通過分析AST，把新的語法轉換為舊的語法實現。
比如像Typescript作為JS的超集，編譯到JS的過程需要用到AST
代碼的一些處理，比如JS的minify
通過代碼生成文檔的實現
代碼靜態掃描
解析器下面列舉一些js、ts的解析器的實現庫
庫名針對語言地址acornesnext&JSX(usingacorn-jsx)https://github.com/acornjs/acornesprimaesnext&olderhttps://github.com/jquery/esprimacherowesnext&olderhttps://github.com/cherow/cherowespreeesnext&olderhttps://github.com/eslint/espreeshiftesnext&olderhttps://github.com/shapesecurity/shift-parser-jsbabelesnext,JSX&typescripthttps://github.com/babel/babelTypeScriptesnext&typescripthttps://github.com/Microsoft/TypeScriptBabelbabel是一個編譯器，可以把新的js語法編譯為老的語法實現。現在基本上為了提高生產力，babel必然是所用的構建工具中的一環。所以很有必要了解，簡單從AST的角度介紹下。
babel主要三步走來完成編譯的過程
讀入JS源代碼，轉換成AST
遍歷AST所有節點，運行插件，執行轉換任務，比如把變數a重命名為x，這個過程生成了一個新的轉換過的AST
把新的AST生成新的JS代碼
這三個過程分別對應了三個包：@babel/parser,@babel/traverse,@babel/generator
當時通常不需要主動調用這些包的方法來自己手動做，只要通過一定的規范格式，寫插件即可。
下面是一個簡單的直接使用的例子：
const?parser?=?require("@babel/parser");const?traverse?=?require("@babel/traverse").default;const?generate?=?require("@babel/generator").default;const?sampleCode?=?`function?add(a,?b)?{??return?a?+?b}`;//?1.解析為ASTconst?ast?=?parser.parse(sampleCode);//?2.遍歷，並做轉換traverse(ast,?{??FunctionDeclaration:?function(path)?{????path.node.id.name?=?'addTwo'??}});//?3.重新生成新的代碼const?result?=?generate(ast)console.log(result.code)//?列印的結果是//?function?addTwo(a,?b)?{//????return?a?+?b//?}這是一個非常基本的例子，但是涵蓋了babel整個工作的基本打框架，可以看到AST在其中的關鍵作用。
總結雖然在平時工作中，尤其在業務開發中很少用到，但是當想要對一些編程工具、編譯工具、寫一些babel或者webpack的插件，去構建一些提效工具的時候，就需要涉及AST的概念，所以去理解，去了解是很有必要。
原文：https://juejin.cn/post/7100082653256220686