Nand2Tetris — 從 NAND 到 Tetris 的完整電腦系統

📖 課程概述

Nand2Tetris（全稱 The Elements of Computing Systems）由 Noam Nisan 和 Shimon Schocken 開發，是電腦科學領域最具影響力的專案式課程之一。從最基礎的 NAND 閘開始，逐步建構出完整電腦系統，涵蓋硬體平台、虛擬機器、編譯器和作業系統。

本頁收錄課程程式碼解答，包含每個專案的完整實作。

Part I: 硬體 (專案 1–6)

布林邏輯與算術運算
循序邏輯與記憶體
機器語言與電腦架構
組譯器

Part II: 軟體 (專案 7–12)

虛擬機器 (堆疊與控制流)
Jack 高階語言
編譯器 (語法分析與程式碼生成)
作業系統 (Math, Memory, Screen, Keyboard...)

🏗️ 完整堆疊

點擊各層查看對應專案的解決方案：

🎮 高階應用 Tetris / Pong / 任何 Jack 程式

📚 作業系統 Math, Memory, Screen, Keyboard, Output, String, Sys

🔄 編譯器 Jack → VM 指令 (詞法/語法分析 + 程式碼生成)

📝 高階語言 Jack 程式語言

⚙️ 虛擬機器 VM → Hack 組合語言 (控制流 + 函數呼叫)

📦 虛擬機器 VM → Hack 組合語言 (堆疊算術)

🔧 組譯器 Hack 組合語言 → 機器碼

💻 電腦架構 CPU + Memory + 整台 Hack 電腦

🔤 機器語言 Hack 組合語言程式設計

🧠 記憶體暫存器 → RAM → 程式計數器

➕ 布林運算半加器 → 全加器 → ALU

🔲 布林邏輯 NAND → 基本邏輯閘

⊼ NAND 唯一原始閘 — 一切從這裡開始

⚡ Part I: 硬體

布林邏輯

▶

從 NAND 閘開始，建構所有基本邏輯閘：Not, And, Or, Xor, Mux, DMux，以及它們的 16 位元和多重變體。

// Nand2Tetris 的起點 — NAND 閘
CHIP Nand {
    IN a, b;
    OUT out;
    PARTS:
    // 內建 — NAND 是唯一原始閘
}

// 從 NAND 建構 Not
CHIP Not {
    IN in;
    OUT out;
    PARTS:
    Nand(a=in, b=in, out=out);
}

// 從 NAND 建構 And
CHIP And {
    IN a, b;
    OUT out;
    PARTS:
    Nand(a=a, b=b, out=AnandB);
    Nand(a=AnandB, b=AnandB, out=out);
}

// Xor 閘
CHIP Xor {
    IN a, b;
    OUT out;
    PARTS:
    Nand(a=a, b=b, out=AnandB);
    Or(a=a, b=b, out=AorB);
    And(a=AnandB, b=AorB, out=out);
}

HDL 所有晶片解答 HDL Xor (專案 00)

布林運算

▶

建構算術運算單元：半加器、全加器、16 位元加法器、增量器，最後是完整的 ALU。

// 半加器
CHIP HalfAdder {
    IN a, b;
    OUT sum, carry;
    PARTS:
    Xor(a=a, b=b, out=sum);
    And(a=a, b=b, out=carry);
}

// 全加器
CHIP FullAdder {
    IN a, b, c;
    OUT sum, carry;
    PARTS:
    Xor(a=a, b=b, out=s1);
    Xor(a=s1, b=c, out=sum);
    And(a=a, b=b, out=ab);
    And(a=b, b=c, out=bc);
    And(a=a, b=c, out=ac);
    Or(a=ab, b=bc, out=abORbc);
    Or(a=abORbc, b=ac, out=carry);
}

HDL 所有晶片解答

記憶體

▶

從 D 型正反器出發，建構 1 位元暫存器、16 位元暫存器，逐步擴展為 RAM8 → RAM64 → RAM512 → RAM4K → RAM16K，最後是程式計數器 (PC)。

// 1-bit 暫存器
CHIP Bit {
    IN in, load;
    OUT out;
    PARTS:
    Mux(a=do, b=in, sel=load, out=mo);
    DFF(in=mo, out=do, out=out);
}

// 16-bit 暫存器
CHIP Register {
    IN in[16], load;
    OUT out[16];
    PARTS:
    Bit(in=in[0],  load=load, out=out[0]);
    Bit(in=in[1],  load=load, out=out[1]);
    // ... 共 16 個 Bit
}

// 程式計數器 (PC)
CHIP PC {
    IN in[16], load, inc, reset;
    OUT out[16];
    PARTS:
    // 支援 load/inc/reset 三種操作
    Register(in=inMux, load=loadFlag, out=out, out=regOut);
    Inc16(in=regOut, out=incOut);
    // ... Mux 鏈選擇正確的輸入
}

HDL Bit, Register, RAM8, RAM64, PC HDL RAM512, RAM4K, RAM16K

機器語言

▶

