《形式语言及其句法分析》求取 ⇩

目录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 TDPL502

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