本书系统、全面地介绍了计算机高级语言编译程序的基本原理和技术，对当前最新的嵌入式系统编译技术做了较详细的讨论。主要内容包括词法分析、语法分析、语法制导翻译的语义分析与中间代码生成、符号表与运行时存储空间的组织与代码优化、面向对象语言编译方法及并行编译基础、嵌入式系统编译器及其工具的应用开发。本书理论与实践并重，每章之前都有导读，最后均附有小结和习题，便于读者学习。

本书适合作为普通高等学校计算机学科及相关专业的本科教材，也可供科技工作者及软件研发人员学习和参考。

        编译程序是计算机系统的核心系统软件之一，是高级程序设计语言的支撑环境。编译原理和技术为人们理解计算机程序语言、构建优秀软件提供了理论基础，拓宽了视野，加深了对高级语言的理解程度。随着各种高级语言的相继出现，支撑这些语言的编译方法和技术也在不断发展。编译的原理和技术也可以应用在诸如软件建模语言、硬件描述语言、脚本语言等的翻译上。在当今的信息化社会里，嵌入式系统的应用开发越来越重要，而其编译技术的研究和应用也成为计算机科学技术的一个重要方面。编译理论的研究有力地推动了计算机科学、计算机工程、软件开发以及人机工程等领域的研究和发展。

本书主要介绍计算机程序语言编译程序的基本原理、设计方法和实现技术，其内容主要针对应用型本科高等院校计算机专业的学生，亦可作为其他高等学校计算机学科及相关专业的教学参考书或教材。?

编者在本书的编写过程中，力求保持较强的系统性，基本概念的阐述力求严谨和清晰，叙述力求通俗易懂，增强教材的可读性和易读性。本书的总体结构和内容具有以下特点：

（1）在内容上增加了嵌入式系统编译技术的内容，介绍了嵌入式系统编译器及其工具的基本概念和应用开发，以利于读者了解编译原理和技术的发展动态和新的应用领域。编者还通过实例描述了嵌入式系统C编译器开发工具的工作过程，以及嵌入式系统Java编译器及开发工具的应用。

（2）简要介绍了面向对象语言一些特性的处理方法，探讨了并行编译理论及实践。针对面向对象语言的语法结构及其语义的特征，着重从类及类的继承结构上讨论了相关的编译技术；用面向对象技术构造编译程序的思路，便于读者学习和理解面向对象的软件体系结构。

（3）本书注重理论与实践相结合，每章都提供了适量的习题，便于读者理解基本概念和原理，掌握编译的基本算法和实现技术。本书还配备了教学辅助课件及书中所有程序示例软件，读者可到中国铁道出版社教材研究开发中心网站下载（网址：http://www.edusources.net）。

全书共分10章：

第1章概述了编译程序的功能、结构、工作过程、组织方式等方面的基本知识，其他各章按照编译程序的构成和编译过程的顺序，依次介绍编译的基本原理、设计方法和构造技术。

第2章介绍形式语言识别的理论基础、文法和语言的一些基本概念。

第3章首先介绍词法分析的设计和词法分析程序的手工构造，然后讲述自动生成词法分析程序的理论基础——有限状态自动机的理论。

第4章介绍语法分析的方法，包括自底向上和自顶向下语法分析方法。

第5章对语义描述技术、属性文法以及以语法制导的语义分析进行了详尽的阐述，讨论了基于语法制导技术的中间代码翻译。

第6章讨论了符号表的组织和访问符号表的各种方法、运行时的存储组织和运行时的分配策略。

第7章介绍代码优化技术，包括中间代码的局部优化和目标代码的优化方法。

第8章论述了目标代码生成时涉及的知识和技术。

第9章论述面向对象语言编译及并行编译基础。

第10章介绍嵌入式系统编译器及其工具的应用开发。

使用本书要求读者已经学习和掌握了高级程序设计语言，如C、Java，最好具备离散数学、数据结构、计算机组成原理和汇编语言的基本知识。

本书的第6～8章由刘升编写；其余各章由游晓明编写，并负责全书的统稿工作。

