下一個目標

我們已經懂了 Hack 組語與 Hack ISA，也會用組譯器把組語變成機器碼。 但組譯器本身是怎麼運作的？ 本週的目標：用 C 打造一個自己的 Hack 組譯器！ 在抽象階梯上，我們正在處理「組合語言 \(\to\) ISA」這一步的翻譯軟體 ——而它的原理與「高階語言 \(\to\) 組語」的編譯器一脈相承。

編譯器的分階段全貌

現代編譯器通常以離散的階段（phases）工作：

• 前置處理：語言特定的步驟，例如把程式檔連結起來、 執行編譯器巨集。在 C 中包括讀 makefile、處理 #include 與 #define。

• 最佳化：自動把低效程式碼變成高效程式碼的過程。

兩者都超出本課程範圍。

中介表示法（IR）

多數編譯器把語意分析萃取出的資訊放進程式碼的 中介表示法（intermediate representation, IR）， 然後對 IR（而非原始碼）做最佳化。 IR 是給電腦（而非人類）用的，相當接近組語； 「最佳化 IR」是最佳化裡困難的那一半。 許多語言可以編譯到同一個 IR——例如 LLVM 被用於 C#、Java bytecode、Ruby 與 Rust 的編譯器。 下週起我們會看到 Hack 的 IR；但一行組語本來就對應一行機器碼， 所以組譯器不需要 IR。

語法 vs 語意

組譯器的簡化

對組譯器而言，語法與語意幾乎相同， 常見做法是把語意分析併入詞法分析與解析。 沒有複雜語意，也就不必把程式碼產生跟解析分開——逐行處理即可。

The Joy of Lex：權杖

可用的權杖列表寫在程式語言的規格書裡， 連同把權杖組成語句的文法（見第 3 章）。 什麼算一個權杖是語言設計者的選擇，不是普世標準—— 例如 Java 把註解與空白當權杖，C 則不是。

Hack 組語的權杖

Nisan 與 Schocken 沒有給 Hack 組語文法，但我們可以自建。 我們取以下權杖：

幾個關鍵觀察：

• A 與 ARG 是不同的關鍵字 ——區分它們要小心（不能看到 A 就停）。 一般而言，關鍵字是語言本身賦予特殊意義、 通常不能重新定義的字串。C 的關鍵字包括 const、 int、for、return， 但不包括 printf。

• C 把符號稱為 punctuators 與 operators， 且有多字元符號如 >=、==、%: 與 %:%:（後兩者由於歷史因素是 # 與 ## 的同義詞）。

• C 把字面值稱為 constants，還有字串、浮點、enum 與字元常數。

• 識別字代表在程式碼（而非語言）中定義的實體， 例如特定變數、函式或 struct 型別。在 C 中 printf 是 stdio 函式庫定義的識別字。 注意我們不區分變數與標籤——都先當識別字。

• C 完全忽略換行，但我們需要換行權杖—— 否則無法區分「A 之後接 D=M」與 AD=M。

詞法分析的好處與範例輸出

為什麼要費工夫做詞法分析？ 因為之後可以把權杖存成乾淨的 struct， 從此不必再跟 C 糟糕的字串處理搏鬥（至少撐到程式碼產生階段…）。

D;JGT      // if D>0 goto output_first

符號表（Symbol Tables）

問題：標籤與變數

回想 Hack 組語中 @ 後面可以接數字、標籤或 變數。組譯器必須：

1. 為每個變數配置一個 RAM 位址（從 16 開始）；

2. 用位址取代變數；

3. 為每個標籤指定 ROM 位址—— 等於其宣告處對應的機器碼行號；

4. 用位址取代標籤；

5. 然後才把 @ 語句轉成 A-指令。

以投影片的範例程式追蹤整個過程（左：原始碼，右：完成後）：

我們用符號表完成這件事。

識別字與符號表

上面範例對應的兩張表：

符號表如何運作？

符號表必須支援三種操作：

1. 加入新的名稱與位址；

2. 檢查某名稱是否在表中；

3. 若在表中，取出對應的位址。

