编译原理及编译程序构造 第2版PDF电子书下载

1 引论 1

1.1程序设计语言与编译 1

1.2编译程序概述 3

1.2.1词法分析 3

1.2.2语法分析 4

1.2.3中间代码生成 5

1.2.4优化 5

1.2.5目标代码生成 6

1.2.6表格与表格管理 6

1.2.7出错处理 8

1.2.8遍 9

1.3编译程序生成 11

1.4编译程序构造 12

习题 12

2 编译基础知识 13

2.1字母表与符号串 13

2.1.1符号串集合的运算 13

2.1.2符号串的前缀、后缀及子串 14

2.1.3字母表的闭包与正闭包 14

2.2文法与语言的关系 14

2.2.1文法的直观概念 14

2.2.2文法与语言的形式定义 18

2.3文法构造与文法简化 21

2.3.1由语言构造文法的例子 21

2.3.2文法的简化 22

2.3.3构造无ε产生式的上下文无关文法 23

2.4语法树与文法的二义性 24

2.4.1语法树 24

2.4.2文法的二义性 26

习题 27

3 词法分析 30

3.1正规文法和有限自动机 30

3.1.1正规文法、正规集与正规式 30

3.1.2有限自动机 32

3.1.3正规式与有限自动机之间的关系 37

3.1.4正规文法与有限自动机 40

3.2词法分析程序 42

3.2.1预处理与超前搜索 42

3.2.2扫描器的输出格式 44

3.2.3扫描器的设计 46

3.3词法分析程序的自动生成 52

3.3.1 LEX语言 53

3.3.2 LEX编译程序的构造 55

习题 57

4 自上而下语法分析 60

4.1下推自动机 60

4.2 自上而下分析法的一般问题 61

4.2.1消除左递归 63

4.2.2消除回溯——预测与提左因子 65

4.3预测分析程序与LL（1）文法 66

4.3.1求串α的终结首符集和非终结符A的随符集 68

4.3.2构造预测分析表 70

4.3.3状态表 72

4.4递归下降分析法 74

习题 81

5 优先分析法 84

5.1简单优先分析方法 84

5.1.1基本思想 84

5.1.2有关文法的一些关系 85

5.1.3优先矩阵的构造算法 89

5.1.4简单优先分析算法 91

5.2算符优先分析法 93

5.2.1算符优先分析技术的引进 94

5.2.2算符优先文法及优先表的构造 97

5.2.3算符优先分析的若干问题 100

5.3优先函数 104

习题 106

6 LR分析法及分析程序自动构造 109

6.1 LR分析器 109

6.2 LR（0）项目集族和LR（0）分析表的构造 112

6.2.1 LR（0）项目集规范族的构造 114

6.2.2 LR（0）分析表的构造算法 115

6.3 SLR分析表的构造 116

6.4规范LR分析表的构造 119

6.4.1构造LR（1）项目集规范族的算法 120

6.4.2构造LR（1）分析表的算法 121

6.5 LALR分析表构造 122

6.5.1基本思想 123

6.5.2构造LALR分析表的算法 124

6.6二义文法的应用 126

6.7分析表的自动生成 130

6.7.1终结符和产生式的优先级 130

6.7.2结合规则 131

6.7.3 LR分析表的安排 133

习题 134

7 语法制导翻译并产生中间代码 136

7.1概述 136

7.2简单算术表达式和赋值语句的翻译 138

7.2.1四元式 138

7.2.2赋值语句的翻译 139

7.2.3类型转换 141

7.3布尔表达式的翻译 142

7.3.1布尔表达式在逻辑演算中的翻译 142

7.3.2控制语句中布尔式的翻译 143

7.4控制语句的翻译 147

7.4.1标号和转移语句 148

7.4.2 IF语句的翻译 149

7.4.3 WHILE语句的翻译 151

7.4.4 REPEAT语句的翻译 152

7.4.5循环FOR语句的翻译 153

7.4.6分情语句的翻译 155

7.4.7复合语句的翻译 160

7.5数组元素及其在赋值语句中的翻译 160

7.5.1数组及其下标变量地址的计算 160

7.5.2数组元素引用的中间代码形式 163

7.5.3按行存放的赋值语句中数组元素的翻译 163

7.5.4按列存放的赋值语句中数组元素的翻译 166

7.6过程调用语句 168

7.6.1参数传递 168

7.6.2过程调用语句的翻译 170

7.6.3过程调用和数组元素相混淆的处理 171

7.7说明语句的翻译 171

7.7.1分程序结构的符号表 171

7.7.2整型、实型说明语句的翻译 174

7.7.3常量定义语句的翻译 176

7.7.4数组说明语句的翻译 176

7.7.5过程说明语句的翻译 177

7.8输入／输出语句的翻译 178

7.9 自上而下分析制导的翻译 179

7.9.1算术表达式的翻译 179

7.9.2布尔表达式的翻译 181

7.9.3简单语句的翻译 183

7.9.4 LL（1）语法制导翻译 186

7.10属性文法与属性翻译 188

7.10.1属性文法与L属性文法 188

7.10.2属性翻译 190

7.11 中间代码的其他形式 192

7.11.1后缀表示法 192

7.11.2三元式 196

7.11.3间接三元式 197

7.11.4树 197

习题 198

8 运行时数据区的管理 202

8.1静态存储管理 202

8.1.1数据区 202

8.1.2公用语句处理 204

8.1.3等价语句处理 205

8.1.4地址分配 207

8.1.5临时变量地址分配 210

8.2栈式存储管理 211

8.2.1允许过程（函数）递归调用的数据存储管理 211

8.2.2嵌套过程语言的栈式存储管理 214

8.3堆式存储管理 219

8.3.1堆式存储管理技术 219

8.3.2堆空间的释放与无用单元收集 222

习题 223

9 代码优化 225

9.1优化概述 225

9.1.1局部优化简介 225

9.1.2循环优化简介 226

9.1.3全局优化简介 228

9.2局部优化 229

9.2.1基本块 229

9.2.2基本块的DAG表示 230

9.2.3 DAG在基本块优化中的作用 234

9.2.4 DAG构造算法讨论 236

9.3控制流程分析和循环查找算法 238

9.3.1程序流图与必经结点集 239

9.3.2深度为主排序 240

9.3.3查找循环算法 241

9.4数据流分析 241

9.4.1到达-定值数据流方程 242

9.4.2引用-定值链（ud链） 244

9.4.3活跃变量及数据流方程 244

9.5循环优化 246

9.5.1代码外提 246

9.5.2强度减弱与归纳变量删除 248

习题 249

10 目标代码生成 255

10.1模型计算机的指令系统 255

10.2一种简单代码生成算法 256

10.2.1活跃信息与待用信息 256

10.2.2寄存器和变量地址描述 257

10.2.3代码生成算法 258

10.3循环中寄存器分配 261

10.4 DAG结点的一种启发式排序 263

习题 266

附录 EL语言编译程序 268

A．EL语言文法的扩充Backus表示法 268

B．EL语言编译程序构造的实践指导 269

C．扩充的EL语言文法与中间代码的解释执行程序 281

参考文献 285