適讀人群 ：適合對編譯原理及語言處理器設計有興趣的讀者以及正在學習相關課程的大中專院校學生。

前百度高 級工程師、專業書《操作繫統真相還原》的作者的又一力作

業界專家聯名推薦

滴滴繫統部技術高 級總監於曉聲

阿裡巴巴螞蟻金服技術專家肖金亮

百度資 深運維工程師陳曉聰

360企業安全集團政企雲事業部技術總監馮顧

ACFUN高 級運維總監陸景玉

Mobvista運維總監黃夢溪

手把手地教讀者從零去實現一門語言，從原理到實踐事無巨細

每一步都有實際的代碼和詳盡的原理說明，讀者可以很輕松地掌握各個實現細節

實現腳本語言重要的垃圾回收（GC）、虛擬機（VM）和線程等黑技術都在本書一一呈現

本書是一本專門介紹自制編程語言的圖書，書中深入淺出地講述了如何開發一門編程語言，以及運行這門編程語言的虛擬機。本書主要內容包括：腳本語言的功能、詞法分析器、類、對像、原生方法、自上而下算符優先、語法分析、語義分析、虛擬機、內建類、垃圾回收、命令行及調試等技術。

本書適合程序員閱讀，也適合對編程語言原理感興趣的計算機從業人員學習。

鄭鋼，網名大剛，畢業於北京大學，前百度運維開發工程師，《操作繫統真像還原》作者。

愛父母，愛老婆，愛運動，愛鑽研。

本書詳細闡述了設計編程語言所需的基本理論，並且以作者自己開發設計的sparrow編程語言為例，引導讀者一步一步地實現一門完善的編程語言，本書還講解了大量的基礎類以及垃圾內存回收功能，切實幫助讀者從理論過渡到實踐，再走向實用。

—肖金亮，阿裡螞蟻金服技術專家

日常有些運維、開發的工作之所以難以開展，很多時候就受限於對底層技術的不了解，本書從獨立開發一門編程語言和虛擬機的實踐入手，對相關知識進行了闡述，講解很清楚，實現的技術很值得稱贊。

—陳曉聰，百度資深運維工程師

回顧計算機技術發展的這幾十年，編程語言層出不窮，語言特性愈發抽像，語言使用則愈發簡潔，底層機制隱藏得也越來越深。這種情況下，程序員想深入理解編程語言原理愈發困難，需要花費大量精力去學習艱深的語言設計理論並深入閱讀語言實現的源碼，但往往事倍功半，收效甚微。本書另闢蹊徑，帶領讀者從零開始自己動手實現一個編程語言及其運行環境，循序漸進，在實踐過程中透徹理解編程語言的來龍去脈。

—馮顧，360企業安全集團政企雲事業部技術總監

在雲與人工智能時代的大背景下，軟件從業者都有必要去了解一下虛擬機與一門編程語言。通過對這部分知識的了解能夠對操作繫統和語言編程有更深刻的理解。市場上介紹編程語言和操作繫統入門的書籍不多，而本書是一本較好的讀物，很值得讀者學習。

—陸景玉，ACFUN高級運維總監

自制編程語言和虛擬機，這是一個看似很深奧的課題，也涉及當今互聯網流行的兩大主題，許多技術人員對其心馳神往，但要領悟其精髓步履維艱。本書循序漸進、由淺到深地講解了豐富的基礎知識，不但覆蓋了常見的編譯原理入門，更難能可貴的是，作者講解的知識覆蓋了其獨特的理解和視角，相信本書能讓讀者能夠受益匪淺。

—黃夢溪，Mobvista運維總監

第0章一些可能令人迷惑的問題1

0.0成功的基石不是堅持，而是“不放棄”1

0.1你懂編程語言的“心”嗎2

0.2編程語言的來歷2

0.3語言一定要用更底層的語言來編寫嗎2

0.4編譯型程序和腳本程序的異同8

0.5腳本語言的分類10

0.6為什麼CPU要用數字而不是字符串作為指令11

0.7為什麼腳本語言比編譯型語言慢11

0.8既然腳本語言比較慢，為什麼大家還要用12

0.9什麼是中間代碼12

0.10什麼是編譯器的前端、後端13

0.11詞法分析、語法分析、語義分析和生成代碼並不是串行執行13

0.12什麼是符號表14

0.13什麼是關繫中的閉包14

0.14什麼是程序中的閉包15

0.15什麼是字母表16

0.16什麼是語言17

0.17正規式就是正則表達式17

