编译原理与技术参考书介绍.doc

编译原理与技术的参考书介绍
1.1 编译原理 技术与工具（英文版）
1.1.1 书本信息
书    名
编译原理 技术与工具（英文版）

页数
796
作    者
Alfred V.Aho Ravi Se

开本
16
责任编辑
李际

字数
1009千字
出 版 社
人民邮电出版社

印张
50.75
出版时间
2002年2月第1版

页数
796
再版时间
2004年8月第5次

书号
09916
装    帧
平装

定价
63元

带盘
否

1.1.2 内容提要
    作为编译器设计的教程，本书重点主要放在解决在设计语言翻译器过程中所普遍面对的一些问题上而并不考虑源语言或者目标机器。本书共12章：第一章介绍了编译器的基本结构；第二章给出了一个将前缀表达式转换成后缀表达式的编译器，主要使用本书的一些基本技巧来构建；第三章阐述了词法分析、正则表达式、有限自动机和扫描生成器工具，这章中的技术广泛应用于文本处理；第四章详细阐述了主要的分析技术，从适合手工实现的递归下降算法到在分析生成器中使用的LR算法；第五章介绍了语法制导翻译中的主要思想，本书的其它部分都用本章来说明和实现翻译；第六章提出了完成静态语义检查的主要思想，并对类型检查和类型的统一进行了详细的讨论；第七章讨论了支持应用程序运行时环境的存储组织；第八章从中间语言的讨论开始，说明了编程语言结构翻译成中间代码；第九章阐述了目标代码的生成，包含基本的on_the_fly代码生成方法、为表达式生成代码的优化方法、Peephole优化和代码生成器；第十章是代码优化的总述。除了关于数据流分析方法的详细说明，还有关于如何进行全局优化的基本方法；第十一章讨论了在编译器实现过程中可能会产生的一些实际问题；第十二章提出一些使用本书中的技术构建的一些编译器的学习用例。    本书可作为高校计算机专业本科和研究生编译原理的教科书，也可供从事计算机软件开发的人员参考。

1.1.3 目录
第1章 编译器概述
1.1 编译器
1.2 源程序代码的分析
1.3 编译器的各个阶段
1.4 编译器的预处理器
1.5 阶段组合
1.6 编译器构造工具
小结：
编写编译器的规则和技术如此普遍，以至于书中的思想可以被计算机科学家在他们的工作生涯中多次使用。书写编译器覆盖了程序语言、机器系统结构、语言理论、算法和软件工程的内容。幸运的是，一些基本编译器技术可以用来为许多种类的语言和机器来构建翻译器。这一章中，我们通过描述编译器的各组成部分分别介绍了编译器的主题，编译器工作的环境，以及使得它较容易构造编译器的软件工具。

第2章 一个简单的一遍扫描编译器
2.1 概述
2.2 语法定义

2.3 语法制导翻译
2.4 分析
2.5 简单表达式的翻译机
2.6 词法分析
2.7 符号表
2.8 抽象的栈机器
2.9 将这些技术组合在一起
小结：
这一章是这本书3到8章内容的概述。它提出了一系列基本的编译技术，这些编译技术是通过能够将前缀表达式翻译成后缀表达式的C工作程序开发来实现的。重点放在编译器的前端上，也就是说放在词法分析、语法分析和中间代码的生成上。9、10章描述代码生成和优化。

第3章 词法分析
3.1 词法分析器的功能
3.2 输入缓冲（扫描处理）
3.3 标号说明
3.4 符号识别
3.5 识别词法分析器的语言
3.6 有穷自动机

