编译原理简明教程 (2008 年度畅销榜NO.21540 )

本书全面地介绍了编译程序的基本结构，系统地阐述了编译原理的一般理论和常用的有效方法与技术。\r\n\r\n 全书共分12章，包括：形式语言与自动机理论、词法分析、语法分析、语义分析及中间代码的生成、代码优化、目标代码生成及错误校正等。在内容的组织上，本书将编译的基本理论和具体的实现技术有机地结合起来，既准确清楚地阐述了相关的概念和原理，又给出了典型的实现程序流程图。在分析方法中介绍了LL(K)方法、递归下降分析法、算符优先分析法和LR(K)方法等。\r\n\r\n 本书理论和实践并重，叙述严谨、简明，富有启发性，内容深入浅出，便于自学。各章之后附有习题，有关部分配有上机练习题。\r\n\r\n 本书可作为大学计算机专业本科生的教材，也可作为教师、研究生或计算机科技人员的参考书籍。\r\n
\r\n

第1章 引言 \r\n\r\n 1. 1 编译程序. 汇编程序. 解释程序 \r\n\r\n 1. 1. 1 什么是编译程序 \r\n\r\n 1. 1. 2 什么是汇编程序 \r\n\r\n 1. 1. 3 什么是解释程序 \r\n\r\n 1. 2　编译过程概述 \r\n\r\n 1. 3 编译程序的结构框图 \r\n\r\n 1. 4 编译程序的开发 \r\n\r\n 1. 4. 1 编译程序的开发步骤 \r\n\r\n 1. 4. 2 编译程序的开发技术 \r\n\r\n 1. 4. 3 编译程序的自动生成 \r\n\r\n 习题1 \r\n\r\n 第2章 形式语言理论基础 \r\n\r\n 2. 1 形式语言的基本概念 \r\n\r\n 2. 1. 1 符号和符号串 \r\n\r\n 2. 1. 2 符号串的运算 \r\n\r\n 2. 2 文法和语言的形式定义 \r\n\r\n 2. 3　语法树和二义性 \r\n\r\n 2. 3. 1 语法树和推导 \r\n\r\n 2. 3. 2　文法的二义性 \r\n\r\n 2. 4 文法的实用限制 \r\n\r\n 2. 4. 1 有害规则 \r\n\r\n 2. 4. 2　多余规则 \r\n\r\n 2. 4. 3 文法的实用限制 \r\n\r\n 2. 4. 4 文法的等价变换 \r\n\r\n 2. 4. 5 扩充的BNF表示法 \r\n\r\n 2. 5 文法和语言的Chomsky分类 \r\n\r\n 2. 5. 1 0型文法与0型语言(对应图灵机) \r\n\r\n 2. 5. 2 1型文法与1型语言(对应线性界限自动机, 自然语言) \r\n\r\n 2. 5. 3 2型文法与2型语言(对应下推自动机, 程序设计语言) \r\n\r\n 2. 5. 4 3型文法与3型语言(对应有限自动机) \r\n\r\n 2. 5. 5 四类文法的关系 \r\n\r\n 习题2 \r\n\r\n 第3章 自动机理论基础 \r\n\r\n 3. 1 有限自动机的基本概念 \r\n\r\n 3. 1. 1 有限自动机的定义及表示法 \r\n\r\n 3. 1. 2 有限自动机的机器模型 \r\n\r\n 3. 1. 3 确定有限自动机(DFA) \r\n\r\n 3. 1. 4 有限自动机在计算机内的表示 \r\n\r\n 3. 1. 5 不确定有限自动机(NFA) \r\n\r\n 3. 1. 6 由NFA到DFA的等价转换 \r\n\r\n 3. 2 确定有限自动机DFA的化简 \r\n\r\n 3. 2. 1 等价状态和无关状态 \r\n\r\n 3. 2. 2 自动机的化简 \r\n\r\n 3. 3 正则表达式形式定义 \r\n\r\n 3. 4 下推自动机PDA \r\n\r\n 3. 4, 1 下推自动机的机器模型 \r\n\r\n 3. 4. 2 PDA的形式定义 \r\n\r\n 习题3 \r\n\r\n 第4章 词法分析 \r\n\r\n 4. 1 词法分析概述 \r\n\r\n 4. 1. 1 词法分析的功能 \r\n\r\n 4. 1. 2 词法分析的两种处理结构 \r\n\r\n 4. 1. 3 单词符号的种类 \r\n\r\n 4. 1. 4 词法分析程序的输出形式 \r\n\r\n 4. 2 词法分析程序的设计与实现 \r\n\r\n 4. 2. 1 词法分析程序流程图 \r\n\r\n 4. 2. 2 读单词 \r\n\r\n 4. 2. 3 读无符号数 \r\n\r\n 4. 2. 4 读标识符 \r\n\r\n 4. 3 词法分析程序的自动生成 \r\n\r\n 4. 3. 1 基本思想 \r\n\r\n 4. 3. 2 LEX源程序结构 \r\n\r\n 4. 3. 3 LEX编译程序工作过程 \r\n\r\n 4. 3. 4 LEX的实现 \r\n\r\n 4. 3. 5 LEX的使用方式 \r\n\r\n 习题4 \r\n\r\n 第5章 语法分析——自顶向下分析方法 \r\n\r\n 5. 1 自顶向下分析技术 \r\n\r\n 5. 2 不确定的自顶向下分析思想 \r\n\r\n 5. 2. 1 三种终结符号集 \r\n\r\n 5. 2. 2 自顶向下分析过程中存在的问题及解决办法 \r\n\r\n 5. 3 确定的自顶向下分析思想 \r\n\r\n 5. 4 LL(K)分析方法 \r\n\r\n 5. 4. 1 LL(1)分析思想 \r\n\r\n 5. 4. 2 LL(1)分析方法的逻辑结构 \r\n\r\n 5. 4. 3 LL(1)分析方法 \r\n\r\n 5. 5 递归下降分析法 \r\n\r\n 5. 5. 1 递归下降分析法的实现思想 \r\n\r\n 5. 5. 2 递归于程序及其性质 \r\n\r\n 5. 5. 3 递归下降分析法 \r\n\r\n 习题5 \r\n\r\n 第6章 语法分析——自底向上分析方法 \r\n\r\n 6. 1 自底向上分析技术 \r\n\r\n 6. 1. 1 自底向上分析的基本思想 \r\n\r\n 6. 1. 2 自底向上分析难点 \r\n\r\n 6. 2 自底向上优先分析方法 \r\n\r\n 6. 2. 1 简单优先分析方法 \r\n\r\n 6. 2. 2 算符优先分析方法 \r\n\r\n 6. 3 LR(K)分析方法 \r\n\r\n 6. 3. 1 LR分析思想及逻辑结构 \r\n\r\n 6. 3. 2 LR(0)分析方法 \r\n\r\n 6. 3. 3 SLR(1)分析方法 \r\n\r\n 6. 3. 4 LR(1)分析方法 \r\n\r\n 6. 3. 5 LALR(1)分析方法 \r\n\r\n 习题6 \r\n\r\n 第7章 语义分析及中间代码的生成 \r\n\r\n 7. 1 基本概念 \r\n\r\n 7. 1. 1 语义分析的概念 \r\n\r\n 7. 1. 2 属性文法技术 \r\n\r\n 7. 2 几种常见的中间语言 \r\n\r\n 7. 2. 1 抽象语法树 \r\n\r\n 7. 2. 2 逆波兰表示 \r\n\r\n 7. 2. 3 四元式 \r\n\r\n 7. 2. 4 二元式 \r\n\r\n 7. 3 表达式的翻译 \r\n\r\n 7. 3. 1 算术表达式的翻译 \r\n\r\n 7. 3. 2 布尔表达式的翻译 \r\n\r\n 7. 4 语句的语法制导翻译 \r\n\r\n 7. 4. 1 说明语句的翻译 \r\n\r\n 7. 4. 2 赋值语句的翻译 \r\n\r\n 7. 4. 3 控制语句的翻译 \r\n\r\n 习题7 \r\n\r\n 第8章 符号表 \r\n\r\n 8. 1 符号表的组织与内容 \r\n\r\n 8. 2 符号表的结构与存放 \r\n\r\n 8. 2. 1 线性符号表 \r\n\r\n 8. 2. 2 有序符号表 \r\n\r\n 8. 2. 3 散列符号表 \r\n\r\n 8. 2. 4 栈式符号表 \r\n\r\n 8. 3 符号表的管理 \r\n\r\n 8. 3. 1 符号表的建立 \r\n\r\n 8. 3. 2 符号表的查填 \r\n\r\n 习题8 \r\n\r\n 第9章 目标程序运行时的存储组织与分配 \r\n\r\n 9. 1 程序运行时的存储组织 \r\n\r\n 9. 2 静态存储分配 \r\n\r\n 9. 3 栈式动态存储分配 \r\n\r\n 9. 3. 1 简单的栈式存储分配 \r\n\r\n 9. 3. 2 嵌套过程语言的栈式存储分配 \r\n\r\n 9. 4 堆式动态存储分配 \r\n\r\n 习题9 \r\n\r\n 第10章　代码优化 \r\n\r\n 10. 1 代码优化的基本概念 \r\n\r\n 10. 1. 1 代码优化的定义 \r\n\r\n 10. 1. 2 代码优化的分类 \r\n\r\n 10. 1. 3 优化技术简介 \r\n\r\n 10. 2 局部优化 \r\n\r\n 10. 2. 1 基本块的划分 \r\n\r\n 10. 2. 2 基本块的DAG表示 \r\n\r\n 10. 2. 3 基本块优化的实现 \r\n\r\n 10. 3 循环优化 \r\n\r\n 10. 3. 1 循环的查找 \r\n\r\n 10. 3. 2 循环优化的实现 \r\n\r\n 习题10 \r\n\r\n 第11章 目标代码的生成 \r\n\r\n 11. 1 目标代码生成程序中的有关问题 \r\n\r\n 11. 1. 1 目标代码生成程序的输入. 输出 \r\n\r\n 11. 1. 2 目标代码 \r\n\r\n 11. 1. 3 寄存器分配 \r\n\r\n 11. 1. 4 运行时的存储管理 \r\n\r\n 11. 2 一个计算机模型——虚拟机 \r\n\r\n 11. 2. 1 虚拟机 \r\n\r\n 11. 2. 2 虚拟机的汇编指令 \r\n\r\n 11. 3 从中间代码生成目标代码 \r\n\r\n 11. 3. 1 从逆波兰表示生成目标代码 \r\n\r\n 11. 3. 2 从四元式序列生成目标代码 \r\n\r\n 习题11 \r\n\r\n 第12章 错误校正 \r\n\r\n 12. 1 引言 \r\n\r\n 12. 1. 1 错误存在的必然性 \r\n\r\n 12. 1. 2 错误的种类 \r\n\r\n 12. 1. 3 错误复原 \r\n\r\n 12. 2 校正词法错误 \r\n\r\n 12. 2. 1 词法错误的种类 \r\n\r\n 12. 2. 2 词法错误的校正 \r\n\r\n 12. 3 校正语法错误 \r\n\r\n 12. 3. 1 语法错误的复原 \r\n\r\n 12. 3. 2 语法错误的校正 \r\n\r\n 12. 4 校正语义错误 \r\n\r\n 12. 4. 1 语义错误的种类 \r\n\r\n 12. 4. 2 语义错误检查措施 \r\n\r\n 习题12 \r\n\r\n 附录A PL/0编译程序 \r\n\r\n 附录B LEX词法分析自动生成程序 \r\n\r\n 附录C YACC语法分析自动生成程序 \r\n\r\n 参考文献 \r\n
\r\n

