编译原理实用教程

本书注重编译原理的应用于实践，将远离具体化、目标化实践化，并且配备了大量的例题和习题，每一章的原理都有相应的算法的实现。在附录中编写了多个实验题目，以供学生实验和进行课程设计使用，有的试验提供了源代码。

这是一本很实用的编译原理教材，内容全面，实践性强，降低了学习难度，强化了理解的深度，可以作为应用性本科、高职高专院校计算机及相关专业的编译原理教材，也可作为计算机相关专业的教师及工程技术人员的参考书。

编译原理是高等院校计算机专业的必修专业课之一，是一门理论和实践相结合的课程。编译原理是介绍程序设计语言翻译的原理、技术和实现的一门课，通过对它的学习，可以训练学生的思维，提高学生实践能力。

本书共有11章。

第1章介绍编译程序的功能、结构、工作过程等方面的基础知识。

第2章介绍程序设计语言理论和文法。主要包括文法、语法树以及二义性文法等内容。词法分析的主要理论基础是有穷自动机。

第3章介绍词法分析的基本过程，主要讨论了自动机和正规文法、正规式之间的相互转换。在此理论的基础上完成了词法分析程序的C语言实现。

第4章主要介绍LL(1)文法和递归下降子程序法及编译器的设计。

第5章主要介绍自底向上的分析方法和算符优先分析方法及编译器的设计。

第6章是LR分析方法，在该方法中主要介绍各种分析表的构造原理。

第7章是语法制导翻译，主要介绍高级语言的各种语句的语义分析和中间代码的生成。

第8章介绍代码优化的方法。

第9章讲解目标程序运行时存储空间的组织与管理。

第10章讨论符号表的组织和存取的各种方法。

作为编译系统的后端设计，实现目标代码的生成程序是很重要的工作。

第11章在目标代码的实现方面做了一些介绍和尝试。

本书是作者在多年教学实践的基础上，参考了许多国内外的教材，结合学生的实际学习情况编写的一本实用性的教材。本教材简化了概念和理论，注重实践和理论的结合。在基本原理的讲述过程中，穿插了许多和实际相结合的实例，并试图以实例的形式探讨编译程序构造的全过程，使学生能够掌握编译原理和实现技术，很方便地进行实验和课程设计。

本书既注重整个编译系统设计原理和概念的完整性，又在各个知识点上强调具体性，对于应用型本科的教学是一本得心应手的教材。本书中主要是用C语言编程来实现词法分析、语法分析、语义分析和代码生成的。

本书是面向教学，针对学生的学习特点和教师的教学需要而编写的。既保证了编译系统理论体系的完整性，又充实了实践环节。课后备有丰富的习题。

本书参考学时为72学时，其中实践教学为12学时。使用者可以根据情况进行取舍。本书在编写过程中，参考了许多计算机专家的著作，在此表示感谢。

本书由杨德芳主编，刘永华、张建明、郑建军任副主编。另外，魏宪民、王丰、王红等同志在整理、校对、绘图等工作中也付出了大量的劳动，在此表示感谢。

编 者

2006年4月

