編譯器構造/基於堆疊的表示
在本章中，我們將討論中間程式碼的基於堆疊的表示。它有很多優點，其中一些是
- 基於堆疊的語言的直譯器往往更緊湊，更直接。
- 語言的語法往往很簡單。
但這種表示也有一些缺點，這使得它不適合用於操作和改進程式碼
- 改變指令順序並不容易。
- 基於堆疊的程式碼的研究很少。
基於堆疊的程式碼在控制流中經常出現複雜情況。
將三地址程式碼等表示形式轉換為基於堆疊的程式碼通常很簡單，因此這種情況留作練習。這是問題的反面，是一個具有挑戰性的問題。
將基於堆疊的程式碼轉換演算法背後的主要任務是識別操作之間的依賴關係。而條件和無條件跳轉使得很難弄清楚這些依賴關係。因此，沒有它們（條件和無條件跳轉）的程式碼可以以直接的方式轉換為三地址程式碼，如下所示
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; }
- 編寫一段基於堆疊的程式碼，以便堆疊的深度在執行路徑完成後可能會有所不同。
- 概述將三地址程式碼轉換為基於堆疊的程式碼的演算法，假設沒有跳轉。提示：將堆疊中的每個位置視為具有一個對應的臨時變數。
- 編寫一段基於堆疊的程式碼，使得堆疊在每個位置的高度無法在編譯時確定。
- 進一步閱讀