自製編譯器

《自製編譯器》是2020年3月人民郵電出版社出版的圖書，作者是[日]青木峰郎。

基本介紹

• 書名：自製編譯器
• 作者：[日]青木峰郎
• ISBN：9787115422187
• 頁數：445頁
• 定價：99元
• 出版社：人民郵電出版社
• 出版時間：2020年3月
• 裝幀：平裝
• 開本：16開

內容簡介

本書將帶領讀者從頭開始製作一門語言的編譯器。筆者特意為本書設計了C?語言，C?可以說是C語言的子集，實現了包括指針運算等在內的C語言的主要部分。本書所實現的編譯器就是C?語言的編譯器， 是實實在在的編譯器，而非有諸多限制的玩具。另外，除編譯器之外，本書對以編譯器為中心的程式語言的運行環境，即編譯器、彙編器、連結器、硬體、運行時環境等都有所提及，介紹了程式運行的所有環節。

圖書目錄

第 1章

開始製作編譯器　1

1.1　本書的概要　2

本書的主題　2

本書製作的編譯器　2

編譯示例　2

執行檔　3

編譯　4

程式運行環境　6

1.2　編譯過程　8

編譯的4個階段　8

語法分析　8

語義分析　9

生成中間代碼　9

代碼生成　10

最佳化　10

總結　10

1.3　使用C 編譯器進行編譯　11

C 編譯器的必要環境　11

安裝C 編譯器　11

C 的Hello,　World!　12

第 2章

C 和cbc　13

2.1　C 語言的概要　14

C 的Hello,　World！　14

C 中刪減的功能　14

import關鍵字　15

導入檔案的規範　16

2.2　C 編譯器cbc的構成　17

cbc的代碼樹　17

cbc的包　18

compiler包中的類群　18

main函式的實現　19

commandMain函式的實現　19

Java5泛型　20

build函式的實現　20

Java　5的foreach語句　21

compile函式的實現　21

第 1部分　代碼分析

第3章

語法分析的概要　24

3.1　語法分析的方法　25

代碼分析中的問題點　25

代碼分析的一般規律　25

詞法分析、語法分析、語義分析　25

掃描器的動作　26

單詞的種類和語義值　27

token　28

抽象語法樹和節點　29

3.2　解析器生成器　30

什麼是解析器生成器　30

解析器生成器的種類　30

解析器生成器的選擇　31

3.3　JavaCC的概要　33

什麼是JavaCC　33

語法描述檔案　33

語法描述檔案的例子　34

運行JavaCC　35

啟動JavaCC所生成的解析器　36

中文的處理　37

第4章

詞法分析　39

4.1　基於JavaCC的掃描器的描述　40

本章的目的　40

JavaCC的正則表達式　40

固定字元串　41

連線　41

字元組　41

排除型字元組　41

重複1次或多次　42

重複0次或多次　42

重複n次到m次　42

正好重複n次　43

可以省略　43

選擇　43

4.2　掃描沒有結構的單詞　44

TOKEN命令　44

掃描標識符和保留字　44

選擇匹配規則　45

掃描數值　46

4.3　掃描不生成token的單詞　48

SKIP命令和SPECIAL_TOKEN命令　48

跳過空白符　48

跳過行注釋　49

4.4　掃描具有結構的單詞　50

**長匹配原則和它的問題　50

基於狀態遷移的掃描　50

MORE命令　51

跳過塊注釋　52

掃描字元串字面量　53

掃描字元字面量　53

第5章

基於JavaCC的解析器的描述　55

5.1　基於EBNF語法的描述　56

本章的目的　56

基於JavaCC的語法描述　56

終端符和非終端符　57

JavaCC的EBNF表示法　58

連線　58

重複0次或多次　59

重複1次或多次　59

選擇　60

可以省略　60

5.2　語法的二義性和token的超前掃描　61

語法的二義性　61

JavaCC的局限性　62

提取左側共通部分　63

token的超前掃描　63

