抽象語法樹(abstract syntax tree)
剖析樹記錄文法如何匹配輸入的每個細節,包括只為引導剖析而存在的標點與記帳。抽象語法樹(abstract syntax tree, AST)是清理過的版本:它保留本質結構,什麼運算施加在什麼之上,並丟掉雜訊。把剖析樹想成會議的逐字稿,把 AST 想成只記錄決議的整潔會議紀錄。
拿 2 + 3 * 4 比較兩者。依像 E -> E + T、T -> T * F、F -> num 這樣的文法,具體的剖析樹有一連串單一子節點的鏈(E 到 T 到 F),以及運算子詞符的明確節點,其中許多只是文法為控制優先序而寫成的產物。對應的 AST 則簡單得多:一個 Plus 節點,其子節點是數字 2 與一個 Times 節點,後者的子節點是數字 3 與 4。括號、輔助非終端符號、冗餘的鏈都不見了;留下的恰是意義,2 與一個乘法的相加,乘法因結合得緊而巢狀其中。剖析器產生器透過附在文法規則上的語意動作建出 AST,因此 AST 是在剖析歸約每個句柄時建構出來的。
AST 之所以重要,是因為它是編譯器其餘部分真正在其上工作的資料結構:型別檢查、最佳化、程式碼產生都走訪 AST,而非冗長的剖析樹或原始文字。藉由丟棄不帶意義的語法,AST 讓後續階段直接對程式的意圖推理。它是前端剖析工作交給後續一切的乾淨交接,而同樣的想法在編譯器之外也屢屢再現,於直譯器、靜態檢查器、格式化工具與原始碼對原始碼的轉譯器中。
對 2 + 3 * 4,具體剖析樹因輔助節點與運算子詞符而很深,AST 卻只是 Plus(2, Times(3, 4))。要算出值你走訪 AST:先算 Times(3,4)=12,再算 Plus(2,12)=14,完全不碰括號之類的語法。
剖析樹 = 完整逐字稿;AST = 只剩意義。後續編譯階段走訪 AST。
AST 不是另一種剖析;它是具體剖析樹的刻意化簡,丟掉只屬語法的節點。兩者編碼同一程式,但 AST 才是下游工具設計來消化的對象。