目录

模块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