自己動手構建編程語言：如何設計編譯器、解釋器和DSL

前言
第一部分　程式設計語言導論
第1章　為什麼要構建另一種程式設計語言2
1.1　編寫自己的程式設計語言的動機2
1.1.1　程式設計語言實現的類型3
1.1.2　組織位元組碼語言實現4
1.1.3　示例中使用的語言4
1.2　程式設計語言與庫的差別5
1.3　適用於其他軟體工程任務6
1.4　建立語言需求6
1.5　案例研究：Unicon語言的創建需求8
1.5.1　Unicon需求#1—保留人們對Icon的喜愛8
1.5.2　Unicon需求#2—支援大型大資料項目目9
1.5.3　Unicon需求#3—現代應用程式的高級輸入/輸出9
1.5.4　Unicon需求#4—提供可實現的通用系統介面9
1.6　本章小結10
1.7　思考題10
第2章　程式設計語言設計11
2.1　確定要程式設計語言提供的單詞和標點符號的類型11
2.2　指定控制流13
2.3　決定支援哪種資料14
2.3.1　原子類型14
2.3.2　複合類型15
2.3.3　領域特定類型16
2.4　整體程式結構16
2.5　完成Jzero語言的定義17
2.6　案例研究：設計Unicon中的圖形功能18
2.6.1　2D圖形語言支援18
2.6.2　添加3D圖形支援20
2.7　本章小結21
2.8　思考題21
第3章　掃描原始程式碼22
3.1　技術需求22
3.2　詞素、詞類和標記23
3.3　規則運算式24
3.3.1　規則運算式規則24
3.3.2　規則運算式示例25
3.4　使用UFlex和JFlex26
3.4.1　頭部分26
3.4.2　規則運算式部分27
3.4.3　編寫一個簡單的原始程式碼掃描器27
3.4.4　運行掃描器30
3.4.5　標記和詞法屬性31
3.4.6　擴展示例以構造標記31
3.5　為Jzero編寫掃描器34
3.5.1　Jzero Flex規範34
3.5.2　Unicon Jzero代碼36
3.5.3　Java Jzero代碼39
3.5.4　運行Jzero掃描器42
3.6　規則運算式並不總是足夠的44
3.7　本章小結46
3.8　思考題47
第4章　解析48
4.1　技術需求48
4.2　語法分析49
4.3　理解上下文無關文法49
4.3.1　編寫上下文無關文法規則50
4.3.2　編寫程式設計構造規則51
4.4　使用iyacc和BYACC/J53
4.4.1　聲明頭部分中的符號53
4.4.2　組合yacc上下文無關文法部分54
4.4.3　理解yacc解析器55
4.4.4　修復yacc解析器中的衝突56
4.4.5　語法錯誤修復57
4.4.6　組合簡單示例57
4.5　為Jzero編寫解析器62
4.5.1　Jzero lex規範62
4.5.2　Jzero yacc規範62
4.5.3　Unicon Jzero代碼66
4.5.4　Java Jzero解析器代碼68
4.5.5　運行Jzero解析器69
4.6　改進語法錯誤消息70
4.6.1　向Unicon語法錯誤消息添加詳細資訊71
4.6.2　向Java語法錯誤消息添加詳細信息71
4.6.3　使用Merr生成更好的語法錯誤消息72
4.7　本章小結72
4.8　思考題73
第5章　語法樹74
5.1　技術需求74
5.2　GNU make的使用75
5.3　樹77
5.3.1　定義語法樹類型78
5.3.2　解析樹與語法樹79
5.4　從終結符創建葉子81
5.4.1　用葉子包裝標記81
5.4.2　使用YACC的值棧82
5.4.3　為解析器的值棧包裝葉子83
5.4.4　確定需要哪些葉子84
5.5　從產生式規則構建內部節點85
5.5.1　訪問值棧上的樹節點85
5.5.2　使用樹節點工廠方法86
5.6　為Jzero語言形成語法樹88
5.7　調試並測試語法樹93
5.7.1　避免常見的語法樹錯誤94
5.7.2　以文本格式輸出語法樹95
5.7.3　使用dot輸出語法樹96
5.8　本章小結101
5.9　思考題101

