编译原理PDF电子书下载

第1章 引论 1

1.1 程序设计语言 1

1.2 程序设计语言的翻译 4

1.3 编译程序的总体结构 8

1.4 编译程序的组织 15

1.5 编译程序的生成 17

1.6 本章小结 22

习题 22

第2章 高级语言及其文法 24

2.1 语言概述 24

2.2 基本定义 26

2.3 文法的定义 31

2.4 文法的分类 40

2.5 CFG的语法树 46

2.6 CFG的二义性 53

2.7 本章小结 57

习题 58

第3章 词法分析 64

3.1 词法分析器的功能 64

3.1.1 单词的分类与表示 65

3.1.2 词法分析器的输出 67

3.1.3 源程序的输入缓冲与预处理 68

3.1.4 词法分析阶段的错误处理 70

3.1.5 词法分析器的位置 72

3.2 单词的描述 73

3.2.1 正则文法 73

3.2.2 正则表达式 74

3.2.3 正则表达式与正则文法的等价性 77

3.2.4 有穷状态自动机 83

3.2.5 状态转换图 86

3.2.6 正则表达式转换为状态转换图 87

3.3 单词的识别 89

3.3.1 有穷状态自动机与单词识别的关系 89

3.3.2 单词识别的状态转换图表示 93

3.3.3 几种典型的单词识别问题 96

3.3.4 状态转换图的实现 98

3.3.5 词法分析程序的编写 103

3.4 词法分析程序的自动生成 106

3.4.1 Lex源程序 106

3.4.2 Lex的实现原理 111

3.5 本章小结 112

习题 112

第4章 自顶向下的语法分析 118

4.1 语法分析概述 118

4.2 自顶向下的语法分析面临的问题与文法的改造 119

4.2.1 自顶向下分析面临的问题 120

4.2.2 对上下文无关文法的改造 123

4.2.3 LL（1）文法 127

4.3 预测分析法 131

4.3.1 预测分析器的构成 131

4.3.2 预测分析表的构造 134

4.3.3 预测分析中错误的处理 134

4.4 递归下降分析法 137

4.4.1 递归下降分析法的基本思想 137

4.4.2 语法图和递归子程序法 138

4.4.3 基于语法图的语法分析器的工作方式 140

4.4.4 语法图的化简与实现 140

4.4.5 递归子程序法的实现步骤 143

4.5 本章小结 143

习题 144

第5章 自底向上的语法分析 148

5.1 自底向上的语法分析概述 148

5.1.1 移进-归约分析 149

5.1.2 优先法 151

5.1.3 状态法 152

5.2 算符优先分析法 155

5.2.1 算符优先文法 155

5.2.2 算符优先矩阵的构造 157

5.2.3 算符优先分析算法 161

5.2.4 优先函数 164

5.2.5 算符优先分析的出错处理 167

5.3 LR分析法 169

5.3.1 LR分析算法 169

5.3.2 LR（0）分析表的构造 173

5.3.3 SLR（1）分析表的构造 181

5.3.4 LR（1）分析表的构造 184

5.3.5 LALR（1）分析表的构造 189

5.3.6 二义性文法的应用 197

5.3.7 LR分析中的出错处理 200

5.4 语法分析程序的自动生成工具Yacc 202

5.4.1 Yacc源程序的结构 203

5.4.2 Yacc源程序的声明部分 204

5.4.3 Yacc源程序的规则部分 205

5.4.4 Yacc源程序的例程部分 206

5.4.5 Yacc对二义性文法的处理 207

5.4.6 Yacc的出错处理 209

5.5 本章小结 209

习题 210

第6章 语法制导翻译与属性文法 215

6.1 语法制导翻译概述 215

6.2 语法制导定义 217

6.3 属性计算 222

6.3.1 依赖图 222

6.3.2 属性的计算顺序 224

6.3.3 S-属性定义 225

6.3.4 L-属性定义 225

6.3.5 属性计算示例 227

6.4 翻译模式 231

6.4.1 翻译模式与语义动作的执行时机 231

6.4.2 S-属性定义的自底向上翻译 235

6.4.3 L-属性定义的自顶向下翻译 238

6.4.4 L-属性定义的自底向上翻译 244

6.5 本章小结 249

习题 249

第7章 语义分析与中间代码生成 252

7.1 中间代码的形式 252

7.1.1 逆波兰表示 252

7.1.2 三地址码 253

7.1.3 图表示 257

7.2 声明语句的翻译 260

7.2.1 类型表达式 260

7.2.2 类型等价 262

7.2.3 声明语句的文法 262

7.2.4 过程内声明语句的翻译 262

7.2.5 嵌套过程中声明语句的翻译 264

7.2.6 记录的翻译 266

7.3 赋值语句的翻译 267

7.3.1 简单赋值语句的翻译 267

7.3.2 数组元素的寻址 268

7.3.3 带有数组引用的赋值语句的翻译 270

7.3.4 记录域的访问 272

7.4 类型检查 273

7.4.1 类型检查的规则 273

7.4.2 类型转换 274

7.5 控制结构的翻译 276