可以省略的規則和衝突　64

重複和衝突　65

更靈活的超前掃描　66

超前掃描的相關注意事項　66

第6章

語法分析　68

6.1　定義的分析　69

表示程式整體的符號　69

語法的單位　69

import聲明的語法　70

各類定義的語法　71

變數定義的語法　72

函式定義的語法　73

結構體定義和聯合體定義的語法　74

結構體成員和聯合體成員的語法　75

typedef語句的語法　76

類型的語法　76

C語言和C 在變數定義上的區別　77

基本類型的語法　77

6.2　語句的分析　79

語句的語法　79

if語句的語法　80

省略if語句和大括弧　80

while語句的語法　81

for語句的語法　81

各類跳轉語句的語法　82

6.3　表達式的分析　83

表達式的整體結構　83

expr的規則　83

條件表達式　84

二元運算符　85

6.4　項的分析　88

項的規則　88

前置運算符的規則　88

後置運算符的規則　89

字面量的規則　89

第 2部分　抽象語法樹和中間代碼

第7章

JavaCC的action和抽象語法樹　92

7.1　JavaCC的action　93

本章的目的　93

簡單的action　93

執行action的時間點　93

返回語義值的action　95

獲取終端符號的語義值　95

Token類的屬性　96

獲取非終端符號的語義值　98

語法樹的結構　99

選擇和action　99

重複和action　100

本節總結　102

7.2　抽象語法樹和節點　103

Node類群　103

Node類的定義　105

抽象語法樹的表示　105

基於節點表示表達式的例子　107

第8章

抽象語法樹的生成　110

8.1　表達式的抽象語法樹　111

字面量的抽象語法樹　111

類型的表示　112

為什麼需要TypeRef類　113

一元運算的抽象語法樹　114

二元運算的抽象語法樹　116

條件表達式的抽象語法樹　117

賦值表達式的抽象語法樹　118

8.2　語句的抽象語法樹　121

if語句的抽象語法樹　121

while語句的抽象語法樹　122

程式塊的抽象語法樹　123

8.3　聲明的抽象語法樹　125

變數聲明列表的抽象語法樹　125

函式定義的抽象語法樹　126

表示聲明列表的抽象語法樹　127

表示程式整體的抽象語法樹　128

外部符號的import　128

總結　129

8.4　cbc 的解析器的啟動　132

Parser對象的生成　132

檔案的解析　133

解析器的啟動　134

第9章

語義分析（1）引用的消解　135

9.1　語義分析的概要　136

本章目的　136

抽象語法樹的遍歷　137

不使用Visitor模式的抽象語法樹的處理　137

基於Visitor模式的抽象語法樹的處理　138

Vistor模式的一般化　140

cbc中Visitor模式的實現　141

語義分析相關的cbc的類　142

9.2　變數引用的消解　144

問題概要　144

實現的概要　144

Scope樹的結構　145

LocalResolver類的屬性　146

LocalResolver類的啟動　146

變數定義的添加　147

函式定義的處理　148

pushScope方法　149

currentScope方法　149

popScope方法　150

添加臨時作用域　150

建立VariableNode和變數定義的關聯　151

從作用域樹取得變數定義　151

9.3　類型名稱的消解　153

問題概要　153

實現的概要　153

TypeResolver類的屬性　153

TypeResolver類的啟動　154

類型的聲明　154

類型和抽象語法樹的遍歷　155

變數定義的類型消解　156

函式定義的類型消解　157

第 10章

語義分析（2）靜態類型檢查　159

10.1　類型定義的檢查　160

問題概要　160

實現的概要　161

檢測有向圖中的閉環的算法　162

結構體、聯合體的循環定義檢查　163

10.2　表達式的有效性檢查　165

問題概要　165

實現的概要　165

DereferenceChecker類的啟動　166

SemanticError異常的捕獲　167

非指針類型取值操作的檢查　167

獲取非左值表達式地址的檢查　168

隱式的指針生成　169

