编译程序原理与技术PDF电子书下载

1 引论 1

1.1 什么是编译程序 1

1.2 解释性程序 1

1.3 编译程序的基本结构 3

1.4 程序语言的语法与语义 8

1.5 程序设计语言设计、编译程序设计及计算机设计之间的关系 9

练习 1 11

2 一个简单的编译程序 13

2.1 语言（XL）概述 13

2.2 XL的词法分析程序 14

2.3 XL递归下降分析 17

2.4 生成中间代码 20

2.4.1 中间语言 20

2.4.2 临时变量 20

2.4.3 动作符号 21

2.4.4 语义信息 22

练习 2 25

3 词法分析 26

3.1 输入子系统 26

3.2 词法分析的两个途径 30

3.3 正规表达式 31

3.3.1 基本定义 32

3.3.2 正规表达式 33

3.4 有限自动机 35

3.5 从正规表达式到词法分析程序 38

3.6 LEX——一个建立词法分析器的自动工具 40

3.7 实践中的几个问题 48

3.7.1 保留字 48

3.7.2 向前看多字符问题 49

3.7.3 词法错误的矫正 50

3.8 正规表达式到有限自动机的转换 51

3.8.1 把正规表达式转换为NFA 51

3.8.2 从NFA到DFA的转换——子集构造法 55

3.8.3 DFA的优化——极小化 58

练习 3 62

4 上下文无关文法与分析 65

4.1 基本概念与定义 65

4.2 推导与分析树 67

4.3 文法的设计 70

4.3.1 右线性文法 71

4.3.2 验证由文法生成的语言 72

4.3.3 消除歧义 73

4.3.4 递归文法 77

4.3.5 提左公因子 80

4.4 文法分析算法 81

4.4.1 空串非终结符 81

4.4.2 FIRST集合及其计算 82

4.4.3 FOLLOW集合及其计算 83

4.5 上下文无关文法的限度 85

练习 4 86

5 LL（1）文法与分析器 89

5.1 自上而下分析与下推自动机 89

5.1.1 作为下推自动机的递归下降分析器 91

5.1.2 利用下推自动机进行自上而下的分析算法 92

5.2 LL（1）预测函数 93

5.3 LL（1）分析表 96

5.4 一个LL（1）分析表及驱动程序实例 97

5.5 LL的自动生成工具 100

5.5.1 LLama 100

5.5.2 LLGen 103

5.6 LL（1）文法的构造 106

5.7 自上而下分析中的查错恢复问题 108

练习 5 110

6 LR分析 113

6.1 自下而上的分析过程——移入归约分析 113

6.2 利用状态机实现对LR分析器的控制 118

6.3 建立LR分析表的基本理论 124

6.3.1 LR（0）文法 124

6.3.2 SLR（1）文法 130

6.3.3 LR（1）文法 133

6.3.4 LALR（1）文法 138

6.4 LR分析表的压缩表示 146

6.5 歧义文法的利用 150

6.6 LR分析中的查错恢复问题 155

6.7 LALR（1）分析器的自动生成工具——YACC与OCCS 156

6.7.1 YACC程序 156

6.7.2 YACC中如何利用歧义文法 158

6.7.3 利用Lex建立YACC的词法分析程序 160

6.7.4 YACC中的查错恢复方法 161

练习 6 162

7 语法制导的翻译 166

7.1 增广文法 166

7.2 属性文法 169

7.3 LL分析中的语义处理技术 174

7.3.1 表驱动的LL分析中使用的增广文法 174

7.3.2 下推自动机中属性文法的实施 174

7.3.3 LL中属性的$表示法 175

7.4 LR分析中的语义处理技术 176

7.4.1 LR分析中属性处理的特点 176

7.4.2 一个LR语义处理流程的例子 177

7.4.3 建立LR分析用的属性文法及LR分析中属性的$表示法 178

7.4.4 嵌入动作与语法变换 180

7.5 语义栈的类型描述 182

7.6 中间语言表示——IR 183

7.6.1 IR的一般形式 183

7.6.2 C代码：一种简单的中间语言与虚拟机 185

7.6.2.1 C虚拟机 185

7.6.2.2 C虚拟机的存储管理 186

7.6.2.3 C代码描述 187

练习 7 195

8.1 符号表模块的基本结构 196

8 符号表 196

8.2 符号表数据库的数据结构 197

8.3 一个分程序结构的哈希符号表 201

8.3.1 基本数据结构 201

8.3.2 分程序结构 203

8.3.3 一种简单的分程序结构符号表的实现方法 204

8.3.4 符号表的高级维护层 205

练习 8 211

9.1 静态分配 214

9 运行时存储器的组织 214

9.2 栈式分配 215

9.3 堆式分配 219

9.4 静态键与动态键 221

练习 9 223

10 声明的语义处理技术 225

10.1 简单变量声明的处理 225

10.2 结构与联合声明的处理 232

10.3 枚举类型声明的处理 236

10.4 函数声明与定义的处理 238

10.5 分程序的处理 245

练习 10 247

11 C代码生成器的接口gen（）子程序 249

练习 11 259

12 表达式的语义处理 261

12.1 临时变量的分配 261

12.2 左值与右值 263

12.3 临时变量的表示——一种支持左右值实现的数据结构 268

12.4 单目运算符的语义处理 270

12.5 双目运算符的处理 279

练习 12 284

13 控制语句的语义处理 286

13.1 简单控制语句的语义处理 287

13.2 条件语句的语义处理 288

13.3 循环语句break与continue语句的语义处理 290

13.4 switch语句的语义处理 294

练习 13 299

14.1 分析器的优化 301

14.2 线性（窥孔）优化 301

14 代码优化 301

14.2.1 强度削减 302

14.2.2 常数折合与常数传播 303

14.2.3 死变量与死代码 305

14.2.4 窥孔优化之例 308

14.3 语法树上的优化 310

14.3.1 从逆波兰至语法树 310

14.3.2 公共子表达式节省 313

14.3.3 寄存器分配 316

14.3.4 局部循环优化 317

练习 14 318

15 代码的生成 320

15.1 寄存器与临时单元的管理 320

15.2 一个简单的代码生成器 322

15.3 一个简单的寄存器分配方案 324

15.4 从树生成代码 329

15.5 代码生成器的自动化技术 332

15.5.1 基于文法的代码生成器 335

15.5.2 基于树重写的代码生成器的生成器 337

练习 15 337

参考文献 340