01 / 導讀
導讀
引用
Nystrom, R. (2021). Crafting Interpreters. Genever Benning. Free official edition: https://craftinginterpreters.com/
章節概要
第1章：引言
引言闡明瞭本書的承諾：為同一門小語言 Lox 編寫兩個完整的直譯器，展示並解釋每一行程式碼，理論比其他書少。Nystrom 認為"小語言"無處不在，構建一門語言是很有挑戰性的程式設計訓練，而且這門學問並非只屬於"巫師"。他介紹了本書的幾種編排手段（註明插入位置的程式碼片段、旁註、章末挑戰題和設計札記），說明為什麼全部手寫而不使用 Lex 和 Yacc，以及為什麼第一個直譯器用 Java、第二個用 C。
第2章：領地地圖
本章概覽語言實現的構造方式，跟隨一個程式依次經過掃描、語法分析、靜態分析、中間表示、最佳化、程式碼生成、虛擬機器和執行時。接著介紹各種捷徑，如單遍編譯器、樹遍歷直譯器、轉譯器和即時編譯，並指出"編譯器"與"直譯器"之間的界線並不清晰，因此本書兩者都講。
第3章：Lox 語言
對將要實現的語言作一次非正式的介紹：一門動態型別、帶垃圾回收、語法類似 C 的指令碼語言，具有布林值、數字、字串和 nil，常見運算子、變數、控制流、帶閉包的一等函式，以及支援單繼承的類。其中一節解釋 Lox 為什麼採用類而不是原型。設計札記比較了以表示式為核心的語言與區分表示式和語句的語言。
第4章：掃描
第二部分開始編寫 jlox，即用 Java 實現的樹遍歷直譯器。本章搭建直譯器框架（執行檔案或 REPL、報告錯誤），並手寫一個把源文本轉為記號的掃描器，涵蓋單字元和雙字元運算子、字串和數字字面量，以及按"最長匹配"原則區分關鍵字與識別符號。有一小節把詞法文法與正則語言聯絡起來，但沒有深入討論自動機。
第5–6章：表示程式碼；解析表示式
第5章介紹上下文無關文法並寫出 Lox 表示式的文法，然後用一個小型元程式生成語法樹類。它討論"表示式問題"，引入訪問者模式，並用它編寫一個簡單的樹列印器。第6章用優先順序和結合性規則消除二義性，為表示式構建遞迴下降語法分析器，並加入語法錯誤報告以及恐慌模式恢復與同步。
第7章：求值表示式
直譯器開始對錶達式樹求值，用 Java 物件表示 Lox 的值。本章定義真值規則，實現一元和二元運算子，並加入帶有清晰報告的執行時型別錯誤。設計札記權衡了靜態型別與動態型別。
第8–9章：語句與狀態；控制流
第8章加入語句、全域變數、賦值和塊作用域，用一條環境鏈實現巢狀與遮蔽。第9章在簡要介紹圖靈機和圖靈完備性之後，加入 if、短路求值的 and/or、while 和 for（後者通過脫糖轉換為 while）。
第10章：函式
使用者自定義函式登場：帶引數個數檢查的呼叫表示式、原生函式 clock()、函式宣告與函式物件、return（通過丟擲異常展開 Java 呼叫堆疊來實現），以及捕獲其環境的區域函式。
第11章：解析與繫結
當閉包遇上可變環境時會出現一個隱蔽的錯誤，因此本章加入一個靜態解析遍，在執行之前準確計算出每個變數引用指向哪個作用域。這是本書對語義分析的初步介紹，同一遍還會報告諸如在頂層程式碼中使用 return 之類的錯誤。
第12–13章：類；繼承
第12章實現類宣告、實例、欄位（get 和 set 表示式）、方法、this 和初始化方法；設計札記比較了類與原型。第13章加入單繼承和 super 呼叫，從而完成 jlox——該部分的引言稱其不到兩千行 Java 程式碼。
第14–15章：位元組碼塊；虛擬機器
第三部分用 C 從頭開始構建 clox。第14章解釋為什麼選擇位元組碼，而不是遍歷 AST（記憶體區域性差）或生成本機程式碼（複雜且不可移植），並實現以動態陣列儲存的指令塊、反組譯器、常數池和行號資訊。第15章編寫虛擬機器的分派迴圈和值堆疊，使其成為一個計算器；設計札記討論基於暫存器的位元組碼。
第16–17章：按需掃描；編譯表示式
第16章編寫只在需要時才產生記號的掃描器，並用類似字典樹的狀態機識別關鍵字。第17章編寫一個直接輸出位元組碼的單遍編譯器，採用 Pratt 語法分析器：每種記號都有字首和中綴解析函式以及一個優先順序。
第18–19章：值的型別；字串
第18章用 C 的帶標籤聯合表示動態型別的值，加入布林值和 nil 以及相應的型別檢查和執行時錯誤。第19章引入共享同一頭部的堆分配物件（"結構體繼承"），實現字串及其拼接，並維護所有物件的連結串列以便釋放；設計札記討論字串編碼。
第20章：雜湊表
用整整一章從零構建雜湊表：桶陣列與負載因子、拉鏈法與開放定址、FNV-1a 雜湊函式、線性探測、擴容、用墓碑標記刪除，以及字串駐留——它使 clox 可以通過指標比較字串。
第21–23章：全域變數；區域變數；來回跳轉
這幾章加入語句和全域變數（存放在雜湊表中）、存放在堆疊槽中並在編譯時解析的塊作用域區域變數，以及用回填技術編譯成條件跳轉和無條件跳轉的控制流。設計札記重新審視了關於 goto 的爭論。
第24–25章：呼叫與函式；閉包
作者稱第24章是一頭"巨獸"，它加入函式物件、呼叫幀、用於巢狀函式的編譯器堆疊、引數繫結、執行時堆疊跟蹤和原生函式。第25章用上值（upvalue）實現閉包：上值起初是"開啟的"（指向堆疊中），當變數離開作用域時被"關閉"（移到堆上）。
第26章：垃圾回收
虛擬機器獲得一個標記-清除垃圾回收器。本章定義可達性和根，使用三色抽象和灰色物件工作列表，把字串表作為弱引用處理，討論何時觸發回收（延遲與吞吐量的權衡，以及自適應的堆閾值），並展示如何藉助壓力測試模式查詢 GC 錯誤。
第27–29章：類與實例；方法與初始化方法；超類
物件模型用三章在 C 中重新構建：類物件和實例物件、欄位、方法和繫結方法、this、初始化方法，以及一條使方法呼叫快上數倍的最佳化呼叫指令。第29章通過把方法向下複製到子類來實現繼承，並實現 super 呼叫，從而完成整個虛擬機器。
第30章：最佳化
最後一章測量並提升效能。它討論基準測試與效能剖析，把雜湊表探測中的取模運算替換為位掩碼，並實現 NaN 裝箱，把每個值壓縮到 64 位中，後者報告的整體提升約為 10%。本章以進一步學習的建議作結，包括編譯器最佳化教材和形式化的程式設計語言理論。
附錄 I–II：Lox 文法；生成的語法樹類
附錄把完整的 Lox 文法集中在一處，並列出由第5章元程式生成的 Java 語法樹類。
核心概念
第1–3章：歡迎
- 樹遍歷直譯器與位元組碼虛擬機器：本書先後構建的兩種實現策略，以簡單性換取速度。
- Lox：一門小型、動態型別、帶垃圾回收的語言，具有閉包和類，專為被實現兩次而設計。
第4–6章：jlox 的掃描與語法分析
- 記號與詞素：詞素是原始子串；記號在其基礎上加入型別、字面量值和行號。
- 訪問者模式：在不修改每個類的前提下，為一組固定的語法樹類新增新操作的方法。
- 恐慌模式恢復：遇到語法錯誤後跳過記號，直到可能的語句邊界，使分析得以繼續並報告更多錯誤。
第7–11章：求值、狀態與函式
- 環境：從名字到值的映射，連結到外層環境以模擬巢狀作用域。
- 脫糖：把方便的語法結構（如
for）翻譯成更簡單的結構（while）來實現。 - 閉包：保留其宣告時所在環境的函式值。
- 解析器（Resolver）：在執行前把每次變數使用繫結到其宣告的靜態遍。
第12–13章：類與繼承
- 繫結方法：與存取它的實例打包在一起的方法值，使
this在之後仍然有效。 - 超類呼叫：
super.method()從包含該呼叫的類的超類開始查詢方法。
第14–19章：位元組碼、虛擬機器與值
- 位元組碼塊：緊湊的線性指令陣列，附帶常數和行號。
- Pratt 語法分析器：由每種記號的字首和中綴函式表驅動的優先順序爬升式分析器。
- 帶標籤聯合：在型別標籤旁存放各種可能載荷之聯合的 C 結構體，用於表示動態值。
第20–25章：雜湊表、變數與呼叫
- 帶墓碑的開放定址：把條目直接存放在桶陣列中，並標記已刪除的槽位，使探測序列保持完整。
- 字串駐留：每個不同的字串只保留一份，使相等比較變成指標比較。
- 上值：虛擬機器對被捕獲變數的間接引用；變數在堆疊上時為開啟狀態，移到堆上後為關閉狀態。
第26–30章：垃圾回收、物件與最佳化
- 三色標記-清除：用白、灰、黑三個集合記錄物件是未造訪、待處理還是已完全追蹤。
- NaN 裝箱：把非數字值編碼進 IEEE 754 NaN 中未使用的位模式，使每個值都能放進 64 位。
- 先剖析再最佳化：用基準測試和效能剖析器找到真正的熱點，而不是憑猜測。
評析
優點
- 每一步都有完整、可執行的程式碼。 兩個直譯器的每一行程式碼都出現在正文中，每個片段都註明應插入的檔案和函式，章節的順序保證每章結束後程序都能執行。讀者最終得到的是兩個可用的實現，而不是零散的片段。
- 同一門語言的兩種實現。 把 Lox 實現兩次，使本書能夠直接對比不同設計：環境與堆疊槽、Java 的垃圾回收器與手寫的回收器、構建 AST 的遞迴下降分析器與單遍 Pratt 編譯器。第三部分的各章開頭反覆說明 jlox 曾經視為理所當然的東西。
- 語法分析之外的工程深度。 關於雜湊表、帶上值的閉包、垃圾回收和 NaN 裝箱的章節，涵蓋了許多入門編譯器教材略過的執行時主題，並解釋了測量結果和取捨（例如以快取區域性作為放棄 AST 的理由）。
- 挑戰題與設計札記。 挑戰題把讀者推到本章內容之外（新增
break、匿名函式、BETA 式繼承、switch語句），而關於隱式分號、靜態與動態型別、"新奇度預算"等主題的設計札記則引入了語言設計方面的判斷。
局限
- 有意弱化理論。 正則語言、文法和語法分析只講到夠用為止；LL 與 LR 理論、語法分析器生成器、型別系統和形式語義都沒有涉及。需要應付編譯原理考試的學生還需要另一本教材。
- 只針對動態的解釋型目標。 Lox 沒有靜態型別，clox 編譯成自己的位元組碼而非機器碼，因此暫存器分配、指令選擇和靜態型別檢查都不在討論範圍內。
- 預設讀者掌握兩門語言。 第二部分需要能用 Java，第三部分需要熟練的 C，包括指標和手動記憶體管理；作者明確表示，如有必要應先去學 C。
- 篇幅長、推進細。 逐段程式碼的寫法使全書篇幅很長；作者也說明，程式碼是為了在書頁上清晰而寫的，並非生產環境的風格。
在課程中的定位
在本課程書單中，Crafting Interpreters 與 Douglas Thain 的 Introduction to Compilers and Language Design 是兩本入門教材，覆蓋的內容各不相同。Nystrom 為一門動態語言手寫每個階段，並深入執行時實現（閉包、垃圾回收、位元組碼虛擬機器）；Thain 則講授文法理論、Flex 和 Bison、靜態型別檢查，以及生成 X86 或 ARM 組合語言。先讀 Nystrom 可以直觀地理解一門語言從頭到尾如何運作；再讀 Thain 可以補上 Nystrom 略去的形式化語法分析內容和本機程式碼生成。
課程中內容更完整的教材——Cooper 和 Torczon 的 Engineering a Compiler 以及 Aho、Lam、Sethi 和 Ullman 的 Compilers: Principles, Techniques, and Tools——通常被認為是對編譯理論和最佳化的全面論述；Nystrom 在最後一章中也推薦把 Cooper 和 Torczon 作為學習編譯期最佳化的下一步。Pierce 的 Types and Programming Languages 則適合學習本書刻意迴避的形式化型別理論。
如何使用本書
本書面向初次接觸語言實現的程式設計師。不需要編譯器背景，但讀者應當能熟練程式設計：第二部分只用到 Java 的一個很小的子集，第三部分則要求紮實的 C 功底。
本書預期的用法是逐章把程式碼敲進去，並讓每個直譯器始終保持可執行狀態，這正是程式碼片段的設計初衷。第一部分（第1–3章）可以快速讀完。第二部分（第4–13章）是理解掃描、語法分析、求值、作用域和閉包的核心；第11章關於解析的內容篇幅不長但很重要。第三部分（第14–30章）更長也更難；第24–26章（呼叫、閉包和垃圾回收）難度最大，也值得投入。較短的課程可以在第二部分結束後停止，或者把第三部分學到第26章，把物件導向各章和第30章作為選讀。
每章至少嘗試幾道挑戰題，但要在程式碼副本中完成，因為後續章節假定直譯器保持未修改的狀態。設計札記可以單獨閱讀，作為語言設計方面的討論。本書網站提供全文，jlox 和 clox 的原始碼以 MIT 許可證釋出，可用於核對自己的實現。
版本與來源
本導讀依據 Crafting Interpreters 的免費網路版 https://craftinginterpreters.com/（正文 © 2015–2020 Robert Nystrom；印刷版 2021 年出版）。內容取材於目錄、各部分引言、第1章全文，以及全部 30 章的開篇部分、每個小節標題、挑戰題和設計札記，其中第14.1節（為何選擇位元組碼）和第30.3–30.4節（NaN 裝箱與"下一步"）為全文閱讀，另包括兩個附錄。