編譯原理

目錄

模塊1引論和基本概念

第1章引論3

1.1編譯器技術的應用4

1.1.1高級語言的實現4

1.1.2針對電腦體系結構的優化6

1.1.3新電腦體系結構的設計7

1.1.4程序翻譯8

1.1.5編譯器相關的建模及科學9

1.1.6程序設計語言的部分特性11

1.1.7提高軟件開發效率的工具18

1.2編譯器概述20

1.2.1詞法分析21

1.2.2語法分析22

1.2.3語義分析23

1.2.4中間代碼生成23

1.2.5代碼優化24

1.2.6代碼生成24

1.2.7符號表管理25

1.2.8階段的分組25

1.2.9解釋器26

1.2.10編譯器的生成與構造27

小結29

習題130

拓展閱讀： 深度學習編譯器30第2章文法和語言34

2.1預備知識35

2.1.1字母表35

2.1.2符號串35

2.2文法的非形式討論36

2.3文法和語言的形式定義40

2.4語法樹與二義性文法42

2.4.1語法樹的概念42

2.4.2二義性與最左（最右）推導42

2.4.3子樹與短語、句柄43

2.4.4抽象語法樹46

2.5句子的分析47

2.6有關文法的實用限制49

2.7文法的其他表示法： EBNF和語法圖50

2.8文法和語言的分類52

2.9文法構造與文法化簡56

2.9.1由語言構造文法的例子56

2.9.2文法的化簡59

2.9.3構造無ε產生式的上下文無關文法60

小結62

習題263

拓展閱讀： 非喬姆斯基的兩種語法與Chart分析算法65

模塊2編譯器的構造技術

第3章詞法分析概述及詞法分析器的人工實現73

3.1詞法單元及屬性73

3.1.1詞法單元、模式、詞素73

3.1.2詞法單元的屬性74

3.1.3詞法錯誤 75

3.2輸入緩沖75

3.2.1緩沖區對76

3.2.2哨兵標記77

3.3詞法單元的描述與識別78

3.3.1串和語言78

3.3.2正則表達式79

3.3.3正則定義81

3.3.4正則文法和正則式的等價性82

3.3.5狀態轉換圖83

小結87

習題387

拓展閱讀： 正則表達式的擴展與漢語詞法分析89第4章語法分析概述及遞歸子程序法94

4.1語法分析概述94

4.1.1上下文無關文法的定義95

4.1.2推導96

4.1.3分析樹97

4.1.4二義性98

4.1.5驗證文法生成的語言100

4.1.6非上下文無關語言的構造100

4.2自上而下分析101

4.2.1自上而下分析的一般方法102

4.2.2存在問題及解決方法106

4.3遞歸下降分析法107

小結 110

習題4110

拓展閱讀： 遞歸子程序的應用112第5章符號表管理115

5.1概述115

5.2符號表的組織和內容116

5.3非分程序結構語言的符號表組織119

5.4分程序結構語言的符號表組織120

小結121

習題5122

拓展閱讀： Open64的符號表設計123第6章運行時存儲空間的組織和管理129

6.1概述129

6.2靜態存儲分配131

6.3動態存儲分配132

6.4面向對象語言的存儲分配策略141

6.4.1類和對象141

6.4.2面向對象程序運行時的特徵141

6.4.3對象的存儲組織142

6.4.4例程的動態綁定143

小結145

習題6146

拓展閱讀： 垃圾回收152第7章源程序的中間形式157

7.1波蘭表示158

7.2n元表示159

7.2.1四元式161

7.2.2三元式161

7.2.3靜態單賦值形式162

7.3圖形表示163

7.3.1抽象語法樹163

7.3.2有向無環圖164

7.4抽象機代碼166

小結167

習題7168

拓展閱讀： LLVM和LLVM IR170第8章錯誤處理172

8.1概述172

8.2錯誤分類173

8.3錯誤的診察和報告174

8.4錯誤處理技術174

8.4.1詞法錯誤的恢復和校正176

8.4.2語法錯誤的恢復和校正176

8.4.3語義錯誤的恢復和校正177

小結178

習題8179

拓展閱讀： 中文錯誤處理179第9章語法制導翻譯技術181

9.1翻譯文法和語法制導翻譯182

9.2屬性翻譯文法185

9.3自上而下語法制導翻譯190

9.3.1遞歸下降翻譯器191

9.3.2LL（1）翻譯器195

小結198

習題9199

拓展閱讀： 前沿語法制導翻譯技術200第10章語義分析和代碼生成202

10.1語義分析的概念203

10.2棧式抽象機及其匯編指令204

10.3聲明的處理207

10.3.1符號常量的處理207

10.3.2簡單變量的處理208

10.3.3數組的處理210

10.4表達式的處理211

10.5賦值語句的處理215

10.6控制語句的處理217

10.6.1if語句的處理217

10.6.2while語句的處理219

10.6.3for語句的處理221

10.7過程調用和返回的處理223

小結227

習題10228

拓展閱讀： 自然語言處理229

模塊3編譯前段分析及其自動化生成技術

第11章詞法分析器的自動生成技術233

11.1有限自動機233

11.1.1不確定的有限自動機235

11.1.2確定的有限自動機237

11.1.3NFA到DFA的轉換238

11.1.4DFA的化簡242

11.2從正則表達式到有限自動機243

11.3從正則文法到有限自動機248

11.4詞法分析器生成工具Lex249

小結252

習題11253

拓展閱讀： 有限自動機的應用257第12章語法分析及自動生成技術261

12.1自上而下分析261

12.1.1自上而下分析的一般方法262

12.1.2消除左遞歸264

12.1.3提取左公因子266

12.1.4LL（1）文法266

12.1.5遞歸下降的預測分析268

12.1.6非遞歸的預測分析269

12.1.7構造分析表271

12.1.8預測分析的錯誤恢復272

12.2自下而上分析275

12.2.1歸約275

12.2.2句柄276

12.2.3用棧實現移進歸約分析277

12.2.4移進歸約分析的沖突278

12.3自下而上優先分析279

12.3.1簡單優先分析法279

12.3.2運算符優先分析法282

12.3.3運算符優先分析算法290

12.3.4優先函數292

12.3.5運算符優先分析法的局限性296

小結297

習題12298

拓展閱讀： 實際應用中語法分析器所面臨的困境302第13章自下而上語法分析——LR（k）分析方法309

13.1LR分析器310

13.1.1LR分析算法310

13.1.2LR文法和LR分析方法的特點318

13.2SLR分析319

13.3規範的LR分析322

13.3.1規範LR（1）項322

13.3.2構造LR（1）項集族323

13.3.3規範LR（1）語法分析表325

13.4LALR分析327

13.4.1LALR分析表的構造327

13.4.2高效構造LALR語法分析表的方法330

13.5非二義且非LR的上下文無關文法334

13.5.1用優先級和結合性解決沖突335

13.5.2懸空else的二義性337

13.6語法分析表的自動生成339

13.6.1終結符和產生式的優先級339

13.6.2結合規則339

13.6.3LR語法分析表的安排342

13.7語法分析器的生成器343

13.7.1分析器的生成器yacc343

13.7.2用yacc處理二義文法346

13.7.3yacc的錯誤恢復348

小結349

習題13350

拓展閱讀： GLR算法與基於統計的語法分析算法353參考文獻358