程序设计语言编译原理PDF电子书下载

目录 1

引论 1

0.1　什么叫编译程序 1

0.2　编译过程概述 1

0.2.1 编译的基本阶段 1

0.2.2 表格管理和出错处理 2

0.2.3　遍 4

0.3　编译程序的生成 4

0.4　学习构造编译程序 5

第一章　高级程序语言概述 6

1.1　程序语言的定义 6

1.1.1 语言的词法和语法结构 6

1.1.2 语义 7

1.2.1　标识符和名字 8

1.2　初等类型数据 8

1.2.2 名字的属性和说明 9

1.3　数据结构 10

1.3.1　数组 10

1.3.2 记录结构 11

1.3.3　字符串、表格和栈 12

1.4　表达式 13

1.5　语句 14

1.5.1　赋值句 14

1.5.2　控制语句 15

1.5.3　说明句 15

1.5.4　简单句和复合句 16

1.6　程序段 16

1.6.1 FORTRAN 16

1.6.2　ALGOL 16

1.7.1　参数 17

1.6.3　PASCAL 17

1.7　参数传递 17

1.7.2 传地址（call by reference） 18

1.7.3 传值（call by value） 19

＊1.7.4 传名（call by name） 19

1.8　存贮管理 19

1.8.1　静态存贮分配 20

1.8.2　动态存贮分配 20

1.8.3　栈式动态存贮分配 20

＊1.8.4 堆式动态存贮分配 21

1.9　历史回顾 22

第二章　词法分析 24

2.1　对于扫描器的考虑 24

2.1.1 单词符号的种类和扫描器的输出形式 24

2.2　扫描器的设计 25

2.1.2　扫描器作为一个独立子程序 25

2.2.1 预处理、缓冲区和超前搜索 26

2.2.2　状态转换图 27

2.2.3　状态转换图的实现 30

＊2.3　正规表达式与有限自动机 31

2.3.1　正规式与正规集 32

2.3.2　确定有限自动机（DFA） 33

2.3.3 非确定有限自动机（NFA） 34

2.3.4　正规式与有限自动机的等价性 35

2.3.5　确定有限自动机的化简 38

＊2.4　词法分析器的自动产生 39

2.4.1 语言LEX的一般描述 40

2.4.2　超前搜索 42

2.4.3　LEX的实现 43

3.1.1　文法与语言 48

3.1　上下文无关文法 48

第三章　程序语言的语法描述与分析 48

3.1.2　语法树与二义性 51

3.1.3　形式语言鸟瞰 53

3.2　语法分析——自下而上分析 55

3.2.1　归约与句柄 56

3.2.2　符号栈的使用和语法树的表示 59

3.3　算符优先分析法 60

3 3.1　直观算符优先分析法 61

3.3.2　算符优先文法和优先表构造 65

3.3.3　算符优先分析算法的设计 67

3.3.4　优先函数 69

3.4　语法分析——自上而下分析 70

＊3.5　递归下降分析法 73

3.5.1　左递归的消除 73

3.5.2　消除回溯、提左因子和递归下降分析器 75

3.5.3　文法的另一种表示法和转换图 77

3.5.4 预测分析程序 79

3.5.5　状态表 83

＊第四章　语法分析程序的自动构造 88

4.1　LR分析器 88

4.1.1　LR文法 91

4.1.2　一些非LR结构 92

4.2　LR（0）项目集族和LR（0）分析 93

表的构造 93

4.2.1　LR（0）项目集规范族的构造 95

4.2.2　有效项目 97

4.2.3　LR（0）分析表的构造 98

4.3　SLR分析表的构造 99

4.4　规范LR分析表的构造 103

4.5　LALR分析表的构造 106

4.6　二义文法的应用 112

4.7　分析表的自动产生 116

4.7.1　终结符和产生式的优先级 116

4.7.2　结合规则 117

4.8　LR分析表的实际安排 118

第五章 语法制导翻译和中间代码 121

产生 121

5.1　语法制导翻译概说 121

5.2　逆波兰表示法 124

5.2.1　后缀式的计值 124

5.2.2　后缀式的推广 125

5.2.3　语法制导生成后缀式 126

5.3　三元式和树 126

5.3.2　树 128

5.3.1　间接三元式 128

5.4　四元式 129

5.5　简单算术表达式和赋值句到 130

四元式的翻译 130

5.6　布尔表达式到四元式的翻译 133

5.7　控制语句的翻译 137

5.7.1　标号和转移语句 137

5.7.2　条件语句 138

5.7.3　循环语句 141

5.7.4　分叉语句 143

5.8　数组元素引用 145

5.8.1 数组元素引用的中间代码 146

5.8.2 赋值句中数组元素的翻译 147

5.8.3 按列为序存放数组元素的情形 149

5.9　过程调用 150

5.9.1 过程调用的四元式产生 151

5.10　说明语句的翻译 152

5.9.2 过程调用和数组元素相混淆的处理 152

＊5.11　记录结构 154

