> 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/stack_machine/compile_to_stack_machine.md).

# 編譯成堆疊機指令

本節會說明把抽象語法樹轉成堆疊機程式的方法。只要做到這點，我們就可以把四則運算的式子分析、建構抽象語法樹，編譯讓以x86-64語法建構的堆疊機可以執行的程式。也就是我們要可以寫出能編譯四則運算的編譯器了。

堆疊機在計算算式的一部份的時候，不論什麼結果，會將1個結果值留在堆疊的頂端。舉例來說我們考慮以下的樹：

![表示加法的抽象語法樹](/files/-Lnv7XBKVox3WkHggXKl)

A和B是部份算式抽象化的表現，實際上是代表某種型態的結點。不過，該型態具體是什麼、樹的形狀如何，在編譯時並不重要。編譯此樹只要照著下面的步驟：

1. 編譯左邊的子樹
2. 編譯右邊的子樹
3. 輸出把堆疊上的2個元素相加，換成加法的結果的指令

執行1.的程式之後，不管該程式是什麼，堆疊頂端應該放著1個代表左邊子樹結果的值。同理，執行2.的程式之後，堆疊頂端應該放著1個代表右邊子樹結果的值。於是，要計算整個樹的值，就只要把這2個值相加，以合計的值取代就好了。

如此，把抽象語法樹編譯成堆疊機指令時，只要遞迴地思考，從樹的最下方逐步輸出組合語言指令就好了。對遞迴思考不習慣的讀者來說可能有點難，但是遞迴是處理樹結構時的基本。處理像樹這樣自己和自己的內部呈相似形的資料結構時，需要用同樣的方式對待部份和全體，也就是同樣的函式要可以用同樣的方法去處理全體、部份、甚至部份的部份。

我們用以下的範例來具體思考：

![表示加法和乘法的抽象語法樹](/files/-LnvArKrC7MhcmHJxN3m)

產生程式的函式的輸入是樹的根結點（root node）。

按照上述的流程，該函式從左子樹開始編譯。也就是先編譯數值`2`。`2`的計算結果就是`2`，這個子樹編譯的結果就是`PUSH 2`。

接下來產出程式的函式要編譯右子樹。然後就會遞迴地編譯到子樹的左子樹，輸出`PUSH 3`。之後編譯子樹的右子樹，輸出`PUSH 4`。

然後產出程式的函式就會返回到呼叫的地方，根據子樹運算子的型態輸出對應的程式。首先輸出的是把堆疊頂端的2個元素相乘結果的指令，再來是把堆疊頂端的2個元素換成其相加結果的指令。底下就是最後輸出的組合語言指令：

```
PUSH 2
PUSH 3
PUSH 4
MUL
ADD
```

使用這樣的手法，就可以機械性地把抽象語法樹轉換成組合語言指令。