Jack 的精神

討論 Jack 時最常出現的兩句話：

• 「就像 C，但是……」

• 「為了（編譯的）簡單起見……」

Jack 的每一個設計決策都圍繞一個目標： 讓學生能在一週內寫出它的編譯器。 語言的不便之處（稍後一一列出）全是刻意用 「程式設計師多打幾個字」換取「編譯器少寫幾百行」。

變數、敘述與註解

函式

函式宣告像 C，但開頭加 function 關鍵字：

function int Main.max (int x, int y) {
    // 函式本體
}

無返回值的函式用 void 宣告。 返回語法同 C（return 42; 或 return;）， 但每個函式都必須以 return 結尾。 函式呼叫也像 C，唯一例外： 只呼叫函式並丟棄返回值的一行必須以 do 開頭——Main.print("Hello"); 不合法， do Main.print("Hello"); 才合法。

運算式

流程控制

Jack 支援與 C 相同的 if-else 與 while，但：

• 不支援 else if——要寫成 else { if (...) {...} }（巢狀）；

• 不支援 do...while 與 for。

if (x > 5 & ~(y + f(x) = 7)) {
    // ...
} else { if (z = 2) {   // else if 不合法，巢狀才合法
    // ...
}}
while (x < 5 | Main.fibonacci(x) = 13) {
    // ...
}

型別

Jack 沒有轉型（cast）。int、char、 boolean 之間支援隱含轉換： char 依 Hack 字元集視為 int； true \(= -1\)、false \(= 0\)。例如：

var int x; var boolean y; var char z;
let x = -1; let y = x; let z = x + 71;

合法，且 y 為 true、z 為 "F" （\(-1 + 71 = 70\)，Hack 字元集的 F）。 實作上「免費」取得：把 char／boolean 在記憶體中一律存成 int，然後完全忽略型別資訊。 （認真做型別檢查會極度複雜——甚至有論文證明 Java 的精確型別 檢查在理論上不可判定，除非接受檢查器可能不停機！）

一個「新」概念：類別（Classes）

Jack 用類別取代 C 的 struct。 類別是物件導向程式設計（OOP，下學期）的核心， 但幸運的是，Jack 缺少讓類別比 struct 複雜的所有（眾多） 特性。Jack 類別與 C struct 唯一的實質差別：

• C 中與 struct 相關的函式與 struct 定義分離 （甚至可以在不同檔案）；

• Jack 中與類別相關的函式包含在類別定義之內。

類別變數：field 與 static

• field 變數 = C 的一般 struct 成員；

• static 變數為該類別所有成員共享 （C 的 struct 沒有這個）；

• 類別變數用一般語法宣告（var Foo myFoo;）， 所有類別變數必須在類別開頭宣告；

• Jack 不支援 myFoo.x 語法存取欄位—— 改用方法。

方法（Methods）

void twiddleFoo(struct Foo *abc) {
    abc->x = abc->x + abc->y;
    abc->y = abc->y - 1;
}
twiddleFoo(myFoo);
twiddleFoo(myOtherFoo);

class Foo {
    method void twiddle() {
        let x = x + y;
        let y = y - 1;
    }
}
// 呼叫端：
do myFoo.twiddle();
do myOtherFoo.twiddle();

第一次呼叫時 this 是 myFoo、 第二次是 myOtherFoo——正如 C 版的 abc。

建構子（Constructors）

建構子是用來建立新類別變數的特殊函式。 執行期，建構子在呼叫開始時自動在堆積上建立新變數， this 指向它，且建構子應以 return this; 結尾：

class Foo {
    field int x, y;
    constructor Foo newFoo(int a) {
        let x = 5;
        let y = a;
        return this;
    }
}
// 呼叫端：
let myFoo = Foo.newFoo(42);

這對應 C 的 malloc(sizeof(Foo)) ＋欄位初始化＋ 回傳指標。呼叫建構子與函式時必須帶類別名前綴 （Foo.newFoo()，不能只寫 newFoo()）。 注意：Jack 的類別配置在堆積上，所以必須像 C 的 malloc 指標一樣手動釋放——慣例是寫一個 dispose 方法，內部呼叫 Memory.deAlloc(this)。 （投影片的兩個範例其實都漏了釋放——都會漏記憶體！）

