《计算机编译原理》

第一章总论1

§1 引言1

§2 程序设计语言与程序2

2.1 程序及其结构2

2.2 程序设计语言的定义3

2.3 程序的执行6

§3 编译程序构造及有关概念8

3.1 编译程序的构造8

3.2 趟的概念9

3.3 编译程序的分类10

3.4 实际应用中的编译程序11

§4 形式语言理论与编译实现技术12

第二章文法与语言14

§1 符号串与符号串集合14

1.1 字母表14

1.2 符号串14

1.3 行号串集合16

§2 文法与语言的形式定义17

2.1 文法的形式定义17

2.2 语言的形式定义23

3.1 Chomsky语言类26

§3 语言的分类26

3.2 形式语言与自动机31

3.3 形式语言的分类与程序设计语言33

3.4 对上下文无关文法的进一步讨论34

§4 文法等价与等价变换37

4.1 文法等价的概念37

4.2 压缩文法等价变换38

4.3 增广文法等价变换40

4.4 消去单规则等价变换40

4.5 范式文法等价变换41

4.6 消去左递归的文法等价变换42

§5 语法树与句型分析45

5.1 语法树的概念45

5.2 句型分析49

习题153

习题253

习题354

习题454

习题555

1.2 符号的识别与重写规则的关系57

1.1 词法分析与词法分析程序57

第三章词法分析57

§1 引言57

1.3 实现方式58

§2 正则表达式与有穷状态自动机59

2.1 状态转换图与转换系统59

2.2 确定有穷状态自动机DFA62

2.3 非确定有穷状态自动机NFA65

2.4 确定有穷状态自动机的化简69

2.5 正则表达式71

3.1 单词与属性字80

§3 词法分析程序的实现80

3.2 标识符的处理85

3.3 词法分析程序的编写90

§4 词法分析程序的自动生成93

4.1 基本思想93

4.2 扫描程序定义与构造程序99

4.3 自动生成系统LEX简介102

习题6103

1.1 自顶向下分析技术及识别算术105

1.2 讨论的前提105

§1 引言105

第四章语法分析——自顶向下分析技术105

1.3 要解决的基本问题106

§2 带回溯的自顶向下分析技术106

2.1 基本思想106

2.2 实现算法及举例109

2.3 问题及其解决112

§3 无回溯的自顶向下分析技术115

3.1 先决条件115

3.2 递归下降分析技术116

3.3 预测分析技术120

习题7126

第五章语法分析——自底向上分析技术127

§1 引言127

1.1 自底向上分析技术及识别算法127

1.2 讨论前提127

1.3 基本实现方法128

§2 简单优先分析技术129

2.1 优先关系与优先文法129

2.2 简单优先分析技术的实现140

2.3 优先函数143

2.4 简单优先分析技术的局限性及克服153

§3 算符优先分析技术154

3.1 算符优先分析技术的引进154

3.2 算符文法155

3.3 算符优先关系与算符优先文法156

3.4 算符优先文法句型的识别160

3.5 实际应用中的算符优先分析技术164

3.6 算符优先技术与简单优先技术的比较166

§4 LR（k）分析技术167

4.1 LR（k）文法与LR（k）分析技术167

4.2 SLR（k）分析表构造方法178

4.3 LALR（k）分析表构造方法190

4.4 识别程序自动构造195

4.5 识别程序自动生成系统YACC简介198

习题8200

习题9201

习题10202

习题11202

第六章语义分析与目标代码生成204

§1 概况204

1.1 语义分析的概念204

1.2 属性文法206

1.3 类型体制与语义分析221

2.1 常量定义的翻译229

§2 说明部分的翻译229

2.2 变量说明的翻译230

2.3 过程说明的翻译231

2.4 记录类型的翻译233

§3 目标代码的生成234

3.1 概况234

3.2 虚拟机236

3.3 控制语句的翻译239

§4 源程序的内部中间表示265

4.1 抽象语法树265

4.2 逆波兰表示267

4.3 四元式序列273

4.4 三元式序列281

习题12282

习题13282

习题14283

习题15284

第七章运行环境286

§1 引言286

1.1 相关的问题286

1.2 名字到存储字的结合286

2.2 栈式存储分配290

2.1 静态存储分配290

§2 存储分配策略290

2.3 堆式存储分配293

§3 符号表296

3.1 符号表的引进296

3.2 符号表的组织296

3.3 符号表的数据结构300

§4 运行时刻支持系统303

习题16304

1.1 优化的概念306

§1 引言306

第八章代码优化306

1.2 代码优化的分类307

1.3 代码优化程序的结构308

§2 基本块与流图308

§3 基本块的优化310

3.1 基本块优化的种类310

3.2 基本块优化的实现313

§4 与循环有关的优化322

4.1 循环优化的种类322

4.2 循环优化的实现329

5.1 冗余指令删除350

§5 窥孔优化350

5.2 控制流优化351

5.3 代数化简352

5.4 特殊指令的使用352

习题17353

第九章程序错误的检查和校正356

§1 概述356

1.1 错误存在的必然性356

1.2 错误的种类356

1.3 错误复原357

2.1 词法错误的种类358

§2 词法错误的复原和校正358

2.2 词法错误的校正359

§3 语法错误的复原和校正360

3.1 语法错误的复原360

3.2 语法错误的校正360

§4 语义错误361

4.1 语义错误的种类361

4.2 语义错误检查措施362

解题规范例解365

总复习思考题378

参考文献380