编译程序设计算法

第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排序算法
标记算法
利用代数性质来减少寄存器的需要数量
窥孔优化
冗余存取
控制流程优化
删除不可达代码
代数简化
强制削弱