0.18什麼是正規（表達）式和正規集17

0.19什麼是有窮自動機18

0.20有窮自動機與詞法分析的關繫19

0.21詞法分析用有窮自動機（有窮狀態自動機）的弊端19

0.22什麼是文法20

0.23BNF和EBNF，非終結符和終結符，開始符號及產生式21

0.24什麼是句型、句子、短語23

0.25什麼是語法分析24

0.26語法分析中的推導和歸約為什麼都要最“左”25

0.27什麼是語義分析26

0.28什麼是語法制導27

0.29詞法分析器喫的是lex，擠出來的是token27

0.30什麼是“遍”28

0.31文法為什麼可以變換28

0.32為什麼消除左遞歸和提取左因子28

0.33FIRST集、FOLLOW集、LL(1)文法29

0.34最右推導、最左歸約、句柄31

0.35算符優先分析法32

0.36算符優先文法33

0.37非終結符中常常定義的因子和項是什麼33

0.38什麼是抽像語法樹33

0.39編譯器如何使用或實現文法中的產生式34

0.40程序計數器pc與ip的區別35

第1章 設計一種面向對像腳本語言36

1.1腳本語言的功能36

1.2關鍵字37

1.3腳本的執行方式38

1.4“純手工”的開發環境38

1.5定義sparrow語言的文法38

第２章實現詞法分析器46

2.1柔性數組46

2.2什麼是字節序47

2.3一些基礎的數據結構（本節源碼stepByStep/c2/a）48

2.4定義虛擬機結構（本節源碼stepByStep/c2/b）56

2.5實現源碼讀取（本節源碼stepByStep/c2/c）57

2.6unicode與UTF-859

2.6.1什麼是unicode59

2.6.2什麼是UTF-859

2.6.3UTF-8編碼規則60

2.6.4實現UTF-8編碼、解碼（本節源碼stepByStep/c2/d）61

2.7實現詞法分析器parser（本節源碼stepByStep/c2/e）66

2.7.1lex和token66

2.7.2字符串和字符串內嵌表達式66

2.7.3單詞識別流程67

2.7.4定義token和parser68

2.7.5解析關鍵字及獲取字符71

2.7.6解析標識符和unicode碼點73

2.7.7解析字符串、內嵌表達式、轉義字符75

2.7.8跳過注釋和空行77

2.7.9獲取token79

2.7.10token匹配和初始化parser84

2.8構建主程序（本節源碼stepByStep/c2/f）85

2.9編譯、測試（本節源碼stepByStep/c2/f）88

2.9.1一個簡單的makefile88

2.9.2測試paser92

第3章類與對像95

3.1對像在C語言中的概貌95

3.2實現對像頭（本節源碼stepByStep/c3/a）96

3.3實現class定義（本節源碼stepByStep/c3/a）99

3.4實現字符串對像（本節源碼stepByStep/c3/a）101

3.5模塊對像和實例對像（本節源碼stepByStep/c3/a）103

3.6upvalue、openUpvalue和closedUpvalue106

3.7實現函數對像、閉包對像與調用框架（本節源碼stepByStep/c3/a）107

3.8完善詞法分析器之數字解析（本節源碼stepByStep/c3/b）111

3.9完善詞法分析器之字符串解析和獲取token（本節源碼stepByStep/c3/b）114

3.10最終版詞法分析器的功能驗證（本節源碼stepByStep/c3/b）116

3.11實現list列表對像（本節源碼stepByStep/c3/c）118

3.12range對像（本節源碼stepByStep/c3/c）121

3.13遲到的class.c（本節源碼stepByStep/c3/c）122

3.14map對像（本節源碼stepByStep/c3/c）124

3.14.1哈希表124

3.14.2map對像頭文件及entry125

3.14.3衝突探測鏈與偽刪除126

3.14.4map對像的實現128

3.15線程對像（本節源碼stepByStep/c3/c）134

3.15.1線程、協程淺述134

3.15.2運行時棧137

3.15.3用戶線程的實現138

第4章原生方法及基礎實現142

4.1解釋器流程（本節源碼stepBystep/c4/a）142

4.2符號表144

4.2.1模塊的符號表144

4.2.2類方法的符號表144

4.2.3模塊變量符號表146

4.2.4局部變量符號表147

4.2.5常量符號表147

4.3方法在運行時棧中的參數147

4.4定義模塊變量（本節源碼stepByStep/c4/b）148

4.5原生方法（本節源碼stepByStep/c4/b）154

4.5.1定義裸類154