这套教材是面向21世纪计算机学科系列教材. 为什么要组织这套教材?根据什么编写这套教材?这些都是在这篇序言中要回答的问题.

计算机学科是一个飞速发展的学科, 尤其是近十年来, 计算机向高度集成化. 网络化和多媒体化发展的速度一日千里. 但是, 从另一个方面来看, 目前高等学校的计算机教育, 特别是教材建设, 远远落后于现实的需要. 现在的教材主要是根据《教学计划1993》的要求组织编写的. 这个教学计划, 在制定过程中主要参照了美国IEEE和ACM的《教学计划1991》.

10年来, 计算机学科已有了长足发展, 这就要求高等学校计算机教育必须跟上形势发展的需要, 在课程设置和教材建设上做出相应调整, 以适应面向21世纪计算机教育的要求. 这是组织这套教材的初衷.

为了组织好这套教材, 全国高等学校计算机教育研究会课程与教材建设委员会在天津召开了“全国高等学校计算机学科课程与教材建设研讨会”, 在北京召开了“教材编写大纲研讨会”. 在这两次会议上, 代表们深入地研讨了全国高校计算机专业教学指导委员会和中国计算机学会教育委员会制定的《计算机学科教学计划2000》以及美国IEEE和ACM的《计算机学科教学计划2001》, 这是这套教材参照的主要依据.

