目录 1
第0章 数学预备知识 1
0.1 集合论的一些概念 1
0.1.1 集合 1
0.1.2 集合的运算 3
0.1.3 关系 5
0.1.4 关系的闭包 7
0.1.5 次序关系 9
0.1.6 映射 11
习题 12
0.2.1 符号串 16
0.2 符号串的集合 16
0.2.2 语言 17
0.2.3 语言的运算 18
习题 20
0.3 逻辑的一些概念 21
0.3.1 证明 21
0.3.2 归纳证明 22
0.3.3 逻辑联结词 23
习题 24
文献注释 27
0.4 过程和算法 27
0.4.1 过程 28
0.4.2 算法 29
0.4.3 递归函数 30
0.4.4 过程的阐明 31
0.4.5 问题 32
0.4.6 波斯特对应问题 35
习题 36
文献注释 39
0.5 图论的一些概念 40
0.5.1 有向图 40
0.5.2 有向无圈图 43
0.5.3 树 43
0.5.4 有序图 45
0.5.6 来自偏序的线性次序 47
0.5.5 涉及有向无圈图的归纳证明 47
0.5.7 树的表示 49
0.5.8 图上的路径 51
习题 54
文献注释 56
第一章 编译导引 57
1.1 程序设计语言 57
1.1.1 程序设计语言的阐明 57
1.1.2 句法和语义 59
文献注释 61
1.2 编译概貌 62
1.2.1 编译程序的部件 62
1.2.2 词法分析 63
1.2.3 簿记 66
1.2.4 句法分析 68
1.2.5 代码产生 69
1.2.6 代码优化 75
1.2.7 误差的分析和挽回 77
1.2.8 小结 79
习题 80
文献注释 82
1.3 句法分析和翻译算法的其它应用 83
1.3.1 自然语言 83
1.3.2 模式的结构描述 84
文献注释 88
2.1 语言的表示法 89
第二章 语言理论基础 89
2.1.1 出发点 90
2.1.2 文法 90
2.1.3 有限制的文法 97
2.1.4 识别程序 100
习题 103
文献注释 109
2.2 正规集及其产生程序和识别程序 110
2.2.1 正规集和正规表达式 110
2.2.2 正规集与右线性文法 117
2.2.3 有限自动机 120
2.2.4 有限自动机与正规集 126
习题 130
2.2.5 小结 130
文献注释 134
2.3 正规集的性质 134
2.3.1 有限自动机的极小化 134
2.3.2 正规集的抽吸引理 138
2.3.3 正规集类的闭包性质 139
2.3.4 关于正规集的可判定性问题 141
习题 143
文献注释 149
2.4 上下文无关语言 149
2.4.1 派生树 150
2.4.2 上下文无关文法的变换 155
2.4.3 乔姆斯基范式 164
2.4.4 格雷巴赫范式 165
2.4.5 达到格雷巴赫范式的另一方法 172
习题 176
文献注释 180
2.5 下推自动机 180
2.5.1 基本定义 180
2.5.2 下推自动机的变形 186
2.5.3 PDA语言和CFL的等价性 191
2.5.4 确定性下推自动机 200
习题 207
文献注释 209
2.6 上下文无关语言的性质 209
2.6.1 奥登引理 210
2.6.2 上下文无关语言类的闭包性质 214
2.6.3 一些可判定性结果 217
2.6.4 确定性CFL的一些性质 220
2.6.5 多义性 221
习题 226
文献注释 230
第三章 翻译理论 232
3.1 翻译的形式方法 232
3.1.1 翻译和语义 233
3.1.2 句法制导的翻译模式 235
3.1.3 有限变换器 244
3.1.4 下推变换器 249
习题 255
文献注释 259
3.2 句法制导翻译的性质 259
3.2.1 特征化语言 259
3.2.2 简单SDT的性质 264
3.2.3 SDT的层次 265
习题 273
文献注释 274
3.3 词法分析 275
3.3.1 正规表达式的一种扩展语言 276
3.3.2 间接词法分析 278
3.3.3 直接词法分析 282
3.3.4 有限变换器的软件模拟 285
习题 286
文献注释 287
3.4 句法分析 287
3.4.1 句法分析的定义 287
3.4.2 自上而下的剖析 289
3.4.3 自下而上的剖析 293
3.4.4 自上而下和自下而上剖析的比较 296
3.4.5 文法的覆盖 301
习题 303
文献注释 306
第四章 一般句法分析方法 307
4.1 回溯剖析法 307
4.1.1 下推变换器的模拟 308
4.1.2 自上而下剖析法的非正式描述 311
4.1.3 自上而下的剖析算法 316
4.1.4 自上而下剖析程序的时、空复杂度 324
4.1.5 自下而上剖析 329
习题 335
文献注释 341
4.2 列表的剖析方法 342
4.2.1 科克-杨格-卡萨米算法 342
4.2.2 厄利剖析方法 349
习题 362
文献注释 364
第五章 单路无回溯剖析法 365
5.1.1 LL（k）文法的定义 366
5.1 LL（k）文法 366
5.1.2 预测剖析算法 370
5.1.3 LL（k）定义的含义 375
5.1.4 剖析LL（1）文法 379
5.1.5 剖析LL（k）文法 382
5.1.6 对LL（k）条件的检验 392
习题 397
文献注释 404
5.2 确定性自下而上剖析法 405
5.2.1 确定性移动-缩减剖析法 405
5.2.2 LR（k）文法 408
5.2.3 LR（k）定义的含义 418
5.2.4 对LR（k）条件的检验 430
5.2.5 LR（k）文法的确定性右剖析程序 432
5.2.6 LL（k）和LR（k）剖析程序的实现 437
习题 437
文献注释 440
5.3 优先文法 440
5.3.1 形式的移动-缩减剖析算法 441
5.3.2 简单优先文法 444
5.3.3 扩展优先文法 452
5.3.4 弱优先文法 458
习题 467
文献注释 469
5.4.1 有界右文关联文法 470
5.4 移动-缩减可剖析文法的其它类型 470
5.4.2 混合策略优先文法 480
5.4.3 算子优先文法 483
5.4.4 弗洛伊德-伊文思产生式语言 488
5.4.5 本章小结 493
习题 495
文献注释 500
第六章 回溯量有限制的剖析算法 501
6.1 回溯量有限制的自上而下剖析法 501
6.1.1 TDPL 502
6.1.2 TDPL与确定性上下文无关语言 513
6.1.3 TDPL的推广 517
6.1.4 识别GTDPL语言的时间复杂度 523
6.1.5 GTDPL程序的实现 526
习题 533
文献注释 536
6.2 回溯量有限制的自下而上剖析法 536
6.2.1 非规范剖析法 536
6.2.2 双堆栈的剖析程序 538
6.2.3 科默劳尔优先关系 542
6.2.4 科默劳尔优先性的检验 544
习题 552
文献注释 553
参考文献 554
索引 566