序
前言
第1章 编译程序概论 1
本章学习目标 1
1.1 程序设计语言 1
1.2 编译程序的编译过程和结构 2
1.3 编译程序的设计技术 5
1.4 形式语言理论和编译实现技术 7
小结 7
习题一 8
第2章 形式语言概述 10
本章学习目标 10
2.1 字母表和符号串 10
2.1.1 字母表 10
2.1.2 符号串 10
2.1.3 符号串集合 12
2.2 文法的定义及其分类 12
2.2.1 文法的直观概念 12
2.2.2 文法的形式定义 13
2.2.3 文法的分类 14
2.2.4 文法举例 15
2.2.5 各类文法与自动机的关系 16
2.2.6 文法分类的意义 17
2.3 文法产生的语言和句型的语法树 18
2.3.1 推导和规范推导 18
2.3.2 句型、句子和语言 19
2.3.3 语法树 20
2.3.4 二义性文法及其他 21
2.3.5 文法产生的语言和产生语言的文法 23
2.4 句型分析与句柄 24
2.4.1 自顶向下的分析方法 25
2.4.2 确定的自顶向下的分析方法 26
2.4.3 自底向上的分析方法 27
2.4.4 文法的存储 30
2.5 例题分析与解答 33
小结 35
习题二 36
第3章 词法分析 37
本章学习目标 37
3.1 词法分析程序与单词符号 37
3.1.1 词法分析 37
3.1.2 单词符号 38
3.1.3 一个简单的词法分析程序的设计 39
3.2 单词的描述工具 42
3.2.1 正规文法 42
3.2.2 正规式 42
3.2.3 正规文法和正规式的相互转换 43
3.3 有穷自动机 45
3.3.1 确定的有穷自动机 45
3.3.2 不确定的有穷自动机 46
3.3.3 不确定的有穷自动机到确定的有穷自动机之间的转换 47
3.4 正规式与有穷自动机的等价性 54
3.4.1 正规式到NFA的转换 54
3.4.2 NFA到正规式的转换 56
3.4.3 NFA和正规式表示的相互转换示例 57
3.5 正规文法和自动机的转换 61
3.5.1 从正规文法到自动机的转换 61
3.5.2 根据自动机写出正规文法 62
3.6 词法分析程序的自动生成 63
3.6.1 用LEX语言表达正规式 63
3.6.2 LEX程序的结构 64
3.7 词法分析程序的C语言实现 66
3.7.1 单词的内部定义 66
3.7.2 词法分析程序流程图 67
3.7.3 数据结构的设计 68
小结 68
习题三 68
第4章 自顶向下的语法分析技术 71
本章学习目标 71
4.1 确定的自顶向下分析方法 71
4.1.1 确定的自顶向下分析思想 71
4.1.2 LL(1)文法的定义 73
4.2 LL(1)文法 75
4.2.1 LL(1)文法的判别 75
4.2.2 将非LL(1)文法转变成LL(1)文法 78
4.3 确定的自顶向下分析技术 84
4.3.1 递归子程序法 84
4.3.2 预测分析法 88
小结 93
习题四 94
第5章 自底向上优先分析技术 97
本章学习目标 97
5.1 自底向上分析方法 97
5.1.1 自底向上分析的基本思想 97
5.1.2 移进—归约方法 98
5.2 简单优先分析技术 100
5.2.1 优先关系 100
5.2.2 简单优先分析法的定义及操作步骤 102
5.2.3 简单优先分析法的局限性 104
5.3 算符优先分析方法 105
5.3.1 算符优先文法 105
5.3.2 算符优先文法（OPG）优先关系表的构造 107
5.3.3 算符优先分析法的算法 112
5.3.4 实际应用中的算符优先函数及其构造 117
5.3.5 采用算符优先分析法的语法分析程序的实现 120
5.4 两种优先分析法的比较 123
小结 124
习题五 124
第6章 LR分析技术 127
本章学习目标 127
6.1 LR分析器的工作原理 127
6.2 LR(0)分析表的构造 130
6.2.1 采用活前缀的方法构造有限自动机 131
6.2.2 采用项目的方法构造有限自动机 133
6.2.3 采用文法的项目集规范族构造有限自动机 135
6.3 SLR(1)分析表的构造 143
6.3.1 问题的提出 144
6.3.2 解决LR(0)分析方法中冲突问题的方法 145
6.4 LR(1)分析 149
6.4.1 问题的提出 149
6.4.2 LR(1)分析的基本思想 151
6.5 LALR分析 154
6.5.1 同心集的合并 154
6.5.2 LALR分析表的构造步骤 155
6.6 二义性文法的应用 157
6.7 SLR(1)分析器的设计实现 161
6.7.1 LR语法分析程序的C语言实现 161
6.7.2 自动生成语法分析器 162
小结 166
习题六 167
第7章 语法制导翻译和中间代码生成 169
本章学习目标 169
7.1 概述 169
7.1.1 语义分析的概念 169
7.1.2 语法制导翻译 170
7.2 属性文法 172
7.2.1 文法的属性 172
7.2.2 属性文法 172
7.3 几种常见的中间代码形式 173
7.3.1 逆波兰式表示方法 173
7.3.2 逆波兰式表示方法的推广 174
7.3.3 四元式 175
7.3.4 三元式和树形表示 176
7.4 表达式及赋值语句的翻译 177
7.4.1 简单表达式及赋值语句的翻译 177
7.4.2 布尔表达式的翻译 179
7.4.3 在控制语句中布尔表达式的翻译 180
7.5 控制语句的翻译 184
7.5.1 控制语句的翻译 185
7.5.2 多分支控制语句case的翻译 190
7.5.3 for循环语句 192
7.6 数组元素的翻译 194
7.6.1 数组元素的地址计算及中间代码的生成 194
7.6.2 赋值语句中数组元素的翻译 195
7.6.3 数组元素翻译示例 196
7.7 高级语言中其他语句的翻译 198
7.7.1 结构体说明和引用的翻译 198
7.7.2 说明语句的翻译 199
7.7.3 转向语句的翻译 200
7.7.4 过程调用语句的翻译 201
小结 202
习题七 203
第8章 代码优化 204
本章学习目标 204
8.1 优化的概念 204
8.1.1 优化概述 204
8.1.2 优化技术简介 205
8.2 局部优化 208
8.2.1 基本块的划分方法 208
8.2.2 基本块的DAG表示 209
8.2.3 用DAG图进行优化得到优化后的四元式 212
8.3 循环优化 213
8.3.1 程序流图 213
8.3.2 循环的查找 215
8.3.3 循环优化 216
8.3.4 窥孔优化 219
小结 219
习题八 219
第9章 运行时存储空间的组织与管理 222
本章学习目标 222
9.1 存储分配策略 222
9.2 静态存储分配 222
9.3 栈式存储分配 223
9.3.1 简单的栈式存储分配 223
9.3.2 嵌套过程语言的栈式实现 226
9.3.3 分程序结构的存储管理 229
9.4 堆式动态存储分配 233
9.5 参数传递方式及其实现 233
9.5.1 参数传递的方法 233
9.5.2 参数传递的示例 234
小结 235
习题九 235
第10章 符号表和错误处理 237
本章学习目标 237
10.1 符号表的组织和内容 237
10.1.1 符号表的建立和访问 237
10.1.2 符号表的组织 238
10.1.3 符号表的内容 245
10.2 符号表的操作和错误处理 246
10.2.1 符号表的初始化 246
10.2.2 符号表的登录 247
10.2.3 符号的查找 247
10.2.4 符号表中关于分层结构的管理 247
10.3 错误处理 250
10.3.1 语法错误的校正 250
10.3.2 语义错误的校正 252
10.4 一个符号表的设计实例 252
小结 256
习题十 256
第11章 目标代码的生成 257
本章学习目标 257
11.1 中间代码生成目标代码 257
11.1.1 假想的计算机模型 257
11.1.2 从四元式生成代码 258
11.1.3 从三元式生成代码 259
11.1.4 从树形表示到生成代码 262
11.1.5 从逆波兰表示生成代码 264
11.1.6 寄存器的分配 264
11.2 常用的代码生成程序的开发方法 265
11.2.1 解释性的代码生成法 265
11.2.2 模式匹配代码生成法 266
11.2.3 表驱动代码生成法 266
11.3 代码生成程序的自动化构造 266
11.3.1 基于语法制导翻译的代码生成程序自动构造技术 266
11.3.2 基于语义制导的代码生成程序自动构造技术 269
11.3.3 模式匹配和动态规划 269
11.4 目标代码生成器设计实例 270
11.4.1 待用信息与活跃信息 271
11.4.2 代码生成算法 272
11.4.3 目标代码生成的具体实例 274
小结 279
习题十一 279
附录A 编译原理实践部分 280
参考文献 315