序言 1
1 引论 1
1.1 什么是编译程序 1
1.2 解释性程序 1
1.3 编译程序的基本结构 3
1.4 程序语言的语法与语义 8
1.5 程序设计语言设计、编译程序设计及计算机设计之间的关系 9
练习1 11
2 一个简单的编译程序 13
2.1 语言（XL）概述 13
2.2 XL的词法分析程序 14
2.3 XL递归下降分析 17
2.4 生成中间代码 20
2.4.1 中间语言 20
2.4.2 临时变量 20
2.4.3 动作符号 21
2.4.4 语义信息 22
练习2 25
3 词法分析 26
3.1 输入子系统 26
3.2 词法分析的两个途径 30
3.3 正规表达式 31
3.3.1 基本定义 32
3.3.2 正规表达式 33
3.4 有限自动机 35
3.5 从正规表达式到词法分析程序 38
3.6 LEX——一个建立词法分析器的自动工具 40
3.7 实践中的几个问题 48
3.7.1 保留字 48
3.7.2 向前看多字符问题 49
3.7.3 词法错误的矫正 50
3.8 正规表达式到有限自动机的转换 51
3.8.1 把正规表达式转换为NFA 51
3.8.2 从NFA到DFA的转换——子集构造法 55
3.8.3 DFA的优化——极小化 58
练习3 62
4 上下文无关文法与分析 65
4.1 基本概念与定义 65
4.2 推导与分析树 67
4.3 文法的设计 70
4.3.1 右线性文法 71
4.3.2 验证由文法生成的语言 72
4.3.3 消除歧义 73
4.3.4 递归文法 77
4.3.5 提左公因子 80
4.4 文法分析算法 81
4.4.1 空串非终结符 81
4.4.2 FIRST集合及其计算 82
4.4.3 FOLLOW集合及其计算 83
4.5 上下文无关文法的限度 85
练习4 86
5 LL（1）文法与分析器 89
5.1 自上而下分析与下推自动机 89
5.1.1 作为下推自动机的递归下降分析器 91
5.1.2 利用下推自动机进行自上而下的分析算法 92
5.2 LL（1）预测函数 93
5.3 LL（1）分析表 96
5.4 一个LL（1）分析表及驱动程序实例 97
5.5 LL的自动生成工具 100
5.5.1 LLama 100
5.5.2 LLGen 103
5.6 LL（1）文法的构造 106
5.7 自上而下分析中的查错恢复问题 108
练习5 110
6 LR分析 113
6.1 自下而上的分析过程——移入归约分析 113
6.2 利用状态机实现对LR分析器的控制 118
6.3 建立LR分析表的基本理论 124
6.3.1 LR（0）文法 124
6.3.2 SLR（1）文法 130
6.3.3 LR（1）文法 133
6.3.4 LALR（1）文法 138
6.4 LR分析表的压缩表示 146
6.5 歧义文法的利用 150
6.6 LR分析中的查错恢复问题 155
6.7 LALR（1）分析器的自动生成工具——YACC与OCCS 156
6.7.1 YACC程序 156
6.7.2 YACC中如何利用歧义文法 158
6.7.3 利用Lex建立YACC的词法分析程序 160
6.7.4 YACC中的查错恢复方法 161
练习6 162
7 语法制导的翻译 166
7.1 增广文法 166
7.2 属性文法 169
7.3 LL分析中的语义处理技术 174
7.3.1 表驱动的LL分析中使用的增广文法 174
7.3.2 下推自动机中属性文法的实施 174
7.3.3 LL中属性的＄表示法 175
7.4 LR分析中的语义处理技术 176
7.4.1 LR分析中属性处理的特点 176
7.4.2 一个LR语义处理流程的例子 177
7.4.3 建立LR分析用的属性文法及LR分析中属性的＄表示法 178
7.4.4 嵌入动作与语法变换 180
7.5 语义栈的类型描述 182
7.6 中间语言表示——IR 183
7.6.1 IR的一般形式 183
7.6.2 C代码：一种简单的中间语言与虚拟机 185
7.6.2.1 C虚拟机 185
7.6.2.2 C虚拟机的存储管理 186
7.6.2.3 C代码描述 187
练习7 195
8 符号表 196
8.1 符号表模块的基本结构 196
8.2 符号表数据库的数据结构 197
8.3 一个分程序结构的哈希符号表 201
8.3.1 基本数据结构 201
8.3.2 分程序结构 203
8.3.3 一种简单的分程序结构符号表的实现方法 204
8.3.4 符号表的高级维护层 205
练习8 211
9 运行时存储器的组织 214
9.1 静态分配 214
9.2 栈式分配 215
9.3 堆式分配 219
9.4 静态键与动态键 221
练习9 223
10 声明的语义处理技术 225
10.1 简单变量声明的处理 225
10.2 结构与联合声明的处理 232
10.3 枚举类型声明的处理 236
10.4 函数声明与定义的处理 238
10.5 分程序的处理 245
练习10 247
11 C代码生成器的接口gen（）子程序 249
练习11 259
12 表达式的语义处理 261
12.1 临时变量的分配 261
12.2 左值与右值 263
12.3 临时变量的表示——一种支持左右值实现的数据结构 268
12.4 单目运算符的语义处理 270
12.5 双目运算符的处理 279
练习12 284
13 控制语句的语义处理 286
13.1 简单控制语句的语义处理 287
13.2 条件语句的语义处理 288
13.3 循环语句break与continue语句的语义处理 290
13.4 switch语句的语义处理 294
练习13 299
14 代码优化 301
14.1 分析器的优化 301
14.2 线性（窥孔）优化 301
14.2.1 强度削减 302
14.2.2 常数折合与常数传播 303
14.2.3 死变量与死代码 305
14.2.4 窥孔优化之例 308
14.3 语法树上的优化 310
14.3.1 从逆波兰至语法树 310
14.3.2 公共子表达式节省 313
14.3.3 寄存器分配 316
14.3.4 局部循环优化 317
练习14 318
15 代码的生成 320
15.1 寄存器与临时单元的管理 320
15.2 一个简单的代码生成器 322
15.3 一个简单的寄存器分配方案 324
15.4 从树生成代码 329
15.5 代码生成器的自动化技术 332
15.5.1 基于文法的代码生成器 335
15.5.2 基于树重写的代码生成器的生成器 337
练习15 337
参考文献 340