- 抽象語法樹（AST）表示程式的邏輯結構，消除了無關的語法細節。
- AST 由字母、元數函數和樹語法構成，定義了哪些節點和結構是有效的。
- 杜威分類法和運算符，例如“.”或“/”，可以精確地引用這些結構中的子樹和路徑。
- 編譯器、解釋器和程式碼分析工具都依賴抽象語法樹 (AST) 來可靠地最佳化、轉換和理解程式。
抽象語法樹是程式設計中一個乍聽之下非常理論化的概念，但一旦掌握了它，你就會發現它無所不在：編譯器、解釋器、程式碼分析、重構工具，甚至結構化資料查詢語言中都有它的身影。本質上，它是機器「理解」程式結構（超越純文字）的一種方式。
儘管抽象語法樹（AST）有時會被誤認為是經典的語法分析樹，但它們有自己獨特的規則。抽象語法樹不僅僅是一張漂亮的圖畫：它是一種緊湊且設計精良的資料結構，它剔除了具體語法中所有多餘的部分（例如括號、逗號、冗餘關鍵字等），而專注於本質：執行哪些操作、操作物件是什麼以及操作順序是什麼。
抽象語法樹（AST）究竟是什麼？
在程式語言理論中，抽象語法樹（AST）是一種樹狀結構，它以簡化的形式表示程式的語法，與具體的語法分析樹相比，它包含與語法分析樹相同的基本訊息，但組織方式更加緊湊和易於管理。
句法分析樹包含語法的所有產生式和所有終結符，包括括號、逗號、分號和其他純粹的句法元素。而抽象語法樹（AST）則去除這些不貢獻語意的細節，只保留表達式和句子的邏輯結構。
在實作方面，抽象語法樹 (AST) 通常由節點物件組成，節點物件具有類型，用於指示它是哪種語法結構（常數、標識符、函數應用、二元運算子等），以及描述其內容的附加屬性：值、名稱、子節點、參數列表等。
AST 的優點在於它有助於編譯器或解釋器的後續階段，例如類型檢查、最佳化或程式碼生成，因為它提供了程式結構的清晰視圖，而沒有語法雜訊。
具體語法樹和抽象語法樹的區別
為了充分理解抽象語法樹（AST）的作用，首先將具體的語法分析樹與抽象語法分析樹進行比較會很有幫助。想像一個簡單的語法，它可以辨識像「a + 4 * 5」這樣的算術表達式。具體的語法分析樹準確地反映了每條語法規則的應用：非終結符、終結符、括號、運算符等等。
這棵特殊的樹通常很深，包含許多中間節點，這些節點僅用於維護語法的形式結構。例如，可能存在「表達式」、「項」、「因子」節點，以及諸如「+」、「*」之類的終結符號、識別碼和數字。每個產生式都成為樹的一個分支，從而增加了結構的複雜性。
另一方面，同一表達式的抽象語法樹僅限於表示實際的運算和操作數。因此，我們不再需要多層“表達式”和“項”，而可以用一個表示加法的根節點，它有兩個子節點：左側是標識符a，右側是乘法節點，其子節點分別是值 4 和 5。純粹的語法節點消失了，部分結構被重新排序或簡化。
這意味著抽象語法樹（AST）和具體的語法樹包含相同的語義訊息，但前者以更直接、更簡潔的形式呈現。這種精簡對於在分析或執行工具中高效處理程式碼至關重要。
具有元數函數的樹和字母表
為了從數學角度形式化這些樹，通常會使用具有元數函數的字母表。字母表並非簡單地包含一組符號，而是定義了一個字母表，其中每個符號都與一個數字相關聯，該數字表示該符號在樹中可以有多少個子節點。
帶有元數函數的字母表，通俗地講，是由有限個符號和一個函數組成的二元組，該函數為每個符號分配一個自然數（包括零）。這個數表示符號的元數：如果為 0，則該符號作為葉節點；如果為 1，則作為一元節點；如果為 2，則為二進位節點；依此類推。通常也允許運算子的參數清單使用可變元數的符號。
元數為 0 的符號對應於樹的葉子節點（例如，常數或標識符）。元數為 1 的符號用於包含單一子表達式的結構。元數為 2 的符號表示經典的二元運算，例如加法、乘法、賦值等。而元數可變的符號允許對接受不確定數量子樹的結構進行建模，例如帶有多個參數的函數呼叫。
從這個具有 k 個元數的字母表中，可以定義所有可能的樹的集合：從空樹（如果考慮的話）開始，添加所有元數為 0 和可變的符號，並進行歸納擴展：如果一個符號是 k 元的，它可以作為 k 個已構造子樹的父節點。這樣就得到了與該字母表關聯的樹語言（或術語）。
樹狀語言和節點的概念
在此上下文中，由字母表及其元數函數構成的所有樹的集合被稱為樹語言或項語言。它相當於克萊恩閉包對字串的作用，只不過是針對樹結構而言。
就像分析字串時我們用「標記」 （token ）一詞來指涉序列中字母符號的出現次數一樣，處理樹時我們通常使用「節點」 （node）一詞。本質上，節點是指樹中特定位置上具有特定元數的字母符號的具體出現次數。
從這個角度來看，樹狀語言之於節點，就如同字串集合之於詞元出現次數。每棵樹都被解釋為由字母表逐步建構而成的結構，而節點則是構成其符號的各個組成部分。
這種看待問題的方式在設計解析器和 AST 生成器時非常有用，因為它允許以類似於字串語法的方式推理這些樹的構造規則，但直接作用於層次結構。
特定抽象語法樹（AST）中節點的元數：以 Egg 為例
從理論到實踐，許多教學材料都使用Egg語言來示範抽象語法樹 (AST) 的建構和操作。在 Egg 語言中，使用了幾種主要的節點類型，每種節點都有明確定義的元數，這使得操作起來非常容易。
在典型的 Egg AST 中， VALUE節點被視為葉子節點：它們代表字面量，例如字串或數字。它們沒有子節點；它們只儲存一個值。類似地，用於識別符（變數名稱、函數名稱等）的 WORD 節點也被視為葉子節點，並具有一個儲存名稱的屬性。
Egg 中的關鍵節點是APPLY類型，它表示函數或運算子的應用。這種節點類型有兩個概念上的子節點：一個OPERATOR子節點，指向正在應用的表達式；以及一個ARGS子節點，它實際上是一個特殊的 ARRAY 節點，負責維護一個子樹集合，每個參數對應一個子樹。
因此，數組是向 AST 引入可變參數量的自然方法：APPLY 始終有兩個組成部分（運算符和參數列表），但該內部列表可以包含零個、一個或多個子樹，具體取決於所表示的特定呼叫。
Egg 中 AST 結節的詳細解剖結構
在實作層面，Egg 的抽象語法樹 (AST) 節點通常表示為帶有屬性的對象，這與 JavaScript 等語言完美契合。所有節點都共用一個公共屬性：`type`，它標識節點類型（VALUE、WORD、APPLY、ARRAY 等），從而決定物件其餘部分的結構。
VALUE 節點用於表示字面常數。它們包含一個屬性，通常稱為value，其中儲存了它們所代表的數字或字串。它們沒有其他子節點，因為它們的內容已完全由該字面值描述。
詞節點專用於儲存識別碼：變數名、函數名、參數名等等。它們通常有一個`name`屬性，用於儲存字串形式的識別碼。與值節點類似，它們在樹中充當葉節點，因為它們的唯一作用是提供名稱。
應用節點代表應用或呼叫。它們包含一個運算子屬性，指向被應用的表達式（另一個節點）；以及一個參數屬性，連結到一個陣列節點。後者是抽象語法樹 (AST) 中的一個特定節點，其目的是保存應用的參數清單。
ARRAY 節點可以理解為其他節點的結構化容器，代表一系列子樹。從參數數量的角度來看，它引入了靈活性，因為它允許在同一個 APPLY 語句中使用無參數、單參數或多參數調用，而無需更改主節點類型的定義。
AST範例：只有一個值的簡單應用程式
為了形象化以上所有內容，讓我們考慮簡單指令的表示，例如使用單一參數 5 應用函數 X。解析器產生的 AST 對應於一個由 VALUE、WORD 和 APPLY 節點建構的項，遵循 Egg 的規則。
從概念層面來說，我們會在根節點放置一個APPLY節點。它的 operator 屬性指向一個名為 X 的 WORD 節點，而它的 args 屬性指向一個包含單一元素的 ARRAY 節點：一個數值為 5 的 VALUE 節點。這樣，該結構就清楚地反映了操作對象和操作內容。
如果我們想明確所有屬性，可以寫更詳細的表示法，顯示型別、運算子、參數、名稱和值。這種更詳盡的表示法對於偵錯解析器或理解文字表達式如何在解釋器中轉換為樹物件非常有用。
在實際應用中，這棵樹通常會被序列化為JSON格式，以便於儲存、傳輸或檢查。事實上，諸如npm 生態系統中的evm2term套件之類的工具和模組，提供了這些抽象語法樹 (AST) 的緊湊表示形式，方便進行分析或轉換。
抽象語法樹範例：嵌套加法和乘法
另一個典型例子是稍微複雜的表達式，例如“+(a, *(4, 5))”。這裡我們有一個加法運算，它的第一個參數是標識符 a，第二個參數是 4 乘以 5 的結果。此表達式產生的抽象語法樹 (AST) 反映了這種嵌套結構。
在樹的根節點，我們再次會看到一個 APPLY 節點，它代表加法運算。它的運算子是一個名為「+」的 WORD 節點，而它的參數則位於一個包含兩個元素的 ARRAY 節點中：第一個元素是一個名為「a」的 WORD 節點；第二個元素是另一個 APPLY 節點，它代表乘法運算。
第二個 APPLY 運算子的參數是一個名為「*」的 WORD，參數是一個包含兩個 VALUE 節點的 ARRAY：一個節點的值為 4，另一個節點的值為 5。從整體來看，該結構清楚地表明，求值順序是將 4 乘以 5，然後將結果加到 a 上。
如果我們擴展這種表示法，使其包含所有屬性，我們就能看到所有節點的類型、名稱或具體值，以及它們之間的關係。這種明確的描述與 Egg 解釋器中的實際實作相對應，其中每個節點都是一個具有上述屬性的物件。
樹語法和解析器語法
這些抽象語法樹的生成方式並非任意的：它是基於所謂的樹文法。在典型的表述中，這種文法被定義為一個四元組，由一個具有n個元數的字母表、一個有限的句法（非終結符）變數集、一個有限的產生式規則集和一個起始符號組成。
在每個產生式規則中，一個變數被替換為一棵樹，該樹的根節點是具有指定元數的字母表符號，其子節點則依序為變數或已定義的樹。這種結構類似於經典的正則文法或上下文無關文法，但它適用於直接生成樹而不是符號串。
與此更正式的定義相關的是 Egg 解析器用於產生其樹的特定語法。這個語法通常在文件中以非正式的方式呈現，它精確地描述了語言中接受哪些關鍵字、運算子、括號等的組合，以及它們如何轉換為 VALUE、WORD、APPLY 和 ARRAY 類型的節點。
這種樹語法可以看作是文獻中所謂的正規樹語法的一個特例。其核心思想是擁有明確定義的規則，用於將輸入標記序列轉換為結構化的抽象語法樹（AST），然後對其進行解釋或編譯。
杜威分類法：樹狀圖中的座標
一旦我們有了抽象語法樹 (AST)，我們經常需要引用特定的子樹：例如，函數的第二個參數、表達式的運算子等等。一種非常優雅的方法是所謂的杜威十進位表示法，它藉鑒了用於對文件中的章節和子章節進行編號的方案。
在這種表示法中，從樹 t 開始，子樹用一串以句點分隔的數字表示。每個數字表示一個子節點的位置（通常從 1 開始），序列沿著樹向下排列。因此，像 t/2.1.3 這樣的表達式指的是 t 的第二個子節點的第一個子節點的第三個子節點。
這種表示法的歸納定義很簡單：空字串指的是整棵樹本身；如果一個字串由一個數字和更多用句點分隔的數字組成，則首先取與指定索引對應的子樹，然後遞歸地將相同的邏輯應用於字串的其餘部分。
例如，假設我們有一個樹 t，它表示一個表達式“+(a, *(4,5))”，根節點是 APPLY（加法），子節點是 WORD（加號），另一個子節點是 APPLY（乘法），我們可以確定特定的節點位置。因此，如果我們對子節點進行適當的編號， t/1可以是運算子為「+」的 WORD 節點，t/2.1 可以是識別碼為「a」的 WORD 節點，t/2.2.2.1 可以是值為 4 的 VALUE 節點。
在 AST 中給出「座標」的方式對於在報告錯誤、導航樹或對特定節點應用局部變換時指出特定位置非常有用，而且不會產生歧義。
程式設計和工具中的等效符號
杜威符號背後的想法並非樹論所獨有；事實上，它反覆出現在我們日常程式設計和結構化資料處理中使用的許多實用符號中，即使我們並不總是意識到這一點。
在程式語言中，當我們使用點運算子編寫表達式（例如 object.property.subproperty）時，我們實際上是在做類似的事情：遍歷嵌套物件樹，每一步都透過名稱而不是位置編號來選擇子物件。從根節點開始，我們向下遍歷到更深層的節點。
同樣的模式也出現在類別 Unix 檔案系統中，其中使用正斜線運算子 (/)來分隔目錄：/src/js/tutu.js 描述了從檔案系統根目錄到特定資源的路徑，遍歷樹結構的連續層級。
在結構化文件領域，像XPath這樣的語言使用非常相似的符號來選擇 XML 樹中的節點。例如，「A//B/*」這樣的查詢會選擇元素 A 的後代元素 B 的第一個子元素（無論其名稱如何），該子元素的位置取決於當前上下文，並使用單斜杠和雙斜杠來表示深度級別。
另一個知名的工具jq語言使用平行系統來瀏覽 JSON 結構，允許透過複合路徑、篩選器和表達式來選擇子物件。所有這些表示法都只是在樹狀結構中表達路徑的不同方式，與杜威十進制分類法非常相似，但都針對各自的領域進行了調整。
語言學和程式設計中的句法分析樹
除了編譯器領域之外，語法樹在語言學中也用來表示句子結構。在語言學中，它們被稱為推導樹或句法分析樹，展示了句子是如何分解成短語、單字和語法範疇的。
在這些樹中，就像在程式設計中一樣，我們發現了三種基本類型的節點：根節點，它代表完整的句子或全局結構；內部節點或分支節點，它們充當父節點並將句子的子集分組；以及葉節點，它們通常對應於輸入字串中出現的特定單字。
根節點是唯一的：整個樹狀結構都依附於它。分支節點位於根節點或其他父節點的正下方，用於依層級結構組織句子或程式的各個部分。而葉節點則位於樹的最底層，沒有子節點，因此封閉了分支結構。
這些樹狀圖被認為是強大的教學工具，因為它們有助於將複雜的句子分解成易於理解的元素。這同樣適用於程式設計：一個結構良好的抽象語法樹（AST）可以讓你一目了然地看到哪些操作是串聯在一起的，哪些表達式是嵌套的，以及求值是如何進行的。
根據分析目標的不同，我們可以找到不同類型的分析樹。有些分析樹強調字詞或成分之間的依賴關係（例如，句子中誰依賴誰），而有些則著重於將字詞或成分分組，從而形成兩大類分析樹。
按依存關係和按成分劃分的語法樹
依存句法樹是其中一種最廣為人知的類型。在這種變體中，句子中的所有詞或所有相關元素都被視為葉節點，它們之間的連接表示直接的依賴關係（例如，主要動詞及其主詞）。因此，與其他方案相比，這種方案通常能產生節點較少的樹。
這種簡潔性使得它們對初學者和某些語言處理任務特別方便，因為其結構專注於關係依存，而無需引入過多的中間節點。應用於程式設計時，其理念是只關注必要的關係，省略語法修飾。
另一方面，我們也有基於成分或組成部分的句法樹，它們區分根節點、內部分支節點和葉節點，並將所有相關的分組清晰地呈現出來。這些樹通常包含更多節點，並能更詳細地反映句子或程式的層級結構。
常見的成分樹模板通常展示具有眾多葉節點、多層分支和一個明確根節點的長句。它們尤其適用於剖析具有多層嵌套結構的複雜句子或程序。
在依存關係樹和組成關係樹中，範例和視覺化資源均以範本形式提供，您只需填寫所需資訊即可。這節省了時間，避免了每次需要展示結構時都必須從頭開始設計圖表。
與AST相關的實際應用與工具
抽象語法樹（AST）並非只是一個理論概念：任何與程式碼打交道的人都會在各種日常工具中積極使用它們。編譯器、解釋器、程式碼壓縮器、程式碼格式化工具和靜態分析器幾乎都依賴 AST 來執行其功能。
典型的編譯器會取得原始碼，進行詞法分析、語法分析，並產生抽象語法樹（AST）。然後，它會執行語義檢查（類型、變數作用域、結構使用不當等），並透過遍歷和轉換 AST 來進行程式碼最佳化，最終產生機器碼，即字節碼。
程式碼檢查器或格式化器等工具也適用於抽象語法樹 (AST)：它們分析結構以檢測問題模式、不良實踐或不一致之處，並提出更改以保持樹的語義結構，但調整程式碼的呈現方式。
例如，在 JavaScript 生態系統中，有多個函式庫以 JSON 格式公開 AST，這使得其他工具更容易依賴它來執行重構、產生自動文件或建立複雜程式結構的視覺化。
即使在一些更專業的領域，例如用於測量測試覆蓋率的工具或將原始程式碼轉換為其他語言，AST 也是許多現代解決方案的基礎，因為它允許在原始文字和機器程式碼之間非常舒適的抽象層級上工作。
總而言之，抽象語法樹是連接語言形式語法、編譯器或解釋器內部表示以及我們用於安全且有效率地編寫、分析和轉換程式碼的高階工具的關鍵所在。理解它們的構造方式、如何瀏覽它們（例如使用杜威十進制分類法）以及涉及哪些類型的節點（VALUE、WORD、APPLY、固定或可變元數結構等），有助於我們更清晰地了解機器在處理程序時實際執行的操作。
