程序设计语言编译原理PDF电子书下载

引论 1

0.1 什么叫编译程序 1

0.2 编译过程概述 1

0.3 编译程序的结构 4

0.3.1 编译程序总框 4

0.3.2 表格与表格管理 5

0.3.3 遍 7

0.4 编译程序的生成 7

0.5 学习构造编译程序 8

第一章 高级程序语言概述 10

1.1 程序语言的定义 10

1.1.1 语言的词法和语法结构 10

1.1.2 语义 11

1.2 初等类型数据 12

1.2.1 标识符和名字 13

1.2.2 名字的属性和说明 13

1.3 数据结构 14

1.3.1 数组 14

1.3.2 记录结构 16

1.3.3 字符串、表格和栈 17

1.4 表达式 17

1.5 语句 19

1.5.1 赋值句 19

1.5.2 控制语句 20

1.5.3 说明句 20

1.5.4 简单句和复合句 20

1.6 程序段 20

1.6.1 FORTRAN 20

1.6.2 ALGOL 21

1.6.3 PASCAL 21

1.7 参数传递 22

1.7.1 参数 22

1.7.2 传地址 22

1.7.3 传值 23

1.7.4 传名 24

1.8 存储管理 24

1.8.1 静态存储分配 24

1.8.2 动态存储分配 24

1.8.3 栈式动态存储分配 25

1.8.4 堆式动态存储分配 26

1.9 历史回顾 27

第二章 词法分析 29

2.1 对于词法分析器的要求 29

2.1.1 词法分析器的功能和输出形式 29

2.1.2 词法分析器作为一个独立子程序 30

2.2 词法分析器的设计 30

2.2.1 输入、预处理 31

2.2.2 单词符号的识别：超前搜索 32

2.2.3 状态转换图 33

2.2.4 状态转换图的实现 36

2.3 正规表达式与有限自动机 38

2.3.1 正规式与正规集 38

2.3.2 确定有限自动机（DFA） 39

2.3.3 非确定有限自动机（NFA） 41

2.3.4 正规式与有限自动机的等价性 41

2.3.5 确定有限自动机的化简 45

2.4 词法分析器的自动产生 46

2.4.1 语言LEX的一般描述 47

2.4.2 超前搜索 49

2.4.3 LEX的实现 50

第三章 程序语言的语法描述与分析 55

3.1 上下文无关文法 55

3.1.1 文法与语言 55

3.1.2 语法树与二义性 58

3.1.3 形式语言鸟瞰 60

3.2 语法分析——自下而上分析 62

3.2.1 归约与分析树 63

3.2.2 规范归约简述 65

3.2.3 符号栈的使用与分析树的表示 67

3.3 算符优先分析法 68

3.3.1 直观算符优先分析法 70

3.3.2 算符优先文法和优先表构造 73

3.3.3 算符优先分析算法的设计 76

3.3.4 优先函数 78

3.4 语法分析——自上而下分析 80

3.5 递归下降分析法 82

3.5.1 左递归的消除 83

3.5.2 消除回溯、提左因子和递归下降分析器 84

3.5.3 文法的另一种表示法和转换图 86

3.5.4 预测分析程序 88

3.5.5 状态表 92

第四章 语法分析程序的自动构造 98

4.1 LR分析器 98

4.1.1 LR文法 101

4.1.2 一些非LR结构 102

4.2 LR（0）项目集族和LR（0）分析表的构造 103

4.2.1 LR（0）项目集规范族的构造 105

4.2.2 有效项目 107

4.2.3 LR（0）分析表的构造 108

4.3 SLR分析表的构造 109

4.4 规范LR分析表的构造 113

4.5 LALR分析表的构造 116

4.6 二义文法的应用 123

4.7 分析表的自动产生 126

4.7.1 终结符和产生式的优先级 126

4.7.2 结合规则 127

4.8 LR分析表的实际安排 128

第五章 语法制导翻译和中间代码产生 132

5.1 语法制导翻译概说 132

5.2 逆波兰表示法 135

5.2.1 后缀式的计值 135

5.2.2 后缀式的推广 136

5.2.3 语法制导生成后缀式 137

5.3 三元式和树 137

5.3.1 间接三元式 139

5.3.2 树 139

5.4 四元式 140

5.5 简单算术表达式和赋值句到四元式的翻译 141

5.6 布尔表达式到四元式的翻译 144

5.6.1 作为条件控制的布尔式翻译 145

5.7 控制语句的翻译 148

5.7.1 标号和转移语句 148

5.7.2 条件语句 149

5.7.3 循环语句 152

5.7.4 分叉语句 154

