目录介绍
第1章概论1
1.1为什么学习编译1
1.2什么叫编译程序2
1.3编译过程概述3
1.3.1词法分析3
1.3.2语法分析4
1.3.3语义分析和中间代码生成5
1.3.4代码优化5
1.3.5目标代码生成6
1.4编译程序的构成7
1.4.1基本功能模块和辅助模块7
1.4.2符号表的组织与管理8
1.4.3错误诊断和报告8
1.5其他与编译有关的概念和技术9
1.5.1遍的概念9
1.5.2编译的前端和后端9
1.5.3编译程序的分类9
1.5.4编译技术和软件工具10
1.6如何开发编译程序11
1.6.1编译程序的自展技术11
1.6.2编译程序的移植技术12
1.6.3编译程序的自动生成技术13
1.7编译系统及其他相关程序13
第2章词法分析16
2.1词法分析器的设计16
2.1.1词法分析器的功能与输出16
2.1.2词法分析器与符号表18
2.1.3词法分析器的两种实现模式18
2.1.4词法错误的处理19
2.1.5输入的预处理19
2.1.6超前搜索和最长匹配20
2.2词法分析器的一种实现方法21
2.2.1状态转换图21
2.2.2基于状态转换图的词法分析器的实现23
2.3单词的表示形式与正规表达式26
2.3.1符号、符号串与符号串集合27
2.3.2正规表达式与正规集28
2.3.3扩展的正规表达式29
2.4单词的识别与有限自动机30
2.4.1确定的有限自动机31
2.4.2不确定的有限自动机33
2.4.3从NFA到DFA的等价变换34
2.4.4确定的有限自动机的最小化37
2.4.5从正规表达式到有限自动机40
2.4.6有限自动机在计算机中的表示43
2.5词法分析自动生成器Lex44
2.5.1Lex概述45
2.5.2Lex的语言与实现45
第3章程序语言的文法描述50
3.1文法及语言的形式定义51
3.1.1文法的形式定义52
3.1.2推导与归约53
3.1.3文法产生的语言54
3.1.4语言的验证55
3.1.5语言的文法表达56
3.2文法的性质和其他表示58
3.2.1分析树与语法树58
3.2.2文法的二义性60
3.2.3BNF与EBNF 63
3.3文法的分类65
3.3.10型文法——短语文法65
3.3.21型文法——上下文有关文法65
3.3.32型文法——上下文无关文法66
3.3.43型文法——正规文法67
3.4语法分析概述68
3.4.1自顶向下的语法分析69
3.4.2自底向上的语法分析70
3.4.3实际文法的使用限制和表示70
第4章自顶向下的语法分析75
4.1文法的等价变换75
4.1.1自顶向下语法分析的问题75
4.1.2文法等价的概念77
4.1.3增广文法77
4.1.4提取左公共因子78
4.1.5消除左递归78
4.1.6对上下文无关文法的期望80
4.2LL(1)文法及其分析81
4.2.1首符号集81
4.2.2?后继符号集83
4.2.3择符号集86
4.2.4LL(1)文法87
4.2.5LL(1)文法的分析89
4.3递归下降分析技术90
4.3.1递归下降分析器的设计90
4.3.2从EBNF构造递归下降分析器94
4.3.3递归下降分析的特点95
4.4预测分析技术95
4.4.1预测分析程序的工作过程95
4.4.2预测分析表的构造96
4.5LL(1)分析中的错误处理100
第5章自底向上的语法分析104
5.1自底向上语法分析概述104
5.1.1自底向上语法分析器的体系结构104
5.1.2规范归约和算符优先归约105
5.1.3短语、句柄和最左素短语107
5.2LR分析方法108
5.2.1LR分析概述109
5.2.2LR(0)分析表的构造112
5.2.3SLR分析表的构造118
5.2.4规范LR分析表的构造124
5.2.5LALR分析表的构造128
5.2.6LR分析方法小结130
5.3算符优先分析方法136
5.3.1算符优先文法137
5.3.2算符优先关系的构造138
5.3.3算符优先分析算法140
5.3.4算符优先函数及其构造142
5.4LALR分析器的生成工具YACC143
5.4.1YACC概述143
5.4.2YACC源程序144
5.4.3YACC解决二义性和冲突的方法146
5.4.4YACC对语法分析中的错误处理147
第6章符号表的组织和管理151
6.1符号表的作用151
6.2符号表的主要属性153
6.3符号表的组织结构155
6.3.1符号表的整体组织结构156
6.3.2关键码域的组织157
6.3.3不等长域的组织158
6.3.4符号表的操作与符号表项的组织159
6.4名字的作用范围162
6.4.1名字的声明162
6.4.2块结构与符号表的分层次管理163
6.4.3静态作用域和动态作用域165
第7章运行时环境167
7.1程序运行的基本概念167
7.1.1过程及其活动167
7.1.2活动记录169
7.1.3调用序列和返回序列169
7.1.4活动树170
7.1.5环境和名字的绑定170
7.2运行时存储空间的组织和管理171
7.2.1运行时存储空间的划分171
7.2.2存储分配策略172
7.3静态运行时环境173
7.4栈式运行时环境175
7.4.1局部数据的组织和访问175
7.4.2无过程嵌套的栈式运行时环境177
7.4.3有过程嵌套的栈式运行时环境178
7.5堆式运行时环境183
7.5.1堆式动态存储分配的实现184
7.5.2堆的自动管理185
7.6面向对象语言的运行时环境188
7.6.1面向对象语言的动态存储管理188
7.6.2Java运行时环境189
7.7参数传递机制191
7.7.1按值调用191
7.7.2引用调用191
7.7.3值-结果调用192
7.7.4换名调用193
第8章属性文法和语义分析199
8.1语义分析概况199
8.2属性与属性文法201
8.2.1属性的引入201
8.2.2属性文法的定义202
8.2.3属性文法的扩展与简化207
8.3属性的计算209
8.3.1属性依赖图和计算顺序209
8.3.2综合属性和继承属性及其计算212
8.3.3语法分析的同时计算属性217
8.4数据类型与类型检查224
8.4.1类型表达式与类型构造器225
8.4.2类型等价227
8.4.3类型检查230
8.4.4类型转换231
8.4.5类型检查的其他主题233
第9章语法制导的中间代码翻译237
9.1中间语言238
9.1.1后缀式239
9.1.2图形表示241
9.1.3字节代码243
9.1.4三地址代码及其四元式实现244
9.2声明语句的翻译247
9.2.1过程中的声明247
9.2.2保留声明的作用域信息248
9.2.3记录中的域名251
9.3赋值语句的翻译252
9.3.1简单算术表达式及赋值语句252
9.3.2数组元素的引用254
9.3.3记录和指针的引用259
9.3.4类型转换260
9.4基本控制结构的翻译261
9.4.1布尔表达式的翻译261
9.4.2控制流语句的多遍翻译模式264
9.4.3回填技术基础266
9.4.4控制流语句的单遍翻译模式269
9.5转向语句的翻译272
9.5.1标号语句与goto语句的翻译273
9.5.2出口语句的翻译273
9.5.3开关语句的翻译274
9.5.4过程调用的翻译276
第10章目标代码生成279
10.1代码生成器的设计的基本问题279
10.1.1目标程序280
10.1.2指令选择280
10.1.3寄存器分配280
10.1.4计算顺序的选择281
10.2虚拟计算机模型281
10.3语法制导的目标代码生成282
10.4基本块和待用信息285
10.4.1基本块及其构造285
10.4.2流图287
10.4.3待用信息288
10.5一个简单的代码生成器289
10.5.1寄存器和地址的描述290
10.5.2寄存器的分配原则与选择算法291
10.5.3代码生成算法291
10.5.4其他三地址语句的目标代码293
10.6代码生成技术小结294
10.7基于寄存器的虚拟机和栈式虚拟机295
第11章代码优化298
11.1代码优化的概念298
11.2代码优化的基本技术300
11.2.1删除公共子表达式302
11.2.2复写传播302
11.2.3删除无用代码303
11.2.4代码外提304
11.2.5强度削弱和删除归纳变量305
11.3局部优化306
11.3.1基本块的变换306
11.3.2基本块的DAG实现307
11.3.3基于DAG的局部优化310
11.4机器代码优化——窥孔技术311
11.4.1冗余存取的删除312
11.4.2不可达代码的删除312
11.4.3控制流优化313
11.4.4代数化简与强度削弱314
11.4.5特殊指令的使用314
11.5代码优化的其他技术简介314
参考文献319