10.3　靜態類型檢查　170

問題概要　170

實現的概要　170

C 中運算元的類型　171

隱式類型轉換　172

TyperChecker類的啟動　173

二元運算符的類型檢查　174

隱式類型轉換的實現　175

第 11章

中間代碼的轉換　178

11.1　cbc的中間代碼　179

組成中間代碼的類　180

中間代碼節點類的屬性　181

中間代碼的運算符和類型　182

各類中間代碼　183

中間代碼的意義　184

11.2　IRGenerator類的概要　185

抽象語法樹的遍歷和返回值　185

IRGenerator類的啟動　185

函式本體的轉換　186

作為語句的表達式的判別　187

11.3　流程控制語句的轉換　189

if語句的轉換（1）概要　189

if語句的轉換（2）沒有else部分的情況　190

if語句的轉換（3）存在else部分的情況　191

while語句的轉換　191

break語句的轉換（1）問題的定義　192

break語句的轉換（2）實現的方針　193

break語句的轉換（3）實現　194

11.4　沒有副作用的表達式的轉換　196

UnaryOpNode對象的轉換　196

BinaryOpNode對象的轉換　197

指針加減運算的轉換　198

11.5　左值的轉換　200

左邊和右邊　200

左值和右值　200

cbc中左值的表現　201

結構體成員的偏移　202

成員引用（expr.memb）的轉換　203

左值轉換的例外：數組和函式　204

成員引用的表達式（ptr->memb）的轉換　205

11.6　存在副作用的表達式的轉換　206

表達式的副作用　206

有副作用的表達式的轉換方針　206

簡單賦值表達式的轉換（1）語句　207

臨時變數的引入　208

簡單賦值表達式的轉換（2）表達式　209

後置自增的轉換　210

第3部分　彙編代碼

第 12章

x86架構的概要　214

12.1　計算機的系統結構　215

CPU和存儲器　215

暫存器　215

地址　216

物理地址和虛擬地址　216

各類設備　217

快取　218

12.2　x86系列CPU的歷史　220

x86系列CPU　220

32位CPU　220

指令集　221

IA-32的變遷　222

IA-32的64位擴展——AMD64　222

12.3　IA-32的概要　224

IA-32的暫存器　224

通用暫存器　225

機器棧　226

機器棧的操作　227

機器棧的用途　227

棧幀　228

指令指針　229

標誌暫存器　229

12.4　數據的表現形式和格式　231

無符號整數的表現形式　231

有符號整數的表現形式　231

負整數的表現形式和二進制補碼　232

位元組序　233

對齊　233

結構體的表現形式　234

第 13章

x86彙編器編程　236

13.1　基於GNU彙編器的編程　237

GNU彙編器　237

彙編語言的Hello,　World!　237

基於GNU彙編器的彙編代碼　238

13.2　GNU彙編器的語法　240

彙編版的Hello,　World!　240

指令　241

彙編偽操作　241

標籤　241

注釋　242

助記符後綴　242

各種各樣的運算元　243

間接記憶體引用　244

x86指令集的概要　245

13.3　傳輸指令　246

mov指令　246

push指令和pop指令　247

lea指令　248

movsx指令和movzx指令　249

符號擴展和零擴展　250

13.4　算術運算指令　251

add指令　251

進位標誌　252

sub指令　252

imul指令　252

idiv指令和div指令　253

inc指令　254

dec指令　255

neg指令　255

13.5　位運算指令　256

and指令　256

or指令　257

xor指令　257

not指令　257

sal指令　258

sar指令　258

shr指令　259

13.6　流程的控制　260

jmp指令　260

條件跳轉指令（jz、jnz、je、jne、……）　261

cmp指令　262

test指令　263

標誌位獲取指令（SETcc）　263

call指令　264

ret指令　265

第 14章

函式和變數　266

14.1　程式調用約定　267

什麼是程式調用約定　267

Linux/x86下的程式調用約定　267

14.2　Linux/x86下的函式調用　269

