導論

童話故事比真實更真實：不是因為它們告訴我們龍的存在，而是因為它們告訴我們龍是可以被擊敗的。

G.K. Chesterton，透過 Neil Gaiman，《鬼媽媽》

我很高興我們能一起踏上這段旅程。這是一本關於實作程式語言直譯器的書。它也是一本關於如何設計一個值得實作的語言的書。這是我剛開始接觸語言時希望擁有的書，也是我在腦海中構思了近十年的書。

在這本書中，我們將逐步完成兩個功能完整的語言直譯器。我假設這是你第一次涉足程式語言，所以我會涵蓋你需要的所有概念和程式碼，以建構一個完整、可用、快速的語言實作。

為了在不讓本書變成磚頭書的情況下塞進兩個完整的實作，本文在理論上比其他書籍更為簡略。在我們建構系統的每個部分時，我將介紹其背後的歷史和概念。我會盡量讓你熟悉術語，這樣如果你發現自己身處一個充滿程式語言（PL）研究人員的雞尾酒派對時，你就能融入其中。

但我們大部分的時間都將花在讓語言啟動並運行上。這並不是說理論不重要。當你處理一個語言時，能夠精確且正式地推理語法和語義是一項重要的技能。但是，就我個人而言，我認為實作是最好的學習方式。我難以理解充滿抽象概念的段落並真正吸收它們。但是如果我編寫了一些程式碼，運行它並進行除錯，那麼我就可以理解它。

這就是我對你的目標。我希望你能對真實語言的運作方式有一個紮實的直覺。我希望當你以後閱讀其他更具理論性的書籍時，那裡的概念能夠牢固地印在你的腦海中，並依附在這個有形的基礎上。

1.1為什麼要學習這些東西？

每本編譯器入門書籍似乎都有這一節。我不知道程式語言有什麼特別之處會引起如此存在的疑慮。我不認為鳥類學書籍會擔心證明它們的存在。它們假設讀者喜歡鳥類並開始教學。

但是程式語言有點不同。我認為我們之中任何人創造出一種廣泛成功、通用的程式語言的可能性都很小。世界上廣泛使用的語言的設計者可以擠進一輛福斯巴士，即使不把露營車的車頂升起來也可以。如果加入這個菁英團體是學習語言的唯一原因，那就很難證明其合理性。幸運的是，情況並非如此。

1.1.1小語言無處不在

對於每一個成功的通用語言，都有數千個成功的利基語言。我們過去稱它們為「小語言」，但行話經濟中的通貨膨脹導致了「領域特定語言」的名稱。這些是為特定任務量身打造的混合語言。想想應用程式腳本語言、範本引擎、標記格式和組態檔。

幾乎每個大型軟體專案都需要這些語言。當你可以時，最好重複使用現有的語言，而不是自己重新開發。一旦你考慮到文件、除錯器、編輯器支援、語法高亮和其他所有相關的事物，你自己做就會變得非常困難。

但是，當沒有符合你需求的現有函式庫時，你仍然很有可能需要臨時編寫一個解析器或其他工具。即使你重複使用一些現有的實作，你也不可避免地需要除錯和維護它，並在其內部進行探索。

1.1.2語言是很好的練習

長跑運動員有時會在腳踝上綁上重物或在高海拔地區（空氣稀薄）進行訓練。當他們後來卸下重負時，輕盈的四肢和富含氧氣的空氣帶來的相對輕鬆感使他們能夠跑得更遠、更快。

實作一種語言是對程式設計技能的真正考驗。程式碼很複雜且對效能至關重要。你必須精通遞迴、動態陣列、樹狀結構、圖形和雜湊表。你可能至少在日常程式設計中使用雜湊表，但你真的了解它們嗎？好吧，在我們從頭開始打造我們自己的雜湊表之後，我保證你會了解。

雖然我打算向你展示直譯器並不像你想像的那麼令人生畏，但實作一個好的直譯器仍然是一項挑戰。接受它，你會成為一個更強大的程式設計師，並且更了解如何在你的日常工作中使用資料結構和演算法。

1.1.3還有一個原因

這最後一個原因我很難承認，因為它深深地觸動了我的內心。自從我小時候學會程式設計以來，我就覺得語言有種神奇的魔力。當我第一次一次一個鍵地輸入 BASIC 程式時，我無法想像 BASIC 本身是如何製作的。

後來，當我的大學朋友們在談論他們的編譯器課程時，臉上充滿敬畏和恐懼的表情足以讓我相信語言駭客是不同類型的人類—某種被賦予訪問神秘藝術特權的巫師。

這是一個迷人的形象，但它有一個陰暗面。我不覺得自己像個巫師，所以我認為自己缺乏加入陰謀集團所必需的某種天賦。雖然我一直對在學校筆記本上塗鴉自創的關鍵字很著迷，但我花了數十年的時間才鼓起勇氣真正去學習它們。那種「神奇」的特質，那種排他感，將我排除在外。