[] 語法與記憶體後門

Jack 中所有類別型變數都存在堆積， 只有 int／char／boolean 存在堆疊。 實際上類別型變數就是指標——把 Foo 型變數 當 int 讀，會看到欄位所在的堆積位址。 運算式 myObject[i] 的意思是： 取 myObject 的位址、加 \(i\)、回傳該處的值。 Array 與 String 類別的實作保證位址 就是陣列／字串的第一個元素，所以語法行為符合直覺。 （這是純 Jack 的做法——C 的 struct 放堆疊！）

這也給了我們一個記憶體後門：

var int x;
let x = 16384;
let x[0] = 0;   // 把 RAM[0x4000]（螢幕第一個字）設為 0

多檔案編譯與範例程式

每個 Jack 檔案含一個類別宣告（Foo.jack 含類別 Foo）。一切都必須在類別內； 不屬於任何類別的程式碼放 Main 類別。 程式從 Main.main() 開始（類比 C 的 main）。 每個 Jack 檔案分開編譯成 Hack VM， 再由 VM 翻譯器合併、組譯器產出機器碼。 Jack 檔案可以使用其他檔案定義的類別—— 編譯器直接假設它們存在 （省掉 C 的 makefile，代價是更差的錯誤處理）。

投影片以 Nisan and Schocken 的 Average 程式收尾： 讀入若干數字、用 Array.new 配置陣列、 while 迴圈累加、輸出平均值—— 其中 Keyboard.readInt、Output.printString 等都來自標準函式庫（寫編譯器時不需要管它們！）。

編譯 Jack（Compiling Jack）

詞法分析（Lexing）

Jack 的詞法分析毫無驚喜，技術與之前完全相同。權杖如下：

兩個值得注意的地方：

• 識別字的定義比 Hack VM／組語更嚴格—— 這讓 myVar+4 不加空格也能無歧義地切出權杖；

• 換行不是權杖！跟 C 一樣只是空白。 （對照：組語與 VM 都以換行分隔指令。）

Jack 的文法（EBNF）

回憶我們的 EBNF 方言：{} 表示「重複任意次 （含零次）」、[] 表示「可有可無」。

注意所有變數都宣告在類別開頭（\(\textcolor{ntred}{\langle\text{\itshape classVarDec}\rangle}\)）或 函式開頭（\(\textcolor{ntred}{\langle\text{\itshape varDec}\rangle}\)）——建符號表時， 在需要產生任何涉及變數的程式碼之前， 變數的全部資訊都已到手！

注意 \(\textcolor{ntred}{\langle\text{\itshape ifStatement}\rangle}\) 與 \(\textcolor{ntred}{\langle\text{\itshape whileStatement}\rangle}\) 中 \(\textcolor{ntred}{\langle\text{\itshape statements}\rangle}\) 的遞迴。 \(\textcolor{ntred}{\langle\text{\itshape statements}\rangle}\) 內不能宣告新變數（宣告只出現在 \(\textcolor{ntred}{\langle\text{\itshape varDec}\rangle}\)／\(\textcolor{ntred}{\langle\text{\itshape classVarDec}\rangle}\)）， 所以不必追蹤獨立的作用域。

看看運算式遞迴得多兇！而這種遞迴是捕捉 Math.sqrt((x+y)*Main.fibonacci(z)) 這類運算式 絕對必要的。我們拖延了很久，但現在必須 用解析樹來處理它們——也就是終於把解析與 程式碼產生分開。 幸好 Jack 是 LL(2) 語言（而且接近 LL(1)）， 過程不會太痛苦。

用 XML 儲存解析樹

解析趟與後續程式碼產生趟之間，解析樹要存在哪？理想上要： 人類可讀（方便除錯）、夠標準 （讀寫檔案不費事）、夠彈性 （不必整棵樹載入記憶體就能瀏覽）。 nand2tetris 正確地指出 XML 三項全中—— 多數語言都有現成的標準函式庫。 當然，C 不是「多數語言」…… 所以課程把第 8–10 週的權杖程式碼改造成 陽春的 XML 處理函式庫放進骨架； 詞法器也用同一函式庫把權杖輸出成 XML 格式。