5.11.1 记录说明的翻译 155

5.11.2 记录结构的引用 156

＊5.12 自上而下分析制导翻译概说 157

第六章　符号表 163

6.1　符号表的组织和使用 163

6.2　整理与查找 165

6.2.1　线性表 165

6.2.2　对折查找与二叉树 166

6.2.3　杂凑技术 168

6.3　名字的作用范围 170

6.3.1 FORTRAN的符号表组织 170

6.3.2　ALGOL的符号表组织 171

6.4　符号表的内容 173

第七章　运行时存贮空间组织 177

7.1 静态存贮管理——FORTRAN 177

存贮分配 177

7.1.1　数据区 178

7.1.2　公用语句的处理 180

7.1.3　等价语句的处理 181

7.1.4　地址分配 184

7.1.5　临时变量的地址分配 186

7.2　一个简单的栈式存贮分配的实现 188

7.2.1 C的活动记录 189

7.2.2 C的过程调用，过程进入，数组空间分配和过程返回 189

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

7.3.1 嵌套层次显示表DISPLAY 191

和活动记录 191

7.3.3　参数传递 193

7.3.2　过程调用，过程进入 193

7.4 ALGOL的实现 195

7.4.1　分程序结构 195

7.4.2 分程序的进入和退出 197

7.4.3　过程调用，进入和返回 199

7.4.4　参数子程序 199

7.5　分程序结构语言存贮分配拾遗 201

第八章　错误的诊察和校正 204

8.1　出错处理概述 204

8.1.1　语法错误 205

8.1.2　语义错误 206

8.1.3　错误处理 206

8.1.4 出错处理系统与编译程序各阶段的联系 207

8.2　词法分析阶段的错误诊察 207

8.3.1　算符优先分析法的错误处理 208

错误诊察 208

8.3　语法分析（自下而上）阶段的 208

＊8.3.2　LR分析算法的错误处理 211

＊8.4 自上而下分析的错误诊察 214

8.5　语义错误诊察 216

8.5.1　遏止株连信息 216

8.5.2　遏止重复信息 216

第九章　代码优化 218

9.1　优化概述 218

9.2 局部优化 221

9.3　基本块的DAG表示及其应用 222

9.3.1 基本块的DAG表示 223

9.3.2　DAG的应用 226

9.3.3　DAG构造算法讨论 227

9.4　控制流程分析和循环查找算法 229

9.4.1　程序流图与循环 230

9.4.2　必经结点集 231

9.4.3　查找循环算法 234

9.4.4　可归约流图 235

9.4.5　深度为主查找及其算法 236

9.5　到达-定值与引用-定值链 238

9.5.1　到达-定值数据流方程 239

9.5.2　到达-定值数据流方程的求解 240

9.5.3　引用-定值链（ud链） 242

9.5.4　ud链的应用 243

9.6　循环优化 243

9.6.1　代码外提 244

9.6.2　强度削弱 247

9.6.3　删除归纳变量 248

9.6.4 循环展开和循环合并 252

10.1.1 活跃变量的数据流方程 258

10.1　活跃变量与定值-引用链（du链） 258

＊第十章　数据流分析 258

10.1.2 活跃变量数据流方程的求解 259

10.1.3　定值-引用链（du链） 261

10.1.4 活跃变量与du链的应用 263

10.2　删除全局公共子表达式 263

10.2.1 可用表达式及其数据流方程 263

10.2.2 可用表达式数据流方程的求解 265

10.2.3 删除全局公共子表达式的算法 265

10.3　复写传播 266

10.4　非常忙表达式和代码提升 269

10.4.1 非常忙表达式数据流方程 270

10.4.2 代码提升 271

10.5　四类数据流方程小结 272

10.6　指示器数据流分析 273

10.7　过程间数据流分析 278

10.8　实施各种优化的综合考虑 283

11.1　一个计算机模型 289

第十一章　代码生成 289

11.2　一个简单代码生成器 290

11.2.1　待用信息 290

11.2.2　寄存器描述和地址描述 291

11.2.3　代码生成算法 291

11.3　寄存器分配 293

＊11.4　DAG的目标代码 296

＊11.5　树的目标代码 299

＊11.6　窥孔优化 304

12.2　高级语言计算机系统结构 309

12.2.1　语言的接近程度 309

12.2.2　冯·诺依曼型结构（类型1） 309

12.1　概述 309

介绍 309

第十二章 高级语言计算机系统结构 309

12.2.3　面向语法的结构（类型2） 310

12.2.4 间接执行计算机结构（类型3） 311

12.2.5　直接执行计算机结构（类型4） 312

12.3　栈式计算机结构 312

12 3.1 栈结构 312

12.3.2　表达式的计算 313

12.3.3　用栈处理程序结构 314

12.3.4　数据结构 315

12.4　子程序连接 317

12.4.1　调用 317

12.4.2　参数 318

12.5　分程序结构 318

12.6　环境及过程常数 321

12.7　子程序连接与分程序结构 324

的合并处理 324