编译原理（陈意云）
目 录
第１章 编译器概述 （１） ………………………
１．１ 词法分析 （２） ……………………………
１．２ 语法分析 （２） ……………………………
１．３ 语义分析 （４） ……………………………
１．４ 中间代码生成 （５） ………………………
１．５ 代码优化 （６） ……………………………
１．６ 代码生成 （６） ……………………………
１．７ 符号表管理 （７） …………………………
１．８ 错误诊断和报告 （７） ……………………
１．９ 阶段的分组 （９） …………………………
习题１ （９） ………………………………………
第２章 词法分析 （１０） …………………………
２．１ 词法记号及属性 （１０） ………………………
２．１．１ 词法记号、模式、词法单元 （１１） ………
２．１．２ 词法记号的属性 （１２） …………………
２．１．３ 词法错误 （１３） …………………………
２．２ 词法记号的描述与识别 （１３） ………………
２．２．１ 串和语言 （１３） …………………………
２．２．２ 正规式 （１５） ……………………………
２．２．３ 正规定义 （１６） …………………………
２．２．４ 状态转换图 （１７） ………………………
２．３ 有限自动机 （２０） ……………………………
２．３．１ 不确定的有限自动机 （２１） ……………
２．３．２ 确定的有限自动机 （２２） ………………
２．３．３ ＮＦＡ到 ＤＦＡ的变换 （２３） ………………
２．３．４ ＤＦＡ的化简 （２７） ………………………
２．４ 从正规式到有限自动机 （２９） ………………
２．５ 词法分析器的生成器 （３２） …………………
习题２ （３６） ………………………………………
第３章 语法分析 （３９） …………………………
３．１ 上下文无关文法 （３９） ………………………
３．１．１ 上下文无关文法的定义 （３９） …………
３．１．２ 推导 （４１） ………………………………
３．１．３ 分析树 （４３） ……………………………
３．１．４ 二义性 （４３） ……………………………
３．２ 语言和文法 （４４） ……………………………
３．２．１ 正规式和上下文无关
文法的比较 （４５） ………………………
３．２．２ 分离词法分析器的理由 （４５） …………
３．２．３ 验证文法产生的语言 （４６） ……………
３．２．４ 适当的表达式文法 （４６） ………………
３．２．５ 消除二义性 （４７） ………………………
３．２．６ 消除左递归 （４９） ………………………
３．２．７ 提左因子 （５０） …………………………
３．２．８ 非上下文无关的语言结构 （５１） ………
３．２．９ 形式语言鸟瞰 （５２） ……………………
３．３ 自上而下分析 （５３） …………………………
３．３．１ 自上而下分析的一般方法 （５４） ………
３．３．２ ＬＬ（１）文法 （５５） ………………………
３．３．３ 递归下降的预测分析 （５６） ……………
３．３．４ 非递归的预测分析 （５８） ………………
３．３．５ 构造预测分析表 （６０） …………………
３．３．６ 预测分析的错误恢复 （６２） ……………
３．４ 自下而上分析 （６５） …………………………
３．４．１ 归约 （６５） ………………………………
３．４．２ 句柄 （６６） ………………………………
３．４．３ 用栈实现移进—归约分析 （６７） ………
３．４．４ 移进—归约分析的冲突 （６９） …………
３．５ ＬＲ分析器 （７０） ……………………………
３．５．１ ＬＲ分析算法 （７１） ………………………
３．５．２ ＬＲ文法和 ＬＲ分析
方法的特点 （７４） ………………………
３．５．３ 构造ＳＬＲ分析表 （７５） …………………
３．５．４ 构造规范的ＬＲ分析表 （８３） …………
３．５．５ 构造ＬＡＬＲ分析表 （８７） ………………
３．５．６ 非ＬＲ的上下文无关结构 （９０） ………
３．６ 二义文法的应用 （９２） ………………………
３．６．１ 使用文法以外的信息来解决
分析动作的冲突 （９２） …………………
３．６．２ 特殊情况产生式引起的
二义性 （９４） ……………………………
３．６．３ ＬＲ分析的错误恢复 （９５） ………………
３．７ 分析器的生成器 （９７） ………………………
３．７．１ 分析器的生成器 Ｙａｃｃ （９７） ……………
３．７．２ 用Ｙａｃｃ处理二义文法 （１００） …………
３．７．３ Ｙａｃｃ的错误恢复 （１０３） ………………
习题３ （１０５） ………………………………………
第４章 语法制导的翻译 （１１１） ………………
４．１ 语法制导的定义 （１１１） ……………………
４．１．１ 语法制导定义的形式 （１１１） …………
４．１．２ 综合属性 （１１３） ………………………
４．１．３ 继承属性 （１１３） ………………………
４．１．４ 属性依赖图 （１１４） ……………………
４．１．５ 属性计算次序 （１１５） …………………
４．２ Ｓ属性定义的自下而上计算 （１１６） …………
４．２．１ 语法树 （１１７） …………………………
４．２．２ 构造语法树的语法制导定义 （１１７） …
４．２．３ Ｓ属性的自下而上计算 （１１９） …………
４．３ Ｌ属性定义的自上而下计算 （１２１） ………
４．３．１ Ｌ属性定义 （１２２） ………………………
４．３．２ 翻译方案 （１２２） ………………………
４．３．３ 预测翻译器的设计 （１２６） ……………
４．３．４ 用综合属性代替继承属性 （１２８） ……
４．４ Ｌ属性的自下而上计算 （１２９） ……………
４．４．１ 删除翻译方案中嵌入的动作 （１２９） …
４．４．２ 分析栈上的继承属性 （１３０） …………
４．４．３ 模拟继承属性的计算 （１３２） …………
４．５ 递归计算 （１３５） ……………………………
４．５．１ 自左向右遍历 （１３６） …………………
４．５．２ 其他遍历方法 （１３７） …………………
４．５．３ 多次遍历 （１３８） ………………………
习题４ （１４０） ………………………………………
第５章 类型检查 （１４３） ………………………
５．１ 类型在程序设计语言中的作用 （１４４） ……
５．１．１ 引言 （１４４） ……………………………
５．１．２ 执行错误和安全语言 （１４５） …………
５．１．３ 类型化语言的优点 （１４７） ……………
５．２ 描述类型系统的语言 （１４８） ………………
５．２．１ 定型断言 （１４９） ………………………
５．２．２ 定型规则 （１５０） ………………………
５．２．３ 类型检查和类型推断 （１５１） …………
５．３ 简单类型检查器的说明 （１５１） ……………
５．３．１ 一个简单的语言 （１５２） ………………
５．３．２ 类型系统 （１５２） ………………………
５．３．３ 类型检查 （１５４） ………………………
５．３．４ 类型转换 （１５６） ………………………
＊５．４ 多态函数 （１５７） ……………………………
５．４．１ 为什么要使用多态函数 （１５７） ………
５．４．２ 类型变量 （１５８） ………………………
５．４．３ 一个含多态函数的语言 （１６０） ………
５．４．４ 代换、实例和合一 （１６１） ………………
５．４．５ 多态函数的类型检查 （１６２） …………
５．５ 类型表达式的等价 （１６７） …………………
５．５．１ 类型表达式的结构等价 （１６８） ………
５．５．２ 类型表达式的名字等价 （１６９） ………
５．５．３ 记录类型 （１７０） ………………………
５．５．４ 类型表示中的环 （１７１） ………………
５．６ 函数和算符的重载 （１７２） …………………
５．６．１ 子表达式的可能类型集合 （１７２） ……
５．６．２ 缩小可能类型的集合 （１７４） …………
习题５ （１７５） ………………………………………
· ２ · 目 录
第６章 运行时存储空间的组织
和管理 （１８１） ……………………………
６．１ 局部存储分配策略 （１８１） …………………
６．１．１ 过程 （１８２） ……………………………
６．１．２ 名字的作用域和绑定 （１８２） …………
６．１．３ 活动记录 （１８３） ………………………
６．１．４ 局部数据的安排 （１８４） ………………
６．１．５ 程序块 （１８５） …………………………
６．２ 全局存储分配策略 （１８７） …………………
６．２．１ 运行时内存的划分 （１８７） ……………
６．２．２ 静态分配 （１８８） ………………………
６．２．３ 栈式分配 （１９０） ………………………
６．２．４ 堆式分配 （１９６） ………………………
６．３ 非局部名字的访问 （１９７） …………………
６．３．１ 无过程嵌套的静态作用域 （１９８） ……
６．３．２ 有过程嵌套的静态作用域 （１９８） ……
６．３．３ 动态作用域 （２０２） ……………………
６．４ 参数传递 （２０３） ……………………………
６．４．１值调用 （２０３） ……………………………
６．４．２ 引用调用 （２０４） ………………………
６．４．３ 复写－恢复调用 （２０４） ………………
６．４．４ 换名调用 （２０５） ………………………
习题６ （２０６） ………………………………………
第７章 中间代码生成 （２１５） …………………
７．１ 中间语言 （２１５） ……………………………
７．１．１ 后缀表示 （２１５） ………………………
７．１．２ 图形表示 （２１６） ………………………
７．１．３ 三地址代码 （２１７） ……………………
７．２ 声明语句 （２１９） ……………………………
７．２．１ 过程中的声明 （２１９） …………………
７．２．２ 作用域信息的保存 （２１９） ……………
７．２．３ 记录的域名 （２２２） ……………………
７．３ 赋值语句 （２２３） ……………………………
７．３．１ 符号表中的名字 （２２３） ………………
７．３．２ 临时名字的重新使用 （２２４） …………
７．３．３ 数组元素的地址计算 （２２５） …………
７．３．４ 数组元素地址计算的
翻译方案 （２２６） ………………………
７．３．５ 类型转换 （２３０） ………………………
７．４ 布尔表达式和控制流语句 （２３１） …………
７．４．１ 布尔表达式的翻译 （２３２） ……………
７．４．２ 控制流语句的翻译 （２３３） ……………
７．４．３ 布尔表达式的控制流翻译 （２３５） ……
７．４．４ 开关语句的翻译 （２３７） ………………
７．４．５ 过程调用的翻译 （２４０） ………………
习题７ （２４１） ………………………………………
第８章 代秒生成 （２４５） ………………………
８．１ 代码生成器设计中的问题 （２４５） …………
８．１．１ 目标程序 （２４５） ………………………
８．１．２ 指令选择 （２４６） ………………………
８．１．３ 寄存器分配 （２４７） ……………………
８．１．４ 计算次序选择 （２４７） …………………
８．２ 目标机器 （２４８） ……………………………
８．２．１ 目标机器的指令系统 （２４８） …………
８．２．２ 指令的代价 （２４９） ……………………
８．３ 基本块和流图 （２５１） ………………………
８．３．１ 基本块 （２５１） …………………………
８．３．２ 基本块的变换 （２５３） …………………
８．３．３ 流图 （２５４） ……………………………
８．３．４ 下次引用信息 （２５５） …………………
８．４ 一个简单的代码生成器 （２５６） ……………
８．４．１ 寄存器描述和地址描述 （２５６） ………
８．４．２ 代码生成算法 （２５７） …………………
８．４．３ 寄存器选择函数 （２５８） ………………
８．４．４ 为变址和指针语句产生代码 （２５９） …
８．４．５ 条件语句 （２６０） ………………………
习题８ （２６１） ………………………………………
＊第９章 代码优化 （２６９） ……………………
９．１ 优化的主要种类 （２６９） ……………………
９．１．１ 代码改进变换的标准 （２６９） …………
９．１．２ 公共子表达式删除 （２７２） ……………
９．１．３ 复写传播 （２７３） ………………………
· ３ · 目 录
９．１．４ 死代码删除 （２７４） ……………………
９．１．５ 代码外提 （２７５） ………………………
９．１．６ 强度削弱和归纳变量删除 （２７５） ……
９．１．７ 优化编译器的组织 （２７６） ……………
９．２ 流图中的循环 （２７８） ………………………
９．２．１ 必经结点 （２７８） ………………………
９．２．２ 自然循环 （２７９） ………………………
９．２．３ 前置结点 （２８０） ………………………
９．２．４ 可归约流图 （２８０） ……………………
９．３ 全局数据流分析介绍 （２８１） ………………
９．３．１ 点和路径 （２８２） ………………………
９．３．２ 到达－定值 （２８３） ……………………
９．３．３ 可用表达式 （２８６） ……………………
９．３．４ 活跃变量分析 （２８９） …………………
９．４ 代码改进变换 （２９０） ………………………
９．４．１ 公共子表达式删除 （２９１） ……………
９．４．２ 复写传播 （２９２） ………………………
９．４．３ 寻找循环不变计算 （２９４） ……………
９．４．４ 代码外提 （２９４） ………………………
９．４．５ 归纳变量删除 （２９７） …………………
习题９ （３００） ………………………………………
第１０章 编译系统和运行系统 （３０６） ………
１０．１ Ｃ语言的编译系统 （３０６） …………………
１０．１．１ 预处理器 （３０７） ………………………
１０．１．２ 汇编器 （３０８） …………………………
１０．１．３ 连接器 （３１０） …………………………
１０．１．４ 目标文件的格式 （３１１） ………………
１０．１．５ 符号解析 （３１３） ………………………
１０．１．６ 静态库 （３１４） …………………………
１０．１．７ 可执行目标文件及装入 （３１６） ………
１０．１．８ 动态连接 （３１７） ………………………
１０．１．９ 处理目标文件的一些工具 （３１９） ……
１０．２ Ｊａｖａ语言的运行系统 （３１９） ………………
１０．２．１ Ｊａｖａ虚拟机语言简介 （３２０） …………
１０．２．２ Ｊａｖａ虚拟机 （３２１） ……………………
１０．２．３ 即时编译器 （３２２） ……………………
＊１０．３ 无用单元收集 （３２４） ………………………
１０．３．１ 标记和清扫 （３２５） ……………………
１０．３．２ 引用计数 （３２６） ………………………
１０．３．３ 拷贝收集 （３２７） ………………………
１０．３．４ 分代收集 （３２８） ………………………
１０．３．５ 渐增式收集 （３３０） ……………………
１０．３．６ 编译器与收集器之间
的相互影响 （３３０） ……………………
习题１０ （３３４） ……………………………………
＊第１１章 面向对象语言的编译 （３３７） ……
１１．１ 面向对象语言的概念 （３３７） ………………
１１．１．１ 对象和对象类 （３３７） …………………
１１．１．２ 继承 （３３８） ……………………………
１１．１．３ 信息封装 （３４１） ………………………
１１．２ 方法的编译 （３４１） …………………………
１１．３ 继承的编译方案 （３４４） ……………………
１１．３．１ 单一继承的编译方案 （３４５） …………
１１．３．２ 重复继承的编译方案 （３４７） …………
习题１１ （３５２） ……………………………………
＊第１２章 函数式语言的编译 （３５５） ………
１２．１ 函数式程序设计语言简介 （３５５） …………
１２．１．１ 语言构造 （３５５） ………………………
１２．１．２ 参数传递机制 （３５７） …………………
１２．１．３ 变量的自由出现和约束
出现 （３５８） ……………………………
１２．２ 函数式语言的编译简介 （３６０） ……………
１２．２．１ 几个受启发的例子 （３６０） ……………
１２．２．２ 编译函数 （３６２） ………………………
１２．２．３ 环境与约束 （３６３） ……………………
１２．３ 抽象机的系统结构 （３６４） …………………
１２．３．１ 抽象机的栈 （３６５） ……………………
１２．３．２ 抽象机的堆 （３６６） ……………………
１２．３．３ 名字的寻址 （３６６） ……………………
１２．３．４ 约束的建立 （３６８） ……………………
１２．４ 指令集和编译 （３６９） ………………………
１２．４．１ 表达式 （３６９） …………………………
· ４ · 目 录
１２．４．２ 变量的引用性出现 （３７１） ……………
１２．４．３ 函数定义 （３７２） ………………………
１２．４．４ 函数应用 （３７３） ………………………
１２．４．５ 构造和计算闭包 （３７６） ………………
１２．４．６ ｌｅｔｒｅｃ表达式和局部变量 （３７８） ………
习题１２ （３８０） ……………………………………
参考文献 （３８２）
评论