编译原理 [平装] 7115217319,978711521

《编译原理》主要介绍编译系统的一般构造原理和基本实现技术。内容包括语言基础知识、词法分析、语法分析、中间代码生成、代码优化、目标代码生成、符号表的构造和运行时存储空间的组织等，同时将“PL/0语言编译程序”的设计作为实例贯穿于相关章节中。最后还通过一系列程序实例介绍了工业界广泛使用的开源工具GCC和Binutils。 《编译原理》： 没有深奥理论，但求论述严谨 没有面面俱到，但求自成体系 立足原理学习，兼顾实际应用 编译程序在计算机科学技术的发展历史中发挥了巨大作用，是计算机系统的核心支撑软件。编译原理一直是国内外大学计算机相关专业的核心课程，其知识结构融贯整个计算机系统，其理论基础是联系计算机科学和计算机系统的典范。《编译原理》介绍编译程序构造的一般原理和基本技术，注重知识体系的基础性和连贯性，内容由语言基础知识、词法分析、语法分析、语法制导的语义处理基础、语义分析和中间代码生成、符号表组织、运行时存储组织、代码优化和目标代码生成等部分组成。同时将“PL／O语言编译程序”的设计作为实例贯穿于相关章节中。 最后通过一系列程序实例介绍了工业界广泛使用的开源工具GCC和Binutils。《编译原理》可作为计算机相关专业本科阶段的教材，也可用于自学或教学参考。《编译原理》的作者长期从事与编译理论和技术相关的课程教学，具有较丰富的教学经验，著有多部编译课程教材，并在程序设计语言理论和系统的研究领域取得许多有影响的成果，发表了较高水平的论文。 第1章 编译程序概论 1 1.1 什么是编译程序 1 1.2 编译过程和编译程序的结构 3 1.2.1 词法分析 3 1.2.2 语法分析 4 1.2.3 语义分析 5 1.2.4 中间代码生成 6 1.2.5 代码优化 6 1.2.6 目标代码生成 6 1.2.7 符号表管理和出错处理 7 1.2.8 编译阶段的组合和编译结构 9 1.3 实例：PL/0编译程序 10 1.3.1 PL/0语言简介 10 1.3.2 PL/0语言处理系统 11 习题 13 第2章 语言和文法 14 2.1 语言的基本概念 14 2.1.1 字母表和字 14 2.1.2 关于字的运算和字母表上的运算 14 2.1.3 语言 15 2.1.4 关于语言的运算 15 2.2 上下文无关文法 16 2.2.1 上下文无关文法的基本概念 16 2.2.2 归约与推导 17 2.2.3 上下文无关语言 18 2.2.4 句型、句子与分析树 20 2.2.5 归约、推导与分析树之间关系 20 2.2.6 文法的二义性 21 2.3 PL/0语言的语法 25 2.3.1 PL/0语言语法的上下文无关文法描述 25 2.3.2 PL/0语言语法的EBNF描述 26 习题 28 第3章 词法分析程序及其自动构造 31 3.1 词法分析概述 31 3.1.1 词法分析的任务 31 3.1.2 词法分析在编译程序中的组织 32 3.1.3 词法分析程序中如何识别单词 33 3.2 实例：PL/0编译程序中词法分析程序的设计和实现 33 3.3 词法分析程序自动构造原理 37 3.3.1 正规表达式与正规语言 37 3.3.2 有限自动机 40 3.3.3 词法分析程序构造的自动化 52 3.4 LEX：一个词法分析程序的生成工具 52 3.4.1 LEX描述文件中使用的正规表达式 53 3.4.2 LEX描述文件的格式 54 3.4.3 LEX的使用 56 3.4.4 与YACC的接口约定 56 3.4.5 用LEX构造PL/0词法分析程序 57 习题 57 第4章 自顶向下语法分析 60 4.1 自顶向下分析思想 60 4.2 LL(1)分析方法 63 4.2.1 First集合和Follow集合 63 4.2.2 LL(1)文法 66 4.2.3 LL(1)分析的实现 66 4.2.4 一些有用的文法变换 72 4.3 实例：PL/0编译程序中语法分析程序的设计和实现 76 4.3.1 PL/0语法分析程序的自顶向下预测分析思想 76 4.3.2 PL/0递归下降语法分析程序的设计 78 4.3.3 PL/0编译程序中的错误处理 80 习题 82 第5章 自底向上语法分析 85 5.1 自底向上分析思想 85 5.1.1 短语和直接短语 86 5.1.2 句柄 87 5.1.3 移进-归约分析 89 5.2 LR分析方法 92 5.2.1 LR分析基础 92 5.2.2 LR(0)分析 95 5.2.3 SLR(1)分析 100 5.2.4 LR(1)分析 102 5.2.5 LALR(1)分析 107 5.2.6 某些非LR文法的强制LR分析 109 5.3 LR分析中的错误处理 111 5.4 几类分析文法之间的关系 113 习题 113 第6章 语法制导的语义分析和中间代码生成 118 6.1 语法制导的语义处理基础 118 6.1.1 属性文法以及基于属性文法的语义处理 118 6.1.2 翻译模式以及基于翻译模式的语义处理 127 6.2 语法制导的语义分析 133 6.2.1 语义分析的主要工作 134 6.2.2 类型检查 134 6.3 语法制导的中间代码生成 137 6.3.1 常见的中间表示形式 137 6.3.2 生成抽象语法树 138 6.3.3 生成三地址码 139 6.4 YACC：一个语法分析/语义处理程序的生成工具 147 6.4.1 YACC描述文件 147 6.4.2 使用YACC的一个简单例子 151 6.4.3 用LEX和YACC实现PL/0编译程序 152 习题 152 第7章 符号表 158 7.1 名字的属性和说明 158 7.2 符号表的组织 159 7.2.1 符号表的总体组织 159 7.2.2 关键字域的组织 160 7.2.3 符号表的基本实现技术 160 7.3 分程序结构的符号表 161 7.4 PL/0编译程序中符号表的设计与实现 164 7.4.1 PL/0符号表的设计 164 7.4.2 作用域与可见性 166 7.4.3 符号表的操作 168 习题 169 第8章 目标程序运行时的存储组织 171 8.1 数据空间的使用和管理方法 171 8.1.1 静态存储分配 172 8.1.2 动态存储分配 172 8.2 栈式存储分配的实现 173 8.2.1 动态地分配和释放一个过程的数据空间 174 8.2.2 对非局部变量的引用 175 8.2.3 分程序共享过程的活动记录 179 8.3 参数传递 180 8.3.1 形实参对应的方法 181 8.3.2 传值的实现 181 8.3.3 传地址的实现 182 8.4 PL/0程序运行时的存储组织 183 8.4.1 PL/0程序运行栈中的过程活动记录 183 8.4.2 实现过程调用和返回的类P-code指令 185 习题 186 第9章 代码优化和代码生成 189 9.1 基本块和流图 191 9.1.1 基本块 191 9.1.2 控制流图 192 9.1.3 循环的判定 193 9.1.4 跟踪基本块内部变量使用信息 194 9.1.5 跟踪基本块之间变量使用信息 196 9.2 中间代码优化 200 9.2.1 局部优化 200 9.2.2 循环优化 202 9.2.3 全局优化 205 9.3 目标代码的生成和优化 207 9.3.1 设计代码生成程序的基本考虑 207 9.3.2 一个简单的代码生成算法 209 9.3.3 目标代码优化 211 9.4 PL/0编译程序中的目标代码生成 212 习题 214 第10章 编译器和相关工具实例——GCC/Binutils 217 10.1 开源编译器GCC 217 10.1.1 GCC介绍 218 10.1.2 GCC总体结构 219 10.1.3 GCC编译流程 220 10.1.4 GCC代码组织 221 10.2 开源工具Binutils 222 10.2.1 目标文件 222 10.2.2 汇编器和链接器 223 10.2.3 其他工具 224 10.3 编译器和工具使用实例 224 10.3.1 编译特定版本的编译器 224 10.3.2 查看目标文件 227 10.3.3 程序代码优化 229 习题 232 附录A PL/0编译程序文本 233 附录A-1 PL/0编译程序文本(Pascal) 233 附录A-2 PL/0编译程序文本(C) 250 附录B 用于生成某个PL/0编译程序的LEX描述文件和YACC描述文件 279 附录B-1 LEX描述文件pl0.l 279 附录B-2 YACC描述文件pl0.y 280 附录B-3 头文件define.h 292 参考文献 293 编译程序是重要的计算机系统软件。编译程序的设计和实现涉及程序设计语言、计算机体系结构、语言理论、算法和软件工程等学科知识，正如著名的计算机科学家AlfredV.Aho和JeffreyD.ullman在他们的编译教材中说得那样：这些原理和技术在每一个计算机学者的工作生涯中，都会反复用到。 本书根据作者多年的教学经验，参照国内外较具影响的专著和教材编写，主要介绍经典的编译原理和技术，内容包括词法分析程序和语法分析程序的设计及自动构造理论、语法制导翻译基础、语义分析、中间代码生成、目标代码运行时的存储组织策略，代码优化和目标代码生成等。这些内容是计算机科学理论应用于计算机系统设计的典范，是计算机学科体系中不可缺少的部分。本书选择PL／O编译程序作为实例，以利于原理部分相应知识点的讲解。此外，考虑到近年来嵌入式系统的迅速发展、体系结构的推陈出新对编译技术的迫切需求，本书安排了有关开源的GCC编译器和相关工具Binutils的章节，为学生将来可能从事相关领域工作构筑基础。 插图： 图1.7所示的编译过程的阶段划分是一种典型的处理模式，事实上并非所有的编译程序都分成这样几个阶段，某些阶段可能组合在一起，这些阶段间的源程序的内部表示形式就没必要构造出来。比如有些编译程序并不要生成中间代码，而是在语法分析和语义分析后直接产生目标指令，有些编译程序没有优化阶段的工作等。 这里所讨论的编译过程中阶段的划分是编译程序的逻辑组织。有时，常常把编译的过程分为前端（front end）和后端（back end），前端由那样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常这些阶段包括词法分析、语法分析、语义分析和中间代码生成，某些优化工作也可能在前端做，还包括与前端每个阶段相关的出错处理工作和符号表管理工作。后端工作指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成、目标代码优化，以及相关出错处理和符号表操作。若按照这种组合方式设计编译程序，则某一编译程序的前端加上相应不同的后端则可以为不同的机器构成同一个源语言的编译程序。而不同语言编译的前端生成同一种中间语言，再使用一个共同的后端，则可为同一机器生成几个语言的编译程序。