3.7 从正则表达式到NFA
3.8 词法分析生成器的设计
3.9 基于DFA模式匹配的优化器
小结：
这一章处理识别和实现词法分析器的技术。构建词法分析器的最简单的一个方法是构建一个描述原语言标号结构的表。然后将这个图表手工翻译成搜索标号的程序。高效的词法分析器可以通过这种方式产生。
用来实现词法分析器的这种技术可以被应用到其它地方像查询语言和信息获取系统中。每一个应用程序中，最根本的问题就是执行由字符串中的模式引发的行为的程序说明和设计。由于模式导引的编程是非常有用的，我们引入一个叫做Lex的模式行为语言来说明词法分析器。在这种语言中，模式由正则表达式标志，Lex的编译器可以为正则表达式生成一个高效的有穷自动机识别器。
一些语言使用正则表达式来描述模式。举例来说，模式扫描语言AWK使用正则表达式来选择输入行进行处理，UNIX系统外壳允许用户通过书写正则表达式来引用一系列文件名字。举例来说，UNIX命令rm*.o，就是移走所有名字结尾为".o"的文件。
词法分析器自动构造的软件工具允许不同背景的人们在他们自己的应用程序领域中使用模式匹配。举例来说，Jarvis使用词法分析生成器创建了一个在印刷电路板上识别缺陷的程序。这个电路可以进行数字化扫描并能被转化成不同角度线段的"字符串"。词法分析器寻找那些同线段"字符串"中的缺陷相对应的模式。词法分析器生成器的主要优点是它使用的是最著名的模式匹配算法，因此为那些在模式匹配技术中并不是专家的人们创造了高效的词法分析。

第4章 文法分析
4.1 分析器的角色
4.2 上下文无关文法
4.3 编写一个文法
4.4 自顶向下的分析
4.5 自下而上的分析
4.6 算符优先算法的分析
4.7 LR分析算法
4.8 使用二义性文法
4.9 分析生成器
小结：
每一个编程语言都有一些描述已经形成的程序的语法结构的规则。Pascal中，举例来说，一个应用程序由块组成的，块由若干语句组成，语句由表达式组成，一个表达式由若干符号组成，等等。编程语言结构的语法可以通过上下文无关文法或者BNF标识来描述，文法为语言设计者和编译器书写者都提供了一些好处。
l 文法给了一个精确的，而且很容易理解的程序语言的文法规则。
l 从一个特定文法的一些类中我们可以自动构造一个高效的分析器来判断一个源程序在语法上结构是否是完整的。有一个额外的优点就是分析器构造过程可以显示出语法的二义性以及一些其它较难分析的结构，而那些结构很可能在一个语言和编译器的最初设计阶段是很难检查出来的。
l 恰当设计的文法将一个结构传给应用程序语言。这个程序语言对于将源程序翻译成正确的目标代码以及进行错误的检测都是非常有用的。工具有利于将基于文法的翻译描述转换成能用的应用程序。
l 随着时间的推移，语言增加了一些新的结构，同时又实现了一些别的工作。这些新的结构可以更容易地添加到语言中，特别是当存在一个基于语言文法描述的实现时。

这一章描述了编译器中使用的分析方法。我们提出的首先是基本概念；接着是适合手工实现的技术；最后是自动化工具中使用的算法。由于程序可能包含语法错误，我们扩展了这个分析方法以使它们能够从产生的普通错误中恢复。

第5章 语法制导翻译
5.1 语法制导定义
5.2 语法树的构造
5.3 S－属性定义的自下而上的求值
5.4 L－属性的定义
5.5 自顶向下的翻译
5.6 继承性属性自下而上的求值
5.7 递归求值
5.8 编译时属性值的空间
5.9 编译器构造时分配空间
5.10 语法制导定义的分析
小结：
这一章发展了2.3节的主题：上下文无关文法制导的语言翻译。我们将信息同程序语言构造联系起来，主要是通过将属性挂接到代表结构的文法象征上实现的。属性的值由同文法产生式相关联的语义规则来计算。
将语义规则同产生式联系要注意两点：语法制导的定义和翻译模式。语法制导定义是翻译的高层次的说明。它们隐藏了许多实现细节从而将用户从不得不明确说明翻译发生的序列中解脱出来。翻译模式表明语义规则求值的顺序，从而允许一些实现细节暴露出来。我们在第六章使用这两点来说明语义检查，特别是类型判断，而在第八章使用它们产生中间代码。
概念上，使用语法制导定义和翻译模式，我们将分析输入标号流，建立分析树，接着根据需要遍历树从而对分析树节点上的语义规则求值，将信息保存在符号表中，发布错误信息，或者完成其它一些动作。标号流的翻译是通过求值语义规则获得的结果。

语法制导翻译的概念视图
一个实现并不一定需要完全符合上图。语法制导定义的特例也可以通过一遍来实现。主要是通过对遍中的语义规则进行求值而不是明显的定义一个分析树或者一个图表来显示属性之间的依赖关系。由于一遍的实现对于编译的高效性有重要影响，这一章主要研究这些特例。一个重要的子类叫做L属性的算法包含了实际上所有的翻译，而这些翻译无需明确构造分析树就能实现的。