第二部分　語法樹遍歷
第6章　符號表104
6.1　技術需求104
6.2　建立符號表基礎105
6.2.1　聲明和作用域105
6.2.2　賦值和取消引用變數106
6.2.3　選擇正確的樹遍歷106
6.3　為每個作用域創建和填充符號表107
6.3.1　向語法樹添加語義屬性108
6.3.2　定義符號表和符號表條目的類109
6.3.3　創建符號表110
6.3.4　填充符號表112
6.3.5　綜合isConst屬性114
6.4　檢查未聲明的變數115
6.4.1　識別方法體115
6.4.2　探索方法體中變數的使用116
6.5　查找重新聲明的變數118
6.5.1　將符號插入符號表118
6.5.2　報告語意錯誤119
6.6　在Unicon中處理包和類作用域119
6.6.1　名稱修飾120
6.6.2　為成員變數引用插入self120
6.6.3　在方法調用中插入self作為第一個參數121
6.7　測試和調試符號表122
6.8　本章小結123
6.9　思考題124
第7章　基本類型檢查125
7.1　技術需求125
7.2　編譯器中的類型表示125
7.2.1　定義表示類型的基類126
7.2.2　子類化複雜類型的基類127
7.3　將類型資訊分配給聲明的變數129
7.3.1　從保留字合成類型130
7.3.2　將類型繼承到變數清單中131
7.4　確定每個語法樹節點的類型132
7.4.1　確定葉子的類型133
7.4.2　計算和檢查內部節點的類型135
7.5　Unicon中的運行時類型檢查和類型推斷139
7.6　本章小結140
7.7　思考題140
第8章　檢查陣列、方法調用和結構訪問的類型142
8.1　技術需求142
8.2　檢查陣列類型的操作142
8.2.1　處理陣列變數聲明143
8.2.2　在陣列創建期間檢查類型143
8.2.3　在陣列訪問期間檢查類型145
8.3　檢查方法調用146
8.3.1　計算參數和返回類型資訊147
8.3.2　檢查每個方法調用網站的類型149
8.3.3　檢查返回語句中的類型152
8.4　檢查結構化類型訪問153
8.4.1　處理執行個體變數聲明154
8.4.2　在創建實例時檢查類型154
8.4.3　在實例訪問時檢查類型157
8.5　本章小結159
8.6　思考題160
第9章　中間代碼生成161
9.1　技術需求161
9.2　準備生成代碼161
9.2.1　為什麼要生成中間代碼162
9.2.2　瞭解生成程式的存儲區域162
9.2.3　為中間代碼引入資料類型163
9.2.4　將中間代碼屬性添加到樹中165
9.2.5　生成標籤和臨時變數165
9.3　中間代碼指令集168
9.3.1　指令168
9.3.2　聲明168
9.4　用標籤為控制流注釋語法樹 169
9.5　為運算式生成代碼171
9.6　為控制流生成代碼173
9.6.1　為條件運算式生成標籤目標174
9.6.2　生成迴圈代碼177
9.6.3　為方法調用生成中間代碼178
9.6.4　檢查生成的中間代碼179
9.7　本章小結180
第10章　IDE中的語法著色182
10.1　下載本章中使用的示例IDE183
10.2　將編譯器集成到程式師的編輯器中184
10.2.1　從IDE中分析原始程式碼185
10.2.2　將編譯器輸出發送到IDE185
10.3　避免在每次更改時重新解析整個文件186
10.4　使用詞法資訊為標記著色189
10.4.1　擴展EditableTextList組件以支援顏色189
10.4.2　在繪製單個標記時對其進行著色190
10.5　使用解析結果突出顯示錯誤191
10.6　添加Java支持192
10.7　本章小結194