IEEE和ACM的《计算机学科教学计划2001》是在总结了从《计算机学科教学计划1991》到现在, 计算机学科十年来发展的主要成果的基础上诞生的. 它认为面向21世纪计算机学科应包括14个主科目, 其中12个主科目为核心主科, 它们是：算法与分析(AL). 体系结构(AR). 离散结构(DS). 计算科学(CN). 图形学. 可视化. 多媒体(GR). 网络计算(NC). 人机交互(HC). 信息管理(IM). 智能系统(IS). 操作系统(OS). 程序设计基础(PF). 程序设计语言(PL). 软件工程(SE). 社会. 道德. 法律和专业问题(SP). 其中除CN和GR为非核心主科目外, 其他12项均为核心主科目.

将2001教学计划与1991教学计划比较可看出：

(1)在1991年计划中, 离散结构只作为数学基础提出, 而在2001计划中, 则作为核心主科目提出, 显然, 提高了它在计算机学科中的地位.

(2)在1991计划中, 未提及网络计算, 而在2001计划中, 则作为核心主科目提出, 以适应网络技术飞速发展的需求.

(3)图形学. 可视化与多媒体也是为适应发展要求新增加的内容.

除此之外, 2001计划在下述5个方面做调整：

将程序设计语言引论调整为程序设计基础, 将人—机通信调整为人机交互, 将人工智能与机器入学调整为智能系统, 将数据库与信息检索调整为信息管理, 将数值与符号计算调整为计算科学.

