目 录 1
第一章语言的基本知识 1
1.1基本定义 1
1.1.1文法的讨论 1
1.1.2字母表 5
1.1.3符号串 6
1.1.4文法和语言的形式定义 9
1.2分析树（parse tree）和二义性 18
1.2.1分析树 18
1.2.2子树 21
1.2.3二义性 23
1.3形式语言概观 27
练习 29
第二章编译概述 31
2.1翻译和解释 31
2.2编译程序的组成部分 33
2.3有关编译程序的设计与实现 37
第三章词法分析 42
3.1词法分析程序的功能 42
3.1.1单词符号的种别和属性 43
3.2输入缓冲 47
3.1.2词法分析程序作为一个独立子程序 47
3.3 正规表达式与正规集 51
3.4正规表达式与正规文法 55
3.5词法与正规文法 58
3.5.1文法的分解 58
3.5.2基本符号的文法 58
3.6状态转换图与基本符号的识别 63
3.6.1状态转换图 63
3.6.2状态转换图的实现 68
3.7有限自动机 71
3.7.1确定的有限自动机（DFA） 72
3.7.2非确定有限自动机（NFA） 75
3.7.3具有ε-转移的非确定有限自动机 78
3.7.4正规文法与有限自动机（FA）的等价性 82
3.7.5有限自动机与正规表达式的等价性 87
3.7.6确定有限自动机的化简 92
练习 97
第四章语法分析 100
4.1语法分析器的作用 100
4.2上下文无关文法 101
4.3.1关于消除二义性 105
4.3书写文法 105
4.3.2消除左递归 107
4.3.3提取左因子 112
4.4自顶向下分析 113
4.4.1递归下降分析方法 113
4.4.2预测分析器 116
4.4.3预测分析器的转换图 121
4.4.4非递归的预测分析方法 126
4.4.5函数FIRST和FOLLOW 129
4.4.6预测分析表的构造 132
4.4.7 LL（1）文法 133
4.4.8在预测分析法中的错误处理示例 134
4.5自底向上分析 137
4.5.1规范归约 137
4.5.2“移进－归约”分析法的栈实现 142
4.6算符优先分析法 146
4.6.1利用算符优先关系寻找右句型的可归约串 149
4.6.2算符优先关系表的构造 152
4.6.3优先函数 154
4.6.4算符优先分析法的错误处理示例 156
4.7.1 LR分析器的逻辑结构及工作过程 159
4.7 LR分析器 159
4.7.2 SLR分析表的构造 163
4.7.3LR（1）分析表的构造 178
4.7.4 LALR分析表的构造 185
4.8 LR分析法对二义文法的应用 197
练习 202
第五章语法制导翻译 208
5.1语法制导定义 209
5.1.1语法制导定义的形式 210
5.1.2综合属性 211
5.1.3继承属性 212
5.1.4依赖图 214
5.1.5计算顺序 217
5.2语法树（syntax tree）的构造 218
5.2.1语法树 219
5.2.2建立表达式的语法树 220
5.2.3建立语法树的语法制导定义 221
5.2.4关于表达式的有向非循环图 223
5.3 S-属性定义及其自底向上的计算 225
5.4 L-属性定义 229
5.4.1 L-属性定义 230
5.4.2翻译模式 231
5.5.1从翻译模式中消除左递归 236
5.5自顶向下的翻译 236
5.5.2预测翻译器的设计 242
5.6自底向上计算继承属性 244
5.6.1从翻译模式中去掉嵌入的动作 245
5.6.2分析栈中的继承属性 246
5.6.3模拟继承属性的计算 248
5.7递归求值 254
练习 262
6.1有关源语言中的一些问题的讨论 265
第六章运行时刻环境 265
6.1.1过程 266
6.1.2活动树 267
6.1.3控制栈 270
6.1.4说明的作用域 271
6.1.5名字的联编 272
6.1.6提出的问题 273
6.2存储组织 274
6.2.1运行时刻内存的划分 274
6.2.2活动记录 275
6.2.3编译时刻的局部数据的设计 277
6.3.1静态存储分配 278
6.3运行时刻存储分配策略 278
6.3.2栈式存储分配 282
6.3.3堆式存储分配 288
6.4对非局部名字的访问 289
6.4.1块 290
6.4.2不含嵌套过程的词法作用域 293
6.4.3含有嵌套过程的词法作用域 294
6.4.4动态作用域 301
6.5参数传递 303
6.5.1传值调用 304
6.5.2引用调用 305
6.5.3复制恢复 307
6.5.4传名调用 308
6.6符号表 309
6.6.1符号表的表项 309
6.6.2线性表（linear list） 312
6.6.3散列表 313
6.6.4表示作用域的信息 316
练习 319
第七章中间代码生成 324
7.1中间语言 324
7.1.1图表示法 324
7.1.2三地址代码 327
7.1.3三地址语句的种类 328
7.1.4语法制导翻译生成三地址代码 329
7.1.5三地址代码的具体实现 331
7.2说明语句 334
7.2.1过程中的说明语句 334
7.2.2保留作用域信息 336
7.2.3记录中的域名 339
7.3赋值语句 340
7.3.1符号表中的名字 340
7.3.2数组元素地址分配 342
7.3.3访问数组元素的翻译模式 345
7.3.4访问记录中的域 349
7.4布尔表达式 349
7.4.1翻译布尔表达式的方法 350
7.4.2数值表示法 350
7.4.3控制流语句 352
7.4.4控制流语句中的布尔表达式的翻译 355
7.5 CASE语句 358
7.6回填 359
7.6.1使用回填翻译布尔表达式 360
7.6.2使用回填翻译控制流语句 365
7.7过程调用 371
7.6.3标号和转移语句 371
练习 374
第八章代码生成 377
8.1目标机器 378
8.2运行存储管理 382
8.2.1静态分配管理 383
8.2.2栈式分配管理 385
8.2.3名字的运行地址 389
8.3基本块和流图 390
8.3.1基本块 390
8.3.2流图 392
8.4下次引用信息 393
8.5一个简单的代码生成器 395
8.5.1寄存器描述器和地址描述器 396
8.5.2代码生成算法 397
8.6基本块的dag表示法 402
8.6.1 dag的构造 405
8.6.2 dag的应用 407
8.7从dag生成目标代码 411
练习 415
参考文献 417