一個（相當）通用的 LL(2) 解析器

while (count < 100) {
    let count = count + 1;
}

從解析樹到 AST

我們的文法已經比 Nisan and Schocken 原版刪掉許多多餘的 非終端符號（如 \(\textcolor{ntred}{\langle\text{\itshape op}\rangle}\)、\(\textcolor{ntred}{\langle\text{\itshape varName}\rangle}\)）。 建解析樹時，還應把 \(\textcolor{ntred}{\langle\text{\itshape type}\rangle}\) 替換成它的定義。 更進一步：if、{}、() 這些權杖 對「把權杖串變成 \(\textcolor{ntred}{\langle\text{\itshape ifStatement}\rangle}\)」有用， 但每個 \(\textcolor{ntred}{\langle\text{\itshape ifStatement}\rangle}\) 都長一樣—— 把它變成程式碼時真的需要這些節點嗎？ 這正是 AST（抽象語法樹）的用意，且沒有唯一正解。 建議做法：先寫包含解析樹每個節點的程式碼、 用 diff 對照提供的 XML 輸出測試， 再考慮要從 AST 略去什麼（把 copy_tag 換成 advance_tag）。

語意分析：變數映射與符號表

Jack 被非常小心地設計成不需要獨立一趟來建符號表或 做其他語意分析。解析之後直接進入程式碼產生， 從頭到尾掃一遍檔案、邊讀 XML 邊產出程式碼。 處理 \(\textcolor{ntred}{\langle\text{\itshape subroutineDec}\rangle}\) 時，遇到開標籤就：

1. 為該副程式建一張新符號表；

2. 若是方法，先加一筆 argument 項目給 this、位移 0（原因見第 3 章！）；

3. 為 \(\textcolor{ntred}{\langle\text{\itshape parameterList}\rangle}\) 的每個變數加一筆 argument 項目；

4. 為 \(\textcolor{ntred}{\langle\text{\itshape subroutineBody}\rangle}\) 每個 \(\textcolor{ntred}{\langle\text{\itshape varDec}\rangle}\) 加 local 項目；

5. 用符號表為 \(\textcolor{ntred}{\langle\text{\itshape statements}\rangle}\) 產生程式碼；

6. 到 \(\textcolor{ntred}{\langle\text{\itshape subroutineBody}\rangle}\) 結尾時釋放符號表 （不再需要）。

每筆符號表項目包含：變數名（查詢鍵）、 型別（字串）、種類（local／argument……）、 位移（貪婪分配）。 例如 Nisan and Schocken 圖 11.2 的表把 this 映射到 argument 0、 other 到 argument 1、 dx 到 local 0、dy 到 local 1。

程式碼產生：遞迴的真正威力

程式碼產生使用與解析非常相似的遞迴結構。

到此，完整 Jack-to-Hack 編譯器只剩一塊拼圖： 類別型變數與方法的程式碼產生——見下一章。

編譯 Jack 的類別

物件的運作方式

var Foo myFoo;
// （初始化 myFoo 的程式碼）
do Output.printInt(myFoo);   // 印出 myFoo 存放的 RAM 位址！

所有物件欄位都配置在堆積；指標本身像一般 var 一樣存在堆疊。 （與 C 的 struct 非常相似，除了 C 的 struct 可以放堆疊、 且要處理不同欄位大小！）

副程式的期望行為

類別可含函式、方法與建構子，合稱副程式 （subroutines）（不尋常的術語——通常 subroutine 指 void 函式——但沿用 Nisan and Schocken）。 所有副程式 myClass.mySub 應該：

• 編譯呼叫時：輸出把各引數（\(\textcolor{ntred}{\langle\text{\itshape expression}\rangle}\)） 推上堆疊的 VM 碼，接著輸出 call myClass.mySub；