7.5.1 布尔表达式的翻译 277

7.5.2 常见控制结构的翻译 279

7.5.3 布尔表达式的控制流翻译 281

7.5.4 混合模式的布尔表达式翻译 283

7.6 回填 285

7.6.1 布尔表达式的回填式翻译 285

7.6.2 常用控制流语句的回填式翻译 288

7.6.3 for循环语句的回填式翻译 293

7.6.4 repeat语句的回填式翻译 294

7.6.5 break、continue及goto语句的翻译 294

7.7 switch语句的翻译 295

7.7.1 switch语句翻译的基本思想 295

7.7.2 switch语句的语法制导翻译 296

7.8 过程调用和返回语句的翻译 298

7.9 输入输出语句的翻译 300

7.10 本章小结 302

习题 302

第8章 符号表管理 307

8.1 符号表的作用 307

8.2 符号表中存放的信息 309

8.2.1 符号表中的名字 309

8.2.2 符号表中的属性 311

8.2.3 符号的地址属性 312

8.3 符号表的组织结构 313

8.3.1 符号表的线性表实现 313

8.3.2 符号表的散列表实现 314

8.4 符号表与作用域 317

8.4.1 程序块结构的符号表 318

8.4.2 程序块结构符号表的其他实现 320

8.4.3 C语言的符号表 323

8.4.4 嵌套过程的符号表 324

8.5 本章小结 325

习题 325

第9章 运行时的存储组织 327

9.1 与存储组织有关的源语言概念与特征 327

9.1.1 名字及其绑定 327

9.1.2 声明的作用域 328

9.1.3 过程及其活动 331

9.1.4 参数传递方式 332

9.1.5 对变长数据及用户自由申请空间的支持 334

9.2 存储组织 335

9.2.1 运行时内存的划分 335

9.2.2 活动记录 336

9.2.3 局部数据的组织 337

9.2.4 全局存储分配策略 337

9.3 静态存储分配 338

9.4 栈式存储分配 340

9.4.1 调用序列和返回序列 341

9.4.2 C语言的过程调用和过程返回 342

9.4.3 栈中的可变长数据 343

9.5 栈中非局部数据的访问 344

9.5.1 无嵌套过程的静态作用域的实现 345

9.5.2 包含嵌套过程的静态作用域的实现 346

9.5.3 动态作用域的实现 351

9.6 堆管理 352

9.6.1 内存管理器 352

9.6.2 内存体系 353

9.6.3 程序中的局部性 354

9.6.4 降低碎片量的堆区空间管理策略 355

9.6.5 人工回收请求 357

9.7 本章小结 359

习题 360

第10章 代码优化 363

10.1 优化的种类 363

10.1.1 公共子表达式删除 364

10.1.2 复制传播 366

10.1.3 无用代码删除 366

10.1.4 代码外提 367

10.1.5 强度削弱和归纳变量删除 367

10.2 控制流分析 369

10.2.1 基本块 369

10.2.2 流图 370

10.2.3 循环 371

10.3 数据流分析 374

10.3.1 数据流方程的一般形式 374

10.3.2 到达-定义分析 375

10.3.3 活跃变量分析 377

10.3.4 可用表达式分析 378

10.4 局部优化 380

10.4.1 基本块的DAG表示 380

10.4.2 局部公共子表达式删除 381

10.4.3 无用代码删除 382

10.4.4 代数恒等式的使用 382

10.4.5 数组引用的DAG表示 383

10.4.6 指针赋值和过程调用的DAG表示 384

10.4.7 从DAG到基本块的重组 385

10.5 循环优化 386

10.5.1 循环不变计算的检测 386

10.5.2 代码外提 387

10.5.3 归纳变量删除和强度削弱 389

10.5.4 带有循环不变表达式的归纳变量 393

10.6 全局优化 393

10.6.1 全局公共子表达式的删除 393

10.6.2 复制传播 395

10.7 本章小结 396

习题 397

第11章 代码生成 400

11.1 代码生成器设计中的问题 400

11.1.1 代码生成器的输入 400

11.1.2 目标代码的形式 400

11.1.3 指令选择 401

11.1.4 寄存器分配 401

11.1.5 计算顺序选择 402

11.2 目标语言 402

11.2.1 目标机模型 402

11.2.2 程序和指令的开销 403

11.2.3 变量的运行时刻地址 404

11.3 一个简单的代码生成器 404

11.3.1 后续引用信息 405

11.3.2 寄存器描述符与地址描述符 406

11.3.3 代码生成算法 406

11.3.4 常用三地址码的代码生成 408

11.4 窥孔优化 409

11.4.1 冗余指令消除 410

11.4.2 不可达代码消除 410

11.4.3 强度削弱 411

11.4.4 特殊机器指令的使用 411

11.4.5 其他处理 411

11.5 寄存器分配与指派 411

11.5.1 全局寄存器分配 411

11.5.2 引用计数 412

11.5.3 外层循环的寄存器指派 413

11.6 本章小结 414

习题 414

附录 “编译原理”课程教学设计 416

缩写符号 424

词汇索引 425

参考文献 438