计算机科学丛书:编译原理(第2版)

书签已装载, 书签制作方法请找 yjyouaremysunshine@163.com 完全免费 由张素琴和吕映芝等编著的《编译原理》介绍编译系统的一般构造原理、基本实现技术和一些自动构造工具。主要由语言基础知识、词法分析、语法分析、中间代码生成、代码优化、目标代码生成、符号表的构造和运行时存储空间的组织等部分组成。 《编译原理》中在介绍编译程序构造基本原理的同时引入“PL/O语言的编译程序”结构及文本,还引入LEX、YACC使用方法与实例。 本书是高等院校计算机科学与技术专业的本科生教材,也可作为教师、研究生或软件工程技术人员的参考书。 封面 书名 版权 前言 目录 第1章 引论 1.1语言处理器 1.2一个编译器的结构 1.2.1词法分析 1.2.2语法分析 1.2.3语义分析 1.2.4中间代码生成 1.2.5代码优化 1.2.6代码生成 1.2.7符号表管理 1.2.8将多个步骤组合成趟 1.2.9编译器构造工具 1.3程序设计语言的发展历程 1.3.1走向高级程序设计语言 1.3.2对编译器的影响 1.3.3 1.3节的练习 1.4构建一个编译器的相关科学 1.4.1编译器设计和实现中的建模 1.4.2代码优化的科学 1.5编译技术的应用 1.5.1高级程序设计语言的实现 1.5.2针对计算机体系结构的优化 1.5.3新计算机体系结构的设计 1.5.4程序翻译 1.5.5软件生产率工具 1.6程序设计语言基础 1.6.1静态和动态的区别 1.6.2环境与状态 1.6.3静态作用域和块结构 1.6.4显式访问控制 1.6.5动态作用域 1.6.6参数传递机制 1.6.7别名 1.6.8 1.6节的练习 1.7第1章总结 1.8第1章参考文献 第2章 一个简单的语法制导翻译器 2.1引言 2.2语法定义 2.2.1文法定义 2.2.2推导 2.2.3语法分析树 2.2.4二义性 2.2.5运算符的结合性 2.2.6运算符的优先级 2.2.7 2.2节的练习 2.3语法制导翻译 2.3.1后缀表示 2.3.2综合属性 2.3.3简单语法制导定义 2.3.4树的遍历 2.3.5翻译方案 2.3.6 2.3节的练习 2.4语法分析 2.4.1自顶向下分析方法 2.4.2预测分析法 2.4.3何时使用?产生式 2.4.4设计一个预测分析器 2.4.5左递归 2.4.6 2.4节的练习 2.5简单表达式的翻译器 2.5.1抽象语法和具体语法 2.5.2调整翻译方案 2.5.3非终结符号的过程 2.5.4翻译器的简化 2.5.5完整的程序 2.6词法分析 2.6.1剔除空白和注释 2.6.2预读 2.6.3常量 2.6.4识别关键字和标识符 2.6.5词法分析器 2.6.6 2.6节的练习 2.7符号表 2.7.1为每个作用域设置一个符号表 2.7.2符号表的使用 2.8生成中间代码 2.8.1两种中间表示形式 2.8.2语法树的构造 2.8.3静态检查 2.8.4三地址码 2.8.52.8节的练习 2.9第2章总结 第3章 词法分析 3.1词法分析器的作用 3.1.1词法分析及语法分析 3.1.2词法单元、模式和词素 3.1.3词法单元的属性 3.1.4词法错误 3.1.5 3.1节的练习 3.2输入缓冲 3.2.1缓冲区对 3.2.2哨兵标记 3.3词法单元的规约 3.3.1串和语言 3.3.2语言上的运算 3.3.3正则表达式 3.3.4正则定义 3.3.5正则表达式的扩展 3.3.6 3.3节的练习 3.4词法单元的识别 3.4.1状态转换图 3.4.2保留字和标识符的识别 3.4.3完成我们的例子 3.4.4基于状态转换图的词法分析器的体系结构 3.4.5 3.4节的练习 3.5词法分析器生成工具Lex 3.5.1Lex的使用 3.5.2Lex程序的结构 3.5.3Lex中的冲突解决 3.5.4向前看运算符 3.5.5 3.5节的练习 3.6有穷自动机 3.6.1不确定的有穷自动机 3.6.2转换表 3.6.3自动机中输入字符串的接受 3.6.4确定的有穷自动机 3.6.5 3.6节的练习 3.7从正则表达式到自动机 3.7.1从NFA到DFA的转换 3.7.2NFA的模拟 3.7.3NFA模拟的效率 3.7.4从正则表达式构造NFA 3.7.5字符串处理算法的效率 3.7.6 3.7节的练习 3.8词法分析器生成工具的设计 3.8.1生成的词法分析器的结构 3.8.2基于NFA的模式匹配 3.8.3词法分析器使用的DFA 3.8.4实现向前看运算符 3.8.5 3.8节的练习 3.9基于DFA的模式匹配器的优化 3.9.1NFA的重要状态 3.9.2根据抽象语法树计算得到的函数 3.9.3计算nullable、firstpos及lastpos 3.9.4计算followpos 3.9.5根据正则表达式构建DFA 3.9.6最小化一个DFA的状态数 3.9.7词法分析器的状态最小化 3.9.8DFA模拟中的时间和空间权衡 3.9.9 3.9节的练习 3.10第3章总结 3.11第3章参考文献 第4章 语法分析 4.1引论 4.1.1语法分析器的作用 4.1.2代表性的文法 4.1.3语法错误的处理 4.1.4错误恢复策略 4.2上下文无关文法 4.2.1上下文无关文法的正式定义 4.2.2符号表示的约定 4.2.3推导 4.2.4语法分析树和推导 4.2.5二义性 4.2.6验证文法生成的语言 4.2.7上下文无关文法和正则表达式 4.2.8 4.2节的练习 4.3设计文法 4.3.1词法分析和语法分析 4.3.2消除二义性 4.3.3左递归的消除 4.3.4提取左公因子 4.3.5非上下文无关语言的构造 4.3.6 4.3节的练习 4.4自顶向下的语法分析 4.4.1递归下降的语法分析 4.4.2FIRST和FOLLOW 4.4.3LL(1)文法 4.4.4非递归的预测分析 4.4.5预测分析中的错误恢复 4.4.6 4.4节的练习 4.5自底向上的语法分析 4.5.1归约 4.5.2句柄剪枝 4.5.3移入-归约语法分析技术 4.5.4移入-归约语法分析中的冲突 4.5.5 4.5节的练习 4.6LR语法分析技术介绍:简单LR技术 4.6.1为什么使用LR语法分析器 4.6.2项和LR(0)自动机 4.6.3LR语法分析算法 4.6.4构造SLR语法分析表 4.6.5可行前缀 4.6.6 4.6节的练习 4.7更强大的LR语法分析器 4.7.1规范LR(1)项 4.7.2构造LR(1)项集 4.7.3规范LR(1)语法分析表 4.7.4构造LALR语法分析表 4.7.5高效构造LALR语法分析表的方法 4.7.6LR语法分析表的压缩 4.7.7 4.7节的练习 4.8使用二义性文法 4.8.1用优先级和结合性解决冲突 4.8.2“悬空-else”的二义性 4.8.3LR语法分析中的错误恢复 4.8.4 4.8节的练习 4.9语法分析器生成工具 4.9.1语法分析器生成工具Yacc 4.9.2使用带有二义性文法的Yacc规约 4.9.3用Lex创建Yacc的词法分析器 4.9.4Yacc中的错误恢复 4.9.5 4.9节的练习 4.10第4章总结 4.11第4章参考文献 第5章 语法制导的翻译 5.1语法制导定义 5.1.1继承属性和综合属性 5.1.2在语法分析树的结点上对SDD求值 5.1.3 5.1节的练习 5.2SDD的求值顺序 5.2.1依赖图 5.2.2属性求值的顺序 5.2.3S属性的定义 5.2.4L属性的定义 5.2.5具有受控副作用的语义规则 5.2.6 5.2节的练习 5.3语法制导翻译的应用 5.3.1抽象语法树的构造 5.3.2类型的结构 5.3.3 5.3节的练习 5.4语法制导的翻译方案 5.4.1后缀翻译方案 5.4.2后缀SDT的语法分析栈实现 5.4.3产生式内部带有语义动作的SDT 5.4.4从SDT中消除左递归 5.4.5L属性定义的SDT 5.4.6 5.4节的练习 5.5实现L属性的SDD 5.5.1在递归下降语法分析过程中进行翻译 5.5.2边扫描边生成代码 5.5.3L属性的SDD和LL语法分析 5.5.4L属性的SDD的自底向上语法分析 5.5.5 5.5节的练习 5.6第5章总结 5.7第5章参考文献 第6章 中间代码生成 6.1语法树的变体 6.1.1表达式的有向无环图 6.1.2构造DAG的值编码方法 6.1.3 6.1节的练习 6.2三地址代码 6.2.1地址和指令 6.2.2四元式表示 6.2.3三元式表示 6.2.4静态单赋值形式 6.2.5 6.2节的练习 6.3类型和声明 6.3.1类型表达式 6.3.2类型等价 6.3.3声明 6.3.4局部变量名的存储布局 6.3.5声明的序列 6.3.6记录和类中的字段 6.3.7 6.3节的练习 6.4表达式的翻译 6.4.1表达式中的运算 6.4.2增量翻译 6.4.3数组元素的寻址 6.4.4数组引用的翻译 6.4.5 6.4节的练习 6.5类型检查 6.5.1类型检查规则 6.5.2类型转换 6.5.3函数和运算符的重载 6.5.4类型推导和多态函数 6.5.5一个合一算法 6.5.6 6.5节的练习 6.6控制流 6.6.1布尔表达式 6.6.2短路代码 6.6.3控制流语句 6.6.4布尔表达式的控制流翻译 6.6.5避免生成冗余的goto指令 6.6.6布尔值和跳转代码 6.6.7 6.6节的练习 6.7回填 6.7.1使用回填技术的一趟式目标代码生成 6.7.2布尔表达式的回填 6.7.3控制转移语句 6.7.4break语句、continue语句和goto语句 6.7.5 6.7节的练习 6.8switch语句 6.8.1switch语句的翻译 6.8.2switch语句的语法制导翻译 6.8.3 6.8节的练习 6.9过程的中间代码 6.10第6章总结 6.11第6章参考文献 第7章 运行时刻环境 7.1存储组织 7.2空间的栈式分配 7.2.1活动树 7.2.2活动记录 7.2.3调用代码序列 7.2.4栈中的变长数据 7.2.5 7.2节的练习 7.3栈中非局部数据的访问 7.3.1没有嵌套过程时的数据访问 7.3.2和嵌套过程相关的问题 7.3.3一个支持嵌套过程声明的语言 7.3.4嵌套深度 7.3.5访问链 7.3.6处理访问链 7.3.7过程型参数的访问链 7.3.8显示表 7.3.9 7.3节的练习 7.4堆管理 7.4.1存储管理器 7.4.2一台计算机的存储层次结构 7.4.3程序中的局部性 7.4.4碎片整理 7.4.5人工回收请求 7.4.6 7.4节的练习 7.5垃圾回收概述 7.5.1垃圾回收器的设计目标 7.5.2可达性 7.5.3引用计数垃圾回收器 7.5.4 7.5节的练习 7.6基于跟踪的回收的介绍 7.6.1基本的标记-清扫式回收器 7.6.2基本抽象 7.6.3标记-清扫式算法的优化 7.6.4标记并压缩的垃圾回收器 7.6.5拷贝回收器 7.6.6开销的比较 7.6.7 7.6节的练习 7.7短停顿垃圾回收 7.7.1增量式垃圾回收 7.7.2增量式可达性分析 7.7.3部分回收概述 7.7.4世代垃圾回收 7.7.5列车算法 7.7.6 7.7节的练习 7.8垃圾回收中的高级论题 7.8.1并行和并发垃圾回收 7.8.2部分对象重新定位 7.8.3类型不安全的语言的保守垃圾回收 7.8.4弱引用 7.8.5 7.8节的练习 7.9第7章总结 7.10第7章参考文献 第8章 代码生成 8.1代码生成器设计中的问题 8.1.1代码生成器的输入 8.1.2目标程序 8.1.3指令选择 8.1.4寄存器分配 8.1.5求值顺序 8.2目标语言 8.2.1一个简单的目标机模型 8.2.2程序和指令的代价 8.2.3 8.2节的练习 8.3目标代码中的地址 8.3.1静态分配 8.3.2栈分配 8.3.3名字的运行时刻地址 8.3.4 8.3节的练习 8.4基本块和流图 8.4.1基本块 8.4.2后续使用信息 8.4.3流图 8.4.4流图的表示方式 8.4.5循环 8.4.6 8.4节的练习 8.5基本块的优化 8.5.1基本块的DAG表示 8.5.2寻找局部公共子表达式 8.5.3消除死代码 8.5.4代数恒等式的使用 8.5.5数组引用的表示 8.5.6指针赋值和过程调用 8.5.7从DAG到基本块的重组 8.5.8 8.5节的练习 8.6一个简单的代码生成器 8.6.1寄存器和地址描述符 8.6.2代码生成算法 8.6.3函数getReg的设计 8.6.4 8.6节的练习 8.7窥孔优化 8.7.1消除冗余的加载和保存指令 8.7.2消除不可达代码 8.7.3控制流优化 8.7.4代数化简和强度消减 8.7.5使用机器特有的指令 8.7.6 8.7节的练习 8.8寄存器分配和指派 8.8.1全局寄存器分配 8.8.2使用计数 8.8.3外层循环的寄存器指派 8.8.4通过图着色方法进行寄存器分配 8.8.5 8.8节的练习 8.9通过树重写来选择指令 8.9.1树翻译方案 8.9.2通过覆盖一个输入树来生成代码 8.9.3通过扫描进行模式匹配 8.9.4用于语义检查的例程 8.9.5通用的树匹配方法 8.9.6 8.9节的练习 8.10表达式的优化代码的生成 8.10.1Ershov数 8.10.2从带标号的表达式树生成代码 8.10.3寄存器数量不足时的表达式求值 8.10.4 8.10节的练习 8.11使用动态规划的代码生成 8.11.1连续求值 8.11.2动态规划的算法 8.11.3 8.11节的练习 8.12第8章总结 8.13第8章参考文献 第9章 机器无关优化 9.1优化的主要来源 9.1.1冗余的原因 9.1.2一个贯穿本章的例子:快速排序 9.1.3保持语义不变的转换 9.1.4全局公共子表达式 9.1.5复制传播 9.1.6死代码消除 9.1.7代码移动 9.1.8归纳变量和强度消减 9.1.9 9.1节的练习 9.2数据流分析简介 9.2.1数据流抽象 9.2.2数据流分析模式 9.2.3基本块上的数据流模式 9.2.4到达定值 9.2.5活跃变量分析 9.2.6可用表达式 9.2.7小结 9.2.8 9.2节的练习 9.3数据流分析基础 9.3.1半格 9.3.2传递函数 9.3.3通用框架的迭代算法 9.3.4数据流解的含义 9.3.5 9.3节的练习 9.4常量传播 9.4.1常量传播框架的数据流值 9.4.2常量传播框架的交汇运算 9.4.3常量传播框架的传递函数 9.4.4常量传递框架的单调性 9.4.5常量传播框架的不可分配性 9.4.6对算法结果的解释 9.4.7 9.4节的练习 9.5部分冗余消除 9.5.1冗余的来源 9.5.2可能消除所有冗余吗 9.5.3懒惰代码移动问题 9.5.4表达式的预期执行 9.5.5懒惰代码移动算法 9.5.6 9.5节的练习 9.6流图中的循环 9.6.1支配结点 9.6.2深度优先排序 9.6.3深度优先生成树中的边 9.6.4回边和可归约性 9.6.5流图的深度 9.6.6自然循环 9.6.7迭代数据流算法的收敛速度 9.6.8 9.6节的练习 9.7基于区域的分析 9.7.1区域 9.7.2可归约流图的区域层次结构 9.7.3基于区域的分析技术概述 9.7.4有关传递函数的必要假设 9.7.5一个基于区域的分析算法 9.7.6处理不可归约流图 9.7.7 9.7节的练习 9.8符号分析 9.8.1参考变量的仿射表达式 9.8.2数据流问题的公式化 9.8.3基于区域的符号化分析 9.8.4 9.8节的练习 9.9第9章总结 9.10第9章参考文献 第10章 指令级并行性 10.1处理器体系结构 10.1.1指令流水线和分支延时 10.1.2流水线执行 10.1.3多指令发送 10.2代码调度约束 10.2.1数据依赖 10.2.2寻找内存访问之间的依赖关系 10.2.3寄存器使用和并行性之间的折衷 10.2.4寄存器分配阶段和代码调度阶段之间的顺序 10.2.5控制依赖 10.2.6对投机执行的支持 10.2.7一个基本的机器模型 10.2.8 10.2节的练习 10.3基本块调度 10.3.1数据依赖图 10.3.2基本块的列表调度方法 10.3.3带优先级的拓扑排序 10.3.4 10.3节的练习 10.4全局代码调度 10.4.1基本的代码移动 10.4.2向上的代码移动 10.4.3向下的代码移动 10.4.4更新数据依赖关系 10.4.5全局调度算法 10.4.6高级代码移动技术 10.4.7和动态调度器的交互 10.4.8 10.4节的练习 10.5软件流水线化 10.5.1引言 10.5.2循环的软件流水线化 10.5.3寄存器分配和代码生成 10.5.4Do-Across循环 10.5.5软件流水线化的目标和约束 10.5.6一个软件流水线化算法 10.5.7对无环数据依赖图进行调度 10.5.8对有环数据依赖图进行调度 10.5.9对流水线化算法的改进 10.5.10模数变量扩展 10.5.11条件语句 10.5.12软件流水线化的硬件支持 10.5.13 10.5节的练习 10.6第10章总结 10.7第10章参考文献 第11章 并行性和局部性优化 11.1基本概念 11.1.1多处理器 11.1.2应用中的并行性 11.1.3循环层次上的并行性 11.1.4数据局部性 11.1.5仿射变换理论概述 11.2矩阵乘法:一个深入的例子 11.2.1矩阵相乘算法 11.2.2优化 11.2.3高速缓存干扰 11.2.4 11.2节的练习 11.3迭代空间 11.3.1从循环嵌套结构中构建迭代空间 11.3.2循环嵌套结构的执行顺序 11.3.3不等式组的矩阵表示方法 11.3.4混合使用符号常量 11.3.5控制执行的顺序 11.3.6坐标轴的变换 11.3.7 11.3节的练习 11.4仿射的数组下标 11.4.1仿射访问 11.4.2实践中的仿射访问和非仿射访问 11.4.3 11.4节的练习 11.5数据复用 11.5.1数据复用的类型 11.5.2自复用 11.5.3自空间复用 11.5.4组复用 11.5.5 11.5节的练习 11.6数组数据依赖关系分析 11.6.1数组访问的数据依赖关系的定义 11.6.2整数线性规划 11.6.3GCD测试 11.6.4解决整数线性规划的启发式规则 11.6.5解决一般性的整数线性规划问题 11.6.6小结 11.6.7 11.6节的练习 11.7寻找无同步的并行性 11.7.1一个介绍性的例子 11.7.2仿射空间分划 11.7.3空间分划约束 11.7.4求解空间分划约束 11.7.5一个简单的代码生成算法 11.7.6消除空迭代 11.7.7从最内层循环中消除条件测试 11.7.8源代码转换 11.7.9 11.7节的练习 11.8并行循环之间的同步 11.8.1固定多个同步运算 11.8.2程序依赖图 11.8.3层次结构化的时间 11.8.4并行化算法 11.8.5 11.8节的练习 11.9流水线化技术 11.9.1什么是流水线化 11.9.2连续过松弛方法:一个例子 11.9.3完全可交换循环 11.9.4把完全可交换循环流水线化 11.9.5一般性的理论 11.9.6时间分划约束 11.9.7用Farkas引理求解时间分划约束 11.9.8代码转换 11.9.9具有最小同步量的并行性 11.9.10 11.9节的练习 11.10局部性优化 11.10.1计算结果数据的时间局部性 11.10.2数组收缩 11.10.3分划单元的交织 11.10.4合成 11.10.5 11.10节的练习 11.11仿射转换的其他用途 11.11.1分布式内存计算机 11.11.2多指令发送处理器 11.11.3向量和SIMD指令 11.11.4数据预取 11.12第11章总结 11.13第11章参考文献 第12章 过程间分析 12.1基本概念 12.1.1调用图 12.1.2上下文相关 12.1.3调用串 12.1.4基于克隆的上下文相关分析 12.1.5基于摘要的上下文相关分析 12.1.6 12.1节的练习 12.2为什么需要过程间分析 12.2.1虚方法调用 12.2.2指针别名分析 12.2.3并行化 12.2.4软件错误和漏洞的检测 12.2.5SQL注入 12.2.6缓冲区溢出 12.3数据流的一种逻辑表示方式 12.3.1Datalog简介 12.3.2Datalog规则 12.3.3内涵断言和外延断言 12.3.4Datalog程序的执行 12.3.5Datalog程序的增量计算 12.3.6有问题的Datalog规则 12.3.7 12.3节的练习 12.4一个简单的指针分析算法 12.4.1为什么指针分析有难度 12.4.2一个指针和引用的模型 12.4.3控制流无关性 12.4.4在Datalog中的表示方法 12.4.5使用类型信息 12.4.6 12.4节的练习 12.5上下文无关的过程间分析 12.5.1一个方法调用的效果 12.5.2在Datalog中发现调用图 12.5.3动态加载和反射 12.5.4 12.5节的练习 12.6上下文相关指针分析 12.6.1上下文和调用串 12.6.2在Datalog规则中加入上下文信息 12.6.3关于相关性的更多讨论 12.6.4 12.6节的练习 12.7使用BDD的Datalog的实现 12.7.1分决策图 12.7.2对BDD的转换 12.7.3用BDD表示关系 12.7.4用BDD操作实现关系运算 12.7.5在指针指向分析中使用BDD 12.7.6 12.7节的练习 12.8第12章总结 12.9第12章参考文献 附录A 一个完整的编译器前端 附录B 寻找线性独立解