目 录

第一章预备知识

1.1 集合论基础

1.1.1 集合

1.1.2 集合的运算

1.1.3 关系

1.1.4 关系闭包

1.1.5 有序关系

1.1.6 映射

习题

1.2 逻辑概念

1.2.1 证明

1.2.2 归纳证明

1.2.3逻辑连接

习题

1.3.1 过程

1.3 过程和算法

1.3.2 算法

1.3.3 递归函数

1.3.4 Post对应问题

习题

1.4 图论概念

1.4.1 方向图

1.4.2 无回路方向图

1.4.3 树

1.4.4 有序图

1.4.5 无回路方向图的归纳证明

1.4.6 树表示

1.4.7 图的路径

习题

第二章语言及其表示

2.1 字符串的集合

2.1.1 字符串

2.1.2 语言

2.1.3 语言的运算

习题

2.2 语言的表示

2.2.1 引言

2.2.2 文法

2.3 文法的分类

2.4 识别器

习题

第三章正则集、右线性文法及有限自动机

3.1 正则集与正则表达式

3.2 正则集和右线性文法

习题

3.3 有限自动机

3.3.1 有限状态系统

3.3.2确定的有限自动机

3.3.3 不确定的有限自动机

3.3.4 有限自动机和右线性语言

3.4.1 有限自动机的极小化

3.4 右线性语言的性质

3.4.2 泵浦引理

3.4.3 右线性语言的封闭性

3.4.4判定问题

习题

第四章上下文无关文法和下推自动机

4.1 概述

4.1.1 派生树

4.1.2 最左推导和最右推导

4.2 上下文无关文法的变换

4.3 CHOMSKY范式（CNF）

4.4 GREIBACH范式（GNF)

习题

4.5 下推自动机

习题

4.6 上下文无关语言的性质

4.6.1 Ogden定理

4.6.2 上下文无关语言的封闭性

4.6.3 判定问题

4.6.4歧义性

4.7 特殊类型的CFL

4.7.1 线性文法

4.7.2 顺序文法

习题

第五章图灵机（Turing Machines）

5.1 图灵机

5.2 图灵机的构造技术

5.2.1 有限控制器内的存贮

5.2.2 多道图灵机

5.2.3 查讫符号

5.2.4 移位

5.2.5 子程序

5.3 变形图灵机

5.3.1 双向无穷带图灵机

5.3.2 多带图灵机

5.3.3 不确定的图灵机

5.3.4 多维图灵机

5.4 图灵机与0型文法

5.5 线性有界自动机与1型文法

习题

第六章翻译原理

6.1 翻译的形式化

6.1.1 翻译与语义

6.1.2 句法引导的翻译格式

6.1.3 有限转换器

6.1.4 下推转换器

习题

6.2 词法分析

6.2.1 扩充正则表达式语言

6.2.2 间接词法分析

6.2.3 直接词法分析

习题

6.3.1 句法分析的定义

6.3 句法分析

6.3.2 由顶至底解析

6.3.3 由底至顶解析

6.3.4 文法覆盖

习题

第七章通用的解析方法

7.1 回溯解析

7.1.1 PDT的模拟

7.1.2 非形式化的顶—底解析

7.1.3 顶—底解析算法

7.1.4 底—顶解析算法

习题

7.2表格法解析

7.2.1 C-Y-K算法

7.2.2 Earley算法

习题

8.1 LL(k)文法

第八章无回溯解析

8.1.1 LL(k)文法的定义

8.1.2预测解析算法

8.1.3 LL(k)定义的实质

8.1.4 LL(1)文法的解析

8.1.5 LL(k)文法的解析

习题

8.2 LR(k)文法

8.2.1 确定移位—归约解析

8.2.2 LR(k)文法

8.2.3 LR(k)定义的实质

8.2.4 LR(k)文法的确定右解析器

习题

8.3 优先文法

8.3.1 移位—归约解析算法的形式化

8.3.2 简单优先文法

8.3.3 扩充优先文法

8.3.4 弱优先文法

习题