4.5.2定義返回值與方法綁定的宏155

4.5.3定義原生方法157

4.5.4符號表操作159

4.5.5定義類、綁定方法、綁定基類160

4類及實現（本節源碼stepByStep/c4/b）161

4.6.1meta-class類、class類、object類161

4.6.2類，綁定類方法163

4.7加載模塊（本節源碼stepByStep/c4/c）164

4.8虛擬機簡介166

4.8.1虛擬機分類及優缺點166

4.8.2為什麼要采用虛擬機168

4.8.3虛擬機的簡單優化170

4.9字節碼171

第5章自上而下算符優先——TDOP177

5.1自上而下算符優先—TDOP177

5.2來自Douglas Crockford的教程177

5.3TDOP原理194

5.3.1一些概念194

5.3.2一個小例子196

5.3.3expression的思想197

5.3.4while（rbp < token.lbp）的意義200

5.3.5進入expression時當前token的類別201

5.3.6TDOP總結202

第6章實現語法分析與語義分析204

6.1定義指令（本節源碼stepByStep/c6/a）204

6.2核心腳本（本節源碼stepByStep/c6/a）206

6.3寫入指令（本節源碼stepByStep/c6/a）212

6.4編譯模塊（本節源碼stepByStep/c6/a）216

6.5語義分析的本質218

6.6注冊編譯函數（本節源碼stepByStep/c6/b）218

6.7賦值運算的條件221

6.8實現expression及其周邊（本節源碼stepByStep/c6/c）223

6.9局部變量作用域管理228

6.10變量聲明、中綴、前綴及混合運算符方法簽名（本節源碼stepByStep/c6/d）229

6.11解析標識符（本節源碼stepByStep/c6/e）233

6.11.1處理參數列表及相關233

6.11.2實現運算符和標識符的簽名函數235

6.11.3upvalue的查找與添加239

6.11.4變量的加載與存儲242

6.11.5編譯代碼塊及結束243

6.11.6各種方法調用246

6.11.7標識符的編譯249

6.12編譯內嵌表達式（本節源碼stepByStep/c6/f）256

6.13編譯bool及null（本節源碼stepByStep/c6/g）258

6.14this、繼承、基類（本節源碼stepByStep/c6/h）259

6.15編譯小括號、中括號及list列表字面量（本節源碼stepByStep/c6/i）260

6.16編譯方法調用和map字面量（本節源碼stepByStep/c6/j）263

6.17編譯數學運算符（本節源碼stepByStep/c6/k）266

6.18編譯變量定義（本節源碼stepByStep/c6/l）270

6.19編譯語句274

6.19.1編譯if語句（本節源碼stepByStep/c6/m）274

6.19.2編譯while語句（本節源碼stepByStep/c6/n）275

6.19.3編譯return、break和continue語句（本節源碼stepByStep/c6/o）280

6.19.4編譯for循環語句（本節源碼stepByStep/c6/p）284

6.19.5編譯代碼塊及單一語句（本節源碼stepByStep/c6/q）288

6.20編譯類定義（本節源碼stepByStep/c6/r）289

6.20.1方法的聲明與定義289

6.20.2構造函數與創建對像291

6.20.3編譯方法293

6.20.4編譯類定義296

6.21編譯函數定義（本節源碼stepByStep/c6/s）298

6.22編譯模塊導入（本節源碼stepByStep/c6/t）300

第7章虛擬機306

7.1創建類與堆棧框架（本節源碼stepByStep/c7/a）306

7.2upvalue的創建與關閉（本節源碼stepByStep/c7/b）309

7.3修正操作數（本節源碼stepByStep/c7/c）312

7.4執行指令（本節源碼stepByStep/c7/d）314

7.4.1一些基礎工作314

7.4.2解碼、譯碼、執行（本節源碼stepByStep/c7/d）316

7.5運行虛擬機（本節源碼stepByStep/c7/e）334

第8章內建類及其方法337

8.1Bool類及其方法（本節源碼stepByStep/c8/a）337

8.2線程類及其方法（本節源碼stepByStep/c8/b）338

8.3函數類及其方法和函數調用重載（本節源碼stepByStep/c8/c）345

8.4Null類及其方法（本節源碼stepByStep/c8/d）347

8.5Num類及其方法（本節源碼stepByStep/c8/e）348

8.6String類及其方法（本節源碼stepByStep/c8/f）355

8.7List類及其方法（本節源碼stepByStep/c8/g）369

8.8Map類及其方法（本節源碼stepByStep/c8/h）374