本书由陈涵生教授主审，他给本书提出了许多宝贵的修改意见，使本书更能体现应用型本科教育“一个目标”（培养计算机应用一线工作的本科人才）、“四个能力”（自我学习能力、创意创新能力、专业应用能力、社会适应能力）、“三种知识”（专业基础知识、专业技能知识、通用职业知识）的基本特征。周广声教授和周海燕编辑为本书的编审付出了辛勤的劳动，在此表示衷心的感谢。在本书的编写过程中，还得到了王裕明老师和张瑜老师的大力支持，并引用了一些学者的论著和研究成果，以及部分公司的产品介绍。对此，编者向所有关心、支持本书的老师和社会同仁表示诚挚的感谢。

由于编者水平所限，书中难免有疏漏或不足之处，恳请广大读者提出宝贵意见。
编 者       

2011年8月   

    
 

第1章  编译概述 1

1.1  程序设计语言 2

1.2  翻译程序 3

1.3  编译程序的逻辑结构 5

1.3.1  词法分析 5

1.3.2  语法分析 6

1.3.3  语义分析及中间代码生成 6

1.3.4  代码优化 7

1.3.5  目标代码生成 7

1.3.6  符号表管理程序 8

1.3.7  错误检查和处理程序 8

1.4  编译程序的组织方式 9

1.4.1  单遍编译程序 9

1.4.2  多遍编译程序 9

1.5  编译程序的前后处理器 10

1.6  编译程序的生成 11

小结 12

习题一 12

第2章  文法和语言 13

2.1  程序设计语言的定义 14

2.1.1  语法 14

2.1.2  语义 14

2.2  基本概念和术语 15

2.2.1  字母表 15

2.2.2  符号串 15

2.2.3  符号串及其集合的运算 15

2.3  文法形式定义 17

2.4  语言和语法树 19

2.4.1  直接推导定义 19

2.4.2  推导定义 19

2.4.3  规范推导 20

2.4.4  句型、句子和语言 20

2.4.5  语法树和二义性 23

2.5  短语、简单短语和句柄 25

2.6  文法的化简与改造 27

2.6.1  无用符号和无用产生式的删除 27

2.6.2  ε产生式的消除 28

2.6.3  单产生式的消除 31

2.7  文法和语言的乔姆斯基分类 31

2.8  PL/0编译程序概述 34

2.8.1  PL/0语言的功能 34

2.8.2  PL/0程序示例 35

2.8.3  PL/0语言的语法描述 35

2.8.4  PL/0编译程序的结构 38

小结 39

习题二 39

第3章  词法分析 41

3.1  词法分析器的功能 42

3.2  单词符号 42

3.3  正规文法及状态转换图 44

3.3.1  正规文法 44

3.3.2  由正规文法构造状态转换图 49

3.4  有限状态自动机 52

3.4.1  确定的有限状态自动机 52

3.4.2  不确定的有限状态自动机 56

3.4.3  NFA与DFA的转化 57

3.4.4  正规表达式与有限状态自动机的等价性 59

3.4.5  确定的有限状态自动机的化简 61

3.5  词法分析程序的设计与实现 63

3.5.1  词法分析程序的手工编写 63

3.5.2  词法分析程序的自动生成 66

3.6  PL/0编译程序的词法分析 70

小结 72

习题三 72

第4章  语法分析 74

4.1  语法分析器的功能 75

4.2  自顶向下分析 75

4.2.1  自顶向下分析面临的问题 75

4.2.2  消除文法的左递归 78

4.2.3  消除左递归算法 79

4.2.4  回溯的消除及LL(1)文法 79

4.2.5  LL(1)文法的判断条件 80

4.2.6  FIRST集合和FOLLOW集合及构造方法 81

4.2.7  LL(1)分析的基本方法 83

4.2.8  预测分析表的构造方法 83

4.2.9  预测分析控制程序的实现技术 84

4.2.10  递归下降分析 86

4.3  自底向上分析 92

4.3.1  规范推导、规范句型和规范归约 92

4.3.2  自底向上分析方法的一般过程 94

4.3.3  算符优先分析 95

