编译原理

封面\n书名\n版权\n前言\n目录\n第1章  引论\n1.1语言处理器\n1.2一个编译器的结构\n1.2.1词法分析\n1.2.2语法分析\n1.2.3语义分析\n1.2.4中间代码生成\n1.2.5代码优化\n1.2.6代码生成\n1.2.7符号表管理\n1.2.8将多个步骤组合成趟\n1.2.9编译器构造工具\n1.3程序设计语言的发展历程\n1.3.1走向高级程序设计语言\n1.3.2对编译器的影响\n1.3.3  1.3节的练习\n1.4构建一个编译器的相关科学\n1.4.1编译器设计和实现中的建模\n1.4.2代码优化的科学\n1.5编译技术的应用\n1.5.1高级程序设计语言的实现\n1.5.2针对计算机体系结构的优化\n1.5.3新计算机体系结构的设计\n1.5.4程序翻译\n1.5.5软件生产率工具\n1.6程序设计语言基础\n1.6.1静态和动态的区别\n1.6.2环境与状态\n1.6.3静态作用域和块结构\n1.6.4显式访问控制\n1.6.5动态作用域\n1.6.6参数传递机制\n1.6.7别名\n1.6.8  1.6节的练习\n1.7第1章总结\n1.8第1章参考文献\n第2章  一个简单的语法制导翻译器\n2.1引言\n2.2语法定义\n2.2.1文法定义\n2.2.2推导\n2.2.3语法分析树\n2.2.4二义性\n2.2.5运算符的结合性\n2.2.6运算符的优先级\n2.2.7  2.2节的练习\n2.3语法制导翻译\n2.3.1后缀表示\n2.3.2综合属性\n2.3.3简单语法制导定义\n2.3.4树的遍历\n2.3.5翻译方案\n2.3.6  2.3节的练习\n2.4语法分析\n2.4.1自顶向下分析方法\n2.4.2预测分析法\n2.4.3何时使用?产生式\n2.4.4设计一个预测分析器\n2.4.5左递归\n2.4.6  2.4节的练习\n2.5简单表达式的翻译器\n2.5.1抽象语法和具体语法\n2.5.2调整翻译方案\n2.5.3非终结符号的过程\n2.5.4翻译器的简化\n2.5.5完整的程序\n2.6词法分析\n2.6.1剔除空白和注释\n2.6.2预读\n2.6.3常量\n2.6.4识别关键字和标识符\n2.6.5词法分析器\n2.6.6  2.6节的练习\n2.7符号表\n2.7.1为每个作用域设置一个符号表\n2.7.2符号表的使用\n2.8生成中间代码\n2.8.1两种中间表示形式\n2.8.2语法树的构造\n2.8.3静态检查\n2.8.4三地址码\n2.8.52.8节的练习\n2.9第2章总结\n第3章  词法分析\n3.1词法分析器的作用\n3.1.1词法分析及语法分析\n3.1.2词法单元、模式和词素\n3.1.3词法单元的属性\n3.1.4词法错误\n3.1.5  3.1节的练习\n3.2输入缓冲\n3.2.1缓冲区对\n3.2.2哨兵标记\n3.3词法单元的规约\n3.3.1串和语言\n3.3.2语言上的运算\n3.3.3正则表达式\n3.3.4正则定义\n3.3.5正则表达式的扩展\n3.3.6  3.3节的练习\n3.4词法单元的识别\n3.4.1状态转换图\n3.4.2保留字和标识符的识别\n3.4.3完成我们的例子\n3.4.4基于状态转换图的词法分析器的体系结构\n3.4.5  3.4节的练习\n3.5词法分析器生成工具Lex\n3.5.1Lex的使用\n3.5.2Lex程序的结构\n3.5.3Lex中的冲突解决\n3.5.4向前看运算符\n3.5.5  3.5节的练习\n3.6有穷自动机\n3.6.1不确定的有穷自动机\n3.6.2转换表\n3.6.3自动机中输入字符串的接受\n3.6.4确定的有穷自动机\n3.6.5  3.6节的练习\n3.7从正则表达式到自动机\n3.7.1从NFA到DFA的转换\n3.7.2NFA的模拟\n3.7.3NFA模拟的效率\n3.7.4从正则表达式构造NFA\n3.7.5字符串处理算法的效率\n3.7.6  3.7节的练习\n3.8词法分析器生成工具的设计\n3.8.1生成的词法分析器的结构\n3.8.2基于NFA的模式匹配\n3.8.3词法分析器使用的DFA\n3.8.4实现向前看运算符\n3.8.5  3.8节的练习\n3.9基于DFA的模式匹配器的优化\n3.9.1NFA的重要状态\n3.9.2根据抽象语法树计算得到的函数\n3.9.3计算nullable、firstpos及lastpos\n3.9.4计算followpos\n3.9.5根据正则表达式构建DFA\n3.9.6最小化一个DFA的状态数\n3.9.7词法分析器的状态最小化\n3.9.8DFA模拟中的时间和空间权衡\n3.9.9  3.9节的练习\n3.10第3章总结\n3.11第3章参考文献\n第4章  语法分析\n4.1引论\n4.1.1语法分析器的作用\n4.1.2代表性的文法\n4.1.3语法错误的处理\n4.1.4错误恢复策略\n4.2上下文无关文法\n4.2.1上下文无关文法的正式定义\n4.2.2符号表示的约定\n4.2.3推导\n4.2.4语法分析树和推导\n4.2.5二义性\n4.2.6验证文法生成的语言\n4.2.7上下文无关文法和正则表达式\n4.2.8  4.2节的练习\n4.3设计文法\n4.3.1词法分析和语法分析\n4.3.2消除二义性\n4.3.3左递归的消除\n4.3.4提取左公因子\n4.3.5非上下文无关语言的构造\n4.3.6  4.3节的练习\n4.4自顶向下的语法分析\n4.4.1递归下降的语法分析\n4.4.2FIRST和FOLLOW\n4.4.3LL（1）文法\n4.4.4非递归的预测分析\n4.4.5预测分析中的错误恢复\n4.4.6  4.4节的练习\n4.5自底向上的语法分析\n4.5.1归约\n4.5.2句柄剪枝\n4.5.3移入-归约语法分析技术\n4.5.4移入-归约语法分析中的冲突\n4.5.5  4.5节的练习\n4.6LR语法分析技术介绍：简单LR技术\n4.6.1为什么使用LR语法分析器\n4.6.2项和LR（0）自动机\n4.6.3LR语法分析算法\n4.6.4构造SLR语法分析表\n4.6.5可行前缀\n4.6.6  4.6节的练习\n4.7更强大的LR语法分析器\n4.7.1规范LR（1）项\n4.7.2构造LR（1）项集\n4.7.3规范LR（1）语法分析表\n4.7.4构造LALR语法分析表\n4.7.5高效构造LALR语法分析表的方法\n4.7.6LR语法分析表的压缩\n4.7.7  4.7节的练习\n4.8使用二义性文法\n4.8.1用优先级和结合性解决冲突\n4.8.2“悬空-else”的二义性\n4.8.3LR语法分析中的错误恢复\n4.8.4  4.8节的练习\n4.9语法分析器生成工具\n4.9.1语法分析器生成工具Yacc\n4.9.2使用带有二义性文法的Yacc规约\n4.9.3用Lex创建Yacc的词法分析器\n4.9.4Yacc中的错误恢复\n4.9.5  4.9节的练习\n4.10第4章总结\n4.11第4章参考文献\n第5章  语法制导的翻译\n5.1语法制导定义\n5.1.1继承属性和综合属性\n5.1.2在语法分析树的结点上对SDD求值\n5.1.3  5.1节的练习\n5.2SDD的求值顺序\n5.2.1依赖图\n5.2.2属性求值的顺序\n5.2.3S属性的定义\n5.2.4L属性的定义\n5.2.5具有受控副作用的语义规则\n5.2.6  5.2节的练习\n5.3语法制导翻译的应用\n5.3.1抽象语法树的构造\n5.3.2类型的结构\n5.3.3  5.3节的练习\n5.4语法制导的翻译方案\n5.4.1后缀翻译方案\n5.4.2后缀SDT的语法分析栈实现\n5.4.3产生式内部带有语义动作的SDT\n5.4.4从SDT中消除左递归\n5.4.5L属性定义的SDT\n5.4.6  5.4节的练习\n5.5实现L属性的SDD\n5.5.1在递归下降语法分析过程中进行翻译\n5.5.2边扫描边生成代码\n5.5.3L属性的SDD和LL语法分析\n5.5.4L属性的SDD的自底向上语法分析\n5.5.5  5.5节的练习\n5.6第5章总结\n5.7第5章参考文献\n第6章  中间代码生成\n6.1语法树的变体\n6.1.1表达式的有向无环图\n6.1.2构造DAG的值编码方法\n6.1.3  6.1节的练习\n6.2三地址代码\n6.2.1地址和指令\n6.2.2四元式表示\n6.2.3三元式表示\n6.2.4静态单赋值形式\n6.2.5  6.2节的练习\n6.3类型和声明\n6.3.1类型表达式\n6.3.2类型等价\n6.3.3声明\n6.3.4局部变量名的存储布局\n6.3.5声明的序列\n6.3.6记录和类中的字段\n6.3.7  6.3节的练习\n6.4表达式的翻译\n6.4.1表达式中的运算\n6.4.2增量翻译\n6.4.3数组元素的寻址\n6.4.4数组引用的翻译\n6.4.5  6.4节的练习\n6.5类型检查\n6.5.1类型检查规则\n6.5.2类型转换\n6.5.3函数和运算符的重载\n6.5.4类型推导和多态函数\n6.5.5一个合一算法\n6.5.6  6.5节的练习\n6.6控制流\n6.6.1布尔表达式\n6.6.2短路代码\n6.6.3控制流语句\n6.6.4布尔表达式的控制流翻译\n6.6.5避免生成冗余的goto指令\n6.6.6布尔值和跳转代码\n6.6.7  6.6节的练习\n6.7回填\n6.7.1使用回填技术的一趟式目标代码生成\n6.7.2布尔表达式的回填\n6.7.3控制转移语句\n6.7.4break语句、continue语句和goto语句\n6.7.5  6.7节的练习\n6.8switch语句\n6.8.1switch语句的翻译\n6.8.2switch语句的语法制导翻译\n6.8.3  6.8节的练习\n6.9过程的中间代码\n6.10第6章总结\n6.11第6章参考文献\n第7章  运行时刻环境\n7.1存储组织\n7.2空间的栈式分配\n7.2.1活动树\n7.2.2活动记录\n7.2.3调用代码序列\n7.2.4栈中的变长数据\n7.2.5  7.2节的练习\n7.3栈中非局部数据的访问\n7.3.1没有嵌套过程时的数据访问\n7.3.2和嵌套过程相关的问题\n7.3.3一个支持嵌套过程声明的语言\n7.3.4嵌套深度\n7.3.5访问链\n7.3.6处理访问链\n7.3.7过程型参数的访问链\n7.3.8显示表\n7.3.9  7.3节的练习\n7.4堆管理\n7.4.1存储管理器\n7.4.2一台计算机的存储层次结构\n7.4.3程序中的局部性\n7.4.4碎片整理\n7.4.5人工回收请求\n7.4.6  7.4节的练习\n7.5垃圾回收概述\n7.5.1垃圾回收器的设计目标\n7.5.2可达性\n7.5.3引用计数垃圾回收器\n7.5.4  7.5节的练习\n7.6基于跟踪的回收的介绍\n7.6.1基本的标记-清扫式回收器\n7.6.2基本抽象\n7.6.3标记-清扫式算法的优化\n7.6.4标记并压缩的垃圾回收器\n7.6.5拷贝回收器\n7.6.6开销的比较\n7.6.7  7.6节的练习\n7.7短停顿垃圾回收\n7.7.1增量式垃圾回收\n7.7.2增量式可达性分析\n7.7.3部分回收概述\n7.7.4世代垃圾回收\n7.7.5列车算法\n7.7.6  7.7节的练习\n7.8垃圾回收中的高级论题\n7.8.1并行和并发垃圾回收\n7.8.2部分对象重新定位\n7.8.3类型不安全的语言的保守垃圾回收\n7.8.4弱引用\n7.8.5  7.8节的练习\n7.9第7章总结\n7.10第7章参考文献\n第8章  代码生成\n8.1代码生成器设计中的问题\n8.1.1代码生成器的输入\n8.1.2目标程序\n8.1.3指令选择\n8.1.4寄存器分配\n8.1.5求值顺序\n8.2目标语言\n8.2.1一个简单的目标机模型\n8.2.2程序和指令的代价\n8.2.3  8.2节的练习\n8.3目标代码中的地址\n8.3.1静态分配\n8.3.2栈分配\n8.3.3名字的运行时刻地址\n8.3.4  8.3节的练习\n8.4基本块和流图\n8.4.1基本块\n8.4.2后续使用信息\n8.4.3流图\n8.4.4流图的表示方式\n8.4.5循环\n8.4.6  8.4节的练习\n8.5基本块的优化\n8.5.1基本块的DAG表示\n8.5.2寻找局部公共子表达式\n8.5.3消除死代码\n8.5.4代数恒等式的使用\n8.5.5数组引用的表示\n8.5.6指针赋值和过程调用\n8.5.7从DAG到基本块的重组\n8.5.8  8.5节的练习\n8.6一个简单的代码生成器\n8.6.1寄存器和地址描述符\n8.6.2代码生成算法\n8.6.3函数getReg的设计\n8.6.4  8.6节的练习\n8.7窥孔优化\n8.7.1消除冗余的加载和保存指令\n8.7.2消除不可达代码\n8.7.3控制流优化\n8.7.4代数化简和强度消减\n8.7.5使用机器特有的指令\n8.7.6  8.7节的练习\n8.8寄存器分配和指派\n8.8.1全局寄存器分配\n8.8.2使用计数\n8.8.3外层循环的寄存器指派\n8.8.4通过图着色方法进行寄存器分配\n8.8.5  8.8节的练习\n8.9通过树重写来选择指令\n8.9.1树翻译方案\n8.9.2通过覆盖一个输入树来生成代码\n8.9.3通过扫描进行模式匹配\n8.9.4用于语义检查的例程\n8.9.5通用的树匹配方法\n8.9.6  8.9节的练习\n8.10表达式的优化代码的生成\n8.10.1Ershov数\n8.10.2从带标号的表达式树生成代码\n8.10.3寄存器数量不足时的表达式求值\n8.10.4  8.10节的练习\n8.11使用动态规划的代码生成\n8.11.1连续求值\n8.11.2动态规划的算法\n8.11.3  8.11节的练习\n8.12第8章总结\n8.13第8章参考文献\n第9章  机器无关优化\n9.1优化的主要来源\n9.1.1冗余的原因\n9.1.2一个贯穿本章的例子：快速排序\n9.1.3保持语义不变的转换\n9.1.4全局公共子表达式\n9.1.5复制传播\n9.1.6死代码消除\n9.1.7代码移动\n9.1.8归纳变量和强度消减\n9.1.9  9.1节的练习\n9.2数据流分析简介\n9.2.1数据流抽象\n9.2.2数据流分析模式\n9.2.3基本块上的数据流模式\n9.2.4到达定值\n9.2.5活跃变量分析\n9.2.6可用表达式\n9.2.7小结\n9.2.8  9.2节的练习\n9.3数据流分析基础\n9.3.1半格\n9.3.2传递函数\n9.3.3通用框架的迭代算法\n9.3.4数据流解的含义\n9.3.5  9.3节的练习\n9.4常量传播\n9.4.1常量传播框架的数据流值\n9.4.2常量传播框架的交汇运算\n9.4.3常量传播框架的传递函数\n9.4.4常量传递框架的单调性\n9.4.5常量传播框架的不可分配性\n9.4.6对算法结果的解释\n9.4.7  9.4节的练习\n9.5部分冗余消除\n9.5.1冗余的来源\n9.5.2可能消除所有冗余吗\n9.5.3懒惰代码移动问题\n9.5.4表达式的预期执行\n9.5.5懒惰代码移动算法\n9.5.6  9.5节的练习\n9.6流图中的循环\n9.6.1支配结点\n9.6.2深度优先排序\n9.6.3深度优先生成树中的边\n9.6.4回边和可归约性\n9.6.5流图的深度\n9.6.6自然循环\n9.6.7迭代数据流算法的收敛速度\n9.6.8  9.6节的练习\n9.7基于区域的分析\n9.7.1区域\n9.7.2可归约流图的区域层次结构\n9.7.3基于区域的分析技术概述\n9.7.4有关传递函数的必要假设\n9.7.5一个基于区域的分析算法\n9.7.6处理不可归约流图\n9.7.7  9.7节的练习\n9.8符号分析\n9.8.1参考变量的仿射表达式\n9.8.2数据流问题的公式化\n9.8.3基于区域的符号化分析\n9.8.4  9.8节的练习\n9.9第9章总结\n9.10第9章参考文献\n第10章  指令级并行性\n10.1处理器体系结构\n10.1.1指令流水线和分支延时\n10.1.2流水线执行\n10.1.3多指令发送\n10.2代码调度约束\n10.2.1数据依赖\n10.2.2寻找内存访问之间的依赖关系\n10.2.3寄存器使用和并行性之间的折衷\n10.2.4寄存器分配阶段和代码调度阶段之间的顺序\n10.2.5控制依赖\n10.2.6对投机执行的支持\n10.2.7一个基本的机器模型\n10.2.8  10.2节的练习\n10.3基本块调度\n10.3.1数据依赖图\n10.3.2基本块的列表调度方法\n10.3.3带优先级的拓扑排序\n10.3.4  10.3节的练习\n10.4全局代码调度\n10.4.1基本的代码移动\n10.4.2向上的代码移动\n10.4.3向下的代码移动\n10.4.4更新数据依赖关系\n10.4.5全局调度算法\n10.4.6高级代码移动技术\n10.4.7和动态调度器的交互\n10.4.8  10.4节的练习\n10.5软件流水线化\n10.5.1引言\n10.5.2循环的软件流水线化\n10.5.3寄存器分配和代码生成\n10.5.4Do-Across循环\n10.5.5软件流水线化的目标和约束\n10.5.6一个软件流水线化算法\n10.5.7对无环数据依赖图进行调度\n10.5.8对有环数据依赖图进行调度\n10.5.9对流水线化算法的改进\n10.5.10模数变量扩展\n10.5.11条件语句\n10.5.12软件流水线化的硬件支持\n10.5.13  10.5节的练习\n10.6第10章总结\n10.7第10章参考文献\n第11章  并行性和局部性优化\n11.1基本概念\n11.1.1多处理器\n11.1.2应用中的并行性\n11.1.3循环层次上的并行性\n11.1.4数据局部性\n11.1.5仿射变换理论概述\n11.2矩阵乘法：一个深入的例子\n11.2.1矩阵相乘算法\n11.2.2优化\n11.2.3高速缓存干扰\n11.2.4  11.2节的练习\n11.3迭代空间\n11.3.1从循环嵌套结构中构建迭代空间\n11.3.2循环嵌套结构的执行顺序\n11.3.3不等式组的矩阵表示方法\n11.3.4混合使用符号常量\n11.3.5控制执行的顺序\n11.3.6坐标轴的变换\n11.3.7  11.3节的练习\n11.4仿射的数组下标\n11.4.1仿射访问\n11.4.2实践中的仿射访问和非仿射访问\n11.4.3  11.4节的练习\n11.5数据复用\n11.5.1数据复用的类型\n11.5.2自复用\n11.5.3自空间复用\n11.5.4组复用\n11.5.5  11.5节的练习\n11.6数组数据依赖关系分析\n11.6.1数组访问的数据依赖关系的定义\n11.6.2整数线性规划\n11.6.3GCD测试\n11.6.4解决整数线性规划的启发式规则\n11.6.5解决一般性的整数线性规划问题\n11.6.6小结\n11.6.7  11.6节的练习\n11.7寻找无同步的并行性\n11.7.1一个介绍性的例子\n11.7.2仿射空间分划\n11.7.3空间分划约束\n11.7.4求解空间分划约束\n11.7.5一个简单的代码生成算法\n11.7.6消除空迭代\n11.7.7从最内层循环中消除条件测试\n11.7.8源代码转换\n11.7.9  11.7节的练习\n11.8并行循环之间的同步\n11.8.1固定多个同步运算\n11.8.2程序依赖图\n11.8.3层次结构化的时间\n11.8.4并行化算法\n11.8.5  11.8节的练习\n11.9流水线化技术\n11.9.1什么是流水线化\n11.9.2连续过松弛方法：一个例子\n11.9.3完全可交换循环\n11.9.4把完全可交换循环流水线化\n11.9.5一般性的理论\n11.9.6时间分划约束\n11.9.7用Farkas引理求解时间分划约束\n11.9.8代码转换\n11.9.9具有最小同步量的并行性\n11.9.10  11.9节的练习\n11.10局部性优化\n11.10.1计算结果数据的时间局部性\n11.10.2数组收缩\n11.10.3分划单元的交织\n11.10.4合成\n11.10.5  11.10节的练习\n11.11仿射转换的其他用途\n11.11.1分布式内存计算机\n11.11.2多指令发送处理器\n11.11.3向量和SIMD指令\n11.11.4数据预取\n11.12第11章总结\n11.13第11章参考文献\n第12章  过程间分析\n12.1基本概念\n12.1.1调用图\n12.1.2上下文相关\n12.1.3调用串\n12.1.4基于克隆的上下文相关分析\n12.1.5基于摘要的上下文相关分析\n12.1.6  12.1节的练习\n12.2为什么需要过程间分析\n12.2.1虚方法调用\n12.2.2指针别名分析\n12.2.3并行化\n12.2.4软件错误和漏洞的检测\n12.2.5SQL注入\n12.2.6缓冲区溢出\n12.3数据流的一种逻辑表示方式\n12.3.1Datalog简介\n12.3.2Datalog规则\n12.3.3内涵断言和外延断言\n12.3.4Datalog程序的执行\n12.3.5Datalog程序的增量计算\n12.3.6有问题的Datalog规则\n12.3.7  12.3节的练习\n12.4一个简单的指针分析算法\n12.4.1为什么指针分析有难度\n12.4.2一个指针和引用的模型\n12.4.3控制流无关性\n12.4.4在Datalog中的表示方法\n12.4.5使用类型信息\n12.4.6  12.4节的练习\n12.5上下文无关的过程间分析\n12.5.1一个方法调用的效果\n12.5.2在Datalog中发现调用图\n12.5.3动态加载和反射\n12.5.4  12.5节的练习\n12.6上下文相关指针分析\n12.6.1上下文和调用串\n12.6.2在Datalog规则中加入上下文信息\n12.6.3关于相关性的更多讨论\n12.6.4  12.6节的练习\n12.7使用BDD的Datalog的实现\n12.7.1分决策图\n12.7.2对BDD的转换\n12.7.3用BDD表示关系\n12.7.4用BDD操作实现关系运算\n12.7.5在指针指向分析中使用BDD\n12.7.6  12.7节的练习\n12.8第12章总结\n12.9第12章参考文献\n附录A  一个完整的编译器前端\n附录B  寻找线性独立解