「正確」的實作方式是雜湊表（hash table） （幾週後的 Programming in C 會教）。 但用你已學過的動態大小容器（動態陣列）也能做，只是較沒效率 ——每次查詢線性掃描整個陣列即可。 這是好的 C 練習、但不是好的架構練習， 所以作業已幫你寫好——見 symboltable.c 與 symboltable.h。

如何填符號表？

在組語中，填符號表簡單到可以整合進詞法分析與解析 （在 C 之類的語言中則發生在較後面的語意分析階段）。 兩張表都從空表開始。

為什麼標籤要在詞法階段先處理？ 因為變數與標籤在使用處長得一模一樣（都是 @名字）， 唯一能區分它們的是宣告；而 @名字 可能出現在 (名字) 宣告之前（向前跳轉）。 先掃一遍把所有標籤收齊，解析時才不會把標籤誤當新變數。

進階符號表：作用域（Scopes）

高階語言的編譯器需要追蹤作用域： 每個作用域建一張符號表。 語意分析建好表後，轉換成 IR 時可以把它們存在一個 堆疊（stack）裡。考慮這段 C 程式：

#include <stdio.h>

int main() {
    double foo = 7;
    char i = 'a';
    for (int i = 0; i <= 5; i++) {
        printf("%f, %d", foo, i);
        foo /= 2;
    }

    foo = 50;
    for (long i = 0; i <= 10; i++) {
        double temp = foo + 500;
        printf("%f, %d", temp, i);
        foo *= 2;
    }

    printf("%c", i);    // Prints 'a'
    printf("%d", temp); // Compile error!
    return 0;
}

編譯器的堆疊操作：從表 1 開始，第 3 行 push 表 2、 第 6 行 push 表 3、第 9 行 pop（for 迴圈結束）、 第 12 行 push 表 4、第 16 行 pop、第 21 行 pop。 查詢變數時從堆疊頂往下找，回傳第一筆結果—— 這就是「內層變數遮蔽（shadow）外層同名變數」的機制： 在第一個 for 內查 i 會先找到表 3 的 int i， 而不是表 2 的 char i。 第 18 行印出 ’a’（表 3、表 4 已被 pop，查到表 2 的 char i）；第 19 行編譯錯誤（temp 只存在於已被 pop 的表 4）。

語法分析與文法（Parsing and Grammars）

描述語言：需要更好的工具

Nisan 與 Schocken 對 Hack 語法的描述散落在說明文字裡 ——對人讀還行，對寫解析器來說不夠精確方便。 我們需要一個高度精密的數學工具：Madlibs（填詞遊戲）！

BNF 入門

一個簡單例子： \[\begin{align*} \ensuremath{\textcolor{ntred}{\langle\text{\itshape noun}\rangle}} &\;::=\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{lecturer}'}}} \;|\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{student}'}}} \;|\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{pizza}'}}}\\ \ensuremath{\textcolor{ntred}{\langle\text{\itshape presentVerb}\rangle}} &\;::=\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{eats}'}}} \;|\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{devours}'}}} \;|\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{consumes}'}}} \end{align*}\]

每個 \(|\) 讀作「或」、每個 \(::=\) 讀作「定義為」。 例如一個 \(\textcolor{ntred}{\langle\text{\itshape noun}\rangle}\) 定義為 \(\text{\textcolor{tokblue}{`\texttt{lecturer}'}}\)、\(\text{\textcolor{tokblue}{`\texttt{student}'}}\)、 \(\text{\textcolor{tokblue}{`\texttt{pizza}'}}\) 三個字串之一。 定義可以疊起來： \[\ensuremath{\textcolor{ntred}{\langle\text{\itshape sentence}\rangle}} \;::=\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{The}'}}}\ \ensuremath{\textcolor{ntred}{\langle\text{\itshape noun}\rangle}}\ \ensuremath{\textcolor{ntred}{\langle\text{\itshape presentVerb}\rangle}}\ \ensuremath{\text{\textcolor{tokblue}{`\texttt{the}'}}}\ \ensuremath{\textcolor{ntred}{\langle\text{\itshape noun}\rangle}}\] 合法的 \(\textcolor{ntred}{\langle\text{\itshape sentence}\rangle}\) 包括 「The lecturer consumes the pizza」、 「The student eats the pizza」、 「The lecturer devours the student」。