8.9range類及其方法（本節源碼stepByStep/c8/i）380

8.10System類及其方法（本節源碼stepByStep/c8/j）383

8.11收尾與測試（本節源碼stepByStep/c8/k）388

第9章垃圾回收393

9.1垃圾回收淺述393

9.2理論基礎395

9.3標記—清掃回收算法396

9.4一些基礎結構（本節源碼stepByStep/c9/a）397

9.5實現GC（本節源碼stepByStep/c9/a）400

9.6添加臨時根對像與觸發GC411

第10章 命令行及調試415

10.1釋放虛擬機（本節源碼stepByStep/c10/a）415

10.2簡單的命令行界面（本節源碼stepByStep/c10/a）415

10.3調試（本節源碼stepByStep/c10/b）417

推 薦 序

很高興能成為本書的首 批讀者，也很高興能為本書寫推薦序。

剛拿到本書手稿時，從書名上我意識到這是對我胃口的書。果然，整書閱對以後，收獲頗多。如今程序員的開發成本已經很低了，項目中有各種成熟的框架和庫可供選擇和使用，但還有人能靜下心來研究編譯器這麼底層的技術，實屬難得。本書猶如一把火炬，點燃了技術人內心對開發的熱情。

依稀記得2010年年初在百度與鄭剛初次見面的情景，那時他工作之餘的時間基本都用在向各個技術專家請教、討論各類技術問題上，他是我帶過的人中最勤奮的人之一。時間荏苒，一分耕耘一分收獲，看到他今天的成長，尤感欣慰。

本書講述了一門腳本語言（sparrow）的開發過程，這是一本“步步為營”式的書籍，延續了他編寫《操作繫統真像還原》的風格，手把手地教讀者從零實現一門語言，從原理到實踐每一步都有實際的代碼和詳盡的原理說明，通過運行書中各小節中的代碼，讀者可以很輕松地掌握各個細節，因此本書的學習曲線並不陡峭，甚至很平坦。另外，值得欣喜的是，本書所編寫的腳本語言並不是用Java、C++等入門難度略大的語言實現的，而是用C語言，這是我們學習編程的基礎語言。也就是說，本書並不需要專業的開發經驗即可上手學習。另外，在實現過程中並未用到復雜的庫函數或繫統調用， 可以負責地說，本書已經將學習成本降到最低。

C語言是一種面向過程的語言，如何用一種面向過程的語言去實現一種面向對像的語言很有意思。另外，PHP和Perl語言雖然也實現了類，但它們其實是一種面向過程的語言，並不是純粹的面向對像語言，而sparrow語言是一種純粹的面向對像語言，它在設計之初就采用對像的方式來處理腳本語言中類的成員和方法，這仿佛讓我們看到了面向對像編程語言的基因。眾所周知，當今最流行的腳本語言應屬Python，Python也是用C語言實現的，也許你很好奇Python的內部原理，但是想到它將近有 4 萬行的源代碼時，也許甚至不想看它的源程序了。那麼研讀本書中的sparrow語言會是一種更好的選擇，其源碼不足7100行，閱讀過程輕松愉快，但可以學到繫Python這種語言的實現原理。

對於腳本語言來說，兩個重要方面就是垃圾回收和運行環境。垃圾回收就是我們平時所說的GC（Garbage Collection）。有了GC，程序員不需要手工釋放所分配的對像，可以使精力專注於業務邏輯而不用擔心內存洩漏問題。在sparrow語言中同樣實現了GC，通過此部分代碼你可以看到GC 的原理，以及哪些對像纔能被回收。 運行時環境就是腳本語言中的虛擬機，即VM（如Java語言的JVM也是一種VM）。腳本語言是通過虛擬機纔能運行的，如何把編譯器生成的操作碼轉換為實際的代碼行為，這裡面的工作對大多數人來說很神秘。相信各位在源碼中一探究竟之後會發現：GC和VM這兩個神秘的黑盒子不過如此。另外，也許程序員最感興趣的就是線程，關於線程在用戶態下是如何實現的、線程如何實現調度，本書將告訴你答案。總之，但凡涉獵，開卷有益。

每個程序員都有實現屬於自己編程語言的夢想，說其是夢想，原因是實現的難度很大......這種情況一直持續到本書的出現。本書講的是純粹的技術“干貨”，符合鄭剛一貫的寫作風格，這是他靜心寫出來的東西，內容滿滿，很值得閱讀。

於曉聲

滴滴繫統部技術高 級總監