编译原理课程专门学习与研究程序设计语言的实现技术，是计算机科学专业的一门主干课程，在计算机科学领域有着及其重要的地位。本书从人对语言的理解出发引入编译原理的基本概念，全面介绍了编译原理的相关概念和实现。
本书特点
●本书引入了源语言、目标语言和编译语言三者关系的符号，通过这个符号可以形象地表达复杂的多层翻译过程。
●深入、透彻地阐述了LL(1)和LR(1)文法，使读者不仅能够知其然，更能知其所以然。
●不仅介绍了传统方法，还介绍了在计算机领域中日益重要的形式化方法。
●对并行编译和网格计算的编译进行了介绍，这是国内很多教材没有涉及的。
●本书将为授课教师提供电子教案，需要者可登录机工新阅读网站www.cmpreading.com下载。
无
从20世纪80年代中期开始，我在暨南大学讲授编译原理这门课程。在几十年的教学中，我深切地感到国内高校缺乏一本实用的、高质量的编译原理教材，特别是在进入21世纪之后，这个问题愈加突出。主要表现在以下几个方面：
1）早年出版的被认为较好的教材内容已显陈旧，但并未及时更新内容，以适应新形势、新发展。
2）很多新推出的教材却沿用既有的框架来写，没有反映编译原理课程和技术的发展。
3）即使是一些国外教材也存在内容庞杂，不分主次、叙述冗长的问题。
面对国内急需一本能够反映最新知识发展且具有较高质量的编译原理教材的形势，我决定结合多年的教学经验和研究成果编写一本满足广大师生需求的优秀教材。
概括而言，本书与市场上的同类书相比，具有以下特色：
1）本书将人的智能中对于语言的理解同编译联系起来。
2）本书创立了源语言、目标语言和编译语言三者关系的符号，通过这个符号可以很形象地表达复杂的多层翻译过程。
3）本书第一次明确地阐明自动机与文法的所谓等价。其实它们并非真正地等价，而是要附上条件后才可以等价。但附上的条件实际上又违背了自动机或文法原来的定义。
4）对LL(1)和LR(1)文法进行了明晰、清楚的表达，使读者能知其然也知其所以然。
5）除了介绍传统方法之外，还介绍了形式化的方法。因为形式化方法在现代科学技术发展中的地位日益突出，所以介绍形式化方法对于读者有重大意义。
6）本书介绍了面向对象语言的编译，弥补了许多国内教材对此问题没有涉及的缺憾。
7）本书介绍了并行编译和网格计算语言的编译。毫无疑问，在本世纪里，并行编译将成为编译程序的主角。因为大量并行计算机的出现和网格计算的出现，必然会使传统的串行编译失去它独尊的地位。
正是上述特色使本书独树一帜，而其中绝大部分观点和结论都来自作者本人的创见和工作体会。
20多年来，我的学生们不断动员我写一本编译原理的教材，因为他们从我的讲授中也感受到我国编译原理教材的不足，他们的鼓励是我力量的源泉。他们许多人可能没有机会阅读这本教材了，但我仍愿意把这本教材献给他们，以表示我对他们的感谢。同时，我也要把这本书郑重献给我国计算机科学专业的师生，献给从事编译程序方面工作的研究人员、设计人员，以及这门课程的自学者。
在此，我要感谢广西梧州学院计算机科学与技术系和电子信息工程系的师生和领导，他们为我的写作提供了许多便利。我还要感谢机械工业出版社华章分社对我的大力支持，没有他们的支持，就不会有本书的问世。
虽然我自认为本书内容足以满足我的写作初衷，但它肯定不是完美的，书中难免会有缺点和错误，我衷心地希望读者予以批评指正。
编者
广西梧州市
2007年3月
编译原理课程专门学习与研究程序设计语言的实现技术，是计算机科学专业的一门主干课程，在计算机科学领域有着及其重要的地位。本书从人对语言的理解出发引入编译原理的基本概念，全面介绍了编译原理的相关概念和实现。
本书特点
●本书引入了源语言、目标语言和编译语言三者关系的符号，通过这个符号可以形象地表达复杂的多层翻译过程。
●深入、透彻地阐述了LL(1)和LR(1)文法，使读者不仅能够知其然，更能知其所以然。
●不仅介绍了传统方法，还介绍了在计算机领域中日益重要的形式化方法。
●对并行编译和网格计算的编译进行了介绍，这是国内很多教材没有涉及的。
●本书将为授课教师提供电子教案，需要者可登录机工新阅读网站（www.cmpreading.com）下载。
苏运霖：苏运霖: 颇具盛名的计算机科学专家，出生于印度尼西亚，曾任教于吉林大学、暨南大学，现任广西大学梧州分校顾问、计算机科学系主任，学科带头人。他曾被评为全国电工学会优秀科技工作者和电机工程优秀科技工作者，获国务院特殊津贴。他还被美国纽约科学院邀请为该院院士，名字被录入《国际传记辞典》、《国际卓越领导者名单》以及《世界知识名人录》。1983年到1986年间，与新西兰的几所著名大学研究组合算法、计算机网络、Petri网络理论。1989年，他到美国访问、讲学近一年，参加分布式算法的设计并撰写了一批有创见的论文。之后，他陆续到挪威、瑞典、瑞士、丹麦、奥地利、德国、比利时、冰岛、荷兰、卢森堡、日本、新加坡、印度尼西亚和香港等国家和地区讲学与访问。曾翻译D. E. Knuth的巨著《计算机程序设计艺术》，并编写了多部教材。
前 言
第1章 概论 1
1.1 语言和人类 1
1.2 语言和计算机 2
1.3 语言和编译 6
1.4 程序设计语言的编译 7
1.5 一个语句的编译举例 9
1.6 编译的遍数 11
1.7 本书的组成 11
习题 13
第2章 文法和语言 14
2.1 预备知识 14
2.2 文法 15
2.3 语言 18
2.4 文法所生成的语言 20
2.5 图灵机 22
2.6 有关文法和语言的问题 29
习题 30
第3章 有限自动机和正则表达式 34
3.1 确定的有限自动机 34
3.2 不确定的有限自动机 37
3.3 带有e的有限自动机 42
3.4 正则表达式 44
3.5 两路有限自动机 49
3.6 正则文法 53
3.7 关于正则语言的判定 61
习题 62
第4章 词法分析 66
4.1 词法分析的作用 67
4.2 词法分析程序的输出 76
4.3 错误处理 78
习题 78
第5章 上下文无关文法和下推自动机 80
5.1 上下文无关文法 80
5.2 上下文无关文法的性质 83
5.3 下推自动机 90
5.4 下推自动机和上下文无关语言 93
习题 98
第6章 语法分析 104
6.1 LL(1)语法分析 104
6.2 LL(1)文法的确定 107
6.3 LL(1)语法分析方法 110
6.4 自底向上的语法分析 115
6.5 LR(1)语法分析方法 118
6.5.1 LR(0)语法分析 118
6.5.2 SLR(1)语法分析 120
6.5.3 LALR(1)语法分析 122
6.5.4 LR(1)语法分析 124
6.5.5 LL(1)语法分析方法和LR(1)语法
分析方法的比较 130
习题 132
第7章 属性文法及其分析 136
7.1 属性文法 136
7.2 依赖图和属性计算 139
7.2.1 动态属性计算 143
7.2.2 循环处理 145
7.3 L属性文法和S属性文法 146
习题 148
第8章 编译程序设计的代数方法 149
8.1 源语言 149
8.2 代数基础和推理语言 154
8.2.1 代数基础 155
8.2.2 推理语言 160
8.3 一个简单的编译程序 178
8.3.1 规范形式 178
8.3.2 规范形式的归结 179
8.3.3 目标机器 182
8.3.4 表达式的化简 183
8.3.5 控制的消除 185
8.3.6 数据求精 187
8.3.7 编译过程 191
8.4 过程、递归和参数 192
8.4.1 记号 193
8.4.2 过程 193
8.4.3 递归 195
8.4.4 带参数的程序 197
8.4.5 带参数的过程 199
8.4.6 带参数的递归 200
8.4.7 讨论 202
8.5 小结 203
习题 204
第9章 中间代码的生成 205
9.1 为什么需要有中间代码生成阶段 205
9.2 中间代码语言 205
9.2.1 图形表示 206
9.2.2 后缀表示 208
9.2.3 四元组代码 209
习题 223
第10章 纠错与优化 226
10.1 错误检测和恢复 226
10.2 语法错误检查 227
10.2.1 LL(1)分析程序的错误处理 229
10.2.2 LR(1)分析中的错误处理 229
10.3 语义错误检查 230
10.4 程序的优化 230
10.5 程序优化的几个主要途径 234
10.5.1 公共子表达式的删除 234
10.5.2 副本传播 234
10.5.3 废代码的删除 235
10.5.4 循环优化 236
习题 237
第11章 存储管理 239
11.1 全局分配策略 239
11.2 动态分配 242
11.2.1 栈式分配 242
11.2.2 堆式分配 243
11.3 存储空间的回收 245
11.3.1 基本垃圾收集算法 245
11.3.2 编译程序对垃圾收集程序的支持 246
11.3.3 引用计数 247
11.3.4 标记和扫描 248
11.3.5 两空间复制 249
11.3.6 紧缩 250
11.4 参数传递 250
11.4.1 值调用 251
11.4.2 引用调用 251
11.4.3 复写-恢复调用 251
11.4.4 换名调用 251
习题 252
第12章 目标代码生成 254
12.1 代码生成程序设计的有关问题 254
12.1.1 代码生成程序的输入 254
12.1.2 目标程序 255
12.1.3 存储管理 255
12.1.4 指令选择 255
12.1.5 寄存器分配 256
12.1.6 计算顺序的选择 257
12.1.7 代码生成的方法 257
12.2 目标机器MMIX 257
12.3 MMIX的汇编语言 274
12.4 MMIXAL目标代码的生成 279
12.4.1 表达式逆波兰表示的翻译 279
12.4.2 表达式三元式的翻译 280
12.4.3 表达式四元组形成的翻译 280
12.4.4 表达式的翻译 281
12.4.5 表达式的语法树形式的翻译 282
12.4.6 各种语句的翻译 282
习题 284
第13章 面向对象语言的编译 286
13.1 对象及其编译 286
13.2 对象的特征 287
习题 294
第14章 并行语言的编译 296
14.1 并行机和并行计算的提出 296
14.2 并行程序设计 298
14.2.1 共享变量和管程 299
14.2.2 消息传送模型 300
14.3 面向对象的语言 301
14.4 Linda元组空间 301
14.5 数据并行语言 303
14.6 隐式并行程序的代码生成 304
14.6.1 区域的类型 305
14.6.2 区域的形成 306
14.6.3 区域的几个调度算法 309
习题 309
第15章 网格计算的编译 310
15.1 网格计算的兴起与其内涵 310
15.2 网格计算模型 311
15.2.1 分组路由 312
15.2.2 线性阵列中的分组路由 313
15.3 网格计算的编译 315
习题 316
参考文献 318