遞迴：BNF 力量的來源

BNF 的最後一個特性是力量的來源：允許遞迴。 假設權杖是 \(\text{\textcolor{tokblue}{`\texttt{0}'}}\) 到 \(\text{\textcolor{tokblue}{`\texttt{9}'}}\)，想定義一個非終端符號 恰好匹配所有非負整數（允許前導零）： \[\begin{align*} \ensuremath{\textcolor{ntred}{\langle\text{\itshape digit}\rangle}} &\;::=\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{0}'}}} \;|\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{1}'}}} \;|\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{2}'}}} \;|\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{3}'}}} \;|\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{4}'}}} \;|\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{5}'}}} \;|\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{6}'}}} \;|\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{7}'}}} \;|\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{8}'}}} \;|\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{9}'}}}\\ \ensuremath{\textcolor{ntred}{\langle\text{\itshape number}\rangle}} &\;::=\;\ensuremath{\textcolor{ntred}{\langle\text{\itshape digit}\rangle}} \;|\;\ensuremath{\textcolor{ntred}{\langle\text{\itshape digit}\rangle}}\ \ensuremath{\textcolor{ntred}{\langle\text{\itshape number}\rangle}} \end{align*}\] 例如 016 是 \(\textcolor{ntred}{\langle\text{\itshape number}\rangle}\)，因為可以這樣展開： \[\ensuremath{\textcolor{ntred}{\langle\text{\itshape number}\rangle}} \to \ensuremath{\textcolor{ntred}{\langle\text{\itshape digit}\rangle}}\ \ensuremath{\textcolor{ntred}{\langle\text{\itshape number}\rangle}} \to \ensuremath{\textcolor{ntred}{\langle\text{\itshape digit}\rangle}}\ \ensuremath{\textcolor{ntred}{\langle\text{\itshape digit}\rangle}}\ \ensuremath{\textcolor{ntred}{\langle\text{\itshape number}\rangle}} \to \ensuremath{\textcolor{ntred}{\langle\text{\itshape digit}\rangle}}\ \ensuremath{\textcolor{ntred}{\langle\text{\itshape digit}\rangle}}\ \ensuremath{\textcolor{ntred}{\langle\text{\itshape digit}\rangle}} \to \ensuremath{\text{\textcolor{tokblue}{`\texttt{0}'}}}\ \ensuremath{\text{\textcolor{tokblue}{`\texttt{1}'}}}\ \ensuremath{\text{\textcolor{tokblue}{`\texttt{6}'}}}.\] 就這樣！這就是全部的 BNF。 用起來與推理起來可能很難，但語法本身很簡單。

練習：更好的整數

如何重新定義 \(\textcolor{ntred}{\langle\text{\itshape number}\rangle}\)，允許負數但禁止前導零？ （權杖有 \(\text{\textcolor{tokblue}{`\texttt{0}'}}\) 到 \(\text{\textcolor{tokblue}{`\texttt{9}'}}\) 和 \(\text{\textcolor{tokblue}{`\texttt{-}'}}\)。） 任何重定義的健全性檢查：

• \(\text{\textcolor{tokblue}{`\texttt{-}'}}\)\(\text{\textcolor{tokblue}{`\texttt{1}'}}\)\(\text{\textcolor{tokblue}{`\texttt{0}'}}\) 應該是 \(\textcolor{ntred}{\langle\text{\itshape number}\rangle}\)；✓

• \(\text{\textcolor{tokblue}{`\texttt{0}'}}\) 應該是 \(\textcolor{ntred}{\langle\text{\itshape number}\rangle}\)；✓

• \(\text{\textcolor{tokblue}{`\texttt{0}'}}\)\(\text{\textcolor{tokblue}{`\texttt{1}'}}\) 不應該是 \(\textcolor{ntred}{\langle\text{\itshape number}\rangle}\)；✗

• \(\text{\textcolor{tokblue}{`\texttt{-}'}}\)\(\text{\textcolor{tokblue}{`\texttt{0}'}}\) 不應該是 \(\textcolor{ntred}{\langle\text{\itshape number}\rangle}\)。✗

做法很多——BNF 的文法表達沒有唯一「正確」寫法。其中一種： \[\begin{align*} \ensuremath{\textcolor{ntred}{\langle\text{\itshape posDigit}\rangle}} &\;::=\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{1}'}}} \;|\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{2}'}}} \;|\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{3}'}}} \;|\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{4}'}}} \;|\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{5}'}}} \;|\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{6}'}}} \;|\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{7}'}}} \;|\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{8}'}}} \;|\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{9}'}}}\\ \ensuremath{\textcolor{ntred}{\langle\text{\itshape posNumber}\rangle}} &\;::=\;\ensuremath{\textcolor{ntred}{\langle\text{\itshape posDigit}\rangle}} \;|\;\ensuremath{\textcolor{ntred}{\langle\text{\itshape posNumber}\rangle}}\ \ensuremath{\textcolor{ntred}{\langle\text{\itshape posDigit}\rangle}} \;|\;\ensuremath{\textcolor{ntred}{\langle\text{\itshape posNumber}\rangle}}\ \ensuremath{\text{\textcolor{tokblue}{`\texttt{0}'}}}\\ \ensuremath{\textcolor{ntred}{\langle\text{\itshape number}\rangle}} &\;::=\;\ensuremath{\textcolor{ntred}{\langle\text{\itshape posNumber}\rangle}} \;|\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{0}'}}} \;|\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{-}'}}}\ \ensuremath{\textcolor{ntred}{\langle\text{\itshape posNumber}\rangle}} \end{align*}\] 思路：\(\textcolor{ntred}{\langle\text{\itshape posNumber}\rangle}\) 的第一個字元只能經由 \(\textcolor{ntred}{\langle\text{\itshape posDigit}\rangle}\) 產生（非零），之後可以接任何數字（包括 0）； \(\text{\textcolor{tokblue}{`\texttt{0}'}}\) 只允許單獨出現，且負號後面只能接 \(\textcolor{ntred}{\langle\text{\itshape posNumber}\rangle}\)。

解析樹（Parse Trees / CST）

以 “\(-886\)” 為例（用上面的文法）：

展開路徑：\(\textcolor{ntred}{\langle\text{\itshape number}\rangle}\) \(\to\) \(\text{\textcolor{tokblue}{`\texttt{-}'}}\) \(\textcolor{ntred}{\langle\text{\itshape posNumber}\rangle}\)； \(\textcolor{ntred}{\langle\text{\itshape posNumber}\rangle}\) \(\to\) \(\textcolor{ntred}{\langle\text{\itshape posNumber}\rangle}\) \(\textcolor{ntred}{\langle\text{\itshape posDigit}\rangle}\)（吃掉 6） \(\to\) \(\textcolor{ntred}{\langle\text{\itshape posNumber}\rangle}\) \(\textcolor{ntred}{\langle\text{\itshape posDigit}\rangle}\)（吃掉第二個 8） \(\to\) \(\textcolor{ntred}{\langle\text{\itshape posDigit}\rangle}\)（吃掉第一個 8）。

抽象語法樹（AST）

為了效率與方便，我們可以把 CST 加工成 抽象語法樹（abstract syntax tree, AST）： 相同的資訊、更方便的形式。 例如決定不需要 \(\textcolor{ntred}{\langle\text{\itshape posDigit}\rangle}\) 節點，把數字直接標在節點上：

歧義（Ambiguity）

考慮這個簡單算術運算式的文法： \[\begin{align*} \ensuremath{\textcolor{ntred}{\langle\text{\itshape expression}\rangle}} &\;::=\;\ensuremath{\textcolor{ntred}{\langle\text{\itshape number}\rangle}} \;|\;\ensuremath{\textcolor{ntred}{\langle\text{\itshape expression}\rangle}}\ \ensuremath{\textcolor{ntred}{\langle\text{\itshape operator}\rangle}}\ \ensuremath{\textcolor{ntred}{\langle\text{\itshape expression}\rangle}}\\ &\quad\;|\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{(}'}}}\ \ensuremath{\textcolor{ntred}{\langle\text{\itshape expression}\rangle}}\ \ensuremath{\textcolor{ntred}{\langle\text{\itshape operator}\rangle}}\ \ensuremath{\textcolor{ntred}{\langle\text{\itshape expression}\rangle}}\ \ensuremath{\text{\textcolor{tokblue}{`\texttt{)}'}}}\\ \ensuremath{\textcolor{ntred}{\langle\text{\itshape operator}\rangle}} &\;::=\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{+}'}}} \;|\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{-}'}}} \;|\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{*}'}}} \;|\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{/}'}}} \;|\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{\^{}}'}}} \end{align*}\] 那麼對 \((3+4)*(5-1)/3\)，解析器可以輸出好幾棵不同的合法 CST （先把 \(*\) 當根、還是先把 \(/\) 當根？）。 只要語意不歧義（此處無論哪棵樹算出來都一樣）， 這種歧義是可以接受的。 但在真實語言中（如 \(3-4-5\) 的左右結合、或懸掛 else）， 文法設計者通常會改寫文法來消除歧義。

