编译原理 本科教学版PDF电子书下载

第1章 引论 1

1.1 语言处理器 1

1.2 一个编译器的结构 2

1.2.1 词法分析 3

1.2.2 语法分析 4

1.2.3 语义分析 5

1.2.4 中间代码生成 5

1.2.5 代码优化 5

1.2.6 代码生成 6

1.2.7 符号表管理 6

1.2.8 将多个步骤组合成趟 6

1.2.9 编译器构造工具 7

1.3 程序设计语言的发展历程 7

1.3.1 走向高级程序设计语言 7

1.3.2 对编译器的影响 8

1.3.3 1.3节的练习 8

1.4 构建一个编译器的相关科学 8

1.4.1 编译器设计和实现中的建模 9

1.4.2 代码优化的科学 9

1.5 编译技术的应用 10

1.5.1 高级程序设计语言的实现 10

1.5.2 针对计算机体系结构的优化 11

1.5.3 新计算机体系结构的设计 12

1.5.4 程序翻译 13

1.5.5 软件生产率工具 14

1.6 程序设计语言基础 15

1.6.1 静态和动态的区别 15

1.6.2 环境与状态 15

1.6.3 静态作用域和块结构 17

1.6.4 显式访问控制 18

1.6.5 动态作用域 19

1.6.6 参数传递机制 20

1.6.7 别名 21

1.6.8 1.6节的练习 22

1.7 第1章 总结 22

1.8 第1章 参考文献 23

第2章 一个简单的语法制导翻译器 24

2.1 引言 24

2.2 语法定义 25

2.2.1 文法定义 26

2.2.2 推导 27

2.2.3 语法分析树 28

2.2.4 二义性 29

2.2.5 运算符的结合性 29

2.2.6 运算符的优先级 30

2.2.7 2.2节的练习 31

2.3 语法制导翻译 32

2.3.1 后缀表示 33

2.3.2 综合属性 33

2.3.3 简单语法制导定义 35

2.3.4 树的遍历 35

2.3.5 翻译方案 35

2.3.6 2.3节的练习 37

2.4 语法分析 37

2.4.1 自顶向下分析方法 38

2.4.2 预测分析法 39

2.4.3 何时使用ε产生式 41

2.4.4 设计一个预测分析器 41

2.4.5 左递归 42

2.4.6 2.4节的练习 42

2.5 简单表达式的翻译器 43

2.5.1 抽象语法和具体语法 43

2.5.2 调整翻译方案 43

2.5.3 非终结符号的过程 44

2.5.4 翻译器的简化 45

2.5.5 完整的程序 46

2.6 词法分析 47

2.6.1 剔除空白和注释 48

2.6.2 预读 48

2.6.3 常量 49

2.6.4 识别关键字和标识符 49

2.6.5 词法分析器 50

2.6.6 2.6节的练习 53

2.7 符号表 53

27.1 为每个作用域设置一个符号表 54

2.7.2 符号表的使用 56

2.8 生成中间代码 57

2.8.1 两种中间表示形式 57

2.8.2 语法树的构造 58

2.8.3 静态检查 61

2.8.4 三地址码 62

2.8.5 2.8节的练习 66

2.9 第2章 总结 66

第3章 词法分析 68

3.1 词法分析器的作用 68

3.1.1 词法分析及语法分析 69

3.1.2 词法单元、模式和词素 69

3.1.3 词法单元的属性 70

3.1.4 词法错误 71

3.1.5 3.1节的练习 71

3.2 词法单元的规约 71

3.2.1 串和语言 72

3.2.2 语言上的运算 72

3.2.3 正则表达式 73

3.2.4 正则定义 74

3.2.5 正则表达式的扩展 75

3.2.6 3.2节的练习 76

3.3 词法单元的识别 78

3.3.1 状态转换图 79

3.3.2 保留字和标识符的识别 80

3.3.3 完成我们的例子 81

3.3.4 基于状态转换图的词法分析器的体系结构 82

3.3.5 3.3节的练习 84

3.4 词法分析器生成工具Lex 86

3.4.1 Lex的使用 86

3.4.2 Lex程序的结构 87

3.4.3 Lex中的冲突解决 89

3.4.4 向前看运算符 89

3.4.5 3.4节的练习 90

3.5 有穷自动机 91

3.5.1 不确定的有穷自动机 91

3.5.2 转换表 92

