商品详情
书名：计算机编译原理（第三版）
定价：79.0
ISBN：9787030212474
作者：张幸儿
版次：3
出版时间：2008-06
内容提要：
本书是普通高等教育“十一五”***规划教材。计算机编译原理是计算机专业的重要专业基础课之一。本书系统地介绍高级程序设计语言编译程序的构造原理，重点讨论词法分析、语法分析、语义分析以及目标代码的生成与代码优化。各章末有本章概要、习题与上机实习题。书末附有解题规范例解与总复习思考题。本书特别讨论了编译各阶段的实现考虑，读者可从这些实际可行的实现方法和技巧中得到借鉴和启发。为了便于教学，本书另配有电子教案和习题解答可供选用，还提供配套教材《计算机编译原理——编译程序构造实践》，可供上机实践参考。
目录：
目录
前言
第1章 总论 1
1.1 引言 1
1.2 程序设计语言与程序 3
1.2.1 程序及其结构 3
1.2.2 程序设计语言的定义 4
1.2.3 程序的执行 7
1.3 编译程序构造及有关概念 9
1.3.1 编译程序的构造 9
1.3.2 遍的概念 11
1.3.3 编译程序的分类 12
1.3.4 实际应用中的编译程序 13
1.4 形式语言理论与编译实现技术 15
本章概要 15
第2章 文法与语言 17
2.1 符号串与符号串集合 17
2.1.1 字母表 17
2.1.2 符号串 17
2.1.3 符号串集合 19
2.2 文法与语言的形式定义 20
2.2.1 文法的形式定义 20
2.2.2 语言的形式定义 31
2.3 语言的分类 35
2.3.1 Chomsky文法类和语言类 35
2.3.2 形式语言与自动机 41
2.3.3 形式语言的分类与程序设计语言 44
2.3.4 对上下文无关文法的进一步讨论 45
2.4 文法等价与等价变换 47
2.4.1 文法等价的概念 47
2.4.2 压缩文法等价变换 48
2.4.3 消去左递归的文法等价变换 51
2.5 语法分析树与句型分析 55
2.5.1 语法分析树的概念 55
2.5.2 句型分析 61
本章概要 65
习题1 65
习题2 66
习题3 66
习题4 67
习题5 67
第2章上机实习题 68
第3章 词法分析 69
3.1 引言 69
3.1.1 词法分析与词法分析程序 69
3.1.2 符号的识别与重写规则的关系 69
3.1.3 实现方式 70
3.2 正则表达式与有穷状态自动机 71
3.2.1 状态转换图 71
3.2.2 确定有穷状态自动机DFA 75
3.2.3 非确定有穷状态自动机NFA 78
3.2.4 确定有穷状态自动机的化简 84
3.2.5 正则表达式 86
3.3 词法分析程序的实现 89
3.3.1 符号与属性字 89
3.3.2 标识符的处理 94
3.3.3 词法分析程序的编写 100
3.4 词法分析程序的自动生成 105
3.4.1 基本思想 105
3.4.2 扫描程序定义与构造程序 111
3.4.3 自动生成系统LEX筒介 114
本章概要 115
习题6 116
第3章上机实习题 117
第4章 语法分析——自顶向下分析技术 119
4.1 引言 119
4.1.1 自顶向下分析技术及识别算法 119
4.1.2 讨论的前提 119
4.1.3 要解决的基本问题 120
4.2 带回溯的自顶向下分析技术 121
4.2.1 基本思想 121
4.2.2 语法分析树的建立及其表列表示 123
4.2.3 问题及其解决 124
4.3 无回溯的自顶向下分析技术 125
4.3.1 先决条件 125
4.3.2 递归下降分析技术 125
4.3.3 预测分析技术 132
本章概要 142
习题7 143
第4章上机实习题 143
第5章 语法分析——自底向上分析技术 145
5.1 引言 145
5.1.1 自底向上分析技术及识别算法 145
5.1.2 讨论前提 145
5.1.3 基本实现方法：移入-归约法 146
5.2 算符优先分析技术 148
5.2.1 算符优先分析技术的引进 148
5.2.2 算符文法 148
5.2.3 算符优先关系与算符优先文法 150
5.2.4 算符优先文法句型的识别 154
5.2.5 优先函数 158
5.2.6 实际应用中的算符优先分析技术 168
5.3 LR(k)分析技术 170
5.3.1 LR(k)文法与LR(k)分析技术 170
5.3.2 SLR(k)分析表构造万法 182
5.3.3 LALR(k)分析表构造方法 196
5.3.4 识别程序自动构造 201
5.3.5 识别程序自动生成系统YACC简介 205
5.4 LR(1)识别程序句型分析的实现 207
本章概要 210
习题8 211
习题9 212
习题10 212
第5章上机实习题 213
第6章 语义分析与目标代码生成 214
6.1 概况 214
6.1.1 语义分析的概念 214
6.1.2 属性文法 216
6.1.3 类型体制与语义分析 233
6.2 说明部分的翻译 241
6.2.1 常量定义的翻译 242
6.2.2 变量说明的翻译 242
6.2.3 函数定义的翻译 244
6.2.4 结构体类型的翻译 247
6.3 目标代码的生成 248
6.3.1 概况 248
6.3.2 虚拟机 251
6.3.3 控制语句的翻译 253
6.4 语义分析的实现考虑 283
6.4.1 注释分析树的构造 283
6.4.2 语义动作的实现 288
6.4.3 语义子程序的例子 295
6.5 源程序的中间表示代码 296
6.5.1 抽象语法树 297
6.5.2 逆波兰表示 300
6.5.3 四元式序列 306
6.5.4 三元式序列 315
本章概要 316
习题11 317
习题12 317
习题13 318
习题14 319
第6章上机实习题 320
第7章 运行环境 321
7.1 引言 321
7.1.1 相关的问题 321
7.1.2 名字到存储字的结合 321
7.2 存储分配策略 325
7.2.1 静态存储分配 325
7.2.2 栈式存储分配 326
7.2.3 堆式存储分配 329
7.3 寄存器分配 332
7.3.1 使用图着色方法进行寄存器分配的思路 332
7.3.2 例子 333
7.3.3 若干问题讨论 335
7.4 符号表 336
7.4.1 符号表的引进 336
7.4.2 符号表的组织 337
7.4.3 符号表的数据结构 341
7.5 运行时刻支持系统 344
本章概要 345
习题15 346
第8章 代码优化 348
8.1 引言 348
8.1.1 优化的概念 348
8.1.2 代码优化的分类 349
8.1.3 代码优化程序的结构 350
8.2 基本块与流图 351
8.3 基本块的优化 352
8.3.1 基本块优化的种类 352
8.3.2 基本块优化的实现 356
8.4 与循环有关的优化 365
8.4.1 循环优化的种类 366
8.4.2 循环优化的实现 373
8.5 窥孔优化 395
8.5.1 冗余指令删除 395
8.5.2 控制流优化 397
8.5.3 代数化简 398
8.5.4 特殊指令的使用 398
本章概要 398
习题16 399
第8章上机实习题 401
第9章 程序错误的检查和校正 402
9.1 概述 402
9.1.1 错误存在的必然性 402
9.1.2 错误的种类 402
9.1.3 错误复原 404
9.2 词法错误的复原和校正 405
9.2.1 词法错误的种类 405
9.2.2 词法错误的校正 405
9.3 语法错误的复原和校正 406
9.3.1 语法错误的复原 406
9.3.2 语法错误的校正 407
9.4 语义错误 408
9.4.1 语义错误的种类 408
9.4.2 语义错误检查措施 409
本章概要 411
解题规范例解 412
总复习思考题 439
参考文献 441
在线试读：
第1章 总论
1.1 引言
作为一种工具，电子计算机以其处理数据容量大、速度快、精度高且具有自动判别功能等显著特点，而广泛应用于各个领域。早先人工必须用几年、甚至几辈子都难以完成的计算量，现在使用计算机只需短短几天、几个小时甚至几分钟即可完成。在当今的社会，人们难以想象离开计算机的世界将是什么模样。
计算机之所以如此神奇，除了硬件基础之外，当归功于计算机软件系统。进一步说，计算机之所以能为广大用户所接受，不能不说是因为有高级程序设计语言的存在。高级程序设计语言的引进，使人们能用接近于数学用语的表示法去表达算法，让计算机做人们想做的事，从而为计算机的推广应用打开了局面。没有高级程序设计语言，计算机要想推广应用是不可思议的。
高级程序设计语言作为一种语言，是人机对话的工具。人们用某种高级语言写出程序来表达自己想做的事情和期望达到的效果，计算机接受这些程序，然后运行而产生相应的效果。程序设计语言是一种符号语言，采用了接近于数学用语的表示法，使人们容易书写与理解，也容易相互交流。请看下列C程序片段：
这种表达非常易读、易理解，即比较x与y的值，若x的值大，让max取x值，否则让max取y值。读者立即可以得出结论：该程序片段的功能是求两个数中的*大值。如果用机器语言写出上述功能的程序将是非常难以理解的。例如，为IBM 370机写出具有相应功能的二进制机器代码如下：
如果不看右边的注解，该机器代码犹如天书一般。只有了解具体机器指令系统的人才能读懂，而且还必须了解存储分配情况，知道为变量x、y与max分别分配了单元1020、1024与1028。即使是汇编语言程序，也不是那样一目了然。例如，相应于上述机器语言的程序片段可编写成如下的汇编语言程序：
高级语言明显的优点为：接近于数学表示法，因而易读、易理解；与具体机器无关，可以在不同型号机器上使用同一个程序。不仅如此，高级语言程序还易于查错，且一个语句往往对应于若干机器指令，使书写程序的效率更高。
然而，高级程序设计语言毕竟是符号语言，任何程序归根结底总是一个字符序列，其中包括英文字母、数字、运算符、括号及标点符号等。计算机能直接理解的只能是二进制机器代码，为使计算机能理解高级语言程序，其间必须有一个“翻译”，把符号程序翻译成计算机可直接接受和运行的二进制代码程序。这个“翻译”就是编译程序。
本书将讨论计算机编译程序的构造原理，也就是讨论在给定某个高级程序设计语言时，编译程序应该有怎样的结构；在构造编译程序时，可采用哪些技术、会发生哪些问题、应如何去解决，等等。
人们感觉到的东西并不一定能深刻理解，只有在理性上进一步认识，才可能更深刻地去洞察领悟它。当读者不仅了解一个编译程序可怎样去实现，而且还了解为什么这样去实现时，将可高屋建瓴，更好地去实现编译程序。为此，作为编译程序构造原理，要基于形式语言理论中的有关概念来讨论编译实现问题。可以概括地用下列公式表达：
编译原理=形式语言理论+编译技术
编译程序可看作是程序设计语言的支持工具或环境。在编译程序支持下，高级语言程序才可能得以运行。为了更好地领会与掌握编译程序的构造，有必要对高级程序设计语言作一定篇幅的讨论。概括起来，全书将涉及以下三方面内容：
①高级程序设计语言（为简便起见，今后除非特别指明，程序设计语言均指高级程序设计语言）。
②与实现编译有关的形式语言理论基本概念。
③构造编译程序的基本概念、原理与技术。
编译程序构造原理又将包括词法分析、语法分析、语义分析、目标代码生成与代码优化等。我们将以C程序设计语言为背景，把这些方面有机地结合起来，比较全面、系统地进行讨论，易于读者掌握。为了便于讨论，对C语言作了简化（仅讨论其子集）；鉴于C语言表示法上的某些不足，本书中也将作适当的变通。例如，C语言中的赋值号“一”易与等号混淆，因此本书的叙述中未明确是赋值语句时赋值号用“：一”表示，“一”则表示等号；又如，在C语言中每个语句都用分号“；”结束，在文字叙述中出现某语句时，易于把此语句的结束分号看作标点符号，本书中往往将省略此分号。另外，C语言中仅有函数的概念，而一般语言中有函数和过程两个概念。事实上，函数一般是指有值函数，而过程就是指无值函数。因此，这两个概念不严加区别，并不影响对相关概念的理解。
期望读者在阅读本书后，对编译程序构造原理能有一个清晰的概念。“编译原理”课程也是一门实践性很强的课程，建议有条件的读者在消化理解的基础上自行设计C语言的一个小子集，并为它构造编译程序，将受益匪浅。
1. 2 程序设计语言与程序
1.2.1 程序及其结构
“程序”这一词在人类社会活动中早已存在，譬如“大会程序”，它规定了大会依次要进行的工作。借用到计算机领域，程序是指一系列指令或语句，它同样规定了依次要进行的一系列工作，只不过现在由计算机去执行，即由计算机执行特定的指令或语句序列以获得某种预期的效果。
在计算机领域里，程序是计算机系统中计算任务的处理对象与处理规则的描述，是计算机实现各类信息处理的工具，是人与计算机的接口。人通过程序命令和操纵计算机完成预期的工作。
一个计算机程序总是联系于某种程序设计语言。程序设计语言用来书写计算机程序，它可以是与具体计算机特性紧密相关的低级语言，如各种特定计算机的机器语言与汇编语言；也可以是接近于日常用语与数学表示法的高级语言。用户可以根据应用领域实际问题的特定情况，选择合适的程序设计语言，如对于工程计算选用Fortran，对于教学与科学计算选用Pasca1，对于开发系统软件选用C语言，等等。
任何用高级程序设计语言书写的程序总是按一定的构架构成的。如有C程序如下：一般C程序的结构成分按概念层次由小到大可表示为：
基本符号一符号（单词）一量一表达式一说明与语句一函数定义一程序
归根结底，程序是由一连串基本符号组成的。C语言的基本符号可以是字母、数字与界限符等。字母包括a，b，…，z，A，B，…，Z，数字包括0，1，…，9，界限符包括关键字（如char与if）和专用符号两类。专用符号可以是运算符（如“+”与“一”）、括号（如“{”与“）”）、分隔符（如逗号“，”与分号“；”）等。
某些基本符号具有特定的含义，如上述的+、一等。但也有一些基本符号不具有特定含义，如一切字母与数字，它们必须在组成标识符、数或标号时才含有特定的含义，这时它们已成为符号（单词）的组成部分。
不言而喻，不同的程序设计语言有不同的基本符号集。
1.2.2 程序设计语言的定义
程序设计语言是为书写计算机程序而人为设计的符号语言。为了能让计算机确切地理解程序的意义，以及便于人们之间相互交流，对同种程序设计语言书写的程序应有一致的理解，换言之，对一种程序设计语言应有明了而确切的定义。
1．程序设计语言的四个方面
一般程序设计语言的定义涉及语法、语义、语用与语境四个方面。
（1）语法
语法是指如何由程序设计语言基本符号组成程序中各个语法成分（包括程序）的一组规则，其中由符号（单词）构成语法成分的规则为一般的语法规则，而由基本符号构成符号（单词）的书写规则特称为词法规则。语法规则可用形式的方式描述，也可用语法图这样的非形式方式描述，甚至用口语方式描述。不论用哪种方式描述，语法定义总可在关于程序设计语言的用户手册上找到。关于语法的定义形式将在下面进一步讨论。
（2）语义
语义是程序设计语言中按语法规则所构成的各个语法成分的意义。一个程序执行的效果说明了该程序的含义，也就是程序的语义。程序的语义自然取决于相应程序设计语言各种语法成分的语义定义，即取决于程序设计语言的语义。语义分静态语义与动态语义，静态语义指编译时刻可确定的语法成分的含义；运行时刻才能理解与确定的含义称动态语义。
语义通常用非形式的口语描述方式来定义。但为了精确而一致地定义程序设计语言的语义，有利于保证或验证程序的正确性，特别是自动生成程序，像语法那样形式地定义语义是至为重要的，因而形成了计算机科学的又一个重要分支——形式语义学。对此，因已超出本书的范畴，我们不作讨论。
（3）语用
语用表示语言符号及其使用者之间的关系，涉及符号的来源、使用和影响。对于程序设计语言，语用表示程序和使用者之间的关系。在程序中往往用注解形式解释某些变量的物理意义与用途等，这可看成是语用的应用。
（4）语境
语境是指理解和实现程序设计语言的环境，这种环境因此包括编译环境与运行环境。语境的不同将影响到语言的实现。例如，C语言整型量通常占用2个字节，若占用4个字节，C程序的书写与运行将有很大的不同。显然，同一种程序设计语言的易移植性受语境所影响。
2．语法定义
（1）语法图
语法图是用图解的形式来描述程序设计语言语法规则的工具。图1-1展示了C语言关于函数定义、简单表达式与因式的语法图。要说明的是，为讨论简单起见，对所引用的C语言语法规则做了一定的简化或修改。
图1-1
图中长方框表示语法成分，圆框表示将出现在程序中的符号。弧表示后继关系，例如，函数类型后继以函数标识符、函数标识符后继以圆括号“（”等。显然，图1-1（a）中的语法图描述了C语言函数定义的结构框架，图1-1（b）中的语法图描述了简单表达式的构成，而图1-1（c）中的语法图描述了四类因式，即无正负号常量、变量、用圆括号括住的表达式以及函数引用（调用）。
语法图的优点是形象直观；不足是不紧凑、篇幅较大，尤其因为是非形式的，不利于语法分析程序的自动生成。
（2） BNF表示法
BNF表示法是语法规则的形式表示系统，其中规则取如下形式，例如：
（函数定义）：：=（函数首部）（函数体）
它读作：（函数定义）定义为（函数首部）后跟以（函数体）。至于（函数首部）则定义为：
（函数首部）：：=（函数类型）（函数标识符）（（形参表列））
与
（函数首部）：：=（函数类型）（函数标识符）（ ）
或者缩写为：
（函数首部）：：=（函数类型）（函数标识符）（（形参表列））（函数类型）（函数标识符）（）
其中符号“”表示“或者”，读作：（函数首部）定义为（函数类型）（函数标识符）（（形参表列））或者定义为（函数类型）（函数标识符）（）。
对于（形参表列）定义为：
（形参表列）：：=（形参表列），（形参）
与
（形参表列）：：=（形参）
或者缩写为：
（形参表列）：：=（形参表列），（形参）|（形参）
BNF表示法是描述程序设计语言的形式体系，称为元语言。一般地，用来描述另外某种语言的语言称为元语言。符号“：：=”与“”称为元语言连接符或称元符号，这里用尖括号对“（”与“）”括住的是语法实体，它们不是语言中真正存在的实体，而是元语言中为了分析程序结构而引进的语法概念，称元语言变量，它们并不出现在程序中，如（函数定义）与（形参）等。今后将称之为非终结符号。它们每一个必出现在规则左部（符号“：：=”左边部分）至少一次。不出现在规则左部的符号是可能出现在程序中的符号，今后将称之为终结符号。
很明显，BNF表示法描述的C语言函数定义的结构与语法图描述的是完全一致的。
BNF表示法的特点是简洁、严谨、精确和无歧义。它首次应用于描述程序设计语言ALGOL。的语法，获得了极大的成功。由于它与今后将讨论的上下文无关文法规则定义形式一致而备受关注。
通常为了更简洁与更易读，对BNF表示法进行扩充。这时引入一些新的元符号，即花括号“{”与“}”、方括号“[”与“]”以及圆括号“（”与“）”，称为扩充的BNF表
定价：79.0
ISBN：9787030212474
作者：张幸儿
版次：3
出版时间：2008-06
内容提要：
本书是普通高等教育“十一五”***规划教材。计算机编译原理是计算机专业的重要专业基础课之一。本书系统地介绍高级程序设计语言编译程序的构造原理，重点讨论词法分析、语法分析、语义分析以及目标代码的生成与代码优化。各章末有本章概要、习题与上机实习题。书末附有解题规范例解与总复习思考题。本书特别讨论了编译各阶段的实现考虑，读者可从这些实际可行的实现方法和技巧中得到借鉴和启发。为了便于教学，本书另配有电子教案和习题解答可供选用，还提供配套教材《计算机编译原理——编译程序构造实践》，可供上机实践参考。
目录：
目录
前言
第1章 总论 1
1.1 引言 1
1.2 程序设计语言与程序 3
1.2.1 程序及其结构 3
1.2.2 程序设计语言的定义 4
1.2.3 程序的执行 7
1.3 编译程序构造及有关概念 9
1.3.1 编译程序的构造 9
1.3.2 遍的概念 11
1.3.3 编译程序的分类 12
1.3.4 实际应用中的编译程序 13
1.4 形式语言理论与编译实现技术 15
本章概要 15
第2章 文法与语言 17
2.1 符号串与符号串集合 17
2.1.1 字母表 17
2.1.2 符号串 17
2.1.3 符号串集合 19
2.2 文法与语言的形式定义 20
2.2.1 文法的形式定义 20
2.2.2 语言的形式定义 31
2.3 语言的分类 35
2.3.1 Chomsky文法类和语言类 35
2.3.2 形式语言与自动机 41
2.3.3 形式语言的分类与程序设计语言 44
2.3.4 对上下文无关文法的进一步讨论 45
2.4 文法等价与等价变换 47
2.4.1 文法等价的概念 47
2.4.2 压缩文法等价变换 48
2.4.3 消去左递归的文法等价变换 51
2.5 语法分析树与句型分析 55
2.5.1 语法分析树的概念 55
2.5.2 句型分析 61
本章概要 65
习题1 65
习题2 66
习题3 66
习题4 67
习题5 67
第2章上机实习题 68
第3章 词法分析 69
3.1 引言 69
3.1.1 词法分析与词法分析程序 69
3.1.2 符号的识别与重写规则的关系 69
3.1.3 实现方式 70
3.2 正则表达式与有穷状态自动机 71
3.2.1 状态转换图 71
3.2.2 确定有穷状态自动机DFA 75
3.2.3 非确定有穷状态自动机NFA 78
3.2.4 确定有穷状态自动机的化简 84
3.2.5 正则表达式 86
3.3 词法分析程序的实现 89
3.3.1 符号与属性字 89
3.3.2 标识符的处理 94
3.3.3 词法分析程序的编写 100
3.4 词法分析程序的自动生成 105
3.4.1 基本思想 105
3.4.2 扫描程序定义与构造程序 111
3.4.3 自动生成系统LEX筒介 114
本章概要 115
习题6 116
第3章上机实习题 117
第4章 语法分析——自顶向下分析技术 119
4.1 引言 119
4.1.1 自顶向下分析技术及识别算法 119
4.1.2 讨论的前提 119
4.1.3 要解决的基本问题 120
4.2 带回溯的自顶向下分析技术 121
4.2.1 基本思想 121
4.2.2 语法分析树的建立及其表列表示 123
4.2.3 问题及其解决 124
4.3 无回溯的自顶向下分析技术 125
4.3.1 先决条件 125
4.3.2 递归下降分析技术 125
4.3.3 预测分析技术 132
本章概要 142
习题7 143
第4章上机实习题 143
第5章 语法分析——自底向上分析技术 145
5.1 引言 145
5.1.1 自底向上分析技术及识别算法 145
5.1.2 讨论前提 145
5.1.3 基本实现方法：移入-归约法 146
5.2 算符优先分析技术 148
5.2.1 算符优先分析技术的引进 148
5.2.2 算符文法 148
5.2.3 算符优先关系与算符优先文法 150
5.2.4 算符优先文法句型的识别 154
5.2.5 优先函数 158
5.2.6 实际应用中的算符优先分析技术 168
5.3 LR(k)分析技术 170
5.3.1 LR(k)文法与LR(k)分析技术 170
5.3.2 SLR(k)分析表构造万法 182
5.3.3 LALR(k)分析表构造方法 196
5.3.4 识别程序自动构造 201
5.3.5 识别程序自动生成系统YACC简介 205
5.4 LR(1)识别程序句型分析的实现 207
本章概要 210
习题8 211
习题9 212
习题10 212
第5章上机实习题 213
第6章 语义分析与目标代码生成 214
6.1 概况 214
6.1.1 语义分析的概念 214
6.1.2 属性文法 216
6.1.3 类型体制与语义分析 233
6.2 说明部分的翻译 241
6.2.1 常量定义的翻译 242
6.2.2 变量说明的翻译 242
6.2.3 函数定义的翻译 244
6.2.4 结构体类型的翻译 247
6.3 目标代码的生成 248
6.3.1 概况 248
6.3.2 虚拟机 251
6.3.3 控制语句的翻译 253
6.4 语义分析的实现考虑 283
6.4.1 注释分析树的构造 283
6.4.2 语义动作的实现 288
6.4.3 语义子程序的例子 295
6.5 源程序的中间表示代码 296
6.5.1 抽象语法树 297
6.5.2 逆波兰表示 300
6.5.3 四元式序列 306
6.5.4 三元式序列 315
本章概要 316
习题11 317
习题12 317
习题13 318
习题14 319
第6章上机实习题 320
第7章 运行环境 321
7.1 引言 321
7.1.1 相关的问题 321
7.1.2 名字到存储字的结合 321
7.2 存储分配策略 325
7.2.1 静态存储分配 325
7.2.2 栈式存储分配 326
7.2.3 堆式存储分配 329
7.3 寄存器分配 332
7.3.1 使用图着色方法进行寄存器分配的思路 332
7.3.2 例子 333
7.3.3 若干问题讨论 335
7.4 符号表 336
7.4.1 符号表的引进 336
7.4.2 符号表的组织 337
7.4.3 符号表的数据结构 341
7.5 运行时刻支持系统 344
本章概要 345
习题15 346
第8章 代码优化 348
8.1 引言 348
8.1.1 优化的概念 348
8.1.2 代码优化的分类 349
8.1.3 代码优化程序的结构 350
8.2 基本块与流图 351
8.3 基本块的优化 352
8.3.1 基本块优化的种类 352
8.3.2 基本块优化的实现 356
8.4 与循环有关的优化 365
8.4.1 循环优化的种类 366
8.4.2 循环优化的实现 373
8.5 窥孔优化 395
8.5.1 冗余指令删除 395
8.5.2 控制流优化 397
8.5.3 代数化简 398
8.5.4 特殊指令的使用 398
本章概要 398
习题16 399
第8章上机实习题 401
第9章 程序错误的检查和校正 402
9.1 概述 402
9.1.1 错误存在的必然性 402
9.1.2 错误的种类 402
9.1.3 错误复原 404
9.2 词法错误的复原和校正 405
9.2.1 词法错误的种类 405
9.2.2 词法错误的校正 405
9.3 语法错误的复原和校正 406
9.3.1 语法错误的复原 406
9.3.2 语法错误的校正 407
9.4 语义错误 408
9.4.1 语义错误的种类 408
9.4.2 语义错误检查措施 409
本章概要 411
解题规范例解 412
总复习思考题 439
参考文献 441
在线试读：
第1章 总论
1.1 引言
作为一种工具，电子计算机以其处理数据容量大、速度快、精度高且具有自动判别功能等显著特点，而广泛应用于各个领域。早先人工必须用几年、甚至几辈子都难以完成的计算量，现在使用计算机只需短短几天、几个小时甚至几分钟即可完成。在当今的社会，人们难以想象离开计算机的世界将是什么模样。
计算机之所以如此神奇，除了硬件基础之外，当归功于计算机软件系统。进一步说，计算机之所以能为广大用户所接受，不能不说是因为有高级程序设计语言的存在。高级程序设计语言的引进，使人们能用接近于数学用语的表示法去表达算法，让计算机做人们想做的事，从而为计算机的推广应用打开了局面。没有高级程序设计语言，计算机要想推广应用是不可思议的。
高级程序设计语言作为一种语言，是人机对话的工具。人们用某种高级语言写出程序来表达自己想做的事情和期望达到的效果，计算机接受这些程序，然后运行而产生相应的效果。程序设计语言是一种符号语言，采用了接近于数学用语的表示法，使人们容易书写与理解，也容易相互交流。请看下列C程序片段：
这种表达非常易读、易理解，即比较x与y的值，若x的值大，让max取x值，否则让max取y值。读者立即可以得出结论：该程序片段的功能是求两个数中的*大值。如果用机器语言写出上述功能的程序将是非常难以理解的。例如，为IBM 370机写出具有相应功能的二进制机器代码如下：
如果不看右边的注解，该机器代码犹如天书一般。只有了解具体机器指令系统的人才能读懂，而且还必须了解存储分配情况，知道为变量x、y与max分别分配了单元1020、1024与1028。即使是汇编语言程序，也不是那样一目了然。例如，相应于上述机器语言的程序片段可编写成如下的汇编语言程序：
高级语言明显的优点为：接近于数学表示法，因而易读、易理解；与具体机器无关，可以在不同型号机器上使用同一个程序。不仅如此，高级语言程序还易于查错，且一个语句往往对应于若干机器指令，使书写程序的效率更高。
然而，高级程序设计语言毕竟是符号语言，任何程序归根结底总是一个字符序列，其中包括英文字母、数字、运算符、括号及标点符号等。计算机能直接理解的只能是二进制机器代码，为使计算机能理解高级语言程序，其间必须有一个“翻译”，把符号程序翻译成计算机可直接接受和运行的二进制代码程序。这个“翻译”就是编译程序。
本书将讨论计算机编译程序的构造原理，也就是讨论在给定某个高级程序设计语言时，编译程序应该有怎样的结构；在构造编译程序时，可采用哪些技术、会发生哪些问题、应如何去解决，等等。
人们感觉到的东西并不一定能深刻理解，只有在理性上进一步认识，才可能更深刻地去洞察领悟它。当读者不仅了解一个编译程序可怎样去实现，而且还了解为什么这样去实现时，将可高屋建瓴，更好地去实现编译程序。为此，作为编译程序构造原理，要基于形式语言理论中的有关概念来讨论编译实现问题。可以概括地用下列公式表达：
编译原理=形式语言理论+编译技术
编译程序可看作是程序设计语言的支持工具或环境。在编译程序支持下，高级语言程序才可能得以运行。为了更好地领会与掌握编译程序的构造，有必要对高级程序设计语言作一定篇幅的讨论。概括起来，全书将涉及以下三方面内容：
①高级程序设计语言（为简便起见，今后除非特别指明，程序设计语言均指高级程序设计语言）。
②与实现编译有关的形式语言理论基本概念。
③构造编译程序的基本概念、原理与技术。
编译程序构造原理又将包括词法分析、语法分析、语义分析、目标代码生成与代码优化等。我们将以C程序设计语言为背景，把这些方面有机地结合起来，比较全面、系统地进行讨论，易于读者掌握。为了便于讨论，对C语言作了简化（仅讨论其子集）；鉴于C语言表示法上的某些不足，本书中也将作适当的变通。例如，C语言中的赋值号“一”易与等号混淆，因此本书的叙述中未明确是赋值语句时赋值号用“：一”表示，“一”则表示等号；又如，在C语言中每个语句都用分号“；”结束，在文字叙述中出现某语句时，易于把此语句的结束分号看作标点符号，本书中往往将省略此分号。另外，C语言中仅有函数的概念，而一般语言中有函数和过程两个概念。事实上，函数一般是指有值函数，而过程就是指无值函数。因此，这两个概念不严加区别，并不影响对相关概念的理解。
期望读者在阅读本书后，对编译程序构造原理能有一个清晰的概念。“编译原理”课程也是一门实践性很强的课程，建议有条件的读者在消化理解的基础上自行设计C语言的一个小子集，并为它构造编译程序，将受益匪浅。
1. 2 程序设计语言与程序
1.2.1 程序及其结构
“程序”这一词在人类社会活动中早已存在，譬如“大会程序”，它规定了大会依次要进行的工作。借用到计算机领域，程序是指一系列指令或语句，它同样规定了依次要进行的一系列工作，只不过现在由计算机去执行，即由计算机执行特定的指令或语句序列以获得某种预期的效果。
在计算机领域里，程序是计算机系统中计算任务的处理对象与处理规则的描述，是计算机实现各类信息处理的工具，是人与计算机的接口。人通过程序命令和操纵计算机完成预期的工作。
一个计算机程序总是联系于某种程序设计语言。程序设计语言用来书写计算机程序，它可以是与具体计算机特性紧密相关的低级语言，如各种特定计算机的机器语言与汇编语言；也可以是接近于日常用语与数学表示法的高级语言。用户可以根据应用领域实际问题的特定情况，选择合适的程序设计语言，如对于工程计算选用Fortran，对于教学与科学计算选用Pasca1，对于开发系统软件选用C语言，等等。
任何用高级程序设计语言书写的程序总是按一定的构架构成的。如有C程序如下：一般C程序的结构成分按概念层次由小到大可表示为：
基本符号一符号（单词）一量一表达式一说明与语句一函数定义一程序
归根结底，程序是由一连串基本符号组成的。C语言的基本符号可以是字母、数字与界限符等。字母包括a，b，…，z，A，B，…，Z，数字包括0，1，…，9，界限符包括关键字（如char与if）和专用符号两类。专用符号可以是运算符（如“+”与“一”）、括号（如“{”与“）”）、分隔符（如逗号“，”与分号“；”）等。
某些基本符号具有特定的含义，如上述的+、一等。但也有一些基本符号不具有特定含义，如一切字母与数字，它们必须在组成标识符、数或标号时才含有特定的含义，这时它们已成为符号（单词）的组成部分。
不言而喻，不同的程序设计语言有不同的基本符号集。
1.2.2 程序设计语言的定义
程序设计语言是为书写计算机程序而人为设计的符号语言。为了能让计算机确切地理解程序的意义，以及便于人们之间相互交流，对同种程序设计语言书写的程序应有一致的理解，换言之，对一种程序设计语言应有明了而确切的定义。
1．程序设计语言的四个方面
一般程序设计语言的定义涉及语法、语义、语用与语境四个方面。
（1）语法
语法是指如何由程序设计语言基本符号组成程序中各个语法成分（包括程序）的一组规则，其中由符号（单词）构成语法成分的规则为一般的语法规则，而由基本符号构成符号（单词）的书写规则特称为词法规则。语法规则可用形式的方式描述，也可用语法图这样的非形式方式描述，甚至用口语方式描述。不论用哪种方式描述，语法定义总可在关于程序设计语言的用户手册上找到。关于语法的定义形式将在下面进一步讨论。
（2）语义
语义是程序设计语言中按语法规则所构成的各个语法成分的意义。一个程序执行的效果说明了该程序的含义，也就是程序的语义。程序的语义自然取决于相应程序设计语言各种语法成分的语义定义，即取决于程序设计语言的语义。语义分静态语义与动态语义，静态语义指编译时刻可确定的语法成分的含义；运行时刻才能理解与确定的含义称动态语义。
语义通常用非形式的口语描述方式来定义。但为了精确而一致地定义程序设计语言的语义，有利于保证或验证程序的正确性，特别是自动生成程序，像语法那样形式地定义语义是至为重要的，因而形成了计算机科学的又一个重要分支——形式语义学。对此，因已超出本书的范畴，我们不作讨论。
（3）语用
语用表示语言符号及其使用者之间的关系，涉及符号的来源、使用和影响。对于程序设计语言，语用表示程序和使用者之间的关系。在程序中往往用注解形式解释某些变量的物理意义与用途等，这可看成是语用的应用。
（4）语境
语境是指理解和实现程序设计语言的环境，这种环境因此包括编译环境与运行环境。语境的不同将影响到语言的实现。例如，C语言整型量通常占用2个字节，若占用4个字节，C程序的书写与运行将有很大的不同。显然，同一种程序设计语言的易移植性受语境所影响。
2．语法定义
（1）语法图
语法图是用图解的形式来描述程序设计语言语法规则的工具。图1-1展示了C语言关于函数定义、简单表达式与因式的语法图。要说明的是，为讨论简单起见，对所引用的C语言语法规则做了一定的简化或修改。
图1-1
图中长方框表示语法成分，圆框表示将出现在程序中的符号。弧表示后继关系，例如，函数类型后继以函数标识符、函数标识符后继以圆括号“（”等。显然，图1-1（a）中的语法图描述了C语言函数定义的结构框架，图1-1（b）中的语法图描述了简单表达式的构成，而图1-1（c）中的语法图描述了四类因式，即无正负号常量、变量、用圆括号括住的表达式以及函数引用（调用）。
语法图的优点是形象直观；不足是不紧凑、篇幅较大，尤其因为是非形式的，不利于语法分析程序的自动生成。
（2） BNF表示法
BNF表示法是语法规则的形式表示系统，其中规则取如下形式，例如：
（函数定义）：：=（函数首部）（函数体）
它读作：（函数定义）定义为（函数首部）后跟以（函数体）。至于（函数首部）则定义为：
（函数首部）：：=（函数类型）（函数标识符）（（形参表列））
与
（函数首部）：：=（函数类型）（函数标识符）（ ）
或者缩写为：
（函数首部）：：=（函数类型）（函数标识符）（（形参表列））（函数类型）（函数标识符）（）
其中符号“”表示“或者”，读作：（函数首部）定义为（函数类型）（函数标识符）（（形参表列））或者定义为（函数类型）（函数标识符）（）。
对于（形参表列）定义为：
（形参表列）：：=（形参表列），（形参）
与
（形参表列）：：=（形参）
或者缩写为：
（形参表列）：：=（形参表列），（形参）|（形参）
BNF表示法是描述程序设计语言的形式体系，称为元语言。一般地，用来描述另外某种语言的语言称为元语言。符号“：：=”与“”称为元语言连接符或称元符号，这里用尖括号对“（”与“）”括住的是语法实体，它们不是语言中真正存在的实体，而是元语言中为了分析程序结构而引进的语法概念，称元语言变量，它们并不出现在程序中，如（函数定义）与（形参）等。今后将称之为非终结符号。它们每一个必出现在规则左部（符号“：：=”左边部分）至少一次。不出现在规则左部的符号是可能出现在程序中的符号，今后将称之为终结符号。
很明显，BNF表示法描述的C语言函数定义的结构与语法图描述的是完全一致的。
BNF表示法的特点是简洁、严谨、精确和无歧义。它首次应用于描述程序设计语言ALGOL。的语法，获得了极大的成功。由于它与今后将讨论的上下文无关文法规则定义形式一致而备受关注。
通常为了更简洁与更易读，对BNF表示法进行扩充。这时引入一些新的元符号，即花括号“{”与“}”、方括号“[”与“]”以及圆括号“（”与“）”，称为扩充的BNF表