• 編譯 \(\textcolor{ntred}{\langle\text{\itshape parameterList}\rangle}\) 與 \(\textcolor{ntred}{\langle\text{\itshape varDec}\rangle}\) 時：建符號表， 用它把變數名換成編號的 local／argument；

• 編譯返回時：把返回的 \(\textcolor{ntred}{\langle\text{\itshape expression}\rangle}\) 推上堆疊 （無返回值就推假值），再輸出 return；

• 編譯 \(\textcolor{ntred}{\langle\text{\itshape doStatement}\rangle}\) 時：\(\textcolor{ntred}{\langle\text{\itshape subroutineCall}\rangle}\) 之後 務必 pop temp 0——丟棄無人要的返回值， 避免堆疊上的「記憶體洩漏」。

三種副程式的差異

函式可以無視宿主類別（除了 static 變數）。 但建構子與方法都關聯到其類別的當前物件 （current object）：

• 建構子被呼叫時自動建立當前物件—— 用 Memory.alloc 在堆積配置適當大小的段 （重點是在呼叫結尾把當前物件返回）；

• 方法通常用 myVar.myMethod() 語法呼叫（而非 myClass.myMethod()）， 以 myVar 為當前物件。

在方法與建構子的本體內：this 求值為當前物件； 宿主類別的欄位 x 解讀為「this 的 x」； 宿主類別的方法可用 myMethod() 呼叫 （解讀為 this.myMethod()）。 這對之後的 OOP 至關重要；在 Jack 的脈絡裡， 它只是讓你能寫 myToken.write(output) 而不是 write_token(myToken, output)。

（附註：Jack 不支援 C 式的 myObject.myField 欄位存取——要編譯它， 必須在編譯某檔案時取得另一個檔案的類別欄位資訊， 那需要跨所有檔案的完整語意分析趟——不是不可能，但很煩。）

類別符號表與 this 的角色

與副程式符號表一樣，我們只在類別自身的程式碼內 需要知道 field／static 變數存在哪。遇到 \(\textcolor{ntred}{\langle\text{\itshape class}\rangle}\) 開標籤： 建新符號表 \(\to\) 為每個 \(\textcolor{ntred}{\langle\text{\itshape classVarDec}\rangle}\) 的變數加項目 （field 與 static 分開編位移）\(\to\) 在其後每個 \(\textcolor{ntred}{\langle\text{\itshape subroutineDec}\rangle}\) 的程式碼產生中使用 \(\to\) 遇閉標籤釋放。

編譯 \(\textcolor{ntred}{\langle\text{\itshape term}\rangle}\)

compile_term 的目標：產生「求出 \(\textcolor{ntred}{\langle\text{\itshape term}\rangle}\) 的值、 留在堆疊頂」的 VM 碼。 整數字面值 85 \(\to\) push constant 85； 括號運算式 \(\to\) 呼叫 compile_expression。 最難的情況是識別字與字串字面值。 識別字：查類別與副程式符號表——

若識別字同時出現在類別表與副程式表， 以副程式表優先（區域遮蔽）。

字串字面值：官方做法與它的漏洞

官方 nand2tetris 做法： 用 String.new 建一個上限長度合適的新 String \(\to\) 用一連串 String.appendChar 填入字元 （Hack 字元集對齊 ASCII，char 直接當 int 用）\(\to\) 把新 String 的位址推上堆疊。問題解決了，對吧？

該修嗎？要先講清楚「修」是什麼意思。 某種意義上它沒壞——語言照規格運作； 自動釋放字面值會弄壞既有的 Jack 程式（和測試腳本）。 更嚴肅地說，看看 C 就知道沒有簡單答案：

• char myString[] = "Hello";—— 在堆疊上放一份副本，函式返回即消失，期間可修改。 但從返回 char * 的函式 return myString; 就留下懸空指標。嗯。

• char *myString = "Hello";—— 程式開始時建一份靜態副本，指標指向它。 但 myString[0] = ’J’; 直接 segfault。糟糕。