到函式調用完成為止　269

到函式開始執行為止　270

到返回原處理流程為止　271

到清理操作完成為止　271

函式調用總結　272

14.3　Linux/x86下函式調用的細節　274

暫存器的保存和復原　274

caller-save暫存器和callee-save暫存器　274

caller-save暫存器和callee-save暫存器的靈活套用　275

大數值和浮點數的返回方法　276

其他平台的程式調用約定　277

第 15章

編譯表達式和語句　278

15.1　確認編譯結果　279

利用cbc進行確認的方法　279

利用gcc進行確認的方法　280

15.2　x86彙編的對象與DSL　282

表示彙編的類　282

表示彙編對象　283

15.3　cbc的x86彙編DSL　285

利用DSL生成彙編對象　285

表示暫存器　286

表示立即數和記憶體引用　287

表示指令　287

表示彙編偽操作、標籤和注釋　288

15.4　CodeGenerator類的概要　290

CodeGenerator類的欄位　290

CodeGenerator類的處理概述　290

實現compileStmts方法　291

cbc的編譯策略　292

15.5　編譯單純的表達式　294

編譯Int節點　294

編譯Str節點　294

編譯Uni節點(1)按位取反　295

編譯Uni節點(2)邏輯非　297

15.6　編譯二元運算　298

編譯Bin節點　298

實現compileBinaryOp方法　299

實現除法和餘數　300

實現比較運算　300

15.7　引用變數和賦值　301

編譯Var節點　301

編譯Addr節點　302

編譯Mem節點　303

編譯Assign節點　303

15.8　編譯jump語句　305

編譯LabelStmt節點　305

編譯Jump節點　305

編譯CJump節點　305

編譯Call節點　306

編譯Return節點　307

第 16章

分配棧幀　308

16.1　操作棧　309

cbc中的棧幀　309

棧指針操作原則　310

函式體編譯順序　310

16.2　參數和局部變數的記憶體分配　312

本節概述　312

參數的記憶體分配　312

局部變數的記憶體分配：原則　313

局部變數的記憶體分配　314

處理作用域內的局部變數　315

對齊的計算　316

子作用域變數的記憶體分配　316

16.3　利用虛擬棧分配臨時變數　318

虛擬棧的作用　318

虛擬棧的接口　319

虛擬棧的結構　319

virtualPush方法的實現　320

VirtualStack#extend方法的實現　320

VirtualStack#top方法的實現　321

virtualPop方法的實現　321

VirtualStack#rewind方法的實現　321

虛擬棧的運作　322

16.4　調整棧訪問的偏移量　323

本節概要　323

StackFrameInfo類　323

計算正在使用的callee-save暫存器　324

計算臨時變數區域的大小　325

調整局部變數的偏移量　325

調整臨時變數的偏移量　326

16.5　生成函式序言和尾聲　327

本節概要　327

生成函式序言　327

生成函式尾聲　328

16.6　alloca函式的實現　330

什麼是alloca函式　330

實現原則　330

alloca函式的影響　331

alloca函式的實現　331

第 17章

最佳化的方法　333

17.1　什麼是最佳化　334

各種各樣的最佳化　334

最佳化的案例　334

常量摺疊　334

代數簡化　335

降低運算強度　335

削除共同子表達式　335

消除無效語句　336

函式內聯　336

17.2　最佳化的分類　337

基於方法的最佳化分類　337

基於作用範圍的最佳化分類　337

基於作用階段的最佳化分類　338

17.3　cbc中的最佳化　339

cbc中的最佳化原則　339

cbc中實現的最佳化　339

cbc中最佳化的實現　339

17.4　更深層的最佳化　341

基於模式匹配選擇指令　341

分配暫存器　342

控制流分析　342

大規模的數據流分析和SSA形式　342

總結　343

第4部分　連結和載入

第 18章

生成目標檔案　346

18.1　ELF檔案的結構　347

ELF的目的　347

ELF的節和段　348

