《形式语言、自动机和语法分析》求取 ⇩

目 录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 特殊类型的CFL157

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