自己動(dòng)手構(gòu)建編程語言：如何設(shè)計(jì)編譯器、解釋器和DSL

Contents　目　錄
前言
第一部分　編程語言導(dǎo)論
第1章　為什么要構(gòu)建另一種編程
　　　　語言2
1.1　編寫自己的編程語言的動(dòng)機(jī)2
1.1.1　編程語言實(shí)現(xiàn)的類型3
1.1.2　組織字節(jié)碼語言實(shí)現(xiàn)4
1.1.3　示例中使用的語言4
1.2　編程語言與庫的差別5
1.3　適用于其他軟件工程任務(wù)6
1.4　建立語言需求6
1.5　案例研究：Unicon語言的創(chuàng)建需求8
1.5.1　Unicon需求#1—保留人們
　　　對(duì)Icon的喜愛8
1.5.2　Unicon需求#2—支持大型
　　　大數(shù)據(jù)項(xiàng)目9
1.5.3　Unicon需求#3—現(xiàn)代應(yīng)用
　　　程序的高級(jí)輸入/輸出9
1.5.4　Unicon需求#4—提供可實(shí)
　　　現(xiàn)的通用系統(tǒng)接口9
1.6　本章小結(jié)10
1.7　思考題10
第2章　編程語言設(shè)計(jì)11
2.1　確定要編程語言提供的單詞和
　　 標(biāo)點(diǎn)符號(hào)的類型11
2.2　指定控制流13
2.3　決定支持哪種數(shù)據(jù)14
2.3.1　原子類型14
2.3.2　復(fù)合類型15
2.3.3　領(lǐng)域特定類型16
2.4　整體程序結(jié)構(gòu)16
2.5　完成Jzero語言的定義17
2.6　案例研究：設(shè)計(jì)Unicon中的圖形
　　 功能18
2.6.1　2D圖形語言支持18
2.6.2　添加3D圖形支持20
2.7　本章小結(jié)21
2.8　思考題21
第3章　掃描源代碼22
3.1　技術(shù)需求22
3.2　詞素、詞類和標(biāo)記23
3.3　正則表達(dá)式24
3.3.1　正則表達(dá)式規(guī)則24
3.3.2　正則表達(dá)式示例25
3.4　使用UFlex和JFlex26
3.4.1　頭部分26
3.4.2　正則表達(dá)式部分27
3.4.3　編寫一個(gè)簡單的源代碼掃
　　　描器27
3.4.4　運(yùn)行掃描器30
3.4.5　標(biāo)記和詞法屬性31
3.4.6　擴(kuò)展示例以構(gòu)造標(biāo)記31
3.5　為Jzero編寫掃描器34
3.5.1　Jzero Flex規(guī)范34
3.5.2　Unicon Jzero代碼36
3.5.3　Java Jzero代碼39
3.5.4　運(yùn)行Jzero掃描器42
3.6　正則表達(dá)式并不總是足夠的44
3.7　本章小結(jié)46
3.8　思考題47
第4章　解析48
4.1　技術(shù)需求48
4.2　語法分析49
4.3　理解上下文無關(guān)文法49
4.3.1　編寫上下文無關(guān)文法規(guī)則50
4.3.2　編寫編程構(gòu)造規(guī)則51
4.4　使用iyacc和BYACC/J53
4.4.1　聲明頭部分中的符號(hào)53
4.4.2　組合yacc上下文無關(guān)文法
　　　部分54
4.4.3　理解yacc解析器55
4.4.4　修復(fù)yacc解析器中的沖突56
4.4.5　語法錯(cuò)誤修復(fù)57
4.4.6　組合簡單示例57
4.5　為Jzero編寫解析器62
4.5.1　Jzero lex規(guī)范62
4.5.2　Jzero yacc規(guī)范62
4.5.3　Unicon Jzero代碼66
4.5.4　Java Jzero解析器代碼68
4.5.5　運(yùn)行Jzero解析器69
4.6　改進(jìn)語法錯(cuò)誤消息70
4.6.1　向Unicon語法錯(cuò)誤消息添加
　　　詳細(xì)信息71
4.6.2　向Java語法錯(cuò)誤消息添加詳
　　　細(xì)信息71
4.6.3　使用Merr生成更好的語法錯(cuò)
　　　誤消息72
4.7　本章小結(jié)72
4.8　思考題73
第5章　語法樹74
5.1　技術(shù)需求74
5.2　GNU make的使用75
5.3　樹77
5.3.1　定義語法樹類型78
5.3.2　解析樹與語法樹79
5.4　從終結(jié)符創(chuàng)建葉子81
5.4.1　用葉子包裝標(biāo)記81
5.4.2　使用YACC的值棧82
5.4.3　為解析器的值棧包裝葉子83
5.4.4　確定需要哪些葉子84
5.5　從產(chǎn)生式規(guī)則構(gòu)建內(nèi)部節(jié)點(diǎn)85
5.5.1　訪問值棧上的樹節(jié)點(diǎn)85
5.5.2　使用樹節(jié)點(diǎn)工廠方法86
5.6　為Jzero語言形成語法樹88
5.7　調(diào)試并測(cè)試語法樹93
5.7.1　避免常見的語法樹錯(cuò)誤94
5.7.2　以文本格式輸出語法樹95
5.7.3　使用dot輸出語法樹96
5.8　本章小結(jié)101
5.9　思考題101
第二部分　語法樹遍歷
第6章　符號(hào)表104
6.1　技術(shù)需求104
6.2　建立符號(hào)表基礎(chǔ)105
6.2.1　聲明和作用域105
6.2.2　賦值和取消引用變量106
6.2.3　選擇正確的樹遍歷106
6.3　為每個(gè)作用域創(chuàng)建和填充符號(hào)表107
6.3.1　向語法樹添加語義屬性108
6.3.2　定義符號(hào)表和符號(hào)表?xiàng)l目的類109
6.3.3　創(chuàng)建符號(hào)表110
6.3.4　填充符號(hào)表112
6.3.5　綜合isConst屬性114
6.4　檢查未聲明的變量115
6.4.1　識(shí)別方法體115
6.4.2　發(fā)現(xiàn)方法體中變量的使用116
6.5　查找重新聲明的變量118
6.5.1　將符號(hào)插入符號(hào)表118
6.5.2　報(bào)告語義錯(cuò)誤119
6.6　在Unicon中處理包和類作用域119
6.6.1　名稱修飾120
6.6.2　為成員變量引用插入self120
6.6.3　在方法調(diào)用中插入self作為
　　　第一個(gè)參數(shù)121
6.7　測(cè)試和調(diào)試符號(hào)表122
6.8　本章小結(jié)123
6.9　思考題124
第7章　基本類型檢查125
7.1　技術(shù)需求125
7.2　編譯器中的類型表示125
7.2.1　定義表示類型的基類126
7.2.2　子類化復(fù)雜類型的基類127
7.3　將類型信息分配給聲明的變量129
7.3.1　從保留字合成類型130
7.3.2　將類型繼承到變量列表中131
7.4　確定每個(gè)語法樹節(jié)點(diǎn)的類型132
7.4.1　確定葉子的類型133
7.4.2　計(jì)算和檢查內(nèi)部節(jié)點(diǎn)的類型135
7.5　Unicon中的運(yùn)行時(shí)類型檢查和
　　　類型推斷139
7.6　本章小結(jié)140
7.7　思考題140
第8章　檢查數(shù)組、方法調(diào)用和結(jié)
　　　　構(gòu)訪問的類型142
8.1　技術(shù)需求142
8.2　檢查數(shù)組類型的操作142
8.2.1　處理數(shù)組變量聲明143
8.2.2　在數(shù)組創(chuàng)建期間檢查類型143
8.2.3　在數(shù)組訪問期間檢查類型145
8.3　檢查方法調(diào)用146
8.3.1　計(jì)算參數(shù)和返回類型信息147
8.3.2　檢查每個(gè)方法調(diào)用站點(diǎn)的類型149
8.3.3　檢查返回語句中的類型152
8.4　檢查結(jié)構(gòu)化類型訪問153
8.4.1　處理實(shí)例變量聲明154
8.4.2　在創(chuàng)建實(shí)例時(shí)檢查類型154
8.4.3　在實(shí)例訪問時(shí)檢查類型157
8.5　本章小結(jié)159
8.6　思考題160
第9章　中間代碼生成161
9.1　技術(shù)需求161
9.2　準(zhǔn)備生成代碼161
9.2.1　為什么要生成中間代碼162
9.2.2　了解生成程序的存儲(chǔ)區(qū)域162
9.2.3　為中間代碼引入數(shù)據(jù)類型163
9.2.4　將中間代碼屬性添加到樹中165
9.2.5　生成標(biāo)簽和臨時(shí)變量165
9.3　中間代碼指令集168
9.3.1　指令168
9.3.2　聲明168
9.4　用標(biāo)簽為控制流注釋語法樹 169
9.5　為表達(dá)式生成代碼171
9.6　為控制流生成代碼173
9.6.1　為條件表達(dá)式生成標(biāo)簽?zāi)繕?biāo)174
9.6.2　生成循環(huán)代碼177
9.6.3　為方法調(diào)用生成中間代碼178
9.6.4　檢查生成的中間代碼179
9.7　本章小結(jié)180
第10章　IDE中的語法著色182
10.1　下載本章中使用的示例IDE183
10.2　將編譯器集成到程序員的編輯
　　　器中184
10.2.1　從IDE中分析源代碼185
10.2.2　將編譯器輸出發(fā)送到IDE185
10.3　避免在每次更改時(shí)重新解析
　　　整個(gè)文件186
10.4　使用詞法信息為標(biāo)記著色189
10.4.1　擴(kuò)展EditableTextList組件以
　　　支持顏色189
10.4.2　在繪制單個(gè)標(biāo)記時(shí)對(duì)其
　　　　進(jìn)行著色190
10.5　使用解析結(jié)果突出顯示錯(cuò)誤191
10.6　添加Java支持192
10.7　本章小結(jié)194
第三部分　代碼生成與運(yùn)行時(shí)系統(tǒng)
第11章　字節(jié)碼解釋器196
11.1　技術(shù)需求196
11.2　什么是字節(jié)碼196
11.3　比較字節(jié)碼和中間碼198
11.4　為Jzero構(gòu)建字節(jié)碼指令集200
11.4.1　定義Jzero字節(jié)碼文件格式200
11.4.2　了解棧機(jī)操作的基礎(chǔ)知識(shí)202
11.5　實(shí)現(xiàn)字節(jié)碼解釋器203
11.5.1　將字節(jié)碼加載到內(nèi)存中203
11.5.2　初始化解釋器狀態(tài)205
11.5.3　獲取指令并推進(jìn)指令指針206
11.5.4　指令解碼207
11.5.5　執(zhí)行指令208
11.5.6　啟動(dòng)Jzero解釋器211
11.6　編寫Jzero運(yùn)行時(shí)系統(tǒng)212
11.7　運(yùn)行Jzero程序213
11.8　檢查Unicon字節(jié)碼解釋器iconx213
11.8.1　了解目標(biāo)導(dǎo)向的字節(jié)碼214
11.8.2　在運(yùn)行時(shí)保留類型信息214
11.8.3　獲取、解碼和執(zhí)行指令214
11.8.4　制作運(yùn)行時(shí)系統(tǒng)的其余部分215
11.9　本章小結(jié)215
11.10　思考題215
第12章　生成字節(jié)碼217
12.1　技術(shù)需求217
12.2　轉(zhuǎn)換中間代碼為Jzero字節(jié)碼217
12.2.1　為字節(jié)碼指令添加類218
12.2.2　將中間代碼地址映射到
　　　　字節(jié)碼地址219
12.2.3　實(shí)現(xiàn)字節(jié)碼生成器方法220
12.2.4　為簡單表達(dá)式生成字節(jié)碼221
12.2.5　生成指針操作的代碼223
12.2.6　為分支和條件分支生成
　　　　字節(jié)碼224
12.2.7　為方法調(diào)用和返回生成代碼225
12.2.8　處理中間代碼中的標(biāo)簽和
　　　　其他偽指令226
12.3　比較字節(jié)碼匯編程序與二進(jìn)制
　　　格式227
12.3.1　以匯編格式輸出字節(jié)碼227
12.3.2　以二進(jìn)制格式輸出字節(jié)碼229
12.4　鏈接、加載并包括運(yùn)行時(shí)系統(tǒng)230
12.5　Unicon示例：icont中的字節(jié)碼
　　　生成230
12.6　本章小結(jié)232
12.7　思考題232
第13章　生成本機(jī)代碼233
13.1　技術(shù)需求233
13.2　決定是否生成本機(jī)代碼233
13.3　x64指令集234
13.3.1　為x64指令添加類234
13.3.2　將內(nèi)存區(qū)域映射到基于x64
　　　　寄存器的地址模式235
13.4　使用寄存器235
13.4.1　從空策略開始236
13.4.2　分配寄存器以加速本地
　　　　區(qū)域237
13.5　將中間代碼轉(zhuǎn)換為x64代碼239
13.5.1　將中間代碼地址映射到x64
　　　　內(nèi)存地址240
13.5.2　實(shí)現(xiàn)x64代碼生成器方法243
13.5.3　生成簡單表達(dá)式的x64代碼244
13.5.4　生成指針操作的代碼245
13.5.5　為分支和條件分支生成
　　　　本機(jī)代碼246
13.5.6　為方法調(diào)用和返回生成代碼247
13.5.7　處理標(biāo)簽和偽指令249
13.6　生成x64輸出250
13.6.1　以匯編語言格式編寫x64
　　　　代碼251
13.6.2　從本機(jī)匯編程序到目標(biāo)文件251
13.6.3　鏈接、加載并包括運(yùn)行時(shí)
　　　　系統(tǒng)252
13.7　本章小結(jié)253
13.8　思考題253
第14章　運(yùn)算符和內(nèi)置函數(shù)的實(shí)現(xiàn)254
14.1　實(shí)現(xiàn)運(yùn)算符254
14.1.1　運(yùn)算符是否需要硬件支持255
14.1.2　在中間代碼生成中添加字符
　　　　串連接255
14.1.3　為字節(jié)碼解釋器添加字符
　　　　串連接257
14.1.4　將字符串連接添加到本機(jī)
　　　　運(yùn)行時(shí)系統(tǒng)259
14.2　編寫內(nèi)置函數(shù)260
14.2.1　向字節(jié)碼解釋器添加內(nèi)置
　　　　函數(shù)260
14.2.2　編寫用于本機(jī)代碼實(shí)現(xiàn)的
　　　　內(nèi)置函數(shù)261
14.3　集成內(nèi)置組件與控制結(jié)構(gòu)262
14.4　為Unicon開發(fā)運(yùn)算符和函數(shù)262
14.4.1　在Unicon中編寫運(yùn)算符263
14.4.2　開發(fā)Unicon的內(nèi)置函數(shù)265
14.5　本章小結(jié)266
14.6　思考題266
第15章　域控制結(jié)構(gòu)267
15.1　了解何時(shí)需要新的控制結(jié)構(gòu)267
15.1.1　定義控制結(jié)構(gòu)268
15.1.2　減少過多的冗余參數(shù)268
15.2　Icon和Unicon中的字符串掃描269
15.2.1　掃描環(huán)境及其基本操作270
15.2.2　通過控制結(jié)構(gòu)消除過多參數(shù)271
15.3　Unicon中的渲染區(qū)域271
15.3.1　從顯示列表渲染3D圖形272
15.3.2　使用內(nèi)置函數(shù)指定渲染區(qū)域272
15.3.3　使用嵌套渲染區(qū)域更改
　　　　圖形細(xì)節(jié)層次273
15.3.4　創(chuàng)建渲染區(qū)域控制結(jié)構(gòu)274
15.4　本章小結(jié)278
15.5　思考題278
第16章　垃圾收集279
16.1　認(rèn)識(shí)垃圾收集的重要性279
16.2　對(duì)象的引用計(jì)數(shù)281
16.2.1　將引用計(jì)數(shù)添加到Jzero281
16.2.2　生成堆分配代碼281
16.2.3　為賦值運(yùn)算符修改生成的
　　　 代碼283
16.2.4　引用計(jì)數(shù)的缺點(diǎn)和局限性283
16.3　標(biāo)記實(shí)時(shí)數(shù)據(jù)并清理剩余數(shù)據(jù)284
16.3.1　組織堆內(nèi)存區(qū)域285
16.3.2　遍歷基本變量以標(biāo)記實(shí)時(shí)
　　　 數(shù)據(jù)286
16.3.3　回收實(shí)時(shí)內(nèi)存并將其放入
　　　 連續(xù)內(nèi)存塊290
16.4　本章小結(jié)293
16.5　思考題293
第17章　結(jié)語294
17.1　反思從編寫這本書中學(xué)到的
　　　 東西294
17.2　決定何去何從295
17.2.1　學(xué)習(xí)編程語言設(shè)計(jì)295
17.2.2　學(xué)習(xí)如何實(shí)現(xiàn)解釋器和字
　　　　節(jié)碼機(jī)器296
17.2.3　獲取代碼優(yōu)化方面的專業(yè)
　　　　知識(shí)297
17.2.4　監(jiān)視和調(diào)試程序執(zhí)行297
17.2.5　設(shè)計(jì)和實(shí)現(xiàn)IDE和GUI
　　　　構(gòu)建器298
17.3　延伸閱讀的參考資料298
17.4　本章小結(jié)301
第四部分　附錄
附錄A　Unicon基礎(chǔ)304
附錄B　部分章節(jié)要點(diǎn)324