目录

第0章 数学预备知识

0.1 集合论的一些概念

0.1.1 集合

0.1.2 集合的运算

0.1.3 关系

0.1.4 关系的闭包

0.1.5 次序关系

0.1.6 映射

习题

0.2.1 符号串

0.2 符号串的集合

0.2.2 语言

0.2.3 语言的运算

习题

0.3 逻辑的一些概念

0.3.1 证明

0.3.2 归纳证明

0.3.3 逻辑联结词

习题

文献注释

0.4 过程和算法

0.4.1 过程

0.4.2 算法

0.4.3 递归函数

0.4.4 过程的阐明

0.4.5 问题

0.4.6 波斯特对应问题

习题

文献注释

0.5 图论的一些概念

0.5.1 有向图

0.5.2 有向无圈图

0.5.3 树

0.5.4 有序图

0.5.6 来自偏序的线性次序

0.5.5 涉及有向无圈图的归纳证明

0.5.7 树的表示

0.5.8 图上的路径

习题

文献注释

第一章 编译导引

1.1 程序设计语言

1.1.1 程序设计语言的阐明

1.1.2 句法和语义

文献注释

1.2 编译概貌

1.2.1 编译程序的部件

1.2.2 词法分析

1.2.3 簿记

1.2.4 句法分析

1.2.5 代码产生

1.2.6 代码优化

1.2.7 误差的分析和挽回

1.2.8 小结

习题

文献注释

1.3 句法分析和翻译算法的其它应用

1.3.1 自然语言

1.3.2 模式的结构描述

文献注释

2.1 语言的表示法

第二章 语言理论基础

2.1.1 出发点

2.1.2 文法

2.1.3 有限制的文法

2.1.4 识别程序

习题

文献注释

2.2 正规集及其产生程序和识别程序

2.2.1 正规集和正规表达式

2.2.2 正规集与右线性文法

2.2.3 有限自动机

2.2.4 有限自动机与正规集

习题

2.2.5 小结

文献注释

2.3 正规集的性质

2.3.1 有限自动机的极小化

2.3.2 正规集的抽吸引理

2.3.3 正规集类的闭包性质

2.3.4 关于正规集的可判定性问题

习题

文献注释

2.4 上下文无关语言

2.4.1 派生树

2.4.2 上下文无关文法的变换

2.4.3 乔姆斯基范式

2.4.4 格雷巴赫范式

2.4.5 达到格雷巴赫范式的另一方法

习题

文献注释

2.5 下推自动机

2.5.1 基本定义

2.5.2 下推自动机的变形

2.5.3 PDA语言和CFL的等价性

2.5.4 确定性下推自动机

习题

文献注释

2.6 上下文无关语言的性质

2.6.1 奥登引理

2.6.2 上下文无关语言类的闭包性质

2.6.3 一些可判定性结果

2.6.4 确定性CFL的一些性质

2.6.5 多义性

习题

文献注释

第三章 翻译理论

3.1 翻译的形式方法

3.1.1 翻译和语义

3.1.2 句法制导的翻译模式

3.1.3 有限变换器

3.1.4 下推变换器

习题

文献注释

3.2 句法制导翻译的性质

3.2.1 特征化语言

3.2.2 简单SDT的性质

3.2.3 SDT的层次

习题

文献注释

3.3 词法分析

3.3.1 正规表达式的一种扩展语言

3.3.2 间接词法分析

3.3.3 直接词法分析

3.3.4 有限变换器的软件模拟

习题

文献注释

3.4 句法分析

3.4.1 句法分析的定义

3.4.2 自上而下的剖析

3.4.3 自下而上的剖析

3.4.4 自上而下和自下而上剖析的比较

3.4.5 文法的覆盖

习题

文献注释

第四章 一般句法分析方法

4.1 回溯剖析法

4.1.1 下推变换器的模拟

4.1.2 自上而下剖析法的非正式描述

4.1.3 自上而下的剖析算法

4.1.4 自上而下剖析程序的时、空复杂度

4.1.5 自下而上剖析

习题

文献注释

4.2 列表的剖析方法

4.2.1 科克-杨格-卡萨米算法

4.2.2 厄利剖析方法

习题

文献注释

第五章 单路无回溯剖析法

5.1.1 LL（k）文法的定义

5.1 LL（k）文法

5.1.2 预测剖析算法

5.1.3 LL（k）定义的含义

5.1.4 剖析LL（1）文法

5.1.5 剖析LL（k）文法

5.1.6 对LL（k）条件的检验

习题

文献注释

5.2 确定性自下而上剖析法

5.2.1 确定性移动-缩减剖析法

5.2.2 LR（k）文法

5.2.3 LR（k）定义的含义

5.2.4 对LR（k）条件的检验

5.2.5 LR（k）文法的确定性右剖析程序

5.2.6 LL（k）和LR（k）剖析程序的实现

习题

文献注释

5.3 优先文法

5.3.1 形式的移动-缩减剖析算法

5.3.2 简单优先文法

5.3.3 扩展优先文法

5.3.4 弱优先文法

习题

文献注释

5.4.1 有界右文关联文法

5.4 移动-缩减可剖析文法的其它类型

5.4.2 混合策略优先文法

5.4.3 算子优先文法

5.4.4 弗洛伊德-伊文思产生式语言

5.4.5 本章小结

习题

文献注释

第六章 回溯量有限制的剖析算法

6.1 回溯量有限制的自上而下剖析法

6.1.1 TDPL

6.1.2 TDPL与确定性上下文无关语言

6.1.3 TDPL的推广

6.1.4 识别GTDPL语言的时间复杂度

6.1.5 GTDPL程序的实现

习题

文献注释

6.2 回溯量有限制的自下而上剖析法

6.2.1 非规范剖析法

6.2.2 双堆栈的剖析程序

6.2.3 科默劳尔优先关系

6.2.4 科默劳尔优先性的检验

习题

文献注释

参考文献

索引