第6章 类型检查
6.1 类型系统
6.2 一个简单的类型检查器的说明
6.3 类型表达式的等价性
6.4 类型转换
6.5 函数和操作符的重载
6.6 多态函数
6.7 统一性的一个算法
小结：
编译器应该检查源程序是否遵循源语言的语法和语义。这种检查，叫做静态检查（将它同目标程序执行时的动态检查区分开来），保证了特定类型的程序错误将被检测和报告出来。静态检查的例子包括：
1 类型检查。比如如果一个操作符应用到一个不兼容的操作数中时，编译器应该报告出错；举例来说，如果一个数组变量和一个函数变量相加的话。
2 控制流检查。存在导致一个控制流离开构造器的语句。举例来说，C语言中的break语句将导致控制流离开最小的循环while，for和switch语句；如果这样一个包含语句不存在的话将导致错误。
3 唯一性检查。有些情况下一个对象只能被定义一次。举例来说，Pascal语言中，标识符应该被声明是唯一的，case语句中的标签也应该是唯一的。
4 相关名称检查。有时候，同样的名字会多次出现。举例来说，Ada中，循环或块中都将有一个名字同时出现在构造器的开始和结束。编译器将检查同样的名字可以在两端被使用。
这一章中，我们着重于类型检查。像上面的例子表示的，大多数静态检查都是惯例程序并且可以运用上一章的技术实现。其中的一些可以被集成到其它一些行为中。举例来说，当我们将名字的信息存到符号表中时。我们可以确定名字的声明是唯一的。许多Pascal编译器通过分析将静态检查和中间代码生成集成为一部分。对于更多的复杂的结构，就象Ada的，很可能是在分析和中间代码生成之间有一个独立的类型检查的遍比较方便。
类型检查核实结构的类型同它期待的环境相匹配。举例来说，Pascal中算术运算符mod需要整型操作数，因此一个类型检查器应该保证mod的操作数都是整数类型，同样的，类型检查器核实引用必须用到一个指针，索引只在数组上操作，而一个用户定义的函数应用时参数个数和类型必须正确等等。一个简单的类型检测器的规则出现在6.2。类型表示和什么时候两种类型匹配的问题将在6.3节讨论。
由类型检查器收集的类型信息可能是需要的特别是当生成代码的时候。举例来说，算术操作符像"＋"通常应用到每一个整数和实数上。也有其它类型的可能，而且我们不得不观察一下"＋"的上下文来决定它导向的意思。在不同的上下文中代表不同操作的符号叫做重载。重载伴随着强制类型转换，编译器提供了一个操作符将操作数转换成上下文期待的类型。
重载的明确概念就是多态。多态函数的主体是可以通过多种类型的参数来执行的。这一章还包括推断多态函数的类型的统一算法。

第7章 运行时环境
7.1 源语言问题
7.2 存储组织
7.3 存储分配策略
7.4 非局部名称的访问
7.5 参数传递
7.6 符号表
7.7 动态存储分配的语言工具
7.8 动态存储分配技术
7.9 Fortran中的动态存储分配
小结：
在考虑代码生成之前，我们需要将一个应用程序的静态源文本同运行时的行为联系起来来实现应用程序。随着执行代码的继续，源文本中的同一个名字在目标机器中可能意味着不同的数据对象。这儿就讨论名字和数据对象之间的关系。
数据对象的分配和回收由run-time support package进行管理，包括随生成的目标代码一起装载的例行程序。Run-time support package的设计受到过程的语义影响。像Fortran，Pascal和Lisp语言的支持包也可以使用本章中的技术来构建。
每一个程序的执行都可看作是这个过程的activation。如果一个程序是递归的，那么它的几个动作应该是同时被激活的。每一个过程的调用都有可能导致分配给它使用的数据对象的操作激活。
运行时数据对象的表示由它的类型决定。经常的，像字符，整数和实数这样的元素数据类型，就是由目标机器中等价的数据对象表示的。可是，像数组，字符串和结构等聚集，通常由原始对象的集合来表示。