學習 Hack 組合語言，撰寫乘法 (Mult) 和螢幕控制 (Fill) 程式。Hack 有兩種指令：A 指令 (位址設定: @value) 和 C 指令 (計算+跳躍: dest=comp;jump)。

// 乘法: RAM[2] = RAM[0] * RAM[1]
// 使用反覆加法實作
   @R1
   D=M
   @END
   D;JEQ       // 如果 R1=0 則結束

   @R0
   D=M
   @END
   D;JEQ       // 如果 R0=0 則結束

   @sum
   M=0          // sum = 0
(LOOP)
   @R0
   D=M
   @sum
   M=D+M        // sum += R0
   @R1
   MD=M-1
   @LOOP
   D;JGT        // R1--; if R1>0 goto LOOP
(END)
   @sum
   D=M
   @R2
   M=D          // R2 = sum
   @END
   0;JMP        // 無窮迴圈

ASM Mult / Fill 解答

電腦架構

▶

組合 CPU、Memory、以及週邊晶片 (Screen, Keyboard)，建構完整的 Hack 電腦。CPU 包含 ALU、A 暫存器、D 暫存器、程式計數器 (PC)，執行 A 和 C 兩種指令。

CPU 核心

// CPU: ALU + A/D 暫存器 + PC
CHIP CPU {
    IN  inM[16], instruction[16], reset;
    OUT outM[16], writeM, addressM[15], pc[15];
    PARTS:
    // 指令解碼
    Or16(a=false, b=instruction, out[15]=isC,
         out[12]=a, out[11..6]=compBits,
         out[5..3]=destBits, out[2..0]=jumpBits);
    // A 暫存器
    ARegister(in=Ain, load=Aload, out=Aout);
    // D 暫存器
    DRegister(in=ALUout, load=Dload, out=Dout);
    // ALU
    ALU(x=Dout, y=AorM, ..., out=ALUout);
    // PC (程式計數器)
    PC(in=Aout, load=PCload, inc=true, reset=reset, out=pc);
}

Memory 映射

CHIP Memory {
    IN in[16], load, address[15];
    OUT out[16];
    PARTS:
    // 0x0000-0x3FFF: RAM 16K
    RAM16K(in=in, load=Mload, address=address[0..13], out=outM);
    // 0x4000-0x5FFF: Screen (8K)
    Screen(in=in, load=Sload, address=address[0..12], out=outS);
    // 0x6000: Keyboard
    Keyboard(out=outK);
}

HDL CPU.hdl, Memory.hdl, Computer.hdl

組譯器

▶

將 Hack 組合語言轉換為機器碼。支援 A 指令 (@symbol) 和 C 指令 (dest=comp;jump) 的編碼，以及標籤和變數解析。

本課程提供 C++、C 和 Python 三種實作。

// C++ 組譯器核心 — 指令編碼
void code2binary(char *code, char *binary) {
  if (code[0]=='@') { // A 指令
    int address;
    if (sscanf(code, "@%d", &address) == 1)
      int2bin(address, binary, 16);
    else { // 符號解析
      // 查 symMap: 預設符號 + 標籤 + 變數
    }
  } else { // C 指令
    // dest=comp 或 comp;jump
    // 編碼為 111 a c1 c2 c3 c4 c5 c6 d1 d2 d3 j1 j2 j3
    sprintf(binary, "111%s%s%s",
            ccode.c_str(), dcode.c_str(), jcode.c_str());
  }
}

C++ asm.cpp C vm.c, dasm.c Python asm.py 實作

🛠️ Part II: 軟體

虛擬機器 I — 堆疊算術

▶

實作 VM 轉譯器，將中間層級的 VM 指令轉換為 Hack 組合語言。本章涵蓋堆疊算術指令 (add, sub, neg, eq, gt, lt, and, or, not) 和記憶體存取 (push/pop)。

// VM 轉譯器 (C) — 算術指令範例
void write_arithmetic(FILE* out, const char* command) {
    if (strcmp(command, "add") == 0)
        fprintf(out, "@SP\nAM=M-1\nD=M\nA=A-1\nM=D+M\n");
    else if (strcmp(command, "eq") == 0) {
        fprintf(out, "@SP\nAM=M-1\nD=M\nA=A-1\nD=M-D\n");
        fprintf(out, "@TRUE_%d\nD;JEQ\n", label_count);
        // ... false 分支: D=0; true 分支: D=-1
    }
    // 其他指令: sub, neg, and, or, not, gt, lt
}

C vm2asm.c

虛擬機器 II — 程式控制

▶

擴充 VM 轉譯器以支援分支指令 (label, goto, if-goto) 和函數呼叫 (function, call, return)。實作虛擬記憶體區段 (local, argument, this, that, pointer, temp, static)。

