计算机编译原理是计算机专业的重要课程之一，所讨论的编译程序实质上是符号处理的工具，其基本原理、技术和方法在很多领域有着广泛的应用。本书将系统介绍高级程序设计语言编译程序的构造原理，重点讨论了词法分析、语法分析、语义分析以及目标代码的生成与优化。读者可以从本书中得到软件开发的方法和经验的启发。
本书特点
●内容上结合作者多年科研工作实践与教学经验, 使读者易于理解与接受。
●以C语言为背景语言来讨论编译原理,使读者在掌握编译程序构造原理的同时，对C程序设计语言相关概念也有更深入的理解与认识。
●强调实践性，对编译程序构造的各个主要方面都给出实现之考虑，并给出具体而实际可行的实现方法和技巧。
●本书为教师配有电子教案，请登录机工新阅读网站（www.cmpreading.com）下载。
无
当前，仅有极少数的计算机工作者从事编译程序的开发工作，那么为什么还要开设编译原理课程呢？这是因为编译原理课程在计算机科学中有着重要的地位和作用。该课程与计算机其他学科紧密相关，在软件工程、逆向工程、软件再工程、语言转换及其他领域中有着广泛的应用，对软件开发也有一定的启发与指导作用。编译程序是一种符号处理工具，可以说，只要涉及符号语言的处理，就可以（也应该）采用编译的基本原理与技术。
设置编译原理课程的目的在于让学生系统地了解并掌握程序设计语言编译程序的构造原理。编译原理课程以形式语言理论中的有关概念为基础，讨论程序设计语言及编译程序实现技术。该课程的内容由三部分组成，即程序设计语言（相关概念）、形式语言理论（与编译实现相关的基本概念）和编译程序构造原理。从中也可以看出该课程的特点：理论性强、实践性强。因此必须考虑的一个问题是：如何将两者完美地结合起来，或者说，对于一般的本科院校，如何降低理论难度，突出实践性，加强实践应用能力。
本书尝试把理论与实践有机地结合起来。通常的编译原理教材虽然讨论了概念，也讨论了实现算法，但这些实现算法往往仍是理论上和概念上的。举几个例子：
·语言的文法如何在计算机内表示？
·语言的句子由推导生成，怎样由计算机自动进行推导来生成句子？
·词法分析程序如何实现？特别是怎样由计算机自动识别标识符之作用域？
·SLR识别程序是典型的识别程序，但分析表如何存入计算机，又如何与驱动程序相配合来实现句子识别，并生成语法分析树？特别是，翻译方案中的语义动作实质上也是字符串，怎样实现这些语义动作？
……
一般的教材中并没有为读者给出这些问题的解答，但读者在本书中将得到满意的答案。
本书编写的指导思想是：
1) 内容覆盖编译程序全过程，但突出主要部分，简洁紧凑地陈述要点，文字简练。特别是系统而又紧凑地讨论了语法制导的翻译，有利于读者学习。
2) 结合作者的理解与体会阐述概念，观点明确，特别是内容中融合了作者的多年科研工作实践与教学经验，易于读者理解与接受。
3) 考虑到C语言是当前大多数读者熟悉的程序设计语言，因此尽管C语言不是最合适的，但还是以C语言为背景语言进行编译原理的讨论，使读者在掌握编译程序构造原理的同时，对C程序设计语言的相关概念也有更深入的理解与认识。
4) 强调实践性，对编译程序构造的各个主要方面都给出实现之考虑，给出具体而实际可行的实现方法和技巧。读者可以体会从源程序到目标程序的编译全过程，可以从本书中得到软件开发的方法和经验的启发。
本书各章末除了全章小结外，还附有习题和上机实习题。希望读者在解题时注意解题规范，培养有条理地思考问题、严谨的学风与工作作风；同时注意提高上机动手能力，有条件的读者可以根据自己的实际情况适当选题，进行上机实践。
学习，不仅仅是知识的积累，更是能力的培养。对于一个学生，重要的是打好基础、 练好基本功、 提高自身素质，才能适应多方面的需要。期望通过编译原理课程的学习，读者能朝着这些目标努力，不仅仅较为深刻地认识和理解程序设计语言及编译原理与技术的有关问题，也能为进一步开展计算机软件工作打下良好的基础。本书希望成为理论和实践紧密结合的编译原理课程教材，通过对编译程序全过程中各主要部分的实践，加深读者对编译程序构造原理的理解，并通过实践来培养和提高分析问题与解决问题的能力。
本书各章末的习题没有给出习题解答，这样可以更充分地发挥读者的独立思考能力。当然，如果有读者愿意和作者一起切磋习题或其他一些问题，作者将热忱欢迎。
作者E-mail地址：zhangxr0@sina.com 或 zhang_xinger@hotmail.com
在这里要感谢温莉芳总编对本书的大力支持，感谢王春华编辑为本书的出版所做的大量工作，也要感谢刘振安教授对本书的关注和支持。最后要感谢李意勉女士，在她的大力支持和帮助下，本书才得以完成，最终与读者见面。
作 者
2007年5月
于南京大学计算机科学与技术系
计算机编译原理是计算机专业的重要课程之一，所讨论的编译程序实质上是符号处理的工具，其基本原理、技术和方法在很多领域有着广泛的应用。本书将系统介绍高级程序设计语言编译程序的构造原理，重点讨论了词法分析、语法分析、语义分析以及目标代码的生成与优化。读者可以从本书中得到软件开发的方法和经验的启发。
本书特点
●内容上结合作者多年科研工作实践与教学经验, 使读者易于理解与接受。
●以C语言为背景语言来讨论编译原理,使读者在掌握编译程序构造原理的同时，对C程序设计语言相关概念也有更深入的理解与认识。
●强调实践性，对编译程序构造的各个主要方面都给出实现之考虑，并给出具体而实际可行的实现方法和技巧。
●本书为教师配有电子教案，请登录华章网站（www.hzbook.com）下载。
前言
第1章 概述 1
1.1 编译程序的引进 1
1.1.1 高级程序设计语言与程序 1
1.1.2 高级程序设计语言程序的执行 1
1.2 编译程序和程序设计语言的联系 2
1.2.1 程序设计语言的定义 2
1.2.2 编译程序构造 4
1.3 编译程序的分类 6
1.4 实际应用中的编译程序 7
本章小结 8
第2章 编译程序构造基础知识 9
2.1 文法和语言 9
2.1.1 符号串和符号串集合 9
2.1.2 字母表的闭包和正闭包 11
2.1.3 文法的定义 11
2.1.4 语言的定义 20
2.2 文法和语言的分类 22
2.2.1 Chomsky文法类 23
2.2.2 Chomsky文法类与程序设计语言 25
2.2.3 对上下文无关文法的进一步讨论 26
2.3 文法等价和等价变换 26
2.3.1 文法等价的概念 26
2.3.2 压缩文法等价变换 27
2.3.3 消去左递归的文法等价变换 31
2.4 句型分析 35
2.4.1 语法分析工具—语法分析树 35
2.4.2 句型分析与分析技术 39
本章小结 42
习题 43
上机实习题 45
第3章 词法分析 46
3.1 概述 46
3.1.1 词法分析和词法分析程序 46
3.1.2 实现方式 47
3.2 有穷状态自动机 47
3.2.1 状态转换图 47
3.2.2 确定有穷状态自动机DFA 51
3.2.3 非确定有穷状态自动机NFA 53
3.2.4 正则表达式 58
3.3 词法分析程序的设计和实现 61
3.3.1 设计要点 61
3.3.2 属性字的设计 61
3.3.3 标识符的处理 65
3.3.4 词法分析程序的编写 70
3.3.5 词法分析程序的自动生成 74
本章小结 82
习题 83
上机实习题 84
第4章 语法分析—自顶向下分析技术 85
4.1 引言 85
4.1.1 自顶向下分析技术概述 85
4.1.2 带回溯的自顶向下分析技术 86
4.2 无回溯的自顶向下分析技术 88
4.2.1 先决条件 88
4.2.2 递归下降分析技术 88
4.2.3 预测分析技术 94
本章小结 104
习题 104
上机实习题 105
第5章 语法分析—自底向上分析技术 106
5.1 引言 106
5.1.1 自底向上分析技术概况 106
5.1.2 基本实现方法 107
5.2 算符优先分析技术 108
5.2.1 算符优先分析技术的引进 108
5.2.2 算符文法 108
5.2.3 算符优先关系与算符优先文法 109
5.2.4 应用算符优先分析技术进行句型
分析 113
5.2.5 优先函数 117
5.3 LR(k)分析技术 124
5.3.1 LR(k)文法和LR(k)分析技术 124
5.3.2 SLR(1)分析表构造方法 134
5.3.3 LALR(1)分析表构造方法 143
5.3.4 LR(1)识别程序实现之考虑 147
5.4 识别程序自动构造 148
5.4.1 自动构造的基本思想 148
5.4.2 非LR(1)文法分析表的构造 149
5.4.3 识别程序自动生成系统YACC
简介 151
本章小结 153
习题 153
上机实习题 155
第6章 语义分析与目标代码生成 156
6.1 概况 156
6.1.1 语义分析的概念 156
6.1.2 属性文法 158
6.1.3 类型表达式与语义分析 170
6.2 说明部分的翻译 177
6.2.1 常量定义的翻译 178
6.2.2 变量说明的翻译 178
6.2.3 函数定义的翻译 180
6.2.4 结构（体）类型的翻译 183
6.3 目标代码的生成 183
6.3.1 概况 183
6.3.2 虚拟机 186
6.3.3 控制语句的翻译 188
6.4 翻译方案实现之考虑 211
6.4.1 实现思路 211
6.4.2 分析 211
6.4.3 程序控制流程示意图和语义子
程序 217
6.5 源程序的内部中间表示 220
6.5.1 抽象语法树 220
6.5.2 逆波兰表示 221
6.5.3 四元式序列 225
6.5.4 三元式序列 232
本章小结 233
习题 233
上机实习题 235
第7章 运行时刻支持环境 236
7.1 引言 236
7.2 运行时刻存储分配策略 236
7.2.1 情况分析 236
7.2.2 静态存储分配 239
7.2.3 栈式存储分配 239
7.2.4 堆式存储分配 240
7.3 符号表 241
7.3.1 符号表的作用 241
7.3.2 符号表的组织 241
7.3.3 符号表的数据结构 245
7.4 运行时刻支持系统 247
本章小结 247
习题 248
第8章 代码优化 250
8.1 概况 250
8.1.1 代码优化的概念 250
8.1.2 代码优化的分类 251
8.1.3 代码优化程序的输入与输出 252
8.1.4 代码优化程序的结构 253
8.2 基本块的优化 253
8.2.1 基本块优化的种类 253
8.2.2 基本块优化的实现 256
8.3 与循环有关的优化 262
8.3.1 循环优化的种类 263
8.3.2 循环优化的实现 268
8.4 窥孔优化 284
8.4.1 冗余指令删除 285
8.4.2 控制流优化 286
8.4.3 代数化简 286
8.4.4 特殊指令的使用 286
本章小结 286
习题 287
上机实习题 288
第9章 程序错误的检查和校正 290
9.1 概述 290
9.1.1 必要性 290
9.1.2 错误的种类 290
9.1.3 错误复原和错误校正 291
9.2 词法错误的复原和校正 292
9.2.1 词法错误的种类 292
9.2.2 词法错误的校正 293
9.3 语法错误的复原和校正 293
9.3.1 语法错误的复原 293
9.3.2 语法错误的校正 294
9.4 语义错误 295
9.4.1 语义错误的种类 295
9.4.2 语义错误检查措施 296
本章小结 297
参考文献 298
