目 录 1
第一章预备知识 1
1.1 集合论基础 1
1.1.1 集合 1
1.1.2 集合的运算 4
1.1.3 关系 5
1.1.4 关系闭包 7
1.1.5 有序关系 9
1.1.6 映射 10
习题 12
1.2 逻辑概念 14
1.2.1 证明 14
1.2.2 归纳证明 15
1.2.3逻辑连接 16
习题 18
1.3.1 过程 19
1.3 过程和算法 19
1.3.2 算法 20
1.3.3 递归函数 21
1.3.4 Post对应问题 22
习题 23
1.4 图论概念 24
1.4.1 方向图 24
1.4.2 无回路方向图 26
1.4.3 树 27
1.4.4 有序图 28
1.4.5 无回路方向图的归纳证明 30
1.4.6 树表示 31
1.4.7 图的路径 33
习题 34
第二章语言及其表示 36
2.1 字符串的集合 36
2.1.1 字符串 36
2.1.2 语言 37
2.1.3 语言的运算 38
习题 39
2.2 语言的表示 40
2.2.1 引言 40
2.2.2 文法 41
2.3 文法的分类 48
2.4 识别器 50
习题 54
第三章正则集、右线性文法及有限自动机 56
3.1 正则集与正则表达式 56
3.2 正则集和右线性文法 63
习题 65
3.3 有限自动机 67
3.3.1 有限状态系统 67
3.3.2确定的有限自动机 69
3.3.3 不确定的有限自动机 74
3.3.4 有限自动机和右线性语言 82
3.4.1 有限自动机的极小化 86
3.4 右线性语言的性质 86
3.4.2 泵浦引理 90
3.4.3 右线性语言的封闭性 91
3.4.4判定问题 93
习题 96
第四章上下文无关文法和下推自动机 99
4.1 概述 99
4.1.1 派生树 99
4.1.2 最左推导和最右推导 103
4.2 上下文无关文法的变换 105
4.3 CHOMSKY范式（CNF） 120
4.4 GREIBACH范式（GNF) 122
习题 125
4.5 下推自动机 127
习题 140
4.6 上下文无关语言的性质 141
4.6.1 Ogden定理 141
4.6.2 上下文无关语言的封闭性 147
4.6.3 判定问题 149
4.6.4歧义性 152
4.7 特殊类型的CFL 157
4.7.1 线性文法 157
4.7.2 顺序文法 159
习题 159
第五章图灵机（Turing Machines） 161
5.1 图灵机 161
5.2 图灵机的构造技术 166
5.2.1 有限控制器内的存贮 166
5.2.2 多道图灵机 167
5.2.3 查讫符号 168
5.2.4 移位 170
5.2.5 子程序 172
5.3 变形图灵机 173
5.3.1 双向无穷带图灵机 174
5.3.2 多带图灵机 177
5.3.3 不确定的图灵机 179
5.3.4 多维图灵机 180
5.4 图灵机与0型文法 183
5.5 线性有界自动机与1型文法 187
习题 188
第六章翻译原理 190
6.1 翻译的形式化 190
6.1.1 翻译与语义 190
6.1.2 句法引导的翻译格式 193
6.1.3 有限转换器 200
6.1.4 下推转换器 204
习题 211
6.2 词法分析 213
6.2.1 扩充正则表达式语言 214
6.2.2 间接词法分析 216
6.2.3 直接词法分析 220
习题 222
6.3.1 句法分析的定义 223
6.3 句法分析 223
6.3.2 由顶至底解析 225
6.3.3 由底至顶解析 230
6.3.4 文法覆盖 234
习题 235
第七章通用的解析方法 237
7.1 回溯解析 237
7.1.1 PDT的模拟 238
7.1.2 非形式化的顶—底解析 240
7.1.3 顶—底解析算法 245
7.1.4 底—顶解析算法 249
习题 255
7.2表格法解析 256
7.2.1 C-Y-K算法 256
7.2.2 Earley算法 263
习题 275
8.1 LL(k)文法 277
第八章无回溯解析 277
8.1.1 LL(k)文法的定义 278
8.1.2预测解析算法 282
8.1.3 LL(k)定义的实质 285
8.1.4 LL(1)文法的解析 289
8.1.5 LL(k)文法的解析 291
习题 299
8.2 LR(k)文法 300
8.2.1 确定移位—归约解析 300
8.2.2 LR(k)文法 302
8.2.3 LR(k)定义的实质 309
8.2.4 LR(k)文法的确定右解析器 317
习题 320
8.3 优先文法 322
8.3.1 移位—归约解析算法的形式化 322
8.3.2 简单优先文法 325
8.3.3 扩充优先文法 332
8.3.4 弱优先文法 335
习题 340