编译技术

编译技术 1

第1章 概论 1

1.1 编译程序的概念 1

1.2 编译过程概述 1

1.3 编译程序的结构 4

1.4 学习构造编译程序 5

习题 5

第2章 文法和语言 6

2.1 符号和符号串 6

2.2 文法和语言的形式定义 7

2.2.1 文法的直观概念 7

2.2.2 文法的形式定义 9

2.2.3 语言的形式定义 9

2.3 文法的类型 11

2.4 上下文无关文法及其语法树 12

2.4.1 上下文无关文法 12

2.4.2 语法树的概念 13

2.4.3 二义性 15

2.5 句型的分析 17

2.5.1 分析技术 17

2.5.2 句型分析的有关问题 18

习题 19

第3章 词法分析 21

3.1 词法分析器的设计 21

3.1.1 词法分析器的功能和输出形式 21

3.1.2 词法分析器作为一个独立子程序 22

3.1.3 词法分析器的实现 22

3.2 正规表达式 28

3.2.1 正规文法 28

3.2.2 正规式 29

3.2.3 正规文法与正规式 30

3.3 有限自动机 32

3.3.1 确定有限自动机 32

3.3.2 非确定有限自动机 33

3.3.3 NFA到DFA的转换 34

3.3.4 确定有限自动机的化简 37

3.4 正规表达式和有限自动机的转换 38

3.5 正规文法和有限自动机的转换 41

3.6 词法分析器的自动产生 42

习题 43

第4章 语法分析 45

4.1 自上而下和自下而上分析法 45

4.1.1 归约与分析树 45

4.1.2 规范归约简述 47

4.1.3 符号栈的使用与分析树的表示 49

4.2 递归下降分析法 51

4.2.1 带回溯的分析法 51

4.2.2 不带回溯的递归下降分析法 53

4.3 算符优先分析法 62

4.3.1 直观算符优先分析法 63

4.3.2 算符优先文法和优先表的构造 67

4.3.3 算符优先分析算法的设计 70

4.3.4 优先函数 73

4.4 LR（0）分析法 75

4.4.1 LR分析器 76

4.4.2 LR文法 79

4.4.3 LR（0）项目集规范簇的构造 80

4.5 SLR分析法 86

4.6 规范LR分析法 91

4.6.1 LR（1）项目集簇的构造 92

4.6.2 LR（1）分析表的构造 94

4.7 LALR分析法 95

4.8 二义文法的应用 98

4.8.1 使用优先级和结合规则来解决分析动作的冲突 98

4.8.2 悬空else的二义性 100

4.9 语法分析器的生成器YACC 102

习题 107

第5章 语法制导翻译和中间代码生成 110

5.1 属性文法 110

5.2 语法制导翻译概述 114

5.3 中间代码的形式 117

5.3.1 逆波兰记号 117

5.3.2 三元式和树形表示 118

5.3.3 四元式 119

5.4 简单赋值语句的翻译 120

5.5 布尔表达式的翻译 123

5.6 控制语句的翻译 128

5.6.1 标号和转移语句 128

5.6.2 条件语句 129

5.6.3 循环语句 132

5.6.4 分叉语句 134

5.7 数组元素引用的翻译 136

5.7.1 数组元素引用的中间代码 138

5.7.2 赋值句中数组元素的翻译 138

5.8 过程调用的翻译 141

5.9 说明语句的翻译 142

5.9.1 简单变量说明的翻译 142

5.9.2 数组说明的翻译 143

习题 145

第6章 符号表 146

6.1 符号表的组织和使用 146

6.2 符号表的整理和查找 148

6.2.1 线性表 148

6.2.2 对折查找与二叉树 149

6.2.3 杂凑技术 151

习题 152

第7章 运行时的存储组织 154

7.1 数据空间的使用和管理 154

7.1.1 静态存储分配 155

7.1.2 动态存储分配 156

7.1.3 栈式动态存储分配 156

7.1.4 堆式动态存储分配 157

7.2 简单的栈式存储分配的实现 157

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

7.4 参数传递 163

7.4.1 传值 164

7.4.2 传地址 165

7.4.3 传结果 166

7.4.4 传名 166

7.4.5 过程参数 166

习题 167

第8章 代码优化 169

8.1 优化概述 169

8.2 局部优化 172

8.2.1 基本块的划分 172

8.2.2 基本块的变换 173

8.2.3 基本块的DAG表示 174

8.2.4 DAG的应用 177

8.3 控制流分析和循环优化 179

8.3.1 程序流图与循环 179

8.3.2 循环 180

8.3.3 循环的查找 181

8.3.4 循环优化 184

8.4 数据流分析和全局优化 188

8.4.1 数据流方程的一般形式 189

8.4.2 到达-定值数据流方程 190

8.4.3 可用表达式及其数据流方程 192

8.4.4 复写传播 195

8.4.5 活跃变量数据流方程 196

8.4.6 非常忙表达式及其数据流方程 197

习题 199

第9章 代码生成 201

9.1 一个简单代码生成器 202

9.1.1 寄存器分配的原则 202

9.1.2 待用信息 202

9.1.3 寄存器描述和地址描述 203

9.1.4 代码生成算法 203

9.2 DAG的目标代码 206

习题 210

附录 编译程序实现 211

参考文献 228

编译技术（6370）自学考试大纲一、课程性质与设置目的 231

二、课程内容与考核目标 231

第1章 概论 231

第2章 文法和语言 232

第3章 词法分析 233

第4章 语法分析 234

第5章 语法制导翻译和中间代码生成 235

第6章 符号表 236

第7章 运行时的存储组织 237

第8章代码优化 237

第9章 代码生成 238

三、有关说明和实施要求 239

附录 题型举例 241