編譯器之旅——打造自己的編程語言（微課視頻版）

目錄

入門篇

第1章編譯器簡介（19min）3

1.1編程語言的發展史3

1.2編譯器在IT行業里的核心地位3

1.3編譯器的代碼架構4

第2章詞法分析（34min）7

2.1“理想語言”的詞法分析7

2.2實際編程語言的詞法擴展8

2.2.1編程語言的標志符9

2.2.2關鍵字9

2.2.3數字10

2.2.4數據結構11

2.3詞法分析的數學解釋12

第3章語法分析（123min）14

3.1語句類型的劃分14

3.2語句的嵌套和遞歸分析16

3.2.1變量聲明語句的分析16

3.2.2類型定義語句的分析17

3.2.3順序塊的分析18

3.2.4表達式的分析18

3.2.5運算符的優先級和結合性19

3.2.6表達式樹的構造步驟20

3.2.7完整的抽象語法樹20

3.2.8抽象語法樹的數據結構21

3.2.9變量和類型的數據結構22

3.2.10變量的語法檢查23

3.2.11星號和乘法的區分24

3.3語法的靈活編輯和有限自動機框架24

3.3.1有限自動機的簡介24

3.3.2語法的編輯25

3.3.3編程語言的語法圖26

3.3.4SCF框架怎麽實現“遞歸”27

3.3.5語法分析框架的模塊上下文29

3.3.6for循環的語法分析模塊30

3.3.7小括號的多種含義36

3.4語法分析的數學解釋36

第4章語義分析（72min）38

4.1類型檢查38

4.2語義分析框架40

4.2.1語義分析的回調函數40

4.2.2語義分析中的遞歸43

4.3運算符重載46

4.3.1運算符重載的實現46

4.3.2函數調用47

4.3.3重載函數的查找47

4.3.4代碼實現48

4.3.5SCF編譯器的類對象51

4.4new關鍵字51

4.5多值函數55

4.5.1應用程序二進制接口56

4.5.2語法層面的支持56

4.5.3語義層面的支持57

進階篇

第5章三地址碼的生成（84min）63

5.1回填技術63

5.1.1回填的數據結構63

5.1.2三地址碼的數據結構64

5.1.3回填的步驟65

5.2ifelse的三地址碼65

5.3循環的入口和出口68

5.4指針與數組的賦值72

5.5new關鍵字的三地址碼74

5.6跳轉的優化77

5.6.1跳轉的優化簡介77

5.6.2邏輯運算符的短路優化78

5.6.3死代碼消除80

5.6.4代碼實現80

第6章基本塊的劃分（19min）83

6.1比較、跳轉導致的基本塊劃分83

6.2函數調用84

6.3基本塊的流程圖84

第7章中間代碼優化（100min）86

7.1代碼框架86

7.2內聯函數88

7.3有向無環圖93

7.3.1公共子表達式93

7.3.2數據結構94

7.3.3有向無環圖的生成95

7.4圖的搜索算法97

7.4.1基本塊的數據結構97

7.4.2寬度優先搜索98

7.4.3深度優先搜索99

7.5指針分析100

7.5.1指針解引用的分析100

7.5.2數組和結構體的指針分析106

7.6跨函數的指針分析109

7.7變量活躍度分析114

7.7.1變量的活躍度114

7.7.2單個基本塊的變量活躍度分析115

7.7.3基本塊流程圖上的分析117

7.7.4代碼實現118

7.8自動內存管理120

7.9DAG優化125

7.9.1無效運算125

7.9.2相同子表達式的判斷126

7.9.3出口活躍變量的優化126

7.9.4後++的優化127

7.9.5邏輯運算符的優化127

7.9.6DAG優化的代碼實現128

7.10循環分析133

7.10.1循環的識別133

7.10.2循環的優化138

第8章寄存器分配（23min）143

8.1不同CPU架構的寄存器組143

8.2變量之間的沖突144

8.3圖的著色算法148

8.3.1簡單著色算法148

8.3.2改進的著色算法150

第9章機器碼的生成（103min）155

9.1RISC架構的優勢155

9.2寄存器溢出155

9.2.1寄存器的數據結構156

9.2.2寄存器的沖突156

9.2.3寄存器的溢出158

9.3X86_64的機器碼生成158

9.3.1X86_64的機器指令158

9.3.2機器碼的生成160

9.3.3目標文件176

9.4ARM64的機器碼生成180

9.4.1指令特點180

9.4.2機器碼生成181

第10章ELF格式和可執行程序的連接（94min）184

10.1ELF格式184

10.1.1文件頭184

10.1.2節頭表186

10.1.3程序頭表188

10.1.4ELF格式的實現190

10.2連接器198

10.2.1連接198

10.2.2靜態連接202

10.2.3動態連接205

10.2.4編譯器的主流程215

10.3可執行文件的運行219

10.3.1進程創建219

10.3.2程序的加載和運行220

10.3.3動態庫函數的加載221

10.3.4源代碼的編譯、連接、運行222

第11章Naja字節碼和虛擬機（67min）224

11.1Naja字節碼224

11.2虛擬機229

11.2.1虛擬機的數據結構229

11.2.2虛擬機的運行230

11.2.3動態庫函數的加載236

第12章信息編碼的數學哲學239

12.1信息編碼格式的轉換239

12.2多項式時間的算法241

12.3自然指數e和梯度下降算法241

12.4復雜問題的簡單解法242