3.5.3 自动机中输入字符串的接受 92

3.5.4 确定的有穷自动机 93

3.5.5 3.5节的练习 93

3.6 从正则表达式到自动机 94

3.6.1 从NFA到DFA的转换 94

3.6.2 最小化一个DFA的状态数 96

3.6.3 从正则表达式构造NFA 99

3.6.4 字符串处理算法的效率 101

3.6.5 3.6节的练习 103

3.7 词法分析器生成工具的设计 103

3.7.1 生成的词法分析器的结构 103

3.7.2 词法分析器使用的DFA 105

3.7.3 词法分析器的状态最小化 105

3.7.4 实现向前看运算符 105

3.7.5 3.7节的练习 106

3.8 第3章 总结 107

3.9 第3章 参考文献 108

第4章 语法分析 110

4.1 引论 110

4.1.1 语法分析器的作用 110

4.1.2 代表性的文法 111

4.1.3 语法错误的处理 112

4.1.4 错误恢复策略 112

4.2 上下文无关文法 113

4.2.1 上下文无关文法的正式定义 114

4.2.2 符号表示的约定 114

4.2.3 推导 115

4.2.4 语法分析树和推导 116

4.2.5 二义性 117

4.2.6 验证文法生成的语言 118

4.2.7 上下文无关文法和正则表达式 119

4.2.8 4.2节的练习 119

4.3 设计文法 121

4.3.1 词法分析和语法分析 121

4.3.2 消除二义性 122

4.3.3 左递归的消除 123

4.3.4 提取左公因子 124

4.3.5 非上下文无关语言的构造 125

4.3.6 4.3节的练习 126

4.4 自顶向下的语法分析 126

4.4.1 递归下降的语法分析 128

4.4.2 FIRST和FOLLOW 129

4.4.3 LL（1）文法 130

4.4.4 非递归的预测分析 133

4.4.5 预测分析中的错误恢复 134

4.4.6 4.4节的练习 136

4.5 自底向上的语法分析 137

4.5.1 归约 138

4.5.2 句柄剪枝 138

4.5.3 移入-归约语法分析技术 139

4.5.4 移入-归约语法分析中的冲突 140

4.5.5 4.5节的练习 141

4.6 LR语法分析技术介绍：简单LR技术 142

4.6.1 为什么使用LR语法分析器 142

4.6.2 项和LR（0）自动机 143

4.6.3 LR语法分析算法 147

4.6.4 构造SLR语法分析表 150

4.6.5 可行前缀 152

4.6.6 4.6节的练习 153

4.7 更强大的LR语法分析器 154

4.7.1 规范LR（1）项 154

4.7.2 构造LR（1）项集 155

4.7.3 规范LR（1）语法分析表 158

4.7.4 构造LALR语法分析表 159

4.7.5 高效构造LALR语法分析表的方法 162

4.7.6 4.7节的练习 165

4.8 使用二义性文法 165

4.8.1 用优先级和结合性解决冲突 165

4.8.2 “悬空-else”的二义性 167

4.8.3 LR语法分析中的错误恢复 168

4.8.4 4.8节的练习 169

4.9 语法分析器生成工具 170

4.9.1 语法分析器生成工具Yacc 170

4.9.2 使用带有二义性文法的Yacc规约 173

4.9.3 用Lex创建Yacc的词法分析器 175

4.9.4 Yacc中的错误恢复 175

4.9.5 4.9节的练习 176

4.10 第4章 总结 177

4.11 第4章 参考文献 178

第5章 语法制导的翻译 182

5.1 语法制导定义 182

5.1.1 继承属性和综合属性 183

5.1.2 在语法分析树的结点上对SDD求值 184

5.1.3 5.1节的练习 186

5.2 SDD的求值顺序 186

5.2.1 依赖图 186

5.2.2 属性求值的顺序 187

5.2.3 S属性的定义 188

5.2.4 L属性的定义 188

5.2.5 具有受控副作用的语义规则 189

5.2.6 5.2节的练习 190

5.3 语法制导翻译的应用 191

5.3.1 抽象语法树的构造 191

5.3.2 类型的结构 194

5.3.3 5.3节的练习 195

5.4 语法制导的翻译方案 195

5.4.1 后缀翻译方案 195

5.4.2 后缀SDT的语法分析栈实现 196

5.4.3 产生式内部带有语义动作的SDT 197

5.4.4 从SDT中消除左递归 198

