目　录

第 1章　绪论　1
1.1　汇编语言和高级程序设计语言　1
1.2　程序设计语言的编译技术　2
1.3　编译技术的基本构造与工作原理　4
1.4　程序设计语言的编译技术　7
1.4.1　词法分析　7
1.4.2　语法分析　8
1.4.3　语义分析　8
1.4.4　中间代码的生成　9
1.4.5　代码优化　10
1.4.6　目标代码生成　10
1.4.7　程序信息管理与错误检查和处理　11
1.5　编译程序的工作过程　11
1.6　文法及其分类　13
1.6.1　文法　13
1.6.2　文法及语言的Chomskey分类　15
1.6.3　规范推导　16
1.6.4　文法的二义性　17
1.7　本书内容简介　18
习题　18

第 2章　扫描器与正规语言　21
2.1　正规表达式　21
2.1.1　正规表达式代数　22
2.1.2　正规表达式的性质　22
2.2　有限状态自动机　24
2.3　非确定的有限状态自动机　26
2.4　将正规文法转换为自动机　27
2.5　NFDA的确定化及化简　29
2.6　从有限状态自动机转换到正规文法　35
2.7　有限自动机在计算机中的实现　36
2.8　扫描器实现中的特殊问题　37
2.8.1　输入符号表　37
2.8.2　扫描器自动机中的终止状态　37
2.8.3　删除空白符号与注释　38
2.8.4　输出单词　38
2.9　字符串表的实现　40
2.10　保留字　41
2.11　使用扫描器自动生成工具　41
2.12　例题解析　41
习题　43

第3章　语法分析与前后文无关文法　45
3.1　下推自动机　45
3.1.1　停机条件的等价性　46
3.1.2　从前后文无关文法CFG构造PDA　47
3.2　LL(k)规范文法　48
3.2.1　FIRST集与FOLLOW集　49
3.2.2　选择集合　50
3.3　文法的左递归性　51
3.4　公共左因子　52
3.5　用正规表达式运算符拓广CFG　52
3.6　递归下降分析程序　53
3.7　作为下推自动机的递归下降分析程序　54
3.8　自底向上的语法分析器的构造　56
3.8.1　自底向上的语法分析　56
3.8.2　LR(k)分析法　59
3.9　语法分析器生成工具简介　70
习题　71

第4章　语法制导的代码生成　73
4.1　常见的中间语言简介　73
4.1.1　逆波兰表示　73
4.1.2　四元式　74
4.1.3　其他表示法　75
4.2　赋值语句的翻译　75
4.3　布尔表达式的翻译　76
4.4　程序流程控制语句的翻译　81
4.4.1　常见控制结构的翻译　81
4.4.2　语句标号及GOTO语句的翻译　84
4.4.3　多分支语句的翻译　87
4.5　含数组元素的算术表达式及赋值语句的翻译　89
4.5.1　下标变量地址的计算　89
4.5.2　含有下标变量的赋值语句的翻译　91
4.6　过程说明和过程调用的翻译　93
4.6.1　过程说明的翻译　94
4.6.2　实参和形参间的信息传递　94
4.6.3　过程语句的翻译　95
4.6.4　关于形实结合的进一步讨论　96
4.7　说明语句的翻译　97
4.7.1　类型说明(变量及数组定义)语句的翻译　97
4.7.2　数据类型定义语句的翻译　99
习题　101

第5章　符号表　103
5.1　概述　103
5.2　符号表的内容、用途与创建过程　104
5.2.1　符号及其所表示的信息　104
5.2.2　符号表　105
5.2.3　符号表的用途　105
5.3　设计符号表时需要考虑的几个问题　107
5.4　符号表的创建和使用　108
5.4.1　符号表的创建及其在语义分析中的使用　108
5.4.2　符号表在内存分配和代码生成阶段的使用　109
5.5　符号表的数据结构与算法　110
5.5.1　符号表数据结构和算法的选择　110
5.5.2　哈希表设计　112
5.5.3　支持作用域的符号表　115
习题　122

第6章　静态与运行时的存储管理　124
6.1　可执行程序的产生和执行过程　124
6.2　可执行程序的存储布局与操作　126
6.3　内存管理技术：静态内存管理　128
6.4　动态内存管理　132
6.5　栈式内存管理　133
6.5.1　递归调用引起的问题　133
6.5.2　栈　134
6.5.3　活动树　136
6.5.4　栈模型和活动树模型的比较　140
6.5.5　栈式内存管理的基本思想和必须解决的问题　140
6.5.6　活动记录和调用序列　142
6.6　堆式管理和垃圾回收技术　152
习题　155

第7章　代码优化　157
7.1　概述　157
7.2　中间代码生成阶段的代码优化　157
7.3　代码优化的基本原则、思路和范围　158
7.4　基本块及其优化方法　159
7.4.1　基本块、基本块划分算法和控制流图　159
7.4.2　基于DAG模型的基本块优化技术　162
7.4.3　基于值编号技术的基本块优化算法　166
7.4.4　基本块中的其他优化　170
7.4.5　更大范围的优化　173
7.5　数据流分析　173
7.5.1　基于数据流分析的冗余表达式删除　174
7.5.2　活性分析　178
7.5.3　过程间数据流分析　182
7.6　循环优化　182
7.6.1　循环的识别　182
7.6.2　循环优化　185
习题　187

第8章　代码生成　189
8.1　代码生成的基本功能　189
8.2　代码生成的不同方式　189
8.3　代码生成的关键技术简介　190
8.3.1　代码生成技术需要考虑的内容　190
8.3.2　代码生成的关键技术　190
8.3.3　指令筛选技术简介　191
8.3.4　指令调度技术简介　198
8.3.5　寄存器分配技术简介　200
8.4　代码生成、软件调试和其他技术　202
习题　205

参考文献　206