编译技术PDF电子书下载

第1部分 基 础篇 3

第1章 编译概述 3

1.1 什么是程序设计语言 3

1.1.1 程序设计语言的定义方法 4

1.1.2 程序设计语言的处理系统 5

1.1.3 编译程序和解释程序 5

1.2 与编译程序相关的处理系统 8

1.3 编译程序和程序设计环境 10

1.4 编译程序的构造 12

1.5 编译技术在软件工程中的应用 19

练习1 21

第2章 文法和语言的概念和表示 22

2.1 文法的非形式讨论 22

2.1.1 语法树 22

2.1.2 规则 23

2.1.3 由规则推导句子 24

练习2-1 26

2.2 符号、符号串及其集合的运算 27

2.2.1 字母表和符号串 27

2.2.2 符号串及其集合的运算 27

练习2-2 29

2.3 文法和语言的形式定义 29

2.3.1 文法的形式定义 29

2.3.2 推导的形式定义 31

2.3.3 语言的形式定义 32

2.3.4 递归规则与递归文法 35

2.3.5 短语、简单短语和句柄 36

练习2-3 38

2.4 语法树和二义性 39

2.4.1 推导与语法树 39

2.4.2 文法的二义性 43

练习2-4 46

2.5 符号串的分析 48

2.5.1 自顶向下分析 49

2.5.2 自底向上分析 50

2.6 有关文法的实用限制 51

练习2-5 53

2.7 扩充的BNF表示和语法图 53

2.7.1 扩充的BNF表示 53

2.7.2 语法图 56

2.8 文法和语言分类 57

第3章 词法分析程序的设计 60

3.1 词法分析程序的功能及实现方案 60

3.2 单词的种类及词法分析程序的输出形式 61

3.3 正则文法及其状态图 63

3.3.1 状态图 63

3.3.2 状态图的使用 64

3.4 词法分析程序的设计与实现 65

3.4.1 文法及其状态图 65

3.4.2 词法分析程序的构造 67

3.4.3 词法分析程序的实现 70

练习3 73

第4章 语法分析（一） 74

4.1 自顶向下分析方法 74

4.1.1 带回溯的自顶向下分析方法 74

4.1.2 存在的问题及解决办法 76

练习4-1 84

4.2 递归下降分析法 84

4.3 基于递归下降分析法的语法分析程序构造 85

练习4-2 91

第5章 符号表管理技术 93

5.1 概述 93

5.1.1 符号表的概念及建立和访问时间 93

5.1.2 符号表的重要性和作用 95

5.1.3 在符号表上的操作 95

5.2 符号表的组织和内容 97

5.2.1 符号表的结构与内容 97

5.2.2 符号表的组织方式 99

5.3 非分程序结构语言的符号表组织 101

5.3.1 标识符的作用域及基本处理方法 101

5.3.2 符号表的组织方式 102

5.4 分程序结构语言的符号表组织 109

5.4.1 标识符的作用域及基本处理方法 109

5.4.2 定位和重定位操作 110

5.4.3 符号表的组织方式 112

练习5 115

第6章 运行时的存储组织及管理 117

6.1 静态存储分配 117

练习6-1 119

6.2 动态存储分配 120

6.2.1 活动记录 121

6.2.2 参数区 121

6.2.3 display区 122

6.2.4 运行时的地址计算 125

6.2.5 递归过程的处理 125

6.3 内存垃圾回收器 128

6.3.1 引用计数 128

6.3.2 标记和清除垃圾回收器 129

6.3.3 标记紧缩算法 129

6.3.4 拷贝回收算法 130

6.3.5 分代垃圾回收器 130

练习6-2 133

第7章 源程序的中间形式 135

7.1 波兰表示 135

7.2 N-元表示 137

7.3 抽象语法树 139

7.4 抽象机代码 140

7.4.1 可移植性和抽象机 141

7.4.2 Pascal的P-code抽象机 142

7.4.3 P-code指令 143

练习7 144

第8章 错误处理 145

8.1 概述 145

8.2 错误的分类 146

8.3 错误的检查与报告 146

8.4 错误处理技术 148

8.4.1 错误改正 149

8.4.2 错误局部化处理 149

8.4.3 目标程序运行时错误检测与处理 152

8.4.4 遏止重复的错误信息 152

第9章 语法制导翻译技术 153

9.1 翻译文法 154

9.2 语法制导翻译 156

9.3 属性翻译文法 158

9.3.1 综合属性 158

9.3.2 继承属性 160

9.3.3 属性翻译文法 162

9.3.4 属性翻译文法举例：算术表达式的翻译 164

练习9-1 166

9.4 自顶向下语法制导翻译 168

9.4.1 翻译文法的自顶向下翻译 168

练习9-2 172

9.4.2 属性翻译文法的自顶向下翻译 173

练习9-3 180

第10章 语义分析和代码生成 182

10.1 语义分析的概念 182

10.2 栈式抽象机及其汇编指令 184

10.3 声明语句的处理 186

10.3.1 常量类型 188

10.3.2 简单变量 188

10.3.3 数组变量 190

10.3.4 记录变量 192

10.3.5 过程声明 193

10.4 表达式语句 194

10.5 赋值语句 201

10.6 控制语句 203