第8章 中间代码的生成
8.1 中间语言
8.2 声明
8.3 分配语句
8.4 布尔表达式
8.5 Case语句
8.6 回填
8.7 过程调用
小结：
编译器分析合成的模型中，前端将源程序翻译成中间表示，然后后端生成目标代码。目标语言的细节尽可能地限制在后台。尽管一个源程序能被直接翻译成目标语言。但使用独立于机器的中间形式也是有好处的：
1. 有利于重定位；不同机器的编译器可以通过将新机器的后端挂接到现存的前端来创建。
2. 独立于机器的代码优化器可以被应用到中间代码的表示上。
这一章展示了第2章和第5章的语法制导方法如何将声明、赋值以及流控制语句等翻译成它们的中间形式的编程语言结构。而为简单起见，我们假定源程序已经通过编译和静态检查，大多数语法制导定义都能通过自下向上或者自上而下的分析来实现，因此中间代码生成可根据具体需要合成到分析里。

第9章 代码生成
9.1 代码生成器设计中的一些问题
9.2 目标机器
9.3 运行时存储管理
9.4 基本块和流程图
9.5 下一步要使用的信息
9.6 一个简单的代码生成器
9.7 寄存器分配
9.8 基本块的dag代表
9.9 Peephole 优化
9.10 从dags产生代码
9.11 动态编程代码生成算法
9.12 代码－生成生成器
小结：
编译器模型的最后阶段是代码生成器。它将源程序的中间表示作为输入，从而产生等价的目标程序作为输出。这章中使用的代码生成技术可以广泛应用，尽管在代码生成之前优化器阶段未必就会发生像在一些所谓的优化编译器中那样。这样的阶段企图将中间代码翻译成表单因此会产生更加有效的目标代码。代码优化将在下一章中详细讨论。
传统上对代码生成器的要求是很严格的。输出代码应该是正确的并具有较高的质量，这意味着能更好的利用目标机器的资源。还有，代码生成器本身是非常高效的。
可是数学上来说，生成优化代码的问题是不确定的。实际上，我们应该满足于启发式技术来产生较好的，并一定是最高效的代码。启发式的选择是重要的，特别是精心设计的代码生成算法能够很容易产生一些代码，它运行起来能比匆忙设计的算法产生的代码快好几倍。

第10章 代码优化
10.1 简介
10.2 优化的主要资源
10.3 基本块的优化
10.4 流程图的循环
10.5 介绍全局数据流分析
10.6 数据流方程的交互策略
10.7 代码优化的改造
10.8 处理别名
10.9 结构流图的数据流分析
10.10 高效的数据流算法
10.11 数据流分析的工具
10.12 类型的评估
10.13 优化代码的符号性调试
小结：
理想中，编译器应该产生像手写的一样好的目标代码。事实是这种目标只会在有限的用例中实现，而且难度还比较高。可是，直接编译算法产生的代码通常运行的比较快或者使用较少的空间，或者两个特征同时具备。这个改善是通过传统上叫做优化的程序改造来实现的，尽管"优化"这个术语是一个误导，因为实际上它很少能保证结果代码是尽可能优化的。应用代码优化改造的编译器叫做优化编译器。
本章重点是独立于机器的优化，程序改造无须考虑目标机器的任何属性就可以改善目标代码。而像寄存器分配和特殊的机器指令序列等这些依赖于机器的优化已经在9章中讨论了。
最少的努力获得最好的效果就是我们找出那些常用程序的执行部分，并使这些部分产生尽可能高的效果。有一个比较流行的说法：大多数的应用程序在10％的代码上花费了90％的执行时间。尽管实际的百分比会发生变化，通常情况下，小部分程序确会占据大多数的运行时间。从输入代表性数据看应用程序运行时的执行时间可准确地找出了问题的吃重运行区域。不幸的是，一个编译器通常没有输入数据的例子，因此它应该尽可能猜测问题热点所在。
实际上，应用程序的内在循环是改善应用程序的一个极好的侯选。在一个强调像while和for控制结构的语言中，循环从程序的语法角度看可能是非常明显的；通常情况下，一个叫作控制流分析的过程在程序的流程图中找出循环。
这章是一个有用的优化改造和实现它们的技术的丰富集合。编译器中进行什么样的改造是值得的决定这一点的最好的技术就是收集关于源程序的统计数据并且评估源程序典型例子上给定优化集合的好处。第12章描述了在对不同语言的编译器优化中证明是有用的改造。
这章的主题是数据流分析，一个收集应用程序中使用变量方法的信息的过程。一个应用程序中不同点收集的信息可以通过简单的集等价方程联合起来。我们展示了几个使用数据流分析收集信息的算法并在优化中高效使用这些信息。我们仍然考虑过程和指针等语言结构对优化的影响。

