编译原理简明教程（第3版）

本书讨论了编译原理的基础理论与实现技术，并在其前几版的基础上进行了修订与更新。本书共13章，内容包括编译概述、形式语言与自动机理论基础、词法分析、语法分析、语义分析及中间代码生成、代码优化、目标代码的生成、符号表和出错处理、面向对象语言的编译、并行编译技术、软件构造等。在内容的组织上，本书将编译的基本理论和具体的实现技术有机地结合起来，清楚地阐述相关的概念和原理，并给出部分C语言实现程序；同时，对编译程序自动生成工具的功能和使用方法做了详细的介绍。本书提供免费电子课件。

目 录 第1章 概述 1 1.1 程序设计语言与翻译 1 1.1.1 程序设计语言 1 1.1.2 编译程序和解释程序 2 1.2 编译过程概述 3 1.2.1 编译程序的工作过程 3 1.2.2 编译程序的结构 7 1.3 编译程序的开发 7 1.3.1 编译程序的开发步骤 8 1.3.2 编译程序的开发技术 8 1.3.3 编译程序的自动生成 10 1.4 本章小结 10 习题1 11 第2章 形式语言理论基础 12 2.1 形式语言的基本概念 12 2.1.1 符号和符号串 12 2.1.2 符号串的运算 13 2.1.3 符号串集合的运算 15 2.2 文法和语言的形式定义 16 2.2.1 文法的形式定义 16 2.2.2 形式语言的定义 19 2.3 语法树和二义性 22 2.3.1 语法树和推导 22 2.3.2 文法的二义性 25 2.4 文法的限制 28 2.4.1 文法的实用限制 28 2.4.2 文法的等价变换 31 2.4.3 扩充的BNF表示法 33 2.5 文法和语言的Chomsky分类 34 2.5.1 0型文法与0型语言(对应图灵机) 34 2.5.2 1型文法与1型语言(对应线性界限自动机) 35 2.5.3 2型文法与2型语言(对应下推自动机) 35 2.5.4 3型文法与3型语言(对应有限自动机) 36 2.5.5 四类文法的关系和区别 37 2.6 本章小结 38 习题2 38 第3章 自动机理论基础 40 3.1 有限自动机的基本概念 40 3.1.1 有限自动机的定义及表示法 40 3.1.2 有限自动机的机器模型 43 3.1.3 确定有限自动机(DFA) 43 3.1.4 有限自动机在计算机内的表示 44 3.1.5 不确定有限自动机(NFA) 45 3.1.6 由NFA到DFA的等价转换 47 3.2 确定有限自动机DFA的化简 50 3.2.1 等价状态和无关状态 50 3.2.2 自动机的化简 51 3.3 正则表达式形式定义 53 3.4 下推自动机PDA 54 3.4.1 下推自动机的机器模型 54 3.4.2 PDA的形式定义 55 3.5 本章小结 57 习题3 57 第4章 词法分析 59 4.1 词法分析概述 59 4.1.1 词法分析的功能 59 4.1.2 词法分析的两种处理结构 59 4.1.3 单词符号的种类 60 4.1.4 词法分析程序的输出形式 60 4.2 词法分析程序 61 4.2.1 词法分析程序的设计与实现 61 4.2.2 单词的识别 61 4.2.3 无符号数的识别 65 4.2.4 标识符的识别 66 4.3 词法分析程序的自动生成 68 4.3.1 基本思想 68 4.3.2 Lex源程序结构 69 4.3.3 Lex编译程序工作过程 71 4.3.4 Lex的实现 71 4.3.5 Lex的使用方式 72 4.4 本章小结 72 习题4 73 第5章 语法分析――自顶向下分析方法 74 5.1 自顶向下语法分析技术 74 5.1.1 自顶向下语法分析思想 75 5.1.2 三种终结符号集 76 5.1.3 自顶向下语法分析难点 78 5.1.4 确定的自顶向下语法分析思想 80 5.2 LL(K)语法分析方法 80 5.2.1 LL(1)语法分析思想 80 5.2.2 LL(1)语法分析方法的逻辑结构 81 5.2.3 LL(1)语法分析方法 81 5.3 递归下降语法分析方法 88 5.3.1 递归下降语法分析方法的实现思想 88 5.3.2 递归子程序及其性质 89 5.3.3 递归下降语法分析方法处理示例 90 5.4 本章小结 95 习题5 95 第6章 语法分析――自底向上分析方法 97 6.1 自底向上语法分析技术 97 6.1.1 自底向上语法分析思想 97 6.1.2 自底向上分析难点 99 6.2 自底向上优先分析方法 99 6.2.1 简单优先分析方法 100 6.2.2 算符优先分析方法 102 6.3 LR(K)分析方法 112 6.3.1 LR分析思想及逻辑结构 113 6.3.2 LR(0)分析方法 116 6.3.3 SLR(1)分析方法 124 6.3.4 LR(1)分析方法 127 6.3.5 LALR(1)分析方法 131 6.4 本章小结 136 习题6 136 第7章 语义分析及中间代码生成 138 7.1 语义分析概述 138 7.1.1 语义分析的概念 138 7.1.2 属性文法技术 140 7.2 中间语言代码 142 7.2.1 抽象语法树 142 7.2.2 逆波兰表示 144 7.2.3 四元式 147 7.2.4 三元式 150 7.3 语法制导翻译 154 7.3.1 表达式的翻译 154 7.3.2 说明语句的翻译 158 7.3.3 赋值语句的翻译 161 7.3.4 控制语句的翻译 161 7.4 本章小结 164 习题7 165 第8章 代码优化 167 8.1 代码优化概述 167 8.1.1 代码优化的定义 167 8.1.2 代码优化的分类 167 8.1.3 优化技术简介 168 8.2 局部优化 171 8.2.1 基本块的划分 171 8.2.2 基本块的DAG表示 173 8.2.3 基本块优化的实现 176 8.3 循环优化 177 8.3.1 循环的查找 177 8.3.2 循环优化的实现 178 8.4 本章小结 182 习题8 182 第9章 目标代码的生成 184 9.1 目标代码生成概述 184 9.1.1 目标代码 185 9.1.2 寄存器分配 185 9.2 一个计算机模型――虚拟机 186 9.2.1 虚拟机 186 9.2.2 虚拟机的汇编指令 187 9.3 从中间代码生成目标代码 189 9.3.1 从逆波兰表示生成目标代码 189 9.3.2 从四元式序列生成目标代码 192 9.4 目标程序运行时的存储管理 192 9.4.1 程序运行时的存储组织 193 9.4.2 静态存储分配 194 9.4.3 栈式动态存储分配 195 9.4.4 堆式动态存储分配 198 9.5 本章小结 200 习题9 201 第10章 符号表和出错处理 202 10.1 符号表的结构与存放 202 10.1.1 符号表的组织与内容 202 10.1.2 线性符号表 204 10.1.3 有序符号表 204 10.1.4 散列符号表 205 10.1.5 栈式符号表 206 10.2 符号表的管理 208 10.2.1 符号表的建立 208 10.2.2 符号表的查填 209 10.3 程序的错误 210 10.3.1 错误存在的必然性 210 10.3.2 错误的种类 211 10.3.3 错误复原 212 10.4 出错处理 213 10.4.1 词法错误的处理 213 10.4.2 语法错误的处理 214 10.4.3 语义错误的处理 216 10.5 本章小结 218 习题10 218 第11章 面向对象语言的编译 220 11.1 概述 220 11.1.1 面向对象语言的基本特征 220 11.1.2 类和成员的属性构造 222 11.1.3 面向对象编译程序的特点 225 11.2 面向对象语言的语法结构 226 11.2.1 单一继承 226 11.2.2 多重继承 228 11.2.3 多态性 229 11.2.4 动态绑定 230 11.2.5 接口类型 230 11.3 面向对象的动态存储分配 231 11.3.1 对象的存储区管理方式 231 11.3.2 静态模型和栈式模型废弃单元的回收 231 11.3.3 堆式模型废弃单元的回收 232 11.4 本章小结 234 习题11 234 第12章 并行编译技术 235 12.1 并行计算机及其编译系统简介 235 12.1.1 并行计算相关技术简介 236 12.1.2 并行编译系统的分类及结构 239 12.2 并行程序设计模型 242 12.2.1 并行体系结构分类及并行程序设计 242 12.2.2 并行程序设计模型 244 12.3 并行编译系统的构造 245 12.3.1 并行编译系统的构造简介 245 12.3.2 程序分析 247 12.3.3 程序优化 251 12.3.4 并行代码生成 252 12.4 自动并行化技术研究现状 255 12.4.1 比较典型的自动并行化系统简介 256 12.4.2 自动并行化编译系统发展简介 257 12.5 本章小结 259 习题12 260 第13章 软件构造 261 13.1 软件构造技术 261 13.1.1 API的设计和构造 261 13.1.2 基于状态和表驱动的构造技术 263 13.1.3 基于复用的构造技术 265 13.2 模块化软件构造 269 13.2.1 模块化设计理论 269 13.2.2 数据结构与算法 271 13.2.3 软件测试与软件调试 273 13.3 面向对象的软件构造技术 276 13.3.1 抽象与封装 277 13.3.2 面向对象的设计 278 13.3.3 测试与调试的基本技术 284 13.4 本章小结 286 习题13 286 附录A 编译程序自动生成工具 287 思考题 306 参考文献 307