5.8 数组元素引用 156

5.8.1 数组元素引用的中间代码 157

5.8.2 赋值句中数组元素的翻译 158

5.8.3 按列为序存放数组元素的情形 160

5.9 过程调用 162

5.9.1 过程调用的四元式产生 162

5.9.2 过程调用和数组元素相混淆的处理 163

5.10 说明语句的翻译 163

5.11 记录结构 165

5.11.1 记录说明的翻译 166

5.11.2 记录结构的引用 167

5.12 输入／输出语句的翻译 168

5.12.1 I/O语句的实现 168

5.12.2 I/O语句的翻译 170

5.12.3 格式语句的处理 171

5.13 自上而下分析制导翻译概说 172

第六章 符号表 178

6.1 符号表的组织和使用 178

6.2 整理与查找 180

6.2.1 线性表 180

6.2.2 对折查找与二叉树 181

6.2.3 杂凑技术 183

6.3 名字的作用范围 185

6.3.1 FORTRAN的符号表组织 185

6.3.2 ALGOL的符号表组织 186

6.4 符号表的内容 189

第七章 运行时存储空间组织 193

7.1 静态存储管理——FORTRAN存储分配 193

7.1.1 数据区 194

7.1.2 公用语句的处理 196

7.1.3 等价语句的处理 197

7.1.4 地址分配 200

7.1.5 临时变量的地址分配 202

7.2 一个简单的栈式存储分配的实现 204

7.2.1 C的活动记录 205

7.2.2 C的过程调用，过程进入，数组空间分配和过程返回 205

7.3 嵌套过程语言的栈式实现 206

7.3.1 嵌套层次显示表DISPLAY和活动记录 207

7.3.2 过程调用，过程进入 208

7.3.3 参数传递 209

7.4 ALGOL的实现 210

7.4.1 分程序结构 211

7.4.2 分程序的进入和退出 212

7.4.3 过程调用，进入和返回 214

7.4.4 参数子程序 215

7.5 分程序结构语言存储分配拾遗 216

第八章 错误的诊察和校正 219

8.1 出错处理概述 219

8.1.1 语法错误 220

8.1.2 语义错误 220

8.1.3 错误处理 221

8.1.4 出错处理系统与编译程序各阶段的联系 222

8.2 词法分析阶段的错误诊察 222

8.3 语法分析（自下而上）阶段的错误诊察 223

8.3.1 算符优先分析法的错误处理 223

8.3.2 LR分析算法的错误处理 226

8.4 自上而下分析的错误诊察 228

8.5 语义错误诊察 231

8.5.1 遏止株连信息 231

8.5.2 遏止重复信息 231

第九章 代码优化 233

9.1 优化概述 233

9.2 局部优化 236

9.3 基本块的DAG表示及其应用 237

9.3.1 基本块的DAG表示 237

9.3.2 DAG的应用 240

9.3.3 DAG构造算法讨论 242

9.4 控制流程分析和循环查找算法 244

9.4.1 程序流图与循环 245

9.4.2 必经结点集 246

9.4.3 查找循环算法 248

9.4.4 可归约流图 250

9.4.5 深度为主查找及其算法 251

9.5 到达-定值与引用-定值链 253

9.5.1 到达-定值数据流方程 253

9.5.2 到达-定值数据流方程的求解 255

9.5.3 引用-定值链（ud链） 257

9.5.4 ud链的应用 257

9.6 循环优化 258

9.6.1 代码外提 258

9.6.2 强度削弱 261

9.6.3 删除归纳变量 263

第十章 数据流分析 271

10.1 活跃变量与定值-引用链（du链） 271

10.1.1 活跃变量的数据流方程 271

10.1.2 活跃变量数据流方程的求解 272

10.1.3 定值-引用链（du链） 273

10.1.4 活跃变量与du链的应用 275

10.2 删除全局公共子表达式 275

10.2.1 可用表达式及其数据流方程 275

10.2.2 可用表达式数据流方程的求解 278

10.2.3 删除全局公共子表达式的算法 278

10.3 复写传播 279

10.4 非常忙表达式和代码提升 281

10.4.1 非常忙表达式数据流方程 283

10.4.2 代码提升 284

10.5 四类数据流方程小结 285

10.6 实施各种优化的综合考虑 286

第十一章 代码生成 293

11.1 一个计算机模型 293

11.2 一个简单代码生成器 294

11.2.1 待用信息 294

11.2.2 寄存器描述和地址描述 295

11.2.3 代码生成算法 295

11.3 寄存器分配 298

11.4 DAG的目标代码 301

11.5 树的目标代码 303