5.4.5 L属性定义的SDT 200

5.4.6 5.4节的练习 204

5.5 实现L属性的SDD 204

5.5.1 在递归下降语法分析过程中进行翻译 205

5.5.2 边扫描边生成代码 207

5.5.3 L属性的SDD和LL语法分析 208

5.5.4 L属性的SDD的自底向上语法分析 212

5.5.5 5.5节的练习 214

5.6 第5章 总结 215

5.7 第5章 参考文献 216

第6章 中间代码生成 217

6.1 语法树的变体 218

6.1.1 表达式的有向无环图 218

6.1.2 构造DAG的值编码方法 219

6.1.3 6.1节的练习 220

6.2 三地址代码 221

6.2.1 地址和指令 221

6.2.2 四元式表示 223

6.2.3 三元式表示 223

6.2.4 静态单赋值形式 225

6.2.5 6.2节的练习 225

6.3 类型和声明 225

6.3.1 类型表达式 226

6.3.2 类型等价 227

6.3.3 声明 227

6.3.4 局部变量名的存储布局 227

6.3.5 声明的序列 229

6.3.6 记录和类中的字段 230

6.3.7 6.3节的练习 230

6.4 表达式的翻译 231

6.4.1 表达式中的运算 231

6.4.2 增量翻译 232

6.4.3 数组元素的寻址 233

6.4.4 数组引用的翻译 234

6.4.5 6.4节的练习 235

6.5 类型检查 236

6.5.1 类型检查规则 236

6.5.2 类型转换 237

6.5.3 函数和运算符的重载 238

6.5.4 6.5节的练习 239

6.6 控制流 239

6.6.1 布尔表达式 240

6.6.2 短路代码 240

6.6.3 控制流语句 240

6.6.4 布尔表达式的控制流翻译 242

6.6.5 避免生成冗余的goto指令 244

6.6.6 布尔值和跳转代码 245

6.6.7 6.6节的练习 246

6.7 回填 246

6.7.1 使用回填技术的一趟式目标代码生成 246

6.7.2 布尔表达式的回填 247

6.7.3 控制转移语句 249

6.7.4 break语句、continue语句和goto语句 250

6.7.5 6.7节的练习 251

6.8 switch语句 252

6.8.1 switch语句的翻译 252

6.8.2 switch语句的语法制导翻译 253

6.8.3 6.8节的练习 254

6.9 过程的中间代码 254

6.10 第6章 总结 255

6.11 第6章 参考文献 256

第7章 运行时刻环境 258

7.1 存储组织 258

7.2 空间的栈式分配 259

7.2.1 活动树 260

7.2.2 活动记录 262

7.2.3 调用代码序列 263

7.2.4 栈中的变长数据 265

7.2.5 7.2节的练习 266

7.3 栈中非局部数据的访问 267

7.3.1 没有嵌套过程时的数据访问 267

7.3.2 和嵌套过程相关的问题 267

7.3.3 一个支持嵌套过程声明的语言 268

7.3.4 嵌套深度 268

7.3.5 访问链 269

7.3.6 处理访问链 270

7.3.7 过程型参数的访问链 271

7.3.8 显示表 272

7.3.9 7.3节的练习 273

7.4 堆管理 274

7.4.1 存储管理器 274

7.4.2 一台计算机的存储层次结构 275

7.4.3 程序中的局部性 276

7.4.4 碎片整理 278

7.4.5 人工回收请求 280

7.4.6 7.4节的练习 282

7.5 垃圾回收概述 282

7.5.1 垃圾回收器的设计目标 282

7.5.2 可达性 284

7.5.3 引用计数垃圾回收器 285

7.5.4 7.5节的练习 286

7.6 基于跟踪的回收的介绍 286

7.6.1 基本的标记-清扫式回收器 287

7.6.2 基本抽象 288

7.6.3 标记-清扫式算法的优化 289

7.6.4 标记并压缩的垃圾回收器 290

7.6.5 复制回收器 292

7.6.6 开销的比较 293

7.6.7 7.6节的练习 294

7.7 第7章 总结 294

7.8 第7章 参考文献 295

第8章 代码生成 298

8.1 代码生成器设计中的问题 299

8.1.1 代码生成器的输入 299

8.1.2 目标程序 299

8.1.3 指令选择 300

8.1.4 寄存器分配 301

8.1.5 求值顺序 302

