(1) 權杖 \(\to\) XML 標籤對。 每個權杖存成 <型態> 內容 </型態>，例如關鍵字 else 存成 <keyword> else </keyword>。 術語：<keyword> 是開標籤、 </keyword> 是閉標籤（以 / 開頭）、 夾在中間的是內容。 四個特殊字元不能直接放進內容，必須跳脫：

（題目原文把 <／> 的跳脫寫反了順序—— XML 標準是 < \(\to\) <、 > \(\to\) >，容易自行對照確認。 為什麼需要跳脫？因為 < 在 XML 裡是標籤的開始記號， 出現在內容裡會讓讀取器誤判結構——例如 Jack 運算子 < 就必須存成 <symbol> &lt; </symbol>。）

(2) Tag struct——權杖與非終端符號的統一容器：

• type（enum JackTagType）＋ data（union TagData）—— 與第 8 週的 Token 同構；

• 非終端符號有專屬的 type： NON_TERMINAL，此時 data 存 enum NonTerminal（class、whileStatement…）；

• close_tag 欄位：非終端的閉標籤為 true、開標籤為 false（權杖的標籤對用不到此欄位）—— 解析樹的巢狀結構就靠開閉標籤對表達， 所有子節點都寫在開閉標籤之間；

• malloc_tag／free_tag （記憶體安全的建立與釋放）、 read_tag／write_tag （讀寫 XML，非終端也適用，還會自動處理縮排）。

(3) 三個解析輔助函式（配合影片 11-2 的 current／lookahead 雙指標）：

整個解析器就用這三個動詞寫成： copy（這個權杖屬於解析樹）、 advance（這個權杖只是文法噪音，AST 不需要）、 write_non_terminal（在正確位置蓋結構章）。

每個 parse_abc 都遵守同一份契約 （影片 11-2）：

• 進入時 current 是 \(\textcolor{ntred}{\langle\text{\itshape abc}\rangle}\) 的 第一個權杖；

• 產生 \(\textcolor{ntred}{\langle\text{\itshape abc}\rangle}\) 的全部 XML（開閉標籤＋子節點）；

• 返回時 current 是 \(\textcolor{ntred}{\langle\text{\itshape abc}\rangle}\) 結束後的第一個權杖。

parse_file 的流程：建立 current／ lookahead \(\to\) 用一次 advance_tag 跳過檔案開頭為符合 XML 標準而存在的特殊 <tokens> 標籤 \(\to\) 呼叫 parse_class （一個 .jack 檔就是一個 \(\textcolor{ntred}{\langle\text{\itshape class}\rangle}\)）\(\to\) 返回時 current 應指向檔尾的 </tokens>， 收尾關檔。