目標檔案的主要ELF節　348

使用readelf命令輸出節頭　349

使用readelf命令輸出程式頭　350

使用readelf命令輸出符號表　351

readelf命令的選項　351

什麼是DWARF格式　352

18.2　全局變數及其在ELF檔案中的表示　354

分配給任意ELF節　354

分配給通用ELF節　354

分配.bss節　355

通用符號　355

記錄全局變數對應的符號　357

記錄符號的附加信息　357

記錄通用符號的附加信息　358

總結　358

18.3　編譯全局變數　360

generate方法的實現　360

generateAssemblyCode方法的實現　360

編譯全局變數　361

編譯立即數　362

編譯通用符號　363

編譯字元串字面量　364

生成函式頭　365

計算函式的代碼大小　366

總結　366

18.4　生成目標檔案　367

as命令調用的概要　367

引用GNUAssembler類　367

調用as命令　367

第 19章

連結和庫　369

19.1　連結的概要　370

連結的執行示例　370

gcc和GNU　ld　371

連結器處理的檔案　372

常用庫　374

連結器的輸入和輸出　374

19.2　什麼是連結　375

連結時進行的處理　375

合併節　375

重定位　376

符號消解　377

19.3　動態連結和靜態連結　379

兩種連結方法　379

動態連結的優點　379

動態連結的缺點　380

動態連結示例　380

靜態連結示例　381

庫的檢索規則　381

19.4　生成庫　383

生成靜態庫　383

Linux中共享庫的管理　383

生成共享庫　384

連結生成的共享庫　385

第 20章

載入程式　387

20.1　載入ELF段　388

利用mmap系統調用進行檔案映射　388

進程的記憶體鏡像　389

記憶體空間的屬性　390

ELF段對應的記憶體空間　390

和ELF檔案不對應的記憶體空間　392

ELF檔案載入的實現　393

20.2　動態連結過程　395

動態連結載入器　395

程式從啟動到終止的過程　395

啟動ld.so　396

系統核心傳遞的信息　397

AUX矢量　397

讀入共享庫　398

符號消解和重定位　399

運行初始化代碼　400

執行主程式　401

執行終止處理　402

ld.so解析的環境變數　402

20.3　動態載入　404

所謂動態載入　404

Linux下的動態載入　404

動態載入的架構　405

20.4　GNU ld的連結　406

用於cbc的ld選項的結構　406

C運行時　407

生成執行檔　408

生成共享庫　408

第 21章

生成地址無關代碼　410

21.1　地址無關代碼　411

什麼是地址無關代碼　411

全局偏移表（GOT）　412

獲取GOT地址　412

使用GOT地址訪問全局變數　413

訪問使用GOT地址的檔案內部的全局變數　414

過程連結表（PLT）　414

調用PLT入口　416

地址無關的執行檔：PIE　416

21.2　全局變數引用的實現　418

獲取GOT地址　418

PICThunk函式的實現　418

刪除重複函式並設定不可見屬性　419

載入GOT地址　420

locateSymbols函式的實現　421

全局變數的引用　421

訪問全局變數：地址無關代碼的情況下　422

函式的符號　423

字元串常量的引用　424

21.3　連結器調用的實現　425

生成執行檔　425

generateSharedLibrary方法　426

21.4　從程式解析到執行　428

build和載入的過程　428

詞法分析　429

語法分析　429

生成中間代碼　430

生成代碼　431

彙編　432

生成共享庫　432

生成執行檔　433

載入　433

第 22章

擴展閱讀　434

22.1　參考書推薦　435

編譯器相關　435

語法分析相關　435

彙編語言相關　436

22.2　連結、載入相關　437

22.3　各種程式語言的功能　438

異常封裝相關的圖書　438

垃圾回收　438

垃圾回收相關的圖書　439

面向對象程式語言的實現　439

函式式語言　440

附　錄　441

A.1　參考文獻　442

A.2　線上資料　444

A.3　原始碼　445