编译系统是计算机系统中的系统软件，是软件开发环境的核心组成部分。《编译原理》介绍编译系统的结构、工作流程及编译程序各组成部分的设计原理和实现技术。作者遵循CDIO工程教育理念将《编译原理》内容分为四篇，第1篇构思（Conceive），包括编译程序概论、文法和语言；第2篇设计（Design），包括词法分析、自顶向下语法分析、自底向上语法分析、语义分析与符号表；第3篇实现（Implement），包括语法制导翻译与中间代码生成、目标程序运行时的存储组织、出错处理、代码优化、目标代码生成；第4篇运作（Operate），包括寄存器分配、垃圾回收、面向对象语言编译器和人工智能编译器。

第1章　编译程序概论
　　软件的实现离不开程序设计语言，用高级语言编写的程序代码必须通过编译程序转换为相应的机器语言代码才能被计算机执行。本章*先阐述与编译程序相关的一些概念，然后介绍编译过程和编译程序结构，*后讨论编译程序的构造技术和程序设计语言的不同风格，目的是使读者对编译系统的概念、编译程序结构、编译原理和工作过程有一个总体了解，以便展开后续各章节内容。
　　1.1　编译程序的概念
　　1.1.1　程序设计语言
　　计算机系统不同于一般的电子设备，它是一个由计算机硬件系统和计算机软件系统组成的复杂的信息处理系统。计算机硬件系统通常由处理器、存储器、输入设备和输出设备等部件组成。计算机软件系统一般包括系统软件(如操作系统、编译系统等)、支撑软件(如各种工具软件、编辑软件等)和应用软件，其中编译系统由编译程序和运行系统组成。
　　从软件工程的角度来看，一个软件的生命周期一般包括需求分析、系统设计、编码实现、测试、运行维护等阶段。其中编码实现是指用某种程序设计语言将系统设计阶段描述的算法编写成程序代码的过程。
　　程序设计语言是用来编写程序的工具，可分为两大类。
　　**类称为低级语言，包括机器语言、汇编语言以及其他面向机器的程序设计语言。机器语言是由0、1代码构成的，不需要翻译就可直接执行其程序；汇编语言是由机器指令助记符(伪代码)构成的，经汇编后才可执行其程序。在计算机诞生后的*初十年，程序员用来编写程序的语言基本上是这类语言，其特点是对计算机硬件依赖性强、可读性差、编写程序的工作量大，只有对相应计算机的结构比较熟悉且经过一定训练的编程人员才能较好地理解和使用。
　　第二类称为高级语言，其特点是对计算机硬件依赖性小、用类自然语言和数学公式形式编写程序代码。世界上**个真正意义上的高级程序设计语言是IBM公司的巴克斯(Backus)经过两年研究于1956年推出的FORTRAN语言，此后又陆续出现了多达数百种的高级语言，但很多都是一些实验性语言，除了一些专用语言之外，得到广泛应用的只有其中少数几种，如FORTRAN、BASIC、ALGOL、COBOL、PASCAL、C、DELPHI、JAVA、C#等。高级语言不论在算法描述的能力上，还是在编写和调试程序的效率上，都远比低级语言优越。
　　然而，计算机硬件只能识别自己的指令系统，即只能直接执行相应机器语言格式的代码程序，而不能直接执行用高级语言或汇编语言编写的程序。因此，要在计算机上运行除机器语言之外的任一程序语言，就应*先使该语言能被计算机所“理解”，即需要把用该语言编写的程序代码翻译为机器语言代码。
　　1.1.2　基本概念和术语
　　在前面对程序设计语言进行讨论的基础上，现在可以对一些概念和术语赋予确切的含义，以便更好地理解编译程序和编译系统。这些概念和术语将在以后的章节中多次出现。
　　源程序(source program)：用源语言写的程序。源语言可以是汇编语言，也可以是高级程序设计语言。
　　目标程序(object program)：也称为结果程序，是源程序经翻译程序加工以后所生成的程序。目标程序可以用机器语言表示，也可以用汇编语言或其他中间语言表示。
　　翻译程序(translating program)：是指把一个源程序翻译成逻辑上等价的目标程序的程序。源程序为其输入，目标程序为其输出。
　　汇编程序(assembler)：是指把一个用汇编语言编写的源程序转换成等价的机器语言表示的目标程序的翻译程序。
　　编译程序(compiler)：源程序是用高级程序设计语言所写的，经翻译程序加工生成目标程序的翻译程序，也可称为编译器。
　　运行系统(run-time system)：目标程序执行时，需要有一些子程序(如一些连接装配程序及一些连接库等)配合进行工作，由这些子程序组成的一个子程序库。
　　编译系统(compiler system)：编译程序和运行系统的合称。
　　1.1.3　程序设计语言的翻译
　　除机器语言程序外，用其他语言书写的程序都必须经过翻译才能被计算机识别。这一过程由翻译程序来完成。
　　翻译是指在计算机中放置一个能由计算机直接执行的翻译程序，它以某一种程序设计语言(源语言)所编写的程序(源程序)作为翻译或加工的对象，当计算机执行翻译程序时，就将它翻译为与之等价的另一种语言(目标语言)的程序(目标程序)，如图1.1所示。
　　图1.1　翻译程序的作用
　　“源”和“目标”这两个术语，总是相对于一类特定的翻译程序和翻译过程而言的。汇编程序是一种翻译程序，它的源语言和目标语言分别是相应的汇编语言和机器语言，如图1.2所示。
　　图1.2　汇编程序的作用
　　如果一个翻译程序的源语言是某种高级语言，其目标语言是相应于某一计算机的汇编语言或机器语言，则称这种翻译程序为编译程序，如图1.3所示。
　　图1.3　编译程序的作用
　　1.1.4　高级语言程序的执行
　　高级语言程序可以两种方式执行：一是编译方式，二是解释方式。这里先讨论编译执行方式，1.4节将讨论解释执行方式。
　　当以编译方式在计算机上执行用高级语言编写的程序时，一般需要经过两个阶段：**阶段称为编译阶段，其任务是由编译程序将源程序编译为目标程序，若目标程序不是机器代码，而是汇编语言程序，则需将汇编程序汇编为机器代码程序；第二阶段称为运行阶段，其任务是在目标计算机上执行编译阶段所得到的目标程序。在执行目标程序时，一般还应有一些子程序配合进行工作，如常见的数据格式转换子程序、标准函数计算子程序、浮点解释子程序、数组动态存储分配子程序、下标变量地址计算子程序等。这些子程序组成一个程序库，即运行系统。显然，库中的子程序越丰富，各子程序的功能越强，编译程序的结构就越简洁紧凑。
　　源程序的编译和目标程序的执行不一定在同一种计算机上完成。当源程序由另一种计算机进行编译(或汇编)时，将此种编译(或汇编)称为交叉编译(或汇编)。图1.4为计算机按编译方式执行一个高级语言程序的主要步骤。
　　编译程序是一种相当复杂的程序，其代码的长度可以从数万行到百万行不等，开发一个某种语言的编译程序的工作量往往以数百人年到上千人年计。编译程序已成为现今任何计算机系统*重要的系统程序之一。本书的目的，在于向读者介绍设计和构造编译程序的基本原理和基本方法，其中许多方法也同样适用于构造解释程序或汇编程序。
　　图1.4　执行高级语言程序的步骤
　　1.2　编译过程
　　编译程序的主要功能是把用高级语言编写的源程序翻译为等价的目标程序，既然编译过程是实现一种语言的翻译，那么可将编译程序的工作过程类比于外文资料(如英文资料)的翻译过程，这有助于更直观地了解一个编译程序一般应由哪些部分组成，以及各个组成部分应如何进行工作。
　　抽象地看，任何一份英文资料都是由英文大小写字母、标点符号(包括空格和其他符号)按相应语法规则所组成的字符串。因此，当需要将英文翻译为中文时，至少应具备如下能力：①认识英文的大小写字母及标点符号；②能识别出文中的各个单词；③会查字典；④懂得英文的语法；⑤具有目标语言(此处为中文)的修辞能力。至于如何进行翻译，概括地讲无非是做两方面的工作：一是进行分析，二是进行综合。所谓分析，就是从**行的**个字母开始，依次阅读英文资料中的各个符号，逐个识别出各个单词，然后根据语法规则进行语法分析，即分析原文中如何由单词组成短语和句子，以及句子的种类特点等。此外，在识别单词和进行语法分析的过程中，还要不时地查阅字典，做语法正确性的检查，进行相应的语义分析，并做一些必要的信息记录工作等。所谓综合，就是根据上述分析所得到的信息，拟定译稿，进行修辞加工，*后写出译文。
　　类似地，编译程序在其工作过程中，也需做两方面的工作，即分析源程序，然后再综合为目标程序。分析源程序时，*先对源程序的字符逐个扫描，进行词法分析，得到单词符号，再进行语法分析，根据语法规则将单词符号组合成句子，然后进行语义分析得到中间代码。综合处理，是对中间代码进行优化，*后生成目标代码。源程序编译过程与英文资料翻译过程的主要工作比较如表1.1所示。