講師的非官方 Hack：修改文法，讓 \(\textcolor{ntred}{\langle\text{\itshape letStatement}\rangle}\) 與 \(\textcolor{ntred}{\langle\text{\itshape expressionList}\rangle}\) 都能直接接受 字串字面值。\(\textcolor{ntred}{\langle\text{\itshape letStatement}\rangle}\) 用官方做法 （明確建立指標的人自己負責 String.dispose）； \(\textcolor{ntred}{\langle\text{\itshape expressionList}\rangle}\)（函式引數）則自動釋放：

• compile_expression_list 把字串字面值引數的 清單回傳給 compile_subroutine_call；

• call 之後，引數仍留在堆疊上 （目前堆疊指標之上）——取回這些字面值、 逐一呼叫 String.dispose；

• 陷阱：第一個引數會被返回值覆寫 （即使函式是 void！）——所以若第一個引數是字串字面值， 就把它再推一次當作額外的最後一個引數 （call 的引數計數相應增加）， 釋放時改釋放最後一個。

總結與展望（Summing Up）

知道我們不知道什麼

課程沒有做的事（每一項都可以是暑期專題！）：

• 用 HDL（如 Verilog）描述遠更複雜的電路、 減少人工接線錯誤；

• 學更進階的組語（如 MIPS）並在低功耗環境開發；

• 硬體能力：進階運算、中斷、管線化、快取；

• 支援多行程的作業系統；

• 更好的編譯器：型別檢查、程式驗證、 程式碼最佳化；

• 更多語言特性：真正的物件導向、並行；

• 網路連線（Twitch plays Tetris？）。

編譯器類專題找程式語言研究群； 硬體／OS 類找（系統）資安與 HPC 研究群。

我們做到了什麼

但別忘了我們做到的事——完整的四層編譯與建造：

1. 把 C 風格語言（Jack）編譯到堆疊機： 用文法與遞迴把複雜運算式轉成長串後綴式指令； 用指標式陣列實作使用者自訂型別； 用不洩漏的演算法配置與釋放堆積記憶體； 用符號表管理不同作用域的變數； 把 while 等複雜流程敘述化為簡單的 goto。

2. 把堆疊機編譯到組語： 用裸組語實作堆疊本身；用堆疊實作函式呼叫； 把虛擬記憶體段映射回實體記憶體（堆疊與堆積皆然）； 合併多檔案以支援函式庫。

3. 把組語編譯到原生機器碼： 把標籤映射到 ROM 位址；貪婪配置變數到指定記憶體區； 用記憶體映射 I/O 寫螢幕、讀鍵盤； 理解指令集本身及其設計理由。

4. 從零建造執行機器碼的電腦： R-S 閂鎖 \(\to\) D 正反器 \(\to\) 暫存器與記憶體； 用多工器／解多工器在元件間路由指令； 用簡單邏輯閘實作複雜算術—— 一路回到卑微的 NAND 閘、真值表與布林代數。

還記得開場演講裡那些真的用麵包板與 NAND 晶片蓋出來的 Hack 電腦嗎？你現在有能力做出它們了。真正的從零開始。 恭喜完成課程，考試順利！

綜合練習題（附詳解）

練習 1：Jack 語法判斷

下列各行是否為合法 Jack？不合法者說明原因。 (a) var int x = 0; (b) Main.print("hi"); (c) let x += 1; (d) if (x = 5) {...} else if (y = 2) {...} (e) while (~(x > 10)) { let x = x + 1; }

練習 2：運算子優先順序

(a) Jack 中 1 + 2 * 3 可能求值為哪些結果？為什麼？ (b) 若用第 2.7 節的 compile_expression （由左至右），會得到哪個？寫出產生的 VM 碼。 (c) 要保證得到 7，Jack 程式設計師該怎麼寫？

push constant 1
push constant 2
add
push constant 3
call Math.multiply 2

練習 3：隱含型別轉換

執行下列 Jack 程式後，y 與 z 的值 （以 16 位元 int 表示）各是多少？

var int x; var boolean y; var char z;
let x = 3;
let y = (x > 2);
let z = 65 + x;

練習 4：EBNF 對照