第11章 如何写编译器
11.1 规划一个编译器
11.2 编译器开发的方法
11.3 编译器开发环境
11.4 测试和维护
小结：
看了这些编译设计的原则，技术和工具，假定我们需要编写一个编译器：如果提前进行规划的话，我们可以进行的更快更好。这章提出了一些编译器构建中出现的实现问题。大多数讨论注意力集中在使用UNIX操作系统和它的工具来编写编译器上。

第12章 看一下一些编译器
12.1 排版数学的预处理器，即EQN
12.2 Pascal编译器
12.3 C编译器
12.4 Fortran H编译器
12.5 Bliss／11编译器
12.6 Modula－2优化编译器
小结：
讨论了Pascal、C、Fortran、Bliss和Modula 2的编译器。我们的意图并不是支持某项设计而排除其它的，而是企图描述编译器实现过程中可能出现的各种情况。

1.2 编译原理（英文版）
1.2.1 书本信息
书    名
编译原理

页数
524
作    者
[美]Alfred V.Aho等

开本
16
责任编辑
杨海玲

字数
千字
出 版 社
机械工业出版社

印张
34
出版时间
2003年8月第1版

页数
524
再版时间
2004年8月第4次

书号
111-12349-2
装    帧
平装

定价
55元

带盘
否
1.2.2 内容提要
　　本书深入讨论了编译器设计的重要主题，包括词法分析、语法分析、语法制导分析、类型检查、运行环境、中间代码生成、代码生成、代码优化等，并在最后两章中讨论了实现编译器的一些编程问题和几个编译器实例，每章都提供了大量的练习和参考文献。本书从介绍编译的原理性概念开始，然后通过构建一个简单的一遍编译器来逐一解释这些概念。 本书是编译原理课程的经典教材，作者曾多次使用本书的内容在贝尔实验室、哥伦比亚大学、普林斯顿大学和斯坦福大学向本科生和研究生讲授初等及高等编译课程。 本书作者Alfred V．Aho、Ravi Sethi和Jeffrey D．Ullman是世界著名的计算机 科学家，他们在计算机科学理论、数据库等很多领域都做出了杰出贡献。本书 是编译领域无可替代的经典著作，被广大计算机专业人士誉为“龙书”。本书一 直被世界各地的著名高等院校和科研机构(如贝尔实验室、哥伦比亚大学、普 林斯顿大学和斯坦福大学等)广泛用作本科生和研究生编译原理与技术课程的 教材，本书对我国计算机教育界也具有重大影响。 书中深入讨论了编译器设计的重要主题，包括词法分析、语法分析、语法制 导分析、类型检查、运行环境、中间代码生成、代码生成、代码优化等，并在 最后两章中讨论了实现编译器的一些编程问题和几个编译器实例，而且每章都 提供了大量的练习和参考文献。 本书可以作为高等院校计算机专业本科生和研究生编译原理与技术课程的 教材，也可以作为计算机技术人员必读的专业参考书之一。
1.2.3 目录
出版者的话
专家指导委员会
译者序
前言
第1章 编译简介 1
1.1 编译器 1
1.1.1 编译的分析-综合模型 1
1.1.2 编译器的前驱与后继 3
1.2 源程序分析 3
1.2.1 词法分析 3
1.2.2 语法分析 3
1.2.3 语义分析 5
1.2.4 文本格式器中的分析 5
1.3 编译器的各阶段 6
1.3.1 符号表管理 7
1.3.2 错误检测与报告 7
1.3.3 各分析阶段 7
1.3.4 中间代码生成 9
1.3.5 代码优化 9
1.3.6 代码生成 10
1.4 编译器的伙伴 10
1.4.1 预处理器 10
1.4.2 汇编器 11
1.4.3 两遍汇编 12
1.4.4 装配器和连接编辑器 12
1.5 编译器各阶段的分组 13
1.5.1 前端与后端 13
1.5.2 编译器的遍 13
1.5.3 减少编译的遍数 14
1.6 编译器的构造工具 14
参考文献注释 15
第2章 简单的一遍编译器 17
2.1 概述 17
2.2 语法定义 17
2.2.1 分析树 19
2.2.2 二义性 20
2.2.3 操作符的结合规则 20
2.2.4 操作符的优先级 21
2.3 语法制导翻译 22
2.3.1 后缀表示 22
2.3.2 语法制导定义 22
2.3.3 综合属性 23
2.3.4 深度优先遍历 24
2.3.5 翻译模式 25
2.3.6 翻译的输出 25
2.4 语法分析 26
2.4.1 自顶向下语法分析 27
2.4.2 预测分析法 29
2.4.3 何时使用产生式 30
2.4.4 设计一个预测语法分析器 30
2.4.5 左递归 31
2.5 简单表达式的翻译器 32
2.5.1 抽象语法和具体语法 32
2.5.2 调整翻译模式 33
2.5.3 非终结符expr、term 和rest 的过程 33
2.5.4 翻译器的优化 35
2.5.5 完整程序 35
2.6 词法分析 37
2.6.1 剔除空白符和注释 37
2.6.2 常数 37
2.6.3 识别标识符和关键字 37
2.6.4 词法分析器的接口 38
2.6.5 词法分析器 38
2.7 符号表 40
2.7.1 符号表接口 40
2.7.2 处理保留的关键字 41
2.7.3 符号表的实现方法 41
2.8 抽象堆栈机 42
2.8.1 算术指令 42
2.8.2 左值和右值 43
2.8.3 堆栈操作 43
2.8.4 表达式的翻译 43
2.8.5 控制流 44
2.8.6 语句的翻译 44
2.8.7 输出一个翻译 45
2.9 技术的综合 46
2.9.1 翻译器的描述 46
2.9.2 词法分析器模块lexer.c 47
2.9.3 语法分析器模块parser.c 48
2.9.4 输出模块emitter.c 48
2.9.5 符号表模块symbol.c和init.c 48
2.9.6 错误处理模块error.c 48
2.9.7 编译器的建立 48
2.9.8 程序清单 49
练习 53
编程练习 54
参考文献注释 55
第3章 词法分析 57
3.1 词法分析器的作用 57
3.1.1 词法分析中的问题 58
3.1.2 记号、模式、词素 58
3.1.3 记号的属性 59
3.1.4 词法错误 60
3.2 输入缓冲 60
3.2.1 双缓冲区 61
3.2.2 标志 62
3.3 记号的描述 62
3.3.1 串和语言 62
3.3.2 语言上的运算 63
3.3.3 正规表达式 64
3.3.4 正规定义 65
3.3.5 缩写表示法 66
3.3.6 非正规集 66
3.4 记号的识别 67
3.4.1 状态转换图 68
3.42 状态转换图的实现 70
3.5 词法分析器描述语言 72
3.5.1 Lex说明 72
3.5.2 超前扫描操作 75
3.6 有穷自动机 76
3.6.1 不确定的有穷自动机 77
3.6.2 确定的有穷自动机 78
3.6.3 从NFA到DFA的变换 79
3.7 从正规表达式到NFA 81
3.7.1 从正规表达式构造NFA 81
3.7.2 NFA的双堆栈模拟 84
3.7.3 时间空间的权衡 85
3.8 设计词法分析器的生成器 85
3.8.1 基于NFA的模式匹配 86
3.8.2 词法分析器的DFA 88
3.8.3 实现超前扫描操作 88