目录
第1篇 构思(Conceive)
第1章 编译程序概论 3
1.1 编译程序的概念 3
1.1.1 程序设计语言 3
1.1.2 基本概念和术语 4
1.1.3 程序设计语言的翻译 4
1.1.4 高级语言程序的执行 5
1.2 编译过程 6
1.3 编译程序的结构 8
1.3.1 词法分析程序 10
1.3.2 语法分析程序 11
1.3.3 语义分析程序 12
1.3.4 中间代码生成程序 12
1.3.5 代码优化程序 13
1.3.6 目标代码生成程序 14
1.3.7 信息表管理程序 15
1.3.8 错误检查和处理程序 16
1.3.9 编译程序的分遍 17
1.4 解释程序 18
1.5 编译程序的评价指标与构造技术 19
1.5.1 编译程序的评价指标 20
1.5.2 编译程序的构造技术 21
1.6 程序设计语言范型 24
习题 26
第2章 文法和语言 27
2.1 符号和符号串 27
2.2 文法和语言的定义 29
2.3 文法的类型 35
2.4 上下文无关文法及其语法树 37
2.4.1 程序设计语言的语法结构的描述 37
2.4.2 语法树 38
2.4.3 文法的二义性 39
2.5 句型的分析 41
2.5.1 规范推导和规范归约 41
2.5.2 短语和句柄 43
2.6 文法描述语言时的限制与扩充 46
2.6.1 文法描述语言时的限制 46
2.6.2 文法描述语言时的扩充 47
习题 48
第2篇 设计(Design)
第3章 词法分析 53
3.1 词法分析概述 53
3.2 词法分析器的结构 53
3.2.1 词法分析器的工作方式 53
3.2.2 词法分析器的输出 54
3.2.3 词法分析作为一个*立阶段的原因 55
3.3 单词的描述工具 55
3.3.1 正规文法 56
3.3.2 正规式 56
3.3.3 正规文法和正规式的等价性 58
3.4 有限自动机 60
3.4.1 确定的有限自动机(DFA) 60
3.4.2 不确定的有限自动机(NFA) 62
3.4.3 NFA转换为等价的DFA 63
3.4.4 确定有限自动机的化简 66
3.5 正规式和有限自动机的等价性 68
3.6 正规文法和有限自动机的等价性 71
3.7 词法分析器的自动构造工具 73
习题 75
实践项目一 76
第4章 自顶向下语法分析 77
4.1 自顶向下语法分析概述 77
4.2 递归下降分析法 78
4.3 LL(1)预测分析法 80
4.4 非LL(1)文法到LL(1)文法的等价变换 83
4.4.1 提取左公共因子 83
4.4.2 消除左递归 84
4.4.3 消除文法左递归的方法 86
4.5 LL的自动生成工具 88
4.5.1 递归子程序法 88
4.5.2 预测分析方法 90
案例分析 91
习题 93
实践项目二 95
第5章 自底向上语法分析 96
5.1 自底向上语法分析概述 96
5.2 算符优先分析 97
5.2.1 算符优先文法的定义 97
5.2.2 算符优先关系表的构造 99
5.2.3 *左素短语 101
5.2.4 优先函数 103
5.3 LR分析 104
5.3.1 LR分析器概述 105
5.3.2 LR(0)分析 106
5.3.3 SLR(1)分析 113
5.3.4 LR(1)分析 114
5.3.5 LALR(1)分析 114
5.4 LR的自动生成工具 115
案例分析 115
习题 120
实践项目三 121
第6章 语义分析与符号表 122
6.1 语义分析概述 122
6.2 符号表的作用 122
6.3 符号表的内容 123
6.4 符号表的组织 128
6.5 符号表的管理 135
习题 137
第3篇 实现(Implement)
第7章 语法制导翻译与中间代码生成 141
7.1 语法制导翻译 141
7.1.1 属性文法 141
7.1.2 语法翻译概述 141
7.2 中间代码表示 143
7.2.1 逆波兰式 143
7.2.2 三地址代码 144
7.2.3 四元式表示 145
7.2.4 其他表示 146
7.3 简单赋值语句的翻译 146
7.4 布尔表达式的翻译 147
7.5 控制语句的翻译 149
习题 151
实践项目四 153
第8章 目标程序运行时的存储组织 154
8.1 存储组织及管理 154
8.2 静态存储分配策略 155
8.3 动态存储分配 157
8.3.1 过程与活动记录 157
8.3.2 简单的栈式存储分配的实现 159
8.3.3 嵌套过程语言的栈式实现 159
习题 161
第9章 出错处理 163
9.1 错误分类 163
9.1.1 语法错误 163
9.1.2 语义错误 163
9.2 编译程序中参数错误的处理 164
9.2.1 校正法 164
9.2.2 局部化法 165
9.2.3 参数FSYS集合内容的补充 168
9.3 一些语义错误的处理 169
9.3.1 遏止株连错误 169
9.3.2 遏止重复错误 169
习题 170
实践项目五 171
第10章 代码优化 172
10.1 优化技术简介 172
10.1.1 删除多余运算 172
10.1.2 复写传播 173
10.1.3 无用代码删除 173
10.1.4 代码外提 173
10.1.5 强度削弱和基本归纳变量删除 174
10.2 局部优化 175
10.2.1 基本块 175
10.2.2 基本块的有向无环图表示 176
10.2.3 基于基本块的优化 179
10.3 循环优化 180
10.3.1 流图 180
10.3.2 循环 180
10.3.3 循环不变计算及代码外提 183
10.3.4 归纳变量相关的优化 186
10.4 全局优化 188
10.4.1 全局公共子表达式 188
10.4.2 复写传播 188
习题 190
实践项目六 192
第11章 目标代码生成 193
11.1 目标代码生成概述 193
11.1.1 代码生成器的输入 193
11.1.2 目标代码的形式 193
11.1.3 指令选择 194
11.1.4 寄存器分配 194
11.1.5 计算顺序的选择 195
11.2 常用的代码生成器的开发方法 195
11.2.1 解释性代码生成法 195
11.2.2 模式匹配代码生成法 196
11.2.3 表驱动代码生成法 196
习题 197
第4篇 运作(Operate)
第12章 寄存器分配 201
12.1 寄存器分配概述 201
12.2 寄存器分配图染色法 202
12.3 合并 204
12.4 预着色的结点 206
12.5 图着色的实现 207
12.6 针对树的寄存器分配 208
习题 212
第13章 垃圾回收 213
13.1 垃圾收集概述 213
13.2 引用计数 214
13.3 复制式收集 215
13.4 分代收集 217
13.5 增量式收集 218
13.6 编译器接口 219
习题 221
第14章 面向对象语言编译器 222
14.1 面向对象语言概述 222
14.2 类与继承 223
14.3 私有域和私有方法 224
14.4 面向对象语言的翻译 225
14.4.1 单继承的编译方案 225
14.4.2 多继承的编译方案 227
14.5 面向对象语言的编译优化 228
习题 230
第15章 人工智能编译器 231
15.1 人工智能编程语言概述 231
15.1.1 Python 231
15.1.2 R 232
15.1.3 LISP 233
15.1.4 Prolog 233
15.2 Python虚拟机基本原理 233
15.2.1 过程概述 233
15.2.2 关于.pyc文件 234
15.2.3 关于PyCodeObject 234
15.2.4 执行字节码 235
15.2.5 Python字节码 236
15.3 代码自动生成与抽象语法树 237
习题 239
参考文献 240