显然, 这些变化使2001计划更具有科学性, 也更好地适应了学科发展的需要.

在组织这套教材的过程中, 充分考虑了这些变化和调整, 在软件和硬件的课程体系. 界面划分方面均做了相应的调整, 使整套教材更具有科学性和实用性.

另外, 还要说明一点, 教材建设既要满足必修课的要求, 又要满足限选课和任选课的要求.

本教材由全国高等学校计算机教育研究会课程与教材建设委员会选定并推荐出版.

“编译原理”是计算机科学和技术专业一门重要的专业课程, 在计算机专业的学科课程中占有非常重要的位置, 它是每个优秀的计算机专业人员必修的一门课程. 设置本课程的目的在于系统地向学生讲述编译程序设计的基本理论. 编译系统的结构及编译程序各部分的设计原理和实现技术. 通过对这些方面知识的学习, 能使学生既掌握编译理论和方法方面的基本知识, 又具有设计. 实现. 分析维护编译程序等方面的初步能力.

全书共分12章, 第1章对编译过程. 编译程序逻辑结构及编译程序各组成部分的主要功能进行了概括说明, 第2. 3章介绍了文法和形式语言. 自动机理论, 它为学习后续各章奠定了理论基础, 第4章讨论了词法分析程序的设计原理, 第5. 6章讲述了语法分析程序的设计技术, 其中主要介绍LL分析法. 递归下降分析法. 算符优先分析法及LR分析法, 第7-12章分别讨论了语义分析及中间代码的生成. 符号表. 目标程序运行时的存储组织与分配. 代码优化. 目标代码生成和源程序的错误校正等.

本书还包含3个附录：附录A列出了PI／O编译程序文本, 附录B和附录C是对编译程序构造工具LEC和YACC的介绍.

“编译原理”是一门理论性和实践性都比较强的课程, 在本书的编写过程中, 作者力图将其中的基本概念. 基本编译技术和实现方法的思路阐述清楚, 由浅入深, 循序渐进, 并对各种编译方法和技术适当配有相应的处理步骤或流程图. 此外, 各章都配有一定数量的习题, 有关部分还配有上机实习题, 学生通过完成这些练习可进一步加深对课堂教学内容的理解.

“编译原理”课程蕴涵着计算机学科中解决问题的思路和抽象问题的解决方法. 在这门课程中所接受的训练很难在其他地方获得. 可以这样说, 像“高等数学”课程影响每一个理工科学生一生的工作和学习一样, 学好“编译原理”课程会让计算机专业学生“享用一辈子”.

本书第1. 2. 3. 12章及附录B由范辉编写, 第4. 5. 7. 11及附录A由崔冬华编写, 第6. 8. 9. 10及附录C由冯秀芳编写. 在本书的编写过程中, 我们得到北京工业大学李大友教授. 太原理工大学余雪丽教授. 段富教授和烟台大学陈守孔教授的大力帮助和支持, 研究生李晋江. 郑丽伟和杨红等同学为本书的图表设计制作. 录入及校对做了大量的工作, 在此谨向他们表示诚挚的感谢.

由于编者水平有限, 书中难免还存在一些缺点和错误, 恳请广大读者批评指正.

编 者

2002年2月