當我終於開始拼湊我自己的小直譯器時，我很快就了解到，當然，根本沒有什麼魔法。這只是程式碼，而那些對語言進行駭客攻擊的人只是普通人。

確實有一些你在語言之外不常遇到的技巧，而且有些部分有點困難。但不會比你克服的其他障礙更困難。我希望，如果你一直對語言感到害怕，而這本書可以幫助你克服這種恐懼，也許我會讓你比以前稍微勇敢一點。

而且，誰知道呢，也許你會創造出下一個偉大的語言。總得有人做。

1.2本書的組織方式

本書分為三個部分。你現在正在閱讀第一部分。這是幾個章節，讓你了解情況，教你一些語言駭客使用的術語，並向你介紹我們將要實作的語言 Lox。

其他兩個部分中的每一部分都建構一個完整的 Lox 直譯器。在這些部分中，每一章的結構都相同。該章節會介紹單一的語言功能、教你其背後的概念，並逐步引導你完成實作。

我花了很多時間進行試錯，但我設法將兩個直譯器分成章節大小的區塊，這些區塊建立在前幾章的基礎上，但不需要後面的章節中的任何內容。從第一章開始，你將擁有一個可以運行和使用的工作程式。隨著章節的推進，它的功能會越來越完整，直到你最終擁有一種完整的語言。

除了大量、精彩的英文散文之外，各章還具有其他一些令人愉快的功能

1.2.1程式碼

我們正在打造直譯器，因此本書包含真實的程式碼。其中包含所需的每一行程式碼，並且每個程式碼片段都會告訴你將其插入到你不斷增長的實作中的哪個位置。

許多其他語言書籍和語言實作都使用像 Lex 和 Yacc 這樣的工具，也就是所謂的 編譯器產生器，它們會從一些高階描述中自動產生實作的一些原始程式檔。對於這些工具來說，各有優缺點，而且雙方都有強烈的意見—有些人可能會說這是宗教信仰—。

我們將在這裡避免使用它們。我想確保沒有魔法和困惑可以隱藏的陰暗角落，因此我們將手寫所有內容。你會發現，它並不像聽起來那麼糟糕，而且這意味著你真的會了解每一行程式碼以及兩個直譯器是如何工作的。

本書與「現實世界」有不同的限制，因此這裡的程式碼風格可能並不總是反映編寫可維護的生產軟體的最佳方式。如果我對，例如，省略 private 或宣告全域變數顯得有些漫不經心，請理解我這樣做是為了讓程式碼更容易閱讀。這裡的頁面不像你的 IDE 那麼寬，而且每個字元都很重要。

此外，程式碼沒有太多註解。那是因為每幾行程式碼都被幾段真實的散文所包圍，解釋了它。當你編寫一本書來配合你的程式時，你也歡迎省略註解。否則，你可能應該比我更常使用 //。

雖然本書包含每一行程式碼並說明每個程式碼的含義，但它並未描述編譯和運行直譯器所需的機制。我假設你可以組合一個 makefile 或在你的 IDE 中建立一個專案，以便讓程式碼運行。這些類型的說明很快就會過時，而且我希望本書像 XO 白蘭地一樣歷久彌新，而不是後院的私釀酒。

1.2.2程式碼片段

由於本書包含實作所需的每一行程式碼，程式碼片段非常精確。此外，由於我嘗試讓程式即使在缺少主要功能時仍保持可執行狀態，因此有時我們會加入臨時程式碼，這些程式碼會在後續的程式碼片段中被替換。

一個完整的程式碼片段看起來像這樣

      default:

        if (isDigit(c)) {
          number();
        } else {
          Lox.error(line, "Unexpected character.");
        }

        break;

在中間，你會看到要加入的新程式碼。它可能在上方或下方有一些淡出的程式碼行，以顯示它在現有程式碼中的位置。還有一小段文字告訴你程式碼片段所在的檔案以及放置位置。如果那段文字說「替換 _ 行」，則在淡出的行之間有一些現有的程式碼，你需要將其刪除並替換為新的程式碼片段。

1 . 2 . 3題外話

題外話包含人物傳記、歷史背景、相關主題的參考資料，以及其他可探索領域的建議。它們沒有任何你必須知道才能理解本書後續部分的東西，所以如果你願意，可以跳過它們。我不會批評你，但我可能會有點難過。

1 . 2 . 4挑戰

每章的結尾都會有一些練習。與教科書中傾向於複習你已經學過的內容的問題集不同，這些練習旨在幫助你學習比章節中更多的內容。它們迫使你離開引導的路徑，自己探索。它們會讓你研究其他語言、弄清楚如何實作功能，或者讓你離開你的舒適區。

