编译程序设计算法PDF电子书下载

1.1　编译程序的基本概念 1

1.2　编译程序的结构 1

1.2.1　编译程序的翻译过程 1

第1章　绪论 1

1.2.2　遍 3

1.2.3　编译程序的基本构成 4

1.3　预备知识 5

1.3.1　字符串 5

1.3.2　集合运算 5

1.3.3　关系 6

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

2.1　有穷状态自动机 7

2.2　非确定性有穷状态自动机（NFA） 9

2.3　带有ε弧的非确定性有穷状态自动机 11

2.4　从NFA到DFA的转换 12

2.4.2　子集构造 13

2.4.1　状态集合的ε－闭包 13

2.5　DFA的化简 15

2.5.1　删除不可达状态的算法 16

2.5.2　识别并合并等价状态 16

2.5.3　删除死状态的算法 18

2.6　正则集与正则表达式 18

2.7　正则表达式与有限自动机 19

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

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

2.8　词法分析器的设计 23

2.8.1　词法分析器的设计步骤 23

2.8.2　正则表达式的LEX约定 24

2.8.3　LEX输入文件的格式 25

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

3.1　语法分析 28

3.2　上下文无关文法 28

3.2.2　推导树 29

3.2.1 推导 29

3.3　上下文无关文法的化简 32

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

3.3.2　ε－产生式和可空非终结符 35

3.3.3　消除单位产生式 37

3.3.4　消除左递归 38

3.4　正则文法 39

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

4.1 自顶向下的语法分析方法 42

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

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

4.2.2　例题 55

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

5.1　右句型中的句柄 61

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

5.3　LR语法分析器 63

5.3.1　扩展文法 65

5.3.2　寻找LR（0）项目集规范族的算法 68

5.3.3　SLR（1）语法分析器的Action表和Goto表 73

5.3.4　计算LR（1）项目集规范族的算法 79

5.3.5　LR（1）语法分析器的Action | Goto表 80

5.3.6　LALR的语法分析表 82

5.3.7　语法分析器的冲突 85

5.3.8　处理二义性文法 87

5.4.1　Action表的数据结构 90

5.4　语法分析表的数据结构 90

5.4.2　Goto表的数据结构 91

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

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

6.1　翻译规范 92

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

6.2.1　综合属性 93

6.2.2　继承属性 94

6.2.3　虚拟综合属性 95

6.4　语法制导翻译方案 96

6.3　L－属性定义 96

6.5　生成中间代码 97

6.5.1　后缀表示法 97

6.5.2　语法树 97

6.5.3　三地址代码 98

6.6　三地址语句表示 99

6.6.1　四元式表示 99

6.6.2　三元式表示 99

6.6.3　间接三元式表示 100

6.6.4 比较 100

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

6.7.1　算术表达式 100

6.7.2　布尔表达式 103

6.7.3　逻辑表达式的短路代码 106

6.8　递增和递减运算符的实现 114

6.9　数组引用 115

6.10　SWITCH/CASE 118

6.11　过程调用 122

6.12　举例 122

第7章　符号表管理 126

7.1 符号表 126

7.2　添加信息到符号表中 126

7.3　组织符号表的方法 127

7.3.1　线性表 127

7.3.3　哈希表 128

7.3.2　查找树 128

7.4　描述符号表中的域信息 129

第8章　存储管理 131

8.1　存储分配 131

8.3　静态分配 132

8.2　过程激活与活动记录 133

8.4　堆栈分配 133

8.4.1　调用和返回顺序 133

8.4.2　访问非局部名字 134

8.4.3　设置访问链 136

9.1　错误恢复 138

9.2　词法阶段的错误恢复 138

第9章　出错处理 138

9.3　语法阶段的错误恢复 139

9.4　LR分析中的错误恢复 139

9.5　YACC中的自动错误恢复 141

9.6　预测性分析的错误恢复 141

9.7　语义错误恢复 143

10.2　循环优化 144

第10章　代码优化 144

10.1　什么是代码优化 144

10.2.1　消除循环不变量的计算 145

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

10.2.3　寻找循环 147

10.2.4　寻找回边 147

10.2.5　可化简的流图 147

10.3　消除归纳变量 154

10.4　删除本地公共子表达式 157

10.5　删除全局公共子表达式 159

10.6　打开循环 160

10.7　循环拥塞 161

第11章　代码生成 163

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

11.2　目标机器模型 164

11.3　直接代码生成 165

11.4.1　启发式DAG排序算法 168

11.4　DAG的目标代码生成 168

11.4.2　标记算法 170

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

11.6　窥孔优化 177

11.6.1　冗余存取 177

11.6.2　控制流程优化 178

11.6.3　删除不可达代码 178

11.6.4　代数简化 179

11.6.5　强制削弱 179