编译原理教程(第五版)

第1章 绪论 1 1.1 程序设计语言和编译程序 1 1.2 编译程序的历史及发展 2 1.3 编译过程和编译程序结构 4 1.4 编译程序的开发 5 1.5 构造编译程序所应具备的知识内容 6 习题1 8 第2章 词法分析 9 2.1 词法分析器的设计方法 9 2.1.1 单词符号的分类与输出形式 9 2.1.2 状态转换图 10 2.2 一个简单的词法分析器示例 12 2.2.1 C语言子集的单词符号表示 12 2.2.2 C语言子集对应的状态转换图 13 2.2.3 状态转换图的实现 13 2.3 正规表达式与有限自动机简介 16 2.3.1 正规表达式与正规集 16 2.3.2 有限自动机 18 2.4 正规表达式到有限自动机的构造 20 2.4.1 由正规表达式构造等价的非确定有限自动机(NFA) 20 2.4.2 NFA的确定化 21 2.4.3 确定有限自动机(DFA)的化简 23 2.4.4 正规表达式到有限自动机构造示例 25 2.5 词法分析器的自动生成 30 习题2 32 第3章 语法分析 35 3.1 文法和语言 35 3.1.1 文法和语言的基本概念 35 3.1.2 形式语言分类 38 3.1.3 正规表达式与上下文无关文法 40 3.2 推导与语法树 41 3.2.1 推导与短语 41 3.2.2 语法树与二义性 42 3.3 自顶向下的语法分析 47 3.3.1 递归下降分析法 47 3.3.2 LL(1) 分析法 55 3.4 自底向上的语法分析 62 3.4.1 自底向上分析原理 62 3.4.2 算符优先分析法 64 3.5 规范归约的自底向上语法分析方法 74 3.5.1 LR分析器的工作原理 74 3.5.2 LR(0)分析器 79 3.5.3 SLR(1)分析器 86 3.5.4 LR(1)分析器 92 3.5.5 LALR(1)分析器 96 3.5.6 二义文法的应用 98 *3.5.7 LR分析器的应用与拓展 102 习题3 104 第4章 语义分析和中间代码生成 112 4.1 概述 112 4.1.1 语义分析的概念 112 4.1.2 语法制导翻译方法 112 4.2 属性文法 114 4.2.1 文法的属性 114 4.2.2 属性文法 114 4.3 几种常见的中间语言 116 4.3.1 抽象语法树 116 4.3.2 逆波兰表示法 117 4.3.3 三地址代码 119 4.4 表达式及赋值语句的翻译 121 4.4.1 简单算术表达式和赋值语句的翻译 121 4.4.2 布尔表达式的翻译 123 4.5 控制语句的翻译 128 4.5.1 条件语句if的翻译 128 4.5.2 循环语句的翻译 130 4.5.3 三种基本控制结构的翻译 132 4.5.4 多分支控制语句switch的翻译 137 4.5.5 语句标号和转移语句的翻译 139 4.6 数组元素的翻译 140 4.6.1 数组元素的地址计算及中间代码形式 140 4.6.2 赋值语句中数组元素的翻译 140 4.6.3 数组元素翻译示例 142 4.7 过程或函数调用语句的翻译 145 4.7.1 过程或函数调用的方法 145 4.7.2 过程或函数调用语句的四元式生成 146 4.8 说明语句的翻译 146 4.8.1 变量说明的翻译 146 4.8.2 数组说明的翻译 147 4.9 递归下降语法制导翻译方法简介 148 习题4 149 第5章 代码优化 153 5.1 局部优化 153 5.1.1 基本块的划分方法 153 5.1.2 基本块的DAG方法 154 5.1.3 用DAG进行基本块的优化处理 158 5.1.4 DAG构造算法的进一步讨论 159 5.2 循环优化 160 5.2.1 程序流图与循环 160 5.2.2 循环的查找 162 5.2.3 循环优化 167 *5.3 全局优化概述 174 5.3.1 到达-定值与引用-定值链 174 5.3.2 定值-引用链(du链) 178 5.3.3 复写传播 181 *5.4 代码优化示例 184 习题5 188 第6章 目标程序运行时存储空间的组织 192 6.1 静态存储分配 192 6.2 简单的栈式存储分配 193 6.2.1 栈式存储分配与活动记录 194 6.2.2 过程的执行 196 6.3 嵌套过程语言的栈式实现 198 6.3.1 嵌套层次显示(DISPLAY)表和活动记录 198 6.3.2 嵌套过程的执行 200 6.3.3 访问非局部名的另一种实现方法 201 6.4 堆式动态存储分配 204 6.4.1 堆式存储的概念 204 6.4.2 堆式存储的管理方法 205 *6.5 参数传递补遗 206 6.5.1 参数传递的方法 207 6.5.2 不同参数传递方法比较 208 习题6 209 第7章 目标代码生成 212 7.1 简单代码生成器 212 7.1.1 待用信息与活跃信息 213 7.1.2 代码生成算法 215 7.1.3 寄存器分配 216 7.1.4 源程序到目标代码生成示例 218 *7.2 汇编指令到机器代码翻译概述 220 习题7 226 第8章 符号表与错误处理 229 8.1 符号表 229 8.1.1 符号表的作用 229 8.1.2 符号表的组织 229 8.1.3 分程序结构语言符号表的建立 231 8.1.4 非分程序结构语言符号表的建立 234 8.1.5 常用符号表结构 235 8.1.6 符号表内容 236 8.2 错误处理 237 8.2.1 语法错误校正 237 8.2.2 语义错误校正 243 习题8 245 *第9章 并行编译技术简介 247 9.1 并行计算机体系结构 247 9.1.1 向量计算机 247 9.1.2 共享存储器多处理机 247 9.1.3 分布式存储器大规模并行计算机 248 9.2 并行编译技术 249 9.2.1 并行编译技术的概念 249 9.2.2 并行编译系统的功能和结构 250 9.3 自动并行编译 251 9.3.1 依赖关系分析 251 9.3.2 程序转换及数据分布 253 9.3.3 调度 253 附录1 8086/8088指令码汇总表 256 附录2 8086/8088指令编码空间表 261 参考文献 263