// VM 函數呼叫轉譯
// call f nArgs: 推入 returnAddr, LCL, ARG, THIS, THAT
//               設定 ARG=SP-5-nArgs, LCL=SP, goto f
void write_call(FILE* out, const char* funcName, int nArgs) {
    fprintf(out, "@RETURN_%d\nD=A\n@SP\nAM=M+1\nA=A-1\nM=D\n",
            return_count);
    // push LCL, ARG, THIS, THAT 到堆疊
    fprintf(out, "@LCL\nD=M\n@SP\nAM=M+1\nA=A-1\nM=D\n");
    // ... 同理 for ARG, THIS, THAT
    // ARG = SP-5-nArgs, LCL = SP
    fprintf(out, "@%d\nD=A\n@SP\nD=M-D\n@ARG\nM=D\n", 5 + nArgs);
    fprintf(out, "@SP\nD=M\n@LCL\nM=D\n");
    fprintf(out, "@%s\n0;JMP\n(RETURN_%d)\n",
            funcName, return_count++);
}

C vm2asm.c (完整版)

高階語言 — Jack

▶

使用 Jack 高階語言撰寫程式。Jack 語法類似 Java/C，支援類別、方法、陣列、字串。習題包含 aⁿbⁿ、運算式解析、流程控制、函數呼叫等。

// Jack 程式範例: aⁿbⁿ (檢查 a^n b^n 字串)
class Main {
    function void main() {
        var char c;
        var int an, bn;
        let an = Keyboard.readInt("a 的個數? ");
        let bn = Keyboard.readInt("b 的個數? ");
        // 印出 an 個 'a' 和 bn 個 'b'
        while (~(an = 0)) { Output.printChar(97); let an = an - 1; }
        while (~(bn = 0)) { Output.printChar(98); let bn = bn - 1; }
        return;
    }
}

Jack 所有範例 Python 編譯器雛形

P10

編譯器 I — 語法分析

▶

實作 Jack 編譯器的詞法分析器和語法分析器，將 Jack 程式解析為 XML 語法樹。本課程以 Python 實作完整的 Jack 編譯器。

// 詞法分析器 (Lex.py) — 將 Jack 原始碼轉為 Token 串流
class JackTokenizer:
    def __init__(self, input_file):
        self.tokens = []
        self.pos = 0
        with open(input_file, 'r') as f:
            text = self.remove_comments(f.read())
            # 逐一辨識: keyword, symbol, integerConstant, stringConstant, identifier
    
    def advance(self):
        self.pos += 1
        return self.tokens[self.pos]

// 語法分析器 (Parser.py) — 遞迴下降解析
class CompilationEngine:
    def compileClass(self):
        self.eat('class')
        className = self.eatIdentifier()
        self.eat('{')
        while self.tokenType() == 'STATIC' or self.tokenType() == 'FIELD':
            self.compileClassVarDec()
        while self.tokenType() in ['CONSTRUCTOR', 'FUNCTION', 'METHOD']:
            self.compileSubroutine()
        self.eat('}')

Python 編譯器原始碼

P11

編譯器 II — 程式碼生成

▶

擴充編譯器以產生 VM 指令。包含符號表管理 (class-level 和 subroutine-level 作用域)、變數解析 (static, field, local, argument)、運算式編譯、控制流生成。

// 符號表 (SymbolTable.py)
class SymbolTable:
    def __init__(self):
        self.classTable = {}    # static, field
        self.subroutineTable = {} # arg, local
        self.fieldIndex = 0
        self.staticIndex = 0
    
    def varCount(self, kind):
        return len([v for v in (self.classTable if kind in ('static', 'field') 
                     else self.subroutineTable) 
                     if v.kind == kind])

// VM 寫入器 (VMWriter.py)
class VMWriter:
    def writePush(self, segment, index):
        self.output.append(f"push {segment} {index}")
    def writeArithmetic(self, command):
        self.output.append(f"{command}")
    def writeCall(self, name, nArgs):
        self.output.append(f"call {name} {nArgs}")

Python Compiler.py, SymbolTable.py, VMWriter.py

P12

作業系統

▶

用 Jack 語言實作 Hack 電腦的作業系統函式庫，包含以下類別：

類別	功能
Math	乘法、除法、平方根、絕對值、最大值、最小值
Memory	記憶體配置 (alloc/dealloc)、記憶體區塊操作 (peek/poke)
Screen	像素繪圖、矩形/圓/線條繪製
Output	字元/字串輸出到螢幕
Keyboard	鍵盤輸入 (readChar, readInt, readLine)
String	動態字串 (concat, substring, parseInt, setCharAt...)
Sys	系統初始化、程式終止、等待
Array	動態陣列配置

// Math.jack — 乘法 (反覆加法演算法)
function int multiply(int x, int y) {
    var int sum, shiftedX, i;
    let shiftedX = x;
    let sum = 0;
    let i = 0;
    while (i < 16) {
        if (~((y & powers_of_two[i]) = 0)) {
            let sum = sum + shiftedX;
        }
        let shiftedX = shiftedX + shiftedX;
        let i = i + 1;
    }
    return sum;
}

Jack 完整 OS 原始碼

🔗 延伸資源

Nand2Tetris 官方網站 — 課程大綱、軟體工具、教材下載
課程解答原始碼 (GitHub) — 完整實作
Nand2Tetris 簡介頁 — 課程基本介紹