Nand2Tetris 第 6 週 -- 組譯器

假如 HackComputer 只有硬體的話，那麼寫起程式來將會是非常痛苦的，就算你可以用另一台電腦寫程式，然後再上傳到 HackComputer 當中，那麼你所寫的程式很可能會長得像這樣。

0000000000010000 1110111111001000 0000000000010001 1110101010001000
0000000000010000 1111110000010000 0000000000001010 1110010011010000
0000000000010010 1110001100000001 0000000000010000 1111110000010000
0000000000010001 1111000010001000 0000000000010000 1111110111001000
0000000000000100 1110101010000111 0000000000010010 1110101010000111

事實上，上述『程式』真的可以在 HackComputer 上執行，這個程式可以計算 1+...+10 的結果，其組合語言如下所示。

    // Adds 1+...+10.
    @i // i refers to some RAM location
    M=1 // i=1
    @sum // sum refers to some RAM location
    M=0 // sum=0
(LOOP)
    @i
    D=M // D = i
    @10
    D=D-A // D = i - 10
    @END
    D;JGT // If (i-100) > 0 goto END
    @i
    D=M // D = i
    @sum
    M=D+M // sum += i
    @i
    M=M+1 // i++
    @LOOP
    0;JMP // Got LOOP
(END)
    @END
    0;JMP // Infinite loop

雖然這種組合語言還是不容易閱讀和撰寫，但是總比寫那些 0 與 1 要好得多了。

本週的 nand2tetris 課程作業，就是要你寫出一個組譯器，可以將上述的組合語言轉換成由 0 與 1 組成的二進位機器碼後輸出。

這次的作業，並沒有要求要用哪一種程式語言撰寫，您可以自行選定一種自己熟悉的就行了。

當然，如果能夠用接下來的課程所要發展的 Jack 程式語言的話，那未來就有可能在 HackComputer 上撰寫這種語言了。

不過我沒有這樣做，我選擇了使用 JavaScript 來開發組譯器，寫了一個稱為 ash.js 的組譯器，並且用 io.js 當作執行工具。

以下是用 ash.js 來組譯 sum.asm 的執行過程，您可以清楚地看到組譯器的兩個階段分別做了什麼事情。

nqu-192-168-61-142:n2t mac020$ iojs ash sum
============== pass1 ================
002:0000     @i // i refers to some RAM location
003:0001     M=1 // i=1
004:0002     @sum // sum refers to some RAM location
005:0003     M=0 // sum=0
 symbol: LOOP 0004
007:0004     @i
008:0005     D=M // D = i
009:0006     @10
010:0007     D=D-A // D = i - 10
011:0008     @END
012:0009     D;JGT // If (i-100) > 0 goto END
013:0010     @i
014:0011     D=M // D = i
015:0012     @sum
016:0013     M=D+M // sum += i
017:0014     @i
018:0015     M=M+1 // i++
019:0016     @LOOP
020:0017     0;JMP // Got LOOP
 symbol: END 0018
022:0018     @END
023:0019     0;JMP // Infinite loop
============== pass2 ================
002:0000000000010000     @i // i refers to some RAM location
003:1110111111001000     M=1 // i=1
004:0000000000010001     @sum // sum refers to some RAM location
005:1110101010001000     M=0 // sum=0
007:0000000000010000     @i
008:1111110000010000     D=M // D = i
009:0000000000001010     @10
010:1110010011010000     D=D-A // D = i - 10
011:0000000000010010     @END
012:1110001100000001     D;JGT // If (i-100) > 0 goto END
013:0000000000010000     @i
014:1111110000010000     D=M // D = i
015:0000000000010001     @sum
016:1111000010001000     M=D+M // sum += i
017:0000000000010000     @i
018:1111110111001000     M=M+1 // i++
019:0000000000000100     @LOOP
020:1110101010000111     0;JMP // Got LOOP
022:0000000000010010     @END
023:1110101010000111     0;JMP // Infinite loop

組譯器的第一階段 (pass1) 是要記錄所有符號的記憶體位址，像是上述程式中的 LOOP 與 END 位址分別為 0004 和 0018，這些內容會儲存在一個稱為符號表的結構當中。

為了配合 nand2tetris 不公佈答案的政策，筆者將自己的程式碼內容抽掉，僅留下框架

function parse(line, i) {
// put your code here
}

function addSymbol(symbol) {
// put your code here
}

function pass1(lines) {
// put your code here
}

接著就可以在第二階段 (pass2) 當中把每個指令都翻譯成二進位的機器碼，然後輸出到目的黨 *.hack 當中，其方法主要是利用查表的方式查出指令各欄位的對應二進位值，然後填入到最後的二進位碼中就行了。

function pass2(lines, objFile) {
// put your code here
}

function toCode(p) {
// put your code here
}

最後，我們在主程式中呼叫上述的兩階段組譯函數，就完成了整個程式的建構。

function assemble(asmFile, objFile) {
  var asmText = fs.readFileSync(asmFile, "utf8"); // 讀取檔案到 text 字串中
  var lines   = asmText.split(/\r?\n/); // 將組合語言分割成一行一行
  pass1(lines);
  pass2(lines, objFile);
} 

接著您可以用上述程式將作業裏給的 Add.asm, Max.asm, Rect.asm, Pong.asm 等程式，組譯成機器碼之後，上傳到課程網站的作業繳交點就可以了。

以下是第六週習題的題目網址，請務必盡可能靠自己的能力完成，這樣才能深度理解這些設計的實作方法。

• http://www.nand2tetris.org/06.php

雖然兩位老師請同學不要將解答上傳到公開網路上，但還是有人上傳了，所以如果您真的做不出來或卡住了，還是可以參考一下答案，以下是 havivha 所提供的參考答案！ (他的組譯器程式是用 Python 寫的）

• https://github.com/havivha/Nand2Tetris/tree/master/06

一旦完成了組譯器之後，我們就可以進入第二階段的課程了。

在第二階段的課程當中，我們將學會『虛擬機，編譯器，作業系統』的設計方式，且讓我們拭目以待！