编译原理PDF电子书下载

目 录 1

1编译概论 1

1.1程序设计语言和编译程序 1

1.2编译的过程和编译程序结构 3

1.3编译阶段的组合 5

1.4编译技术在软件工具中的应用 6

2文法和语言 9

2.1文法的非形式化描述 9

2.2符号、符号串及其运算 11

2.3.1文法的形式化定义 13

2.3文法和语言的形式化定义 13

2.3.2推导的形式化定义 14

2.3.3语言的形式化定义 17

2.3.4语法树 19

2.4文法和语言的类型 21

思考题与习题 23

3词法分析 25

3.1词法分析概述 25

3.2单词的描述工具 27

3.2.1正规文法 28

3.2.2正规表达式 29

3.3有限自动机（DFA） 32

3.3.1确定的有限自动机（DFA） 35

3.3.2不确定的有限自动机（NFA） 36

3.3.3 NFA的确定化 38

3.3.4 DFA的最小化 42

3.4正规文法、正规式和有限自动机之间的等价转换 45

3.4.1正规文法与正规式 45

3.4.2正规文法与有限自动机 49

3.4.3正规式与有限自动机 51

3.5词法分析程序的自动生成 56

3.5.1 LEX源文件的结构 59

3.5.2 LEX系统中的正规式 62

3.5.3 LEX翻译程序简介 66

3.5.4 LEX的使用方式 67

3.5.5 LEX应用举例 68

思考题与习题 72

4 自顶向下的语法分析 75

4.1 自顶向下的语法分析思想 76

4.1.1确定的自顶向下分析 77

4.1.2不确定的自顶向下分析 83

4.2 LL（1）文法 86

4.2.1 LL（1）文法的判别 86

4.2.2某些非LL（1）到LL（1）文法的等价转换 93

4.3预测分析方法 100

4.3.1预测分析程序的工作流程 101

4.3.2预测分析表的构造 104

4.3.3预测分析方法举例 104

思考题与习题 109

5 自底向上的语法分析 113

5.1 自底向上的分析方法简介 113

5.1.1算符优先分析法 114

5.1.2 LR分析法 116

5.2算符优先分析方法 119

5.2.1算符优先文法的定义 119

5.2.2构造算符优先关系表 122

5.2.3算符优先分析算法 125

5.2.4优先函数 127

5.2.5算符优先分析方法的讨论 129

5.3 LR分析方法 130

5.3.1 LR（0）分析器 130

5.3.2 SLR（1）分析器 138

5.3.3 LR（1）分析器 140

5.3.4 LALR（1）分析器 144

5.3.5 LR分析方法的讨论 147

思考题与习题 149

6属性文法与语法制导翻译技术 151

6.1属性文法 152

6.1.1继承属性和综合属性 154

6.1.2属性翻译文法 158

6.2语法制导翻译技术 161

6.2.1 自顶向下的语法制导翻译 162

6.2.2自底向上的语法制导翻译 167

思考题与习题 174

7语义分析和中间代码生成 176

7.1中间代码 176

7.1.1逆波兰记号 176

7.1.2三元式 178

7.1.3四元式 179

7.2赋值语句与算术表达式的翻译 180

7.3布尔表达式的翻译 184

7.4控制结构的翻译 188

7.4.1条件语句 188

7.4.2循环语句 190

7.4.3过程调用 193

7.5说明语句的翻译 194

7.5.1数组说明的翻译 195

7.5.2结构说明的翻译 197

7.6数组元素访问的翻译 199

思考题与习题 203

8符号表 207

8.1符号表概述 207

8.2符号表的组织 208

8.2.1符号表的一般形式 208

8.2.2符号表的名字栏 209

8.2.3符号表的信息栏 210

8.2.4符号表中的数据 211

8.3符号表的管理 212

8.3.1符号表的初始化 212

8.3.2符号表的编制与查找 212

8.3.3名字作用域信息的表示 219

思考题与习题 221

9 目标程序运行时存储空间组织 223

9.1概述 223

9.1.1存储空间的一般组织 223

9.1.2过程和过程的活动记录 225

9.1.3名字和名字的作用域 227

9.2数据对象的存储分配 228

9.2.1基本数据对象的存储分配 229

9.2.2数组的存储分配 229

9.2.3记录结构的存储分配 232

9.3.1名字调用 233

9.3参数传递 233

9.3.2引用调用 234

9.3.3值调用 235

9.3.4结果调用 235

9.4静态存储分配 235

9.5栈式存储分配 237

9.5.1简单栈式存储分配 238

9.5.2嵌套过程的栈式存储分配 240

9.5.3分程序结构的栈式存储分配 243

9.6堆式存储分配 247

思考题与习题 250

10代码优化 253

10.1代码优化技术概述 254

10.1.1删除公共子表达式（删除多余运算） 255

10.1.2代码外提 255

10.1.3强度削弱 256

10.1.4变换循环控制条件（删除归纳变量） 257

10.1.5合并已知变量 257

10.1.6复写传播 257

10.1.7删除无用赋值 258

10.2局部优化 259

10.2.1基本块的划分和变换 259

10.2.2基本块的DAG表示和应用 261

10.3循环优化 270

10.3.1程序流图 270

10.3.2循环 272

10.3.3可归约流图 279

10.3.4循环优化方法 280

10.4全局优化概述 284

10.4.1“到达－定值”数据流方程 285

10.4.2活跃变量数据流方程的推导 290

思考题与习题 293

11 目标代码生成 298

11.1概述 298

11.1.1代码生成器的输入和输出 299

11.1.2指令的选择 300

11.1.3寄存器分配 301

11.1.4计算顺序的选择 301

11.2计算机模型 301

11.3代码生成器 304

11.3.1待用信息 305

11.3.2寄存器分配 307

11.3.3代码生成算法 311

思考题与习题 321

12并行编译技术基础 324

12.1.1向量计算机 325

12.1并行计算机 325

12.1.2共享存储器多处理机 326

12.1.3分布式存储器大规模并行计算机 328

12.2并行编译器的结构 329

12.2.1程序分析 330

12.2.2程序优化 330

12.2.3并行代码生成 331

12.3依赖关系 331

12.3.1依赖关系的定义 332

12.3.2语句依赖图 336

12.3.3循环的迭代依赖图 337

12.4.1可向量化循环 344

12.4循环的向量化和并行化 344

12.4.2可并行化循环 347

12.5循环的变换技术 348

12.5.1语句重排（Statement Reordering） 349

12.5.2循环置换（Loop Permutation） 350

12.5.3循环逆转（Loop Reversal） 352

12.5.4圈收缩（Cycle Shrinking） 353

12.5.5循环分布（Loop Distribution） 354

思考题与习题 358

参考文献 363