編譯器構造/中間表示
不同編譯器之間內部表示的形式差異很大。如果後端由前端作為子程式呼叫，那麼中間表示可能就是某種形式的帶註釋的解析樹，可能還包含補充表。如果後端作為一個單獨的程式執行，那麼中間表示很可能就是某種低階的偽組合語言或暫存器傳輸語言（它可以只是數字，但如果它是人可讀的，除錯會更容易）。
在本章中，我們將討論中間程式碼的基於堆疊的表示。它有許多優點，其中一些是
- 基於堆疊的語言的直譯器往往更緊湊和直接。
- 語言的語法往往很簡單。
但是，這種表示也有以下缺點，使其不適合於操作和改進程式碼
- 更改指令順序並非易事。
- 對基於堆疊的程式碼的研究很少。
基於堆疊的程式碼在控制流中經常會出現問題。
將三地址程式碼等表示轉換為基於堆疊的程式碼通常是微不足道的，因此這種情況留作練習。反過來，這是一個具有挑戰性的問題。
將基於堆疊的程式碼轉換演算法背後的主要任務是識別操作之間的依賴關係。而條件跳轉和無條件跳轉使得確定這些依賴關係變得困難。因此，沒有它們（條件跳轉和無條件跳轉）的程式碼可以以直接的方式轉換為三地址程式碼，如下所示
push 2 push 3 push 4 add mul
我們可以看到堆疊中的每個位置都有一個對應的臨時變數。換句話說，儲存和載入分別只由 push 和 pop 完成，並且一次可以訪問的臨時變數僅限於頂部，而不是通常情況下變數可以自由指定。
s0 = 2 s1 = 3 s2 = 4 s1 = s1 + s2 s0 = s0 * s1
當輸入變數型別時，採用SSA 形式可能會有所幫助。這消除了分析每個變數在某一時刻儲存的型別的需要，正如下面所述，這可能很棘手。這種適應可以在轉換後完成，也可以在轉換程式碼時同時進行。
現在，假設執行可能不會從上到下進行。在這種情況下，我們基本上必須在翻譯程式碼之前分析控制流。更具體地說，我們計算每條指令對堆疊深度的貢獻。例如，
... goto A // unconditionally jump to label A ... A: // a label add // push the sum of two values popped from the stack. ...
正如我們所見，在標籤 A 處，堆疊的狀態取決於指令“goto A”之前的操作。
一種保守的方法是在轉換之前對位元組碼進行註釋。基本思想是，當我們解釋程式碼時，我們既知道我們在哪裡，也知道堆疊有多高。因此，透過假裝我們正在評估程式碼，我們可以計算每個位置的堆疊高度。為此的演算法類似於（在實際編寫時，必須安排程式碼使其能夠終止。）
procedure eval(start, depth)
{
for i from start to code.length
{
depth_at[i] = depth
case code[i]
{
'push': depth = depth + 1
'pop': depth = depth - 1
'goto': i = code[i].target
'if_so_goto': eval(code[i].target, depth)
...
}
}
}
eval(0, 0) // start the calculation
在實踐中，對上述解決方案進行編碼可能很繁瑣，尤其是當語言中的指令數量很多時。Java 位元組碼就是一個很好的例子。因此，下面提供了一種激進的替代方案，即不是以通常的順序方式轉換基於堆疊的程式碼，而是按基本塊（即沒有跳轉的塊）進行轉換。要了解這一點，請考慮以下內容
0 (A): push 10 1 (A): push 13 2 (A): less_than // pop < pop 3 (A): if_not_goto 6 4 (B): push '10 < 13' 5 (B): goto 7 6 (C): push 'it is not 10 < 13; your computer is broken!' 7 (C): print
在上面，我們可以識別出三個基本塊：第一個 (A) 從 0 到 3，第二個 (B) 從 4 到 5，第三個 (C) 從 6 到 7。我們首先編譯 A，然後我們知道 B 或 C 開始時堆疊的高度。在每個塊編譯完後，我們將塊按它們在原始碼中出現的順序輸出。
敏銳的讀者會注意到，在本節中，我們始終假設在每個指令位置堆疊的深度是固定的，因此可以在編譯時確定。如果該假設不成立，那麼我們必須在執行時擁有某種型別的堆疊。
- 為以下每個高階表示式編寫基於堆疊的程式碼
- 10 * (20 + 30);
- if a < b then -a else -b;
- case a % 3 { 0: x; 1: y; 2: z; }
- 編寫一段基於堆疊的程式碼，以便根據執行路徑，堆疊的深度在該段程式碼之後可能會有所不同。
- 草擬將三地址程式碼轉換為基於堆疊的程式碼的演算法，假設沒有跳轉。提示：將堆疊中的每個位置視為一個對應的臨時變數。
- 編寫一段基於堆疊的程式碼，使得在每個位置的堆疊高度無法在編譯時確定。
- 進一步閱讀
- Raja Vallee-Rai The Jimple Framework. 1998. [1]
- expr.c 來自 GCC。
- CFG.java 來自 Soot 框架。
- 直譯器的堆疊快取 由 M. Anton Ertl 撰寫