實務上怎麼做？用解析器產生器

解析是困難而微妙、但被透徹理解的問題—— 這代表我們不該自己重新解決它！ 應該用解析器產生器（parser generator）： 把 BNF 文法餵給它，它輸出你選定語言的解析器程式碼。 （例如 C 的 yacc。）

擴充 BNF（EBNF）

解析器產生器與語言規格書常為易用性給 BNF 加語法， 但沒有統一標準。鬆散依據 ISO 14977，我們加入：

（\(A - B\) 只在 \(B\) 只能展開成有限多種權杖序列時是合法 EBNF，例如 \(\ensuremath{\textcolor{ntred}{\langle\text{\itshape number}\rangle}} - \ensuremath{\textcolor{ntred}{\langle\text{\itshape posNumber}\rangle}}\) 就不合法。）

EBNF 沒有讓 BNF 能表達任何原本表達不了的文法 （每個 EBNF 構造都能機械地改寫回純 BNF—— 分組展開、選項用兩條規則、重複用遞迴）， 但讀寫舒服得多。例如「更好的整數」變成一行： \[\ensuremath{\textcolor{ntred}{\langle\text{\itshape number}\rangle}} \;::=\;([\ensuremath{\text{\textcolor{tokblue}{`\texttt{-}'}}}]\ (\ensuremath{\textcolor{ntred}{\langle\text{\itshape digit}\rangle}} - \ensuremath{\text{\textcolor{tokblue}{`\texttt{0}'}}})\ \{\ensuremath{\textcolor{ntred}{\langle\text{\itshape digit}\rangle}}\}) \;|\;\ensuremath{\text{\textcolor{tokblue}{`\texttt{0}'}}}\] 有了 EBNF，連整個 C 語言的文法都能寫得可讀，何況 Hack！

Hack 組語的解析器

Hack 組語的 EBNF

把 Hack 形式化成 EBNF 的方式很多，以下是其中一種 （, 表示串接、; 結束一條規則—— 這是 ISO 風格 EBNF 的慣例）：

注意這個文法如何精準編碼第七週的 comp 表： \(\textcolor{ntred}{\langle\text{\itshape computation}\rangle}\) 的六個分支恰好對應常數（0、\(\pm\)1）、 單運算元（含 -、!）、加減一、 以及 D 與 A/M 的二元運算—— 文法本身就排除了 A+M 這種不存在的運算。

兩棵範例 CST

例一：0;JMP\n

例二：DM=M+D;JLE\n

LL 解析：由左往右、由上往下

逐權杖追蹤例一 0;JMP\n：

1. 讀到 0：0 只可能是一整個 \(\textcolor{ntred}{\langle\text{\itshape computation}\rangle}\)， 它必在 \(\textcolor{ntred}{\langle\text{\itshape cInstruction}\rangle}\) 裡、又必在 \(\textcolor{ntred}{\langle\text{\itshape instruction}\rangle}\) 裡 ——三個節點一次掛好。也得知這個 \(\textcolor{ntred}{\langle\text{\itshape cInstruction}\rangle}\) 沒有 \(\textcolor{ntred}{\langle\text{\itshape assignment}\rangle}\)（但可能有 \(\textcolor{ntred}{\langle\text{\itshape jump}\rangle}\)）。

2. 讀到 ;：只可能是 \(\textcolor{ntred}{\langle\text{\itshape jump}\rangle}\) 的第一項， 掛進已有的 \(\textcolor{ntred}{\langle\text{\itshape cInstruction}\rangle}\)。

3. 讀到 JMP：必是那個 \(\textcolor{ntred}{\langle\text{\itshape jump}\rangle}\) 的延續。

4. 讀到 \n：必是 \(\textcolor{ntred}{\langle\text{\itshape instruction}\rangle}\) 的結尾。完成！

若某一步下一個權杖無處可掛 （例如解析 01;JMP 中的 1 時），就回報錯誤。

逐權杖追蹤例二 DM=M+D;JLE\n——需要往前看：

1. 讀到 D：無法立刻判斷它屬於 \(\textcolor{ntred}{\langle\text{\itshape assignment}\rangle}\) 還是 \(\textcolor{ntred}{\langle\text{\itshape computation}\rangle}\)！ 解法：往前看（lookahead）第二個權杖—— 若是 M 或 =，必在 \(\textcolor{ntred}{\langle\text{\itshape assignment}\rangle}\)； 若是 +、-、&、|、 ; 或 \n，必在 \(\textcolor{ntred}{\langle\text{\itshape computation}\rangle}\)。 這裡下一個是 M，所以 D 開啟一個 \(\textcolor{ntred}{\langle\text{\itshape assignment}\rangle}\)。

2. 讀到 M：往前看見 =，確認仍在 \(\textcolor{ntred}{\langle\text{\itshape assignment}\rangle}\)。

3. 讀到 =：只能收尾這個 \(\textcolor{ntred}{\langle\text{\itshape assignment}\rangle}\)。

4. 讀到 M：往前看見 +，必在 \(\textcolor{ntred}{\langle\text{\itshape computation}\rangle}\)。

5. 讀到 +：可能是 M+1 型也可能是 M+D 型 ——再往前看一個權杖分辨；這裡是 \(\textcolor{ntred}{\langle\text{\itshape binaryOp}\rangle}\)， 並預期 \(\textcolor{ntred}{\langle\text{\itshape computation}\rangle}\) 的下一項是 D。

6. 讀到 D、;、JLE、 \n：依次完成 \(\textcolor{ntred}{\langle\text{\itshape computation}\rangle}\)、 \(\textcolor{ntred}{\langle\text{\itshape jump}\rangle}\) 與整個 \(\textcolor{ntred}{\langle\text{\itshape instruction}\rangle}\)。

實際上怎麼解析 Hack？

CST 對優雅的錯誤處理和編譯 i=(k+j++)/m 這種複雜運算式極有用，但對 Hack 來說是殺雞用牛刀。 我們實際需要知道的只有：

• 這條語句是 A-指令還是 C-指令？ （第一個權杖是不是 @？）

• 若是 A-指令，該載入 \(A\) 的值是多少？ （@ 後面是什麼？若是識別字， 查符號表拿 RAM/ROM 位址。）

• 若是 C-指令，dest、comp、jump 的值是多少？

  • = 有沒有出現？左邊有 A、D、 M 中的哪些？

  • ; 有沒有出現？右邊是哪個跳躍指令？

  • = 右邊、; 左邊是什麼？（約 30 種可能。）

這些問題全都能用對權杖的簡單邏輯回答。 （不過如果有多的時間，把 CST 做出來仍是很好的練習！）

Hack 組譯器總結

注意這把第七週（機器碼格式）與本週 （詞法＋符號表＋解析）完全接起來了： 第二趟輸出的每一行，就是查第七週那三張表得到的 16 個位元。

綜合練習題（附詳解）

練習 1：詞法分析

把下列各行 Hack 程式碼轉成權杖序列（標明 type 與 value）： (a) @R13； (b) AM=M-1  // pop； (c) @counter。

練習 2：關鍵字 vs 識別字

判斷下列字串被詞法器歸為哪一類，並說明理由： (a) ARG；(b) ARGS；(c) R16； (d) 2fast；(e) loop。

練習 3：為什麼需要換行權杖？

(a) C 完全忽略換行，為什麼我們的 Hack 詞法器不能？舉具體例子。 (b) 為什麼 ( 和 ) 不是我們的符號權杖？

練習 4：填符號表

對下列程式跑完整個組譯流程，寫出標籤表、變數表與最終輸出 （以 @位址 形式）：

@x
M=0
(loop)
@x
M=M+1
@y
D=M
@loop
D;JGT

練習 5：標籤行號的陷阱

某程式有 20 行組語，其中第 5、10、15 行（從 0 數起）是標籤宣告 (a)、(b)、(c)。 三個標籤的 ROM 位址各是多少？

練習 6：BNF 判定

用「更好的整數」文法（\(\textcolor{ntred}{\langle\text{\itshape posDigit}\rangle}\)／\(\textcolor{ntred}{\langle\text{\itshape posNumber}\rangle}\)／\(\textcolor{ntred}{\langle\text{\itshape number}\rangle}\)） 判定下列字串是否為合法 \(\textcolor{ntred}{\langle\text{\itshape number}\rangle}\)，合法者寫出展開過程： (a) -305；(b) 007；(c) 0；(d) --5。

練習 7：自己寫 BNF

寫一個 BNF 文法，權杖為 \(\text{\textcolor{tokblue}{`\texttt{0}'}}\) 與 \(\text{\textcolor{tokblue}{`\texttt{1}'}}\)， 使 \(\textcolor{ntred}{\langle\text{\itshape binary}\rangle}\) 恰好匹配無前導零的二進位正整數 （1、10、101 合法； 0、01 不合法）。再用 EBNF 重寫成一行。

練習 8：畫 CST

用第 4 章的 Hack 文法，畫出 D=D-1\n 的 CST。

練習 9：EBNF \(\to\) BNF

把下列 EBNF 規則改寫成純 BNF（可新增非終端符號）： \[\ensuremath{\textcolor{ntred}{\langle\text{\itshape list}\rangle}} \;::=\;\text{“\texttt{(}”},\ [\ensuremath{\textcolor{ntred}{\langle\text{\itshape item}\rangle}},\ \{\text{“\texttt{,}”},\ \ensuremath{\textcolor{ntred}{\langle\text{\itshape item}\rangle}}\}],\ \text{“\texttt{)}”}\] （一個括號包起來的、以逗號分隔的 item 列表，允許空列表。）

練習 10：LL(1) vs LL(2)

(a) 解釋為什麼解析器讀到 DM=M+D 的第一個 D 時， 只看這一個權杖無法決定 CST 的形狀。 (b) 往前看一個權杖後，哪些「下一個權杖」意味著 \(\textcolor{ntred}{\langle\text{\itshape assignment}\rangle}\)？ 哪些意味著 \(\textcolor{ntred}{\langle\text{\itshape computation}\rangle}\)？ (c) 0;JMP 需要 lookahead 嗎？為什麼？

練習 11：作用域堆疊

用第 2 章的 C 程式回答： (a) 在第 7 行（第一個 for 內的 printf）， 查詢 i 得到什麼型別？查詢 foo 呢？ (b) 為什麼第 18 行印出 ’a’？ (c) 為什麼第 19 行編譯錯誤？

練習 12：端到端組譯

把下列程式完整組譯成 16 位元機器碼（用第七週的編碼表）：

@5
D=A
(wait)
@wait
0;JMP

附錄：速查表

Hack 權杖分類

組譯器流程圖

EBNF 記號速查

名詞中英對照

參考資料

• John Lapinskas, Compiler concepts: Lexing／ Symbol tables／Parsing／ A parser for Hack assembly（8-1 至 8-4）， COMSM1302, University of Bristol.

• Nisan & Schocken, The Elements of Computing Systems （nand2tetris），Ch. 6（The Assembler）.

• Aho, Lam, Sethi & Ullman, Compilers: Principles, Techniques, and Tools （「龍書」——詞法、文法與解析的標準教科書）.

• ISO/IEC 14977, Extended BNF（EBNF 標準）.

• C11 標準（ISO/IEC 9899:2011）§6.4 Lexical elements （C 的權杖定義）.

• Clang 原始碼 clang/lib/Parse/ （工業級手寫遞迴下降解析器的實例）.