第三部分　代碼生成與運行時系統
第11章　位元組碼解譯器196
11.1　技術需求196
11.2　什麼是位元組碼196
11.3　比較位元組碼和中間碼198
11.4　為Jzero構建位元組碼指令集200
11.4.1　定義Jzero位元組碼檔案格式200
11.4.2　瞭解棧機操作的基礎知識202
11.5　實現位元組碼解譯器203
11.5.1　將位元組碼載入到記憶體中203
11.5.2　初始化解譯器狀態205
11.5.3　獲取指令並推進指令指標206
11.5.4　指令解碼207
11.5.5　執行指令208
11.5.6　啟動Jzero解譯器211
11.6　編寫Jzero運行時系統212
11.7　運行Jzero程式213
11.8　檢查Unicon位元組碼解譯器iconx213
11.8.1　瞭解目標導向的位元組碼214
11.8.2　在運行時保留類型資訊214
11.8.3　獲取、解碼和執行指令214
11.8.4　製作運行時系統的其餘部分215
11.9　本章小結215
11.10　思考題215
第12章　生成位元組碼217
12.1　技術需求217
12.2　轉換中間代碼為Jzero位元組碼217
12.2.1　為位元組碼指令添加類218
12.2.2　將中間代碼位址映射到位元組碼位址219
12.2.3　實現位元組碼生成器方法220
12.2.4　為簡單運算式生成位元組碼221
12.2.5　生成指針操作的代碼223
12.2.6　為分支和條件分支生成位元組碼224
12.2.7　為方法調用和返回生成代碼225
12.2.8　處理中間代碼中的標籤和其他虛擬指令226
12.3　比較位元組碼組合語言程式與二進位格式227
12.3.1　以彙編格式輸出位元組碼227
12.3.2　以二進位格式輸出位元組碼229
12.4　連結、載入並包括運行時系統230
12.5　Unicon示例：icont中的位元組碼生成230
12.6　本章小結232
12.7　思考題232
第13章　生成本機代碼233
13.1　技術需求233
13.2　決定是否生成本機代碼233
13.3　x64指令集234
13.3.1　為x64指令添加類234
13.3.2　將記憶體區域映射到基於x64寄存器的位址模式235
13.4　使用寄存器235
13.4.1　從空策略開始236
13.4.2　分配寄存器以加速本地區域237
13.5　將中間代碼轉換為x64代碼239
13.5.1　將中間代碼位址映射到x64記憶體位址240
13.5.2　實現x64代碼生成器方法243
13.5.3　生成簡單運算式的x64代碼244
13.5.4　生成指針操作的代碼245
13.5.5　為分支和條件分支生成本機代碼246
13.5.6　為方法調用和返回生成代碼247
13.5.7　處理標籤和虛擬指令249
13.6　生成x64輸出250
13.6.1　以組合語言格式編寫x64代碼251
13.6.2　從本機組合語言程式到目的檔案251
13.6.3　連結、載入並包括運行時系統252
13.7　本章小結253
13.8　思考題253
第14章　運算子和內置函數的實現254
14.1　實現運算子254
14.1.1　運算子是否需要硬體支援255
14.1.2　在中間代碼生成中添加字元串連接255
14.1.3　為位元組碼解譯器添加字元串連接257
14.1.4　將字元串連接添加到本機運行時系統259
14.2　編寫內置函數260
14.2.1　向位元組碼解譯器添加內置函數260
14.2.2　編寫用於本機代碼實現的內置函數261
14.3　集成內建群組件與控制結構262
14.4　為Unicon開發運算子和函數262
14.4.1　在Unicon中編寫運算子263
14.4.2　開發Unicon的內置函數265
14.5　本章小結266
14.6　思考題266
第15章　域控制結構267
15.1　瞭解何時需要新的控制結構267
15.1.1　定義控制結構268
15.1.2　減少過多的冗餘參數268
15.2　Icon和Unicon中的字串掃描269
15.2.1　掃描環境及其基本操作270
15.2.2　通過控制結構消除過多參數271
15.3　Unicon中的渲染區域271
15.3.1　從顯示清單渲染3D圖形272
15.3.2　使用內置函數指定渲染區域272
15.3.3　使用嵌套渲染區域更改圖形細節層次273
15.3.4　創建渲染區域控制結構274
15.4　本章小結278
15.5　思考題278
第16章　垃圾收集279
16.1　認識垃圾收集的重要性279
16.2　物件的引用計數281
16.2.1　將引用計數添加到Jzero281
16.2.2　生成堆分配代碼281
16.2.3　為設定運算子修改生成的代碼283
16.2.4　引用計數的缺點和局限性283
16.3　標記即時資料並清理剩餘資料284
16.3.1　組織堆記憶體區域285
16.3.2　遍歷基本變數以標記即時數據286
16.3.3　回收即時記憶體並將其放入連續區塊290
16.4　本章小結293
16.5　思考題293
第17章　結語294
17.1　反思從編寫這本書中學到的東西294
17.2　決定何去何從295
17.2.1　學習程式設計語言設計295
17.2.2　學習如何實現解譯器和字節碼機器296
17.2.3　獲取代碼優化方面的專業知識297
17.2.4　監視和偵錯工具執行297
17.2.5　設計和實現IDE和GUI構建器298
17.3　延伸閱讀的參考資料298
17.4　本章小結301

第四部分　附錄
附錄A　Unicon基礎304
附錄B　部分章節要點324