已給的 parse_class 是所有函式的模板 （文法：\(\ensuremath{\textcolor{ntred}{\langle\text{\itshape class}\rangle}} \ensuremath{\Coloneqq}\ensuremath{\text{\textcolor{tokblue}{`\texttt{class}'}}},\ \text{identifier},\ \ensuremath{\text{\textcolor{tokblue}{`\texttt{\{}'}}},\ \{\ensuremath{\textcolor{ntred}{\langle\text{\itshape classVarDec}\rangle}}\},\ \{\ensuremath{\textcolor{ntred}{\langle\text{\itshape subroutineDec}\rangle}}\},\ \ensuremath{\text{\textcolor{tokblue}{`\texttt{\}}'}}}\)）：

// 骨架的形狀（示意）
write_non_terminal(CLASS, /*close=*/false, output);
copy_tag(...);   // 'class'
copy_tag(...);   // 類別名（識別字）
copy_tag(...);   // '{'
while (current 是 'static' 或 'field')
    parse_class_var_dec(...);
while (current 是 'constructor'/'function'/'method')
    parse_subroutine_dec(...);
copy_tag(...);   // '}'
write_non_terminal(CLASS, /*close=*/true, output);

「重複 {}」翻成 while 迴圈、 「擇一 |」翻成 if/switch、 「巢狀非終端」翻成遞迴呼叫——文法就是程式碼的形狀。

依文法逐一寫（縮排即巢狀關係；「複製」= copy_tag）：

parse_subroutine_dec （\(\ensuremath{\Coloneqq}(\ensuremath{\text{\textcolor{tokblue}{`\texttt{constructor}'}}} \ensuremath{\mid}\ensuremath{\text{\textcolor{tokblue}{`\texttt{function}'}}} \ensuremath{\mid} \ensuremath{\text{\textcolor{tokblue}{`\texttt{method}'}}}),\ (\ensuremath{\text{\textcolor{tokblue}{`\texttt{void}'}}} \ensuremath{\mid}\ensuremath{\textcolor{ntred}{\langle\text{\itshape type}\rangle}}),\ \text{identifier},\ \ensuremath{\text{\textcolor{tokblue}{`\texttt{(}'}}},\ \ensuremath{\textcolor{ntred}{\langle\text{\itshape parameterList}\rangle}},\ \ensuremath{\text{\textcolor{tokblue}{`\texttt{)}'}}},\ \ensuremath{\textcolor{ntred}{\langle\text{\itshape subroutineBody}\rangle}}\)）： 複製 kind 關鍵字 \(\to\) 複製返回型別（\(\textcolor{ntred}{\langle\text{\itshape type}\rangle}\) 不寫標籤， 直接複製那個權杖——見下方「抑制規則」）\(\to\) 複製函式名 \(\to\) 複製 ( \(\to\) parse_parameter_list \(\to\) 複製 ) \(\to\) parse_subroutine_body。

parse_parameter_list （\(\ensuremath{\Coloneqq}[\ensuremath{\textcolor{ntred}{\langle\text{\itshape type}\rangle}},\ \text{identifier},\ \{\ensuremath{\text{\textcolor{tokblue}{`\texttt{,}'}}},\ \ensuremath{\textcolor{ntred}{\langle\text{\itshape type}\rangle}},\ \text{identifier}\}]\)）： 若 current 是 )，參數列為空、直接返回； 否則複製「型別、名字」，之後只要 current 是 , 就複製「逗號、型別、名字」。

parse_subroutine_body （\(\ensuremath{\Coloneqq}\ensuremath{\text{\textcolor{tokblue}{`\texttt{\{}'}}},\ \{\ensuremath{\textcolor{ntred}{\langle\text{\itshape varDec}\rangle}}\},\ \ensuremath{\textcolor{ntred}{\langle\text{\itshape statements}\rangle}},\ \ensuremath{\text{\textcolor{tokblue}{`\texttt{\}}'}}}\)）： 複製 { \(\to\) 只要 current 是 var 就 parse_var_dec \(\to\) parse_statements \(\to\) 複製 }。

parse_var_dec （\(\ensuremath{\Coloneqq}\ensuremath{\text{\textcolor{tokblue}{`\texttt{var}'}}},\ \ensuremath{\textcolor{ntred}{\langle\text{\itshape type}\rangle}},\ \text{identifier},\ \{\ensuremath{\text{\textcolor{tokblue}{`\texttt{,}'}}},\ \text{identifier}\},\ \ensuremath{\text{\textcolor{tokblue}{`\texttt{;}'}}}\)）： 與已給的 parse_class_var_dec 幾乎相同—— 複製 var、型別、名字， , 迴圈補名字，最後複製 ;。

parse_statements：分派器—— 只要 current 是 let／if／ while／do／return 之一， 就呼叫對應函式；遇到別的（實務上是 }） 寫閉標籤返回。

每個函式頭尾都夾 write_non_terminal 的開閉標籤（<letStatement>… </letStatement> 等）。 注意 \(\textcolor{ntred}{\langle\text{\itshape ifStatement}\rangle}\)／\(\textcolor{ntred}{\langle\text{\itshape whileStatement}\rangle}\) 透過 \(\textcolor{ntred}{\langle\text{\itshape statements}\rangle}\) 遞迴——巢狀迴圈免費獲得。

parse_expression （\(\ensuremath{\Coloneqq}\ensuremath{\textcolor{ntred}{\langle\text{\itshape term}\rangle}},\ \{op,\ \ensuremath{\textcolor{ntred}{\langle\text{\itshape term}\rangle}}\}\)）： parse_term，然後只要 current 是九個 二元運算子（+ - * / & | < > =）之一： 複製運算子、再 parse_term。

parse_term——全解析器唯一需要 lookahead 的地方。按 current 分七種情況：

為什麼需要看 lookahead？ 遇到識別字開頭的 \(\textcolor{ntred}{\langle\text{\itshape term}\rangle}\)，光看 current 分不出它是變數、陣列存取還是 \(\textcolor{ntred}{\langle\text{\itshape subroutineCall}\rangle}\) 的函式名——要看下一個權杖是不是 (／.／[。 這就是「Jack 是 LL(2)」的全部內容； 其他所有函式只看 current 就夠（LL(1)）。

parse_subroutine_call （\(\ensuremath{\Coloneqq}\text{identifier},\ [\ensuremath{\text{\textcolor{tokblue}{`\texttt{.}'}}},\ \text{identifier}],\ \ensuremath{\text{\textcolor{tokblue}{`\texttt{(}'}}},\ \ensuremath{\textcolor{ntred}{\langle\text{\itshape expressionList}\rangle}},\ \ensuremath{\text{\textcolor{tokblue}{`\texttt{)}'}}}\)）： 複製名字；若 current 是 . 再複製 . 與名字；複製 (、 parse_expression_list、複製 )。

parse_expression_list （\(\ensuremath{\Coloneqq}[\ensuremath{\textcolor{ntred}{\langle\text{\itshape expression}\rangle}},\ \{\ensuremath{\text{\textcolor{tokblue}{`\texttt{,}'}}},\ \ensuremath{\textcolor{ntred}{\langle\text{\itshape expression}\rangle}}\}]\)）： 若 current 是 ) 直接返回（空列表）； 否則 parse_expression， 之後 , 迴圈。

測試順序（難度遞增）：

對每個 foo.jack 跑你的解析器， 把輸出與 foo.xml 用 diff／fc／ Meld 比對。fooT.xml 平常用不到—— 它是詞法器輸出的對照檔，懷疑 bug 在詞法層時 先比它排除（詞法器骨架已完整實作，理論上直接過）。

diff 的讀法：XML 每個標籤一行、含縮排， 第一個差異行直接指出哪個非終端的哪個位置出錯。 常見前三名：忘了抑制 \(\textcolor{ntred}{\langle\text{\itshape type}\rangle}\)／\(\textcolor{ntred}{\langle\text{\itshape parameterList}\rangle}\)／ \(\textcolor{ntred}{\langle\text{\itshape subroutineDec}\rangle}\) 標籤；parse_term 的識別字情況漏看 lookahead； \(\textcolor{ntred}{\langle\text{\itshape returnStatement}\rangle}\) 的可選運算式判斷寫反。

TableEntry 的變化（從組譯器的「名字 \(\to\) 位址」 升級成編譯器的完整變數描述）：

關鍵行為變更：offset 只對同 kind 遞增。 例如表裡已有 3 筆 VK_VAR 與 10 筆 VK_ARGUMENT， 再加一筆 VK_VAR 會拿到 offset \(=3\)（第 4 個 VAR）， 而不是 14（第 14 筆）。 原因：VM 的 local 與 argument 是各自獨立的記憶體段，編號各從 0 起—— 符號表直接維護這個不變量，碼產生時查到就能用。

is_primitive：型別是 int／char／boolean 回傳 true。 用途在編譯 \(\textcolor{ntred}{\langle\text{\itshape subroutineCall}\rangle}\) 時分辨 foo.bar() 的 foo： 是物件變數（非 primitive）\(\to\) 方法呼叫， 要把 foo 推成第一個引數； 不在表裡 \(\to\) 類別名，普通 call。

CompileData：把（類別符號表、副程式符號表、 類別名、標籤計數器、輸出檔……）打包成一個 struct， 省得每個 compile_*** 都拖七八個參數—— 純工程便利，compile_file 已初始化好。

符號表的生命週期（Jack 特意設計成 不需要獨立的語意分析趟）：

• \(\textcolor{ntred}{\langle\text{\itshape class}\rangle}\) 開標籤：建類別表， 每個 \(\textcolor{ntred}{\langle\text{\itshape classVarDec}\rangle}\) 加 field／static 項目 （兩種 kind 分開編號）；閉標籤時釋放；

• \(\textcolor{ntred}{\langle\text{\itshape subroutineDec}\rangle}\) 開始：建副程式表； 若是方法先加一筆 this（type = 類別名、kind = argument、 offset 0）；再為 \(\textcolor{ntred}{\langle\text{\itshape parameterList}\rangle}\) 每個參數加 argument、為每個 \(\textcolor{ntred}{\langle\text{\itshape varDec}\rangle}\) 加 local； 本體結束時釋放；

• 查變數時副程式表優先（區域遮蔽）。

compile_expression：後序輸出—— compile_term（第一個 term 的值上堆疊）， 然後每遇一個運算子與 term：先 compile_term、 再輸出運算子的 VM 碼。由左至右、無優先順序 （Jack 的設計——括號才有結合力， 這正是 () 只作為 \(\textcolor{ntred}{\langle\text{\itshape term}\rangle}\) 出現的原因）。

compile_term——目標：算出值、留在堆疊頂：

變數的段對映即符號表 kind： var \(\to\) local、參數 \(\to\) argument、 static \(\to\) static、field \(\to\) this （不變式：this 0 永遠是當前物件的位址， 所以第 \(i\) 個欄位就是 this \(i\)）。 陣列則走 that 段：把基底＋下標的和放進 pointer 1，that 0 就是那一格—— this 給欄位、that 給 []，兩者互不打架。

compile_let（普通變數）： 編譯右邊的 \(\textcolor{ntred}{\langle\text{\itshape expression}\rangle}\)， pop 到查表得到的段與編號。

compile_let（陣列目標）let a[e1] = e2 ——本作業最精緻的一段舞步：

push a          // 基底
//（編譯 e1 的 VM 碼）
add             // 堆疊頂 = a+e1 的位址
//（編譯 e2 的 VM 碼）——過程中可能用到 pointer 1！
pop temp 0      // 先把 e2 的值收進 temp 0
pop pointer 1   // 現在才把 a+e1 裝進 pointer 1
push temp 0
pop that 0      // RAM[a+e1] = e2

為什麼不能「先 pop pointer 1 再編譯 e2」？ 因為 e2 自己可能含陣列存取（如 let a[i] = b[j]），會覆寫 pointer 1。 先算位址、再算值、值暫存 temp 0、最後才設定指標—— 順序就是為了讓兩邊的陣列互不踩腳。 ComplexArrays 測試（let a[b[a[3]]] = a[a[5]] * b[...]） 專門抓這個。

compile_while（標籤由計數器生成，如 while_start_4／while_end_4）：

label while_start_4
//（條件運算式的 VM 碼）
not
if-goto while_end_4
//（本體 statements 的 VM 碼）
goto while_start_4
label while_end_4

compile_if：

//（條件運算式的 VM 碼）
not
if-goto if_else_7
//（then 部分）
goto if_end_7
label if_else_7
//（else 部分，若無 else 則兩標籤重合）
label if_end_7

compile_do：編譯 \(\textcolor{ntred}{\langle\text{\itshape subroutineCall}\rangle}\) 之後 務必 pop temp 0——呼叫必留一個返回值 在堆疊上，沒人要就得丟掉，否則堆疊「漏水」， 迴圈裡的 do 會讓堆疊無限長高。

compile_return：有運算式就編譯它； void 函式推假值 push constant 0 （VM 的 return 一律搬一個返回值， 呼叫端的 pop temp 0 正好接走）。最後輸出 return。

編譯 \(\textcolor{ntred}{\langle\text{\itshape subroutineCall}\rangle}\)——三種形態：

注意第一種的 call 用的是變數的型別 （查符號表的 type 欄位）拼出 Type.method—— 這就是 type 欄位存在的理由； is_primitive 幫你排除 int 等 不可能有方法的情況。

編譯 \(\textcolor{ntred}{\langle\text{\itshape subroutineDec}\rangle}\)——輸出 function 類別名.副程式名 k（\(k =\) local 數， 從副程式表數 VK_VAR），然後按種類加開場白：

開場白之後，本體內不要再動 pointer 0—— 維持「this 0 \(=\) 當前物件」的不變式， 欄位存取才永遠正確。

官方做法——三步：

push constant L        // L = 字串長度
call String.new 1      // 堆疊頂 = 新字串的位址
// 對每個字元 c：
push constant 72       // 'H' 的 ASCII 碼
call String.appendChar 2   // 返回同一字串位址，可連鎖
//（重複 L 次）

題目的提示：Hack 字元集在一般字元上與 ASCII 一致——所以 C 端直接把 char 當 int 用（sprintf("push constant %d", (int) c)），不需要 50 多筆的查表。

（第十一週影片也誠實揭露：這個做法讓每次執行到字面值 都在堆積配置新字串、永不釋放——Jack 的 Hello world 自帶記憶體洩漏。測試腳本都照官方語意設計， 本作業照官方做法即可。）

測試矩陣（照序漸進，每個只引入少量新特性）：

題目給的除錯錦囊（全部實測有用）：

1. VM 模擬器設 No animation 快跑時， 動畫速度滑桿變成時脈速度—— Square／Pong 這種互動程式一定要拉滿；

2. 用 currentFunction 變數設斷點 ——「每次進入某函式就停」， 直接跳過一定正確的函式庫呼叫；

3. 程式崩潰時，視窗左下角有呼叫堆疊 （按呼叫順序列出所有函式）—— 先看死在哪個函式再回頭讀碼；

4. 測試程式編不對時，自己寫最小失敗範例： 把出錯的構造抽成十行的 Jack 程式， 在 VM 模擬器先讓它動起來。 Average 很慢的話，把 Keyboard.readInt 的字串字面值改短，重跑到出錯點的時間就短了。

（選做）任務 3——完整管線： 把三個作業串起來：本週的編譯器（.jack \(\to\) .vm）\(\to\) 第 9–10 週的 VM 翻譯器 （.vm \(\to\) .asm）\(\to\) 第 8 週的組譯器（.asm \(\to\) .hack）， 最後裝進第 7 週你在 Logisim 蓋的 CPU—— 從高階語言原始碼到你自己蓋的硬體， 整條路每一吋都是你寫的。 實務注意：資料夾裡每個 .jack 都要編譯、 連同 OS 函式庫的 .vm 一起交給 VM 翻譯器 （它會自動加開機碼）， 輸出的 .asm 可能上萬行——組譯器的 符號表若還是線性搜尋，這裡會第一次感覺到慢。