> For the complete documentation index, see [llms.txt](https://koshizuow.gitbook.io/compilerbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://koshizuow.gitbook.io/compilerbook/calculator_level_language/recursive_descendent_parsing/tree_structure.md).

# 將文法結構表示為樹（tree）

實作程式語言的分析器時，輸入為扁平的標記列，而輸出為表示巢狀結構的樹式非常常見的作法。本書的構造也是如此。

C語言的`if`或`while`文法可以是巢狀的，也很適合用樹結構來表現此類架構。

算式中，有括號內必須先計算、先乘除後加減的結構。這樣的結構乍看之下可能不像樹結構，但是用樹來表示的話可以非常簡單地代表算式的結構。舉例來說 `1*(2+3)`可以想成用底下的樹來表示：

![表示1\*(2+3)的樹](https://416395721-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LjokrNdcE1H2E8hE2Dc%2F-LmcuUTxRKY4mPCmBuQO%2F-Lmcurj-6pOqgbSJgTGf%2Findex.svg?alt=media\&token=083f277e-9920-426e-b9b3-5867d00067c2)

我們從最邊緣照順序開始計算的話，上述的樹，可以代表`1`乘上`2+3`的算式。也就是說，上述的樹是以樹的結構代表了 `1*(2+3)`的具體計算順序。

再用一個例子來說明。以下式表示`7-3-3`的樹：

![表示7-3-3的樹](https://416395721-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LjokrNdcE1H2E8hE2Dc%2F-LmgpsR3kv_pZCGjFdtu%2F-LmgqL8UrlUJ5mB82KKi%2Findex.svg?alt=media\&token=e7c90750-7e78-4100-8211-f1160aa78b30)

上述的樹是以樹的結構表達「減法必須從左至右計算」規則的結果。也就是說，上述的樹是代表`(7-3)-3 = 1`而不是`7-(3-3) = 7`。如果是後者的話，其代表的樹應該是右邊會比較深，而不是左邊。

必須從左至右計算的運算子為「左結合」運算子，而必須從右邊開始計算的運算子叫作「右結合」運算子。在C裡，除了`=`（代入）之外，大部分的運算子都是左結合。

以樹來表達的話，加深樹的深度可以表達任意長度的算式。底下的樹為代表`1*2+3*4*5`的樹。

![代表1\*2+3\*4\*5的樹](https://416395721-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LjokrNdcE1H2E8hE2Dc%2F-LmgvH-nDISH8-KSSBcd%2F-Lmgvhs2HDzEtR9X6mlR%2Findex.svg?alt=media\&token=398b1107-ab25-47cf-87d6-28f87fd8910e)

上述的樹叫作「語法樹」（syntax tree）。其中，去除分組用的括號等冗長的元素，儘可能精減的語法樹稱為「抽象語法樹」（abstract syntax tree, AST）。上述的語法樹都可以轉成抽象語法樹。

抽象語法樹是編譯器的內部結構，可以依據實作上的方便來定義。但像是加法或乘法等算術運算子都是定義為左邊和右邊兩邊計算，採用二分樹比較自然。但是，如函式引數等照順序執行、可以有任意長度的要素，則是用可以表示所有要素的扁平樹結構比較自然。

語法分析的目標就是建立抽象語法樹。編譯器首先會進行語法分析，把輸入的標記列轉換成抽象語法樹，再把抽象語法樹轉換成組合語言指令。