10.6.1 if语句 203

10.6.2 分情形语句 205

10.6.3 repeat-while语句 208

10.6.4 for循环语句 209

10.7 过程调用和返回语句 211

10.7.1 参数的基本传递形式 211

10.7.2 过程调用 213

10.7.3 返回语句和过程终止 217

10.8 输入/输出语句 218

10.8.1 输入语句 218

10.8.2 输出语句 221

10.9 编译程序的辅助功能 222

练习10 223

第2部分 提 高篇 227

第11章 词法分析程序的自动生成技术 227

11.1 正则文法与正则表达式 227

11.1.1 正则表达式 227

11.1.2 正则文法转换为正则表达式 230

11.1.3 正则表达式转换为正则文法 231

11.2 有穷自动机 231

11.2.1 确定的有穷自动机 232

11.2.2 不确定的有穷自动机 233

11.2.3 NFA的确定化 235

11.2.4 确定有穷自动机的化简（最小化） 238

11.2.5 正则表达式与有穷自动机的等价性 242

11.2.6 正则文法与有穷自动机的等价性 246

11.3 词法分析程序的自动生 248

成器 248

11.3.1 Lex源程序（Lex的输入文件） 248

11.3.2 Lex的实现 250

练习11 254

第12章 语法分析（二） 256

12.1 LL（1）分析方法 256

12.1.1 LL（1）分析器的逻辑结构及工作过程 256

12.1.2 LL（1）分析表的构造方法 259

练习12-1 264

12.2 自底向上分析方法 265

12.3 算法优先分析法 268

12.3.1 方法概述 268

12.3.2 直观算符优先分析法 270

12.3.3 算符优先分析法的进一步讨论 273

练习12-2 279

12.4 LR语法分析方法 280

12.4.1 概念和术语 281

练习12-3 282

12.4.2 LR分析算法 282

练习12-4 288

12.4.3 LR文法 288

12.4.4 构造SLR语法分析表 289

练习12-5 297

12.4.5 构造规范LR语法分析表 299

练习12-6 304

12.4.6 构造LALR语法分析表 305

练习12-7 309

第13章 语法制导翻译技术（二） 311

13.1 LL（1）文法的语法制导翻译 311

13.1.1 翻译文法的自顶向下翻译——LL（1）翻译器 311

练习13-1 313

13.1.2 属性文法自顶向下翻译的实现——下推机法 314

练习13-2 320

13.2 自底向上语法制导翻译 321

13.2.1 波兰翻译 322

13.2.2 S-属性文法 323

练习13-3 325

第14章 代码优化 327

14.1 基本块和流图 328

14.2 基本块内优化 330

14.2.1 基本块的DAG图表示 331

14.2.2 消除局部公共子表达式 331

14.2.3 数组、指针及函数调用 332

14.2.4 从DAG图重新导出中间代码 334

14.2.5 窥孔优化 336

14.2.6 常数合并和传播 337

14.3 全局优化 338

14.3.1 数据流分析 338

14.3.2 活跃变量分析 344

14.3.3 定义-使用链、网和冲突图 346

14.3.4 消除全局公共子表达式 351

14.3.5 复制传播 352

14.3.6 死代码删除 353

14.4 循环优化 353

14.4.1 循环交换 354

14.4.2 循环展开 354

14.4.3 代码外提和循环强度削弱 355

练习14 356

第15章 目标代码生成及优化 357

15.1 微处理器体系结构简介 358

15.1.1 指令集架构 359

15.1.2 存储层次架构 362

15.1.3 流水线 364

15.2 地址空间 367

15.2.1 程序地址空间的实例分析 369

15.2.2 程序运行栈的设计 371

15.3 寄存器的分配和指派 374

15.3.1 全局寄存器分配 374

15.3.2 临时寄存器分配 377

15.4 指令选择 379

练习15 381

第16章 编译程序生成方法和工具 383

16.1 编译程序的书写语言 383

16.2 自展 384

16.3 移植 385

16.4 编译程序的生成工具 386

16.4.1 语法分析器的生成器YACC 387

16.4.2 用YACC处理二义文法 390

16.4.3 用Lex建立YACC的词法分析器 393

16.4.4 YACC的错误恢复 394

练习16 396

第3部分 实 例篇 399

第17章 PL/O简单编译系统 399

17.1 PL/O语言 399

17.2 PL/O编译系统结构 404

17.3 PL/O的词法分析 406

17.4 PL/O的语法分析 407

17.5 出错处理 409

17.6 目标代码的生成和解释执行 411

17.7 PL/O程序编译和运行举例 414

第18章 Pascal-S编译系统 427

18.1 Pascal-S语言 427

18.2 Pascal-S编译程序的结构 434

18.3 Pascal-S编译程序 439

18.3.1 表格 439

18.3.2 编译初启 446

18.3.3 实用程序 447

18.3.4 词法分析及处理 448

18.3.5 语法分析处理 449

18.3.6 出错处理 455

18.4 Pascal-S解释执行程序 458

18.4.1 P代码指令系统 458

18.4.2 运行栈 461

18.4.3 运行时的display 462

18.4.4 运行出错处理和现场剖析打印 464

18.5 编译及运行的例子 465

参考文献 479