编译原理

✍ Scribed by 张素琴

• Publisher: 清华大学出版社
• Year: 2011
• Tongue: Chinese
• Leaves: 649
• Series: 清华大学计算机系列教材
• Category: Library

✦ Synopsis

书签已装载，
书签制作方法请找 [email protected]
完全免费

由张素琴和吕映芝等编著的《编译原理》介绍编译系统的一般构造原理、基本实现技术和一些自动构造工具。主要由语言基础知识、词法分析、语法分析、中间代码生成、代码优化、目标代码生成、符号表的构造和运行时存储空间的组织等部分组成。 《编译原理》中在介绍编译程序构造基本原理的同时引入“PL/O语言的编译程序”结构及文本，还引入LEX、YACC使用方法与实例。 本书是高等院校计算机科学与技术专业的本科生教材，也可作为教师、研究生或软件工程技术人员的参考书。

✦ Table of Contents

封面
书名
版权
前言
目录
第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 寻找线性独立解