《现代编译原理c语言描述》由会员分享，可在线阅读，更多相关《现代编译原理c语言描述（9页珍藏版）》请在金锄头文库上搜索。
1、 作者简介作者简介A n d r e w W. A p p e l ，美国普林斯顿大学计算机科学系教授，第2 6 届A C M SIG PLA N-SIG A C T 程序设计原 理年会大会执行主席，19 9 8 -19 9 9 年在贝尔实验室做研究工作。主要研究方向是计算机安全、编译器 设计、程序设计语言等。本书简介本书简介本书全面讲述了现代编译器的各个组成部分，包括词法分析、语法分析、抽象语法、语义检查 、中间代码表示、指令选择、数据流分析、寄存器分配以及运行时系统等。全书分成两部分，第一 部分是编译的基础知识，适用于第一门编译原理课程( 一个学期) ；第二部分是高级主题，包括面向 对象语
2、言和函数语言、垃圾收集、循环优化、SSA ( 静态单赋值) 形式、循环调度、存储结构优化等 ，适合于后续课程或研究生教学。书中专门为学生提供了一个用C 语言编写的实习项目，包括前端 和后端设计，学生可以在一学期内创建一个功能完整的编译器。本书适用于高等院校计算机及相关专业的本科生或研究生，也可供科研人员或工程技术人员参 考。目录目录第一部分 编译基本原理第1章 绪论 1 1. 1 模块与接口 1 1. 2 工具和软件 3 1. 3 树语言的数据结构 3 程序设计：直线式程序解释器 7 推荐阅读 9 习题 9第2 章 词法分析 10 2 . 1 词法单词 10 2 . 2 正则表达式 11 2
3、. 3 有限自动机 13 2 . 4 非确定有限自动机 15 2 . 4. 1 将正则表达式转换为NFA 16 2 . 4. 2 将NFA 转换为D FA 18 2 . 5 Le x ：词法分析器的生成器 2 0 程序设计：词法分析 2 2 推荐阅读 2 3 习题 2 3第3章 语法分析 2 7 3. 1 上下文无关文法 2 8 3. 1. 1 推导 2 9 3. 1. 2 语法分析树 2 9 3. 1. 3 二义性文法 30 3. 1. 4 文件结束符 31 3. 2 预测分析 32 3. 2 . 1 FI R ST 集合和FO LLO W集合 33 3. 2 . 2 构造一个预测分析器 3
4、5 3. 2 . 3 消除左递归 36 3. 2 . 4 提取左因子 37 3. 2 . 5 错误恢复 37 3. 3 LR 分析 39 3. 3. 1 LR 分析引擎 40 3. 3. 2 LR ( 0 ) 分析器生成器 41 3. 3. 3 SLR 分析器的生成 44 3. 3. 4 LR ( 1) 项和LR ( 1) 分析表 45 3. 3. 5 LA LR ( 1) 分析表 46 3. 3. 6 各类文法的层次 47 3. 3. 7 二义性文法的LR 分析 47 3. 4 使用分析器的生成器 483. 4. 1 冲突 49 3. 4. 2 优先级指导 50 3. 4. 3 语法和语义
5、53 3. 5 错误恢复 54 3. 5. 1 用e r r o r 符号恢复 54 3. 5. 2 全局错误修复 55 程序设计：语法分析 57 推荐阅读 58 习题 58第4章 抽象语法 6 2 4. 1 语义动作 6 2 4. 1. 1 递归下降 6 2 4. 1. 2 Ya c c 生成的分析器 6 2 4. 1. 3 语义动作的解释器 6 4 4. 2 抽象语法分析树 6 5 4. 2 . 1 位置 6 7 4. 2 . 2 T i g e r 的抽象语法 6 8 程序设计：抽象语法 7 1 推荐阅读 7 1 习题 7 2第5章 语义分析 7 3 5. 1 符号表 7 3 5. 1.
6、 1 多个符号表 7 4 5. 1. 2 高效的命令式风格符号表 7 5 5. 1. 3 高效的函数式符号表 7 6 5. 1. 4 T i g e r 编译器的符号 7 7 5. 1. 5 函数式风格的符号表 7 9 5. 2 T i g e r 编译器的绑定 7 9 5. 3 表达式的类型检查 8 2 5. 4 声明的类型检查 8 4 5. 4. 1 变量声明 8 4 5. 4. 2 类型声明 8 5 5. 4. 3 函数声明 8 5 5. 4. 4 递归声明 8 6 程序设计：类型检查 8 7 习题 8 7第6 章 活动记录 8 9 6 . 1 栈帧 9 0 6 . 1. 1 帧指针 9
7、 1 6 . 1. 2 寄存器 9 2 6 . 1. 3 参数传递 9 2 6 . 1. 4 返回地址 9 4 6 . 1. 5 栈帧内的变量 9 4 6 . 1. 6 静态链 9 5 6 . 2 T i g e r 编译器的栈帧 9 66 . 2 . 1 栈帧描述的表示 9 8 6 . 2 . 2 局部变量 9 8 6 . 2 . 3 计算逃逸变量 9 9 6 . 2 . 4 临时变量和标号 10 0 6 . 2 . 5 两层抽象 10 0 6 . 2 . 6 管理静态链 10 2 6 . 2 . 7 追踪层次信息 10 2 程序设计：栈帧 10 3 推荐阅读 10 3 习题 10 3第7
8、章 翻译成中间代码 10 6 7 . 1 中间表示树 10 6 7 . 2 翻译为树中间语言 10 8 7 . 2 . 1 表达式的种类 10 8 7 . 2 . 2 简单变量 111 7 . 2 . 3 追随静态链 112 7 . 2 . 4 数组变量 113 7 . 2 . 5 结构化的左值 114 7 . 2 . 6 下标和域选择 114 7 . 2 . 7 关于安全性的劝告 115 7 . 2 . 8 算术操作 116 7 . 2 . 9 条件表达式 116 7 . 2 . 10 字符串 117 7 . 2 . 11 记录和数组的创建 118 7 . 2 . 12 w h i l e
9、循环 119 7 . 2 . 13 f o r 循环 119 7 . 2 . 14 函数调用 12 0 7 . 3 声明 12 0 7 . 3. 1 变量定义 12 0 7 . 3. 2 函数定义 12 0 7 . 3. 3 片段 12 1 程序设计：翻译成树 12 2 习题 12 3第8 章 基本块和轨迹 12 5 8 . 1 规范树 12 6 8 . 1. 1 ESEQ 的转换 12 6 8 . 1. 2 一般重写规则 12 6 8 . 1. 3 将C A LL移到顶层 130 8 . 1. 4 线性语句表 131 8 . 2 处理条件分支 131 8 . 2 . 1 基本块 131 8
10、. 2 . 2 轨迹 132 8 . 2 . 3 完善 133 8 . 2 . 4 最优轨迹 133 推荐阅读 134 习题 134第9 章 指令选择 136 9 . 1 指令选择算法 138 9 . 1. 1 M a x i m a l M u n c h 算法 138 9 . 1. 2 动态规划 140 9 . 1. 3 树文法 141 9 . 1. 4 快速匹配 143 9 . 1. 5 覆盖算法的效率 143 9 . 2 C I SC 机器 144 9 . 3 T i g e r 编译器的指令选择 146 9 . 3. 1 抽象的汇编语言指令 146 9 . 3. 2 生成汇编指令 1
11、48 9 . 3. 3 过程调用 151 9 . 3. 4 无帧指针的情形 151 程序设计：指令选择 152 推荐阅读 153 习题 154第10 章 活跃分析 155 10 . 1 数据流方程的解 156 10 . 1. 1 活跃性计算 156 10 . 1. 2 集合的表示 158 10 . 1. 3 时间复杂度 158 10 . 1. 4 最小不动点 159 10 . 1. 5 静态活跃性与动态活跃性 16 0 10 . 1. 6 冲突图 16 1 10 . 2 T i g e r 编译器的活跃分析 16 2 10 . 2 . 1 图 16 2 10 . 2 . 2 控制流图 16 3
12、 10 . 2 . 3 活跃分析 16 4 程序设计：构造流图 16 4 程序设计：活跃分析模块 16 5 习题 16 5第11章 寄存器分配 16 6 11. 1 通过简化进行着色 16 6 11. 2 合并 16 8 11. 3 预着色的结点 17 1 11. 3. 1 机器寄存器的临时副本 17 1 11. 3. 2 调用者保护的寄存器和被调用者保护的寄存器 17 2 11. 3. 3 含预着色结点的例子 17 2 11. 4 图着色的实现 17 5 11. 4. 1 传送指令工作表的管理 17 6 11. 4. 2 数据结构 17 6 11. 4. 3 程序代码 17 7 11. 5
13、针对树的寄存器分配 18 1 程序设计：图着色 18 4 推荐阅读 18 5习题 18 5第12 章 整合为一体 18 8 程序设计：过程入口/ 出口 18 9 程序设计：创建一个可运行的编译器 19 1第二部分高级主题第13章 垃圾收集 19 3 13. 1 标记-清扫式收集 19 4 13. 2 引用计数 19 7 13. 3 复制式收集 19 8 13. 4 分代收集 2 0 1 13. 5 增量式收集 2 0 3 13. 6 Ba k e r 算法 2 0 5 13. 7 编译器接口 2 0 5 13. 7 . 1 快速分配 2 0 5 13. 7 . 2 数据布局的描述 2 0 6
14、13. 7 . 3 导出指针 2 0 7 程序设计：描述字 2 0 8 程序设计：垃圾收集 2 0 8 推荐阅读 2 0 8 习题 2 10第14章 面向对象的语言 2 11 14. 1 类 2 11 14. 2 数据域的单继承性 2 13 14. 3 多继承 2 14 14. 4 测试类成员关系 2 16 14. 5 私有域和私有方法 2 18 14. 6 无类语言 2 19 14. 7 面向对象程序的优化 2 19 程序设计：O BJEC T -T i g e r 2 2 0 推荐阅读 2 2 0 习题 2 2 1第15章 函数式程序设计语言 2 2 2 15. 1 一个简单的函数式语言
15、2 2 2 15. 2 闭包 2 2 4 15. 3 不变的变量 2 2 5 15. 3. 1 基于延续的I / O 2 2 6 15. 3. 2 语言上的变化 2 2 7 15. 3. 3 纯函数式语言的优化 2 2 8 15. 4 内联扩展 2 2 9 15. 5 闭包变换 2 33 15. 6 高效的尾递归 2 35 15. 7 懒惰计算 2 36 15. 7 . 1 传名调用计算 2 3715. 7 . 2 按需调用 2 38 15. 7 . 3 懒惰程序的计算 2 39 15. 7 . 4 懒惰函数式程序的优化 2 39 15. 7 . 5 严格性分析 2 41 推荐阅读 2 43
16、程序设计：编译函数式语言 2 44 习题 2 44第16 章 多态类型 2 46 16 . 1 参数多态性 2 46 16 . 1. 1 显式带类型的多态语言 2 47 16 . 1. 2 多态类型的检查 2 48 16 . 2 类型推论 2 53 16 . 2 . 1 一个隐式类型的多态语言 2 54 16 . 2 . 2 类型推论算法 2 55 16 . 2 . 3 递归的数据类型 2 57 16 . 2 . 4 H i n d l e y -M i l n e r 类型的能力 2 59 16 . 3 多态变量的表示 2 59 16 . 3. 1 多态函数的扩展 2 6 0 16 . 3. 2 完全的装箱转换 2 6 1 16 . 3. 3 基于强制的表示分析 2 6 2 16 . 3. 4 将类型作为运行时参数传递 2 6 4 16 . 4 静态重载的解决方法 2 6 5 推荐阅读 2 6 6 习题 2 6 6第17 章 数据流分析 2 6 9