克服這些挑戰，你將會對它有更廣泛的理解，並可能有一些磕磕碰碰。或者，如果你想待在遊覽車的舒適範圍內，也可以跳過它們。這是你的書。

1 . 2 . 5設計筆記

大多數「程式語言」書籍嚴格來說是程式語言實作書籍。它們很少討論人們可能如何設計正在實作的語言。實作很有趣，因為它是如此精確定義的。我們程式設計師似乎對黑白分明、只有一和零的事物有著親和力。

就我個人而言，我認為世界上只需要那麼多的 FORTRAN 77 實作。在某些時候，你會發現自己正在設計一種新的語言。一旦你開始玩那個遊戲，那麼等式中較柔和、人性化的一面就變得至關重要。例如哪些功能容易學習、如何平衡創新和熟悉度、哪種語法更易讀以及對誰而言。

所有這些東西都深深地影響著你的新語言的成功。我希望你的語言能夠成功，所以在某些章節中，我會以「設計筆記」結尾，這是一篇關於程式語言人性化方面的小文章。我不是這方面的專家—我不確定是否真的有人是—所以請帶著大量的懷疑來看待這些。這應該使它們成為更美味的思考食糧，這也是我的主要目標。

1 . 3第一個直譯器

我們將用 Java 編寫我們的第一個直譯器 jlox。重點在於概念。我們將編寫最簡單、最乾淨的程式碼，以正確實作該語言的語義。這將使我們熟悉基本技術，並加深我們對該語言應如何運作的理解。

Java 是這方面的好語言。它的層次夠高，我們不會被繁瑣的實作細節所淹沒，但它仍然非常明確。與腳本語言不同，引擎蓋下往往隱藏著較少的複雜機制，並且你可以使用靜態類型來查看你正在使用的資料結構。

我選擇 Java 的另一個特別原因是因為它是一種物件導向的語言。這種範式在 90 年代席捲了程式設計界，現在是數百萬程式設計師的主要思考方式。你很有可能已經習慣將程式碼組織成類別和方法，所以我們會讓你待在那個舒適區。

雖然學術界的語言人士有時會看不起物件導向語言，但現實情況是，它們甚至廣泛用於語言工作。GCC 和 LLVM 是用 C++ 編寫的，大多數 JavaScript 虛擬機也是如此。物件導向語言無處不在，而且語言的工具和編譯器通常是用相同的語言編寫的。

最後，Java 非常受歡迎。這意味著你很有可能已經了解它，因此你不需要學習太多東西就能在本書中上手。如果你不太熟悉 Java，請不要驚慌。我試著堅持使用它相當小的子集。我使用了 Java 7 中的菱形運算子來使事情更簡潔一些，但就「進階」功能而言，就差不多是這樣了。如果你了解其他物件導向語言，例如 C# 或 C++，你可以應付得來。

在第二部分的結尾，我們將有一個簡單、可讀的實作。它不是很快速，但它是正確的。但是，我們只能透過建立在 Java 虛擬機器自身的執行時設施的基礎上才能實現這一點。我們想學習 Java 本身如何實作這些東西。

1 . 4第二個直譯器

因此，在下一部分中，我們將重新開始，但這次是用 C 語言。C 語言是理解實作如何真正運作的完美語言，一直到記憶體中的位元組和流經 CPU 的程式碼。

我們使用 C 的一個重要原因是，我可以向你展示 C 特別擅長的事情，但這確實意味著你需要對它非常熟悉。你不必是 Dennis Ritchie 的轉世，但你也不應該被指標嚇到。

如果你還沒有達到這個程度，請拿起一本 C 語言入門書並咀嚼它，然後在完成後再回來這裡。作為回報，你將從本書中成為更強大的 C 語言程式設計師。鑑於有許多語言實作是用 C 語言編寫的，這非常有用：Lua、CPython 和 Ruby 的 MRI，僅舉幾例。

在我們的 C 語言直譯器 clox 中，我們被迫自己實作所有 Java 免費提供的東西。我們將編寫自己的動態陣列和雜湊表。我們將決定物件如何在記憶體中表示，並建立一個垃圾收集器來回收它們。

我們的 Java 實作側重於正確性。現在我們已經掌握了這一點，我們將轉向同時追求快速。我們的 C 語言直譯器將包含一個 編譯器，該編譯器將 Lox 翻譯為高效的位元組碼表示形式（別擔心，我會很快講到那是什麼意思），然後執行它。這與 Lua、Python、Ruby、PHP 和許多其他成功語言的實作所使用的技術相同。

我們甚至會嘗試基準測試和最佳化。最後，我們將為我們的語言提供一個穩健、準確、快速的直譯器，能夠跟上其他專業水準的實作。對於一本書和幾千行程式碼來說，這還不錯。