第1章 字符串、语言和编译器 1
1.1概述 1
1.2语言的基本概念 1
1.3编译器的基本概念 2
1.4集合论中的基本概念 4
1.5空串 6
1.6连接 6
1.7指数记法 6
1.8星运算符（也称为0次或多次运算符） 7
1.9串集合的连接 8
1.10加运算符（也称为1次或多次运算符） 9
1.11问号运算符（也称为0次或1次运算符） 10
1.12包含单独一个串的集合的简便记法 10
1.13运算符优先级 11
1.14正规表达式 11
1.15 正则表达式的局限性 13
问题 14
第2章 上下文无关文法（一） 16
2.1概述 16
2.2什么是上下文无关文法 17
2.3基于上下文无关文法的推导 18
2.4由上下文无关文法定义的语言 19
2.5上下文无关文法的不同表示方法 21
2.6一些简单文法 22
2.7基于上下文无关文法的语言生成技术 25
2.8正规文法和右线性文法 30
2.9基于正规文法的计数 32
2.10表的文法 33
2.11一个不是上下文无关的重要语言 38
问题 39
第3章 上下文无关文法（二） 42
3.1概述 42
3.2语法分析树 42
3.3最左和最右推导 43
3.4替换 45
3.5二义文法 46
3.6确定可致空的非终结符 51
3.7消除λ产生式 52
3.8消除unit产生式 55
3.9消除无用非终结符 57
3.10递归转换 62
3.11增加空串到语言 67
问题 68
第4章 上下文无关文法（三） 73
4.1概述 73
4.2算术表达式文法 73
4.3文法中结合性和优先级的描述 78
4.4 Backus-Naur范式 80
4.5语法图 82
4.6抽象语法树和三地址码 84
4.7非收缩文法 85
4.8基本非收缩文法 85
4.9上下文无关文法到基本非收缩文法的转换 86
4.10上下文无关语言的pumping特性 88
问题 92
第5章Chomsky层次（选讲） 94
5.1概述 94
5.2上下文有关产生式 95
5.3上下文有关文法 96
5.4非受限文法 98
问题 98
第6章 自上而下语法分析 100
6.1概述 100
6.2自上而下构造语法分析树 100
6.3失败的语法分析 102
6.4不适合自上而下语法分析的文法 102
6.5确定的语法分析器 103
6.6借助栈的语法分析器 104
6.7用表来表示栈式语法分析器 109
6.8处理不以终结符领头的产生式 109
6.9用Java写一个栈式语法分析器 110
问题 117
第7章LL（1）文法 120
7.1概述 120
7.2产生式右端的FIRST集合 120
7.3确定操作序列 122
7.4确定λ产生式的选择集合 124
7.5后跟-左端-后跟-最右规则 127
7.6右端可致空的产生式的选择集合 129
7.7包含输入结束符的选择集合 130
7.8针对含lambda产生式文法的栈式语法分析器 133
7.9将非LL（1）文法转换为LL（1）文法 134
7.10用二义文法进行分析 141
7.11计算FIRST和FOLLOW集合 143
问题 145
第8章 表驱动的栈式语法分析器（选讲） 151
8.1概述 151
8.2统一栈式语法分析器的操作 152
8.3实现表驱动的栈式语法分析器 154
8.4表驱动栈式语法分析器的改进 159
8.5不确定的语法分析器——偏向理论的内容（选讲） 160
问题 162
第9章 递归-下降语法分析 164
9.1概述 164
9.2一个简单的递归-下降语法分析器 164
9.3处理lambda产生式 171
9.4一个公共错误 175
9.5产生式的Java代码 176
9.6递归-下降语法分析器中提取左公因子 177
9.7消除尾递归 182
9.8翻译星号、加号和问号算符 185
9.9反向动作 187
问题 189
第10章 递归-下降翻译 192
10.1概述 192
10.2一个简单的翻译文法 192
10.3转换翻译文法到Java代码 193
10.4翻译文法的描述 195
10.5在语法分析过程中传递信息 207
10.6 L-属性文法 213
10.7个新的单词符号管理器 214
10.8解决单词符号向前一个字符看问题 217
10.9新单词符号管理器的代码 217
10.10前缀表达式编译器的翻译文法 229
10.11趣用递归（选讲） 233
问题 236
第11章 汇编语言 239
11.1概述 239
11.2 J1计算机的结构 239
11.3机器语言指令 240
11.4汇编语言指令 242
11.5压入字符 242
11.6 aout指令 243
11.7使用标号 243
11.8使用汇编器 245
11.9 stav指令 248
11.10编译赋值语句 249
11.11编译print和println 252
11.12输出字符串 253
11.13输入十进制数 256
11.14入口指导语句 257
11.15 更多的汇编语言内容 257
问题 257
第12章 一个简单的编译器S 1 261
12.1概述 261
12.2源语言 261
12.3源语言的文法 262
12.4目标语言 263
12.5符号表 264
12.6代码生成器 264
12.7 token类 265
12.8写出翻译文法 265
12.9实现S1编译器 272
12.10使用S 1 287
12.11关于扩展S1编译器的忠告 290
12.11.1更新单词符号管理器 290
12.11.2先调试单词符号管理器 291
12.11.3选择集合 291
12.11.4使用必要的break语句 291
12.11.5使用必要的Consume方法调用 291
12.11.6正确地解释翻译文法 292
12.12对于S2的描述 292
问题 296
第13章JavaCC（选讲） 302
13.1概述 302
13.2 JavaCC中扩展的正规表达式 303
13.3 JavaCC输入文件 308
13.4正规表达式动作描述 315
13.5 S1j的JavaCC输入文件 318
13.6 JavaCC产生的文件 326
13.7使用星号和加号操作 330
13.8选择点和向前看 333
13.9 JavaCC的选择算法 338
13.10语法和语义的向前看描述（选讲） 342
13.11用JavaCC仅生成单词符号管理器 344
13.12使用单词符号链 346
13.13抑制警告信息 349
问题 350
第14章在S2基础上构造 354
14.1概述 354
14.2扩展println和print 354
14.3级联赋值语句 359
14.4一元加和减 362
14.5 readint语句 365
14.6从命令行控制单词符号踪迹的生成 365
14.7 S3的规范 366
问题 366
第15章 编译控制结构 370
15.1概述 370
15.2 while语句 370
15.3 if语句 374
15.4 do-while语句 377
15.5数字常量的范围检查 378
15.6处理字符串中的反斜线-引号 380
15.7用JavaCC处理反斜线（选讲） 381
15.8 JavaCC中的全局块（选讲） 386
15.9处理跨行字符串 388
15.10用JavaCC处理跨行字符串（选讲） 389
15.11 JavaCC中的SPECIAL TOKEN块（选讲） 394
15.12错误恢复 396
15.13 JavaCC中的错误恢复（选讲） 400
15.14 S4的规范 401
问题 402
第16章 编译函数形式的程序 405
16.1概述 405
16.2分别汇编和连接 405
16.3调用函数和从函数返回 408
16.4 S5的源语言 412
16.5 S5的符号表 413
16.6 S5的代码生成器 415
16.7 S5的翻译文法 416
16.8与库连接 427
16.9 S5规范 428
16.10扩展S5（选讲） 428
问题 430
第17章 有限自动机 433
17.1概述 433
17.2确定有限自动机 433
17.3转换DFA到正规表达式 435
17.4 DFA的Java代码 438
17.5非确定有限自动机 441
17.6使用NFA作为一个算法 443
17.7利用子集算法转换NFA到DFA 444
17.8转换DFA到正规文法 446
17.9转换正规文法到NFA 448
17.10转换正规表达式到NFA 449
17.11求出最小的DFA 452
17.12正规语言的泵理论 456
问题 457
第18章 课程设计项目：用编译技术实现grep 460
18.1概述 460
18.2 grep程序的正规表达式 461
18.3针对正规表达式的单词符号管理器 462
18.4正规表达式的文法 463
18.5正规表达式编译器的目标语言 465
18.6用NFA进行模式匹配 471
问题 474
第19章 编译到面向寄存器的结构 476
19.1概述 476
19.2使用寄存器指令集 477
19.3修改R1符号表 478
19.4 R1的语法分析器和代码生成器 480
问题 487
第20章 优化 488
20.1概述 488
20.2使用ldc指令 489
20.3重用临时变量 490
20.4常量合并 494
20.5寄存器分配 496
20.6窥孔优化 498
问题 502
第21章 解释器 506
21.1概述 506
21.2转换S1到11 507
21.3解释转移控制的语句 510
21.4实现编译：解释器CI 1 512
21.5解释器的优点 517
问题 517
第22章 自下而上语法分析 519
22.1概述 519
22.2自下而上语法分析原理 519
22.3语法分析：右递归文法对比左递归文法 522
22.4用二义文法进行自下而上语法分析 523
22.5不归约规则 526
22.6 SLR（1）语法分析 528
22.7移进/归约冲突 533
22.8归约/归约冲突 535
22.9 LR（1）语法分析 537
问题 540
第23章yacc 542
23.1概述 542
23.2 yacc输入和输出文件 542
23.3一个yacc-生成的简单语法分析器 543
23.4用取值栈传递值 551
23.5对二义文法使用yacc 556
23.6在语法分析树中传递值 559
23.7实现Sly 560
23.8 jflex 567
问题 574
附录A栈指令集 576
附录B寄存器指令集 580
参考文献 583