8.2 目标语言 302

8.2.1 一个简单的目标机模型 302

8.2.2 程序和指令的代价 304

8.2.3 8.2节的练习 304

8.3 目标代码中的地址 306

8.3.1 静态分配 306

8.3.2 栈分配 307

8.3.3 名字的运行时刻地址 309

8.3.4 8.3节的练习 309

8.4 基本块和流图 310

8.4.1 基本块 311

8.4.2 后续使用信息 312

8.4.3 流图 312

8.4.4 流图的表示方式 313

8.4.5 循环 313

8.4.6 8.4节的练习 314

8.5 基本块的优化 314

8.5.1 基本块的DAG表示 314

8.5.2 寻找局部公共子表达式 315

8.5.3 消除死代码 316

8.5.4 代数恒等式的使用 316

8.5.5 数组引用的表示 317

8.5.6 指针赋值和过程调用 318

8.5.7 从DAG到基本块的重组 319

8.5.8 8.5节的练习 320

8.6 一个简单的代码生成器 320

8.6.1 寄存器和地址描述符 321

8.6.2 代码生成算法 321

8.6.3 函数getReg的设计 324

8.6.4 8.6节的练习 324

8.7 窥孔优化 325

8.7.1 消除冗余的加载和保存指令 325

8.7.2 消除不可达代码 326

8.7.3 控制流优化 326

8.7.4 代数化简和强度消减 327

8.7.5 使用机器特有的指令 327

8.7.6 8.7节的练习 327

8.8 寄存器分配和指派 327

8.8.1 全局寄存器分配 328

8.8.2 使用计数 328

8.8.3 外层循环的寄存器指派 330

8.8.4 通过图着色方法进行寄存器分配 330

8.8.5 8.8节的练习 331

8.9 通过树重写来选择指令 331

8.9.1 树翻译方案 331

8.9.2 通过覆盖一个输入树来生成代码 333

8.9.3 通过扫描进行模式匹配 334

8.9.4 用于语义检查的例程 335

8.9.5 通用的树匹配方法 335

8.9.6 8.9节的练习 336

8.10 表达式的优化代码的生成 337

8.10.1 Ershov数 337

8.10.2 从带标号的表达式树生成代码 337

8.10.3 寄存器数量不足时的表达式求值 338

8.10.4 8.10节的练习 340

8.11 使用动态规划的代码生成 340

8.11.1 连续求值 340

8.11.2 动态规划的算法 341

8.11.3 8.11节的练习 343

8.12 第8章 总结 343

8.13 第8章 参考文献 344

第9章 机器无关优化 346

9.1 优化的主要来源 346

9.1.1 冗余的原因 346

9.1.2 一个贯穿本章的例子：快速排序 347

9.1.3 保持语义不变的转换 348

9.1.4 全局公共子表达式 349

9.1.5 复制传播 350

9.1.6 死代码消除 350

9.1.7 代码移动 351

9.1.8 归纳变量和强度消减 351

9.1.9 9.1节的练习 353

9.2 数据流分析简介 354

9.2.1 数据流抽象 354

9.2.2 数据流分析模式 355

9.2.3 基本块上的数据流模式 356

9.2.4 到达定值 357

9.2.5 活跃变量分析 362

9.2.6 可用表达式 363

9.2.7 小结 365

9.2.8 9.2节的练习 365

9.3 数据流分析基础 367

9.3.1 半格 368

9.3.2 传递函数 371

9.3.3 通用框架的迭代算法 372

9.3.4 数据流解的含义 374

9.3.5 9.3节的练习 375

9.4 常量传播 376

9.4.1 常量传播框架的数据流值 376

9.4.2 常量传播框架的交汇运算 377

9.4.3 常量传播框架的传递函数 377

9.4.4 常量传递框架的单调性 378

9.4.5 常量传播框架的不可分配性 378

9.4.6 对算法结果的解释 379

9.4.7 9.4节的练习 380

9.5 流图中的循环 380

9.5.1 支配结点 380

9.5.2 深度优先排序 382

9.5.3 深度优先生成树中的边 384

9.5.4 回边和可归约性 384

9.5.5 流图的深度 385

9.5.6 自然循环 385

9.5.7 迭代数据流算法的收敛速度 386

9.5.8 9.5节的练习 388

9.6 第9章 总结 389

9.7 第9章 参考文献 391

附录 一个完整的编译器前端 394