本书主要介绍设计和构造高级语言编译程序中的基本原理及各种算法，重点描述了设计编译程序所涉及的各种算法。书中给出的算法涵盖了程序设计语言的文法及编译程序设计各个阶段的基本技术和主要算法。全书共分11章。第1章对编译程序进行了简要介绍，第2章、第3章介绍了有限自动机与正则表达式及上下文无关文法中的基本算法，第4章至第6章、第10章、第11章讲解了语法分析、语法制导的翻译、代码优化、代码生成等编译阶段中的基本技术和主要算法，第7章至第9章介绍了符号表管理、内存管理和出错处理的主要算法。书中采用类C语言描述了各种算法，并通过大量的例子来解释它们在编译程序设计中的具体应用。

第1章 绪论

编译程序的基本概念

编译程序的结构

编译程序的翻译过程

遍

编译程序的基本构成

预备知识

字符串

集合运算

关系

第2章 有穷状态自动机和正则表达式

有穷状态自动机

非确定性有穷状态自动机(NFA)

带有s弧的非确定性有穷状态自动机

从NFA到DFA的转换

状态集合的g一闭包

子集构造

DFA的化简

删除不可达状态的算法

识别并合并等价状态

删除死状态的算法

正则集与正则表达式

正则表达式与有限自动机

从正则表达式到有限自动机

从有限自动机到正则表达式

词法分析器的设计

词法分析器的设计步骤

正则表达式的LEX约定

LEX输入文件的格式

第3章 上下文无关文法和语法分析

语法分析

上下文无关文法

推导

推导树

上下文无关文法的化简

识别和删除无用文法符号的算法

e一产生式和可空非终结符

消除单位产生式

消除左递归

正则文法

第4章 自顶向下的语法分析

自顶向下的语法分析方法

带预测的自顶向下语法分析器

表驱动预测语法分析器的实现

例题

第5章 自底向上的语法分析

右句型中的句柄

自底向上的语法分析的实现

LR语法分析器

扩展文法

寻找LR(0)项目集规范族的算法

SLR(1)语法分析器的Action表和Goto表

计算LR(1)项目集规范族的算法

LR(1)语法分析器的ActionIGoto表

LALR的语法分析表

语法分析器的冲突

处理二义性文法

语法分析表的数据结构

Action表的数据结构

Goto表的数据结构

LR语法分析器的优点和缺点

第6章 语法制导的定义和翻译

翻译规范

通过语法制导定义实现指定翻译

综合属性

继承属性

虚拟综合属性

L-属性定义

语法制导翻译方案

生成中间代码

后缀表示法

语法树

三地址代码

三地址语句表示

四元式表示

三元式表示

间接三元式表示

比较

不同程序设计语言结构的语法制导翻译方案

算术表达式

布尔表达式

逻辑表达式的短路代码

递增和递减运算符的实现

数组引用

SWITC：H／CASE

过程调用

举例

第7章 符号表管理

符号表

添加信息到符号表中

组织符号表的方法

线性表

查找树

哈希表

描述符号表中的域信息

第8章 存储管理

存储分配

过程激活与活动记录

静态分配

堆栈分配

调用和返回顺序

访问非局部名字

设置访问链

第9章 出错处理

错误恢复

词法阶段的错误恢复

语法阶段的错误恢复

LR分析中的错误恢复

YACC中的自动错误恢复

预测性分析的错误恢复

语义错误恢复

第10章 代码优化

什么是代码优化

循环优化

消除循环不变量的计算

将三地址代码分成基本块的算法

寻找循环

寻找回边

可化简的流图

消除归纳变量

删除本地公共子表达式

删除全局公共子表达式

打开循环

循环拥塞

第11章 代码生成

高效代码生成中隐含的主要问题

目标机器模型

直接代码生成

DAG的目标代码生成

启发式DAG排序算法

标记算法

利用代数性质来减少寄存器的需要数量

窥孔优化

冗余存取

控制流程优化

删除不可达代码

代数简化

强制削弱