4.3.4  LR分析方法 106

4.3.5  LR分析表的构造 110

4.3.6  SLR(1)分析器 117

4.3.7  LR(1)分析器 121

4.3.8  LALR(1)分析器 122

4.4  语法分析程序的自动生成 124

4.4.1  语法分析程序的自动生成工具YACC 124

4.4.2  PL/0编译程序的语法分析 130

小结 132

习题四 132

第5章  语法制导翻译和中间代码生成 135

5.1  语法制导翻译的基本思想 136

5.2  属性文法综述 139

5.2.1  文法的属性 139

5.2.2  属性文法 139

5.3  语法制导翻译的实现方法 141

5.4  中间代码的形式 142

5.4.1  树形表示法 142

5.4.2  逆波兰表示法 143

5.4.3  三元式 144

5.4.4  四元式 145

5.5  语句的翻译 146

5.5.1  说明语句（简单变量）的翻译 146

5.5.2  赋值语句的翻译 147

5.5.3  布尔表达式的翻译 151

5.5.4  标号和无条件转移语句的翻译 153

5.5.5  控制语句的翻译 155

5.5.6  复合语句的翻译 156

5.5.7  多分支控制语句case的翻译 158

5.5.8  数组元素的翻译 158

5.5.9  过程或函数调用语句的翻译 159

5.5.10  数组说明的翻译 160

小结 160

习题五 160

第6章  符号表与运行环境 162

6.1  符号表的组织和作用 162

6.1.1  符号表的作用和地位 163

6.1.2  符号表的内容 163

6.1.3  符号表的组织方式 163

6.2  存储组织 167

6.2.1  目标程序运行时的组织 167

6.2.2  运行时存储器的划分 167

6.2.3  活动记录 168

6.3  运行时的分配策略 169

6.3.1  静态存储分配 170

6.3.2  栈式分配 173

6.3.3  堆式动态存储分配 180

小结 182

习题六 182

第7章  代码优化 183

7.1  优化概述 183

7.2  局部优化 185

7.2.1  基本块的划分方法 186

7.2.2  利用DAG进行基本块的优化 188

7.3  循环优化 192

7.3.1  程序流图与循环 192

7.3.2  循环的查找 196

7.3.3  循环优化的实现 197

小结 207

习题七 207

第8章  目标代码生成 209

8.1  代码生成器 209

8.2  一个简单的目标代码生成器 211

8.2.1  待用信息与活跃信息 212

8.2.2  源程序到目标代码生成示例 217

8.3  代码生成器的开发方法 219

小结 220

习题八 220

第9章  面向对象语言编译及并行编译基础 222

9.1  面向对象语言的概念 223

9.2  方法的编译 224

9.3  继承的编译方案 226

9.3.1  单一继承的编译方案 226

9.3.2  多重继承的编译方案 227

9.4  并行编译系统 228

9.4.1  并行编译系统的结构 229

9.4.2  并行编译方法 231

9.4.3  向量计算机 231

9.4.4  共享存储器多处理机 232

9.4.5  分布存储器大规模并行计算机 233

9.5  并行编译基础 233

9.5.1  向量与向量的次序 233

9.5.2  循环模型与索引空间 234

9.5.3  输入与输出集合 234

9.5.4  语句的执行顺序 234

9.5.5  依赖关系定义 235

9.6  循环的向量化与并行化 236

9.7  循环变换技术 236

小结 237

习题九 237

第10章  嵌入式系统编译器及其工具的应用开发 239

10.1  嵌入式系统概述 240

10.2  嵌入式系统常用芯片介绍 242

10.3  嵌入式系统结构、开发工具和编译器 244

10.3.1  嵌入式系统的体系结构 244

10.3.2  嵌入式系统开发工具和编译器 248

10.4  嵌入式系统C编译器开发和相应开发工具的应用 249

10.5  嵌入式系统Java编译器开发、JDK结构及开发工具的应用 252

10.5.1  JIT编译方法 253

10.5.2  AOT编译方法 256

10.5.3  JDK结构及开发工具的应用 258

小结 260

习题十 261

参考文献 262

无