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

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

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

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

![表示1\*(2+3)的樹](/files/-Lmcurj-6pOqgbSJgTGf)

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

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

![表示7-3-3的樹](/files/-LmgqL8UrlUJ5mB82KKi)

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

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

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

![代表1\*2+3\*4\*5的樹](/files/-Lmgvhs2HDzEtR9X6mlR)

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

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

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://koshizuow.gitbook.io/compilerbook/calculator_level_language/recursive_descendent_parsing/tree_structure.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.