用 2.2 節的文法，指出解析 let a[i+1] = f(x) - 2; 時， (a) 這整行匹配哪個非終端符號及哪個選項； (b) i+1、f(x)、f(x) - 2 各匹配什麼； (c) 解析器在讀到哪個權杖時知道有 [...] 部分？

練習 5：為什麼是 LL(2)？

(a) 解析 \(\textcolor{ntred}{\langle\text{\itshape term}\rangle}\) 時，哪種開頭權杖需要看 lookahead？ 列出 lookahead 的三種情況與對應動作。 (b) 為什麼其他敘述（let/if/while/do/return）都只需 LL(1)？

練習 6：符號表建構

為下列副程式建出完整符號表（名稱、型別、種類、位移）：

class Point {
    field int x, y;
    static int count;
    method int distSq(Point other) {
        var int dx, dy;
        // ...
    }
}

練習 7：手工編譯 while

把下列 Jack 編譯成 Hack VM（n 為 local 0）：

while (n > 0) {
    let n = n - 1;
}

label while_start_0
push local 0
push constant 0
gt                     // n > 0
not                    // 條件取反
if-goto while_end_0    // 不成立則離開
push local 0
push constant 1
sub
pop local 0            // n = n - 1
goto while_start_0
label while_end_0

練習 8：手工編譯運算式

在練習 6 的 distSq 方法內，把 let dx = x - other[0]; 編譯成 VM 碼。 提示：other[0] 用 that 段。

push this 0        // x（field 0，經 this 段）
push argument 1    // other（物件位址）
push constant 0
add                // other + 0
pop pointer 1      // that 0 -> other[0]
push that 0        // other[0] 的值
sub                // x - other[0]
pop local 0        // dx =

練習 9：方法呼叫的編譯

p 是型別 Point 的 local 2。 (a) 把 do p.distSq(q);（q 為 local 3） 編譯成 VM 碼。 (b) 編譯器如何分辨 p.distSq(q) 是方法呼叫、 而 Math.sqrt(x) 是函式呼叫？

push local 2           // p 作為隱藏的第一個引數（this）
push local 3           // q
call Point.distSq 2    // 2 個引數（p 算一個！）
pop temp 0             // do 敘述：丟棄返回值

練習 10：建構子的編譯

類別 Point 有 2 個 field（練習 6）。 寫出編譯 constructor Point new(int ax, int ay) 開頭與結尾所產生的 VM 碼骨架，並解釋每一步。

function Point.new 0     // 0 個 local
push constant 2          // 物件大小 = field 數 = 2（查類別符號表）
call Memory.alloc 1      // 在堆積配置 2 個字，返回基底位址
pop pointer 0            // this 段指向新物件
// ...本體：let x = ax; -> push argument 0 / pop this 0
//          let y = ay; -> push argument 1 / pop this 1
push pointer 0           // return this;
return

練習 11：do 與 void 的堆疊衛生

(a) 為什麼 do 敘述編譯後必須 pop temp 0？ 不做會怎樣？ (b) void 函式的 return; 為什麼要推假值？ (c) 呼叫 void 函式後，呼叫端拿到的「返回值」是什麼？

練習 12：字串字面值洩漏

(a) 逐步說明 do Output.printString("Hi"); 在官方編譯法下產生哪些堆積操作。 (b) 這段程式在迴圈裡跑 1000 次，堆積淨增多少個 String 物件？ (c) 講師的修法中，為什麼「第一個引數是字串字面值」 需要特殊處理？

附錄：速查表

Jack 權杖總表

Jack \(\to\) VM 對照配方

變數種類 \(\to\) 記憶體段

名詞中英對照

參考資料

• John Lapinskas, The Jack language／ Compiling Jack／Compiling Jack’s classes／ Summing up and looking forward（11-1 至 11-4）， COMSM1302, University of Bristol.

• Nisan & Schocken, The Elements of Computing Systems （nand2tetris），Ch. 9（Jack）、Ch. 10（Compiler I: Syntax Analysis）、Ch. 11（Compiler II: Code Generation）、 附錄 5（Hack 字元集）、附錄 6（OS API）.

• nand2tetris Project 10 & 11 （nand2tetris.org）——編譯器兩階段開發與 漸進式測試程式.