3.9 基于DFA的模式匹配器的优化 89
3.9.1 NFA的重要状态 89
3.9.2 从正规表达式到DFA 89
3.9.3 最小化DFA的状态数 93
3.9.4 词法分析器的状态最小化 95
3.9.5 表压缩方法 95
练习 97
编程练习 103
参考文献注释 103
第4章 语法分析 105
4.1 语法分析器的作用 105
4.1.1 语法错误的处理 106
4.1.2 错误恢复策略 108
4.2 上下文无关文法 109
4.2.1 符号的使用约定 110
4.2.2 推导 110
4.2.3 分析树和推导 112
4.2.4 二义性 113
4.3 文法的编写 113
4.3.1 正规表达式和上下文无关文法的
比较 114
4.3.2 验证文法所产生的语言 114
4.3.3 消除二义性 115
4.3.4 消除左递归 116
4.3.5 提取左因子 117
4.3.6 非上下文无关语言的结构 118
4.4 自顶向下语法分析 120
4.4.1 递归下降语法分析法 120
4.4.2 预测语法分析器 121
4.4.3 预测语法分析器的状态转换图 121
4.4.4 非递归的预测分析 123
4.4.5 FIRST和FOLLOW 124
4.4.6 预测分析表的构造 125
4.4.7 LL1)文法 126
4.4.8 预测分析的错误恢复 127
4.5 自底向上语法分析 128
4.5.1 句柄 129
4.5.2 句柄裁剪 130
4.5.3 用栈实现移动归约分析 131
4.5.4 活前缀 133
4.5.5 移动归约分析过程中的冲突 133
4.6 算符优先分析法 134
4.6.1 使用算符优先关系 135
4.6.2 从结合律和优先级获得算符优先
关系 136
4.6.3 处理一元操作符 137
4.6.4 优先函数 137
4.6.5 算符优先分析中的错误恢复 139
4.7 LR语法分析器 142
4.7.1 LR语法分析算法 142
4.7.2 LR文法 145
4.7.3 构造SLR语法分析表 146
4.7.4 构造规范LR语法分析表 151
4.7.5 构造LALR语法分析表 155
4.7.6 LALR语法分析表的有效构造
方法 158
4.7.7 LR语法分析表的压缩 161
4.8 二义文法的应用 163
4.8.1 使用优先级和结合规则来解决分析
动作的冲突 163
4.8.2 悬空else的二义性 164
4.8.3 特例产生式引起的二义性 165
4.8.4 LR语法分析中的错误恢复 167
4.9 语法分析器的生成器 168
4.9.1 语法分析器的生成器Yacc 169
4.9.2 用Yacc处理二义文法 171
4.9.3 用Lex建立Yacc的词法分析器 173
4.9.4 Yacc的错误恢复 174
练习 174
参考文献注释 182
第5章 语法制导翻译 185
5.1 语法制导定义 185
5.1.1 语法制导定义的形式 186
5.1.2 综合属性 186
5.1.3 继承属性 187
5.1.4 依赖图 187
5.1.5 计算顺序 189
5.2 语法树的构造 189
5.2.1 语法树 190
5.2.2 构造表达式的语法树 190
5.2.3 构造语法树的语法制导定义 191
5.2.4 表达式的无环有向图 192
5.3 自底向上计算S属性定义 194
5.4 L属性定义 195
5.4.1 L属性定义 196
5.4.2 翻译模式 196
5.5 自顶向下翻译 198
5.5.1 从翻译模式中消除左递归 198
5.5.2 预测翻译器的设计 201
5.6 自底向上计算继承属性 202
5.6.1 删除嵌入在翻译模式中的动作 202
5.6.2 分析栈中的继承属性 203
5.6.3 模拟继承属性的计算 204
5.6.4 用综合属性代替继承属性 206
5.6.5 一个难计算的语法制导定义 207
5.7 递归计算 207
5.7.1 从左到右遍历 207
5.7.2 其他遍历方法 208
5.8 编译时属性值的空间分配 209
5.8.1 在编译时为属性分配空间 209
5.8.2 避免复制 211
5.9 编译器构造时的空间分配 211
5.9.1 从文法中预知生存期 212
5.9.2 不相重叠的生存期 214
5.10 语法制导定义的分析 215
5.10.1 属性的递归计算 216
5.10.2 强无环的语法制导定义 216
5.10.3 环形检测 217
练习 219
参考文献注释 221
第6章 类型检查 223
6.1 类型系统 224
6.1.1 类型表达式 224
6.1.2 类型系统 225
6.1.3 静态和动态类型检查 226
6.1.4 错误恢复 226
6.2 一个简单的类型检查器的说明 226
6.2.1 一种简单语言 226
6.2.2 表达式的类型检查 227
6.2.3 语句的类型检查 228
6.2.4 函数的类型检查 228
6.3 类型表达式的等价 229
6.3.1 类型表达式的结构等价 229
6.3.2 类型表达式的名字 231
6.3.3 类型表示中的环 232
6.4 类型转换 233
6.5 函数和运算符的重载 234
6.5.1 子表达式的可能类型的集合 235
6.5.2 缩小可能类型的集合 236
6.6 多态函数 237
6.6.1 为什么要使用多态函数 237
6.6.2 类型变量 238
6.6.3 包含多态函数的语言 239
6.6.4 代换、实例和合一 240
6.6.5 多态函数的检查 241
6.7 合一算法 244
练习 247
参考文献注释 251
第7章 运行时环境 253
7.1 源语言问题 253
7.1.1 过程 253
7.1.2 活动树 253
7.1.3 控制栈 255
7.1.4 声明的作用域 256
7.1.5 名字的绑定 256
7.1.6 一些问题 257
7.2 存储组织 257
7.2.1 运行时内存的划分 257
7.2.2 活动记录 258
7.2.3 编译时的局部数据布局 259
7.3 存储分配策略 260
7.3.1 静态存储分配 260
7.3.2 栈式存储分配 262
7.3.3 悬空引用 265
7.3.4 堆式存储分配 265
7.4 对非局部名字的访问 266
7.4.1 程序块 267
7.4.2 无嵌套过程的词法作用域 268
7.4.3 包含嵌套过程的词法作用域 269
7.4.4 动态作用域 274
7.5 参数传递 275
7.5.1 传值调用 275
7.5.2 引用调用 276
7.5.3 复制-恢复 277
7.5.4 传名调用 277
7.6 符号表 278
7.6.1 符号表表项 278
7.6.2 名字中的字符 279
7.6.3 存储分配信息 280
7.6.4 符号表的线性表数据结构 280
7.6.5 散列表 281
7.6.6 表示作用域的信息 283
7.7 支持动态存储分配的语言措施 285
7.7.1 垃圾单元 285
7.7.2 悬空引用 286
7.8 动态存储分配技术 287
7.8.1 固定块的显式分配 287
7.8.2 变长块的显式分配 287
7.8.3 隐式存储释放 288
7.9 Fortran语言的存储分配 288
7.9.1 COMMON区域中的数据 289
7.9.2 一个简单的等价算法 290
7.9.3 Fortran语言的等价算法 292
7.9.4 映射数据区 294
练习 294
参考文献注释 298
第8章 中间代码生成 299
8.1 中间语言 299
8.1.1 图表示 299
8.1.2 三地址码 300
8.1.3 三地址语句的类型 301
8.1.4 语法制导翻译生成三地址码 302
8.1.5 三地址语句的实现 303
8.1.6 表示方法比较：间址的使用 305
8.2 声明语句 305
8.2.1 过程中的声明语句 305
8.2.2 跟踪作用域信息 306
8.2.3 记录中的域名 308
8.3 赋值语句 309
8.3.1 符号表中的名字 309
8.3.2 临时名字的重用 310
8.3.3 寻址数组元素 311
8.3.4 数组元素寻址的翻译模式 312
8.3.5 赋值语句中的类型转换 314
8.3.6 记录域的访问 315
8.4 布尔表达式 315
8.4.1 翻译布尔表达式的方法 316
8.4.2 数值表示 316
8.4.3 短路代码 317
8.4.4 控制流语句 317
8.4.5 布尔表达式的控制流翻译 319
8.4.6 混合模式的布尔表达式 321
8.5 case语句 321
8.6 回填 323
8.6.1 布尔表达式 323
8.6.2 控制流语句 326
8.6.3 翻译的实现方案 326
8.6.4 标号和goto 327
8.7 过程调用 328
8.7.1 调用序列 328
8.7.2 一个简单的例子 328
练习 329
参考文献注释 331
第9章 代码生成 333
9.1 代码生成器设计中的问题 333
9.1.1 代码生成器的输入 333
9.1.2 目标程序 334
9.1.3 存储管理 334
9.1.4 指令选择 334
9.1.5 寄存器分配 335
9.1.6 计算次序的选择 336
9.1.7 代码生成方法 336
9.2 目标机器 336
9.3 运行时存储管理 338
9.3.1 静态分配 339
9.3.2 栈式分配 340
9.3.3 名字的运行地址 342
9.4 基本块和流图 343
9.4.1 基本块 343
9.4.2 基本块的变换 344
9.4.3 保结构变换 344
9.4.4 代数变换 345
9.4.5 流图 345
9.4.6 基本块的表示 345
9.4.7 循环 346
9.5 下次引用信息 346
9.5.1 计算下次引用信息 346
9.5.2 临时名字的存储分配 347
9.6 一个简单的代码生成器 347
9.6.1 寄存器描述符和