第一章 引言 1
§1 前言 1
目录 1
§2 对程序设计语言及若干编译技术的回顾 2
2.1 程序设计语言的引进 2
2.2 编译程序的构造 3
2.3 基本编译技术 5
1.1 语言是什么 10
1.2 语言的要点 10
§1 语言概况 10
第二章 文法与语言 10
1.3 语言的特征 11
1.4 与语言有关的若干概念 12
§2 符号串与符号串集合 12
2.1 字母表 12
2.2 符号串 12
2.3 符号串集合 13
3.1 重写规则 15
§3 文法与语言的形式定义 15
3.2 文法 17
3.3 语言的形式定义 21
3.4 为语言构造文法的例 22
3.5 压缩了的文法 24
§4 语言的分类 26
4.1 Chomsky语言类 26
4.2 形式语言与自动机 31
4.3 形式语言的分类与程序设计语言 34
4.4 对上下文无关文法的进一步讨论 35
§5 语法树 38
5.1 语法树的引进 38
5.2 从推导构造语法树 39
5.3 从语法树构造推导 40
5.4 二义性 40
§6 句型分析 42
6.1 句型分析的概念 42
6.2 分析技术 43
6.4 句型分析的基本问题 45
6.3 规范推导与规范归约 45
§7 关系及其传递闭包 46
7.1 关系的概念 46
7.2 传递闭包 49
7.3 计算有穷集上关系的传递闭包的算法 52
习题 57
1.2 符号的识别与重写规则的关系 61
1.1 词法分析 61
§1 引言 61
第三章 扫描程序 61
1.3 实现方式 62
§2 正则表达式与有穷状态自动机 63
2.1 状态转换图 63
2.2 确定有穷自动机DFA 67
2.3 非确定有穷自动机NFA 69
2.4 DFA的化简 74
2.5 正则表达式 75
3.1 扫描程序的输入输出 82
§3 扫描程序的编写 82
3.2 扫描程序与状态图 84
3.3 扫描程序的实现 86
§4 扫描程序的自动生成 88
4.1 基本思想 88
4.2 符号的结构与字符类 89
4.3 通用扫描算法 90
4.4 扫描程序定义与构造程序 91
习题 95
1.1 自顶向下分析技术及识别算法 98
1.2 讨论的前提 98
第四章 自顶向下分析技术 98
§1 引言 98
§2 带回溯的自顶向下分析技术 99
2.1 基本思想 99
2.2 实现算法及例 101
§3 自顶向下分析技术中的问题及其解决 105
3.1 效率问题 105
3.2 语义影响问题 106
3.4 左递归问题 107
3.3 语法错误的校正问题 107
§4 无回溯的自顶向下分析技术 110
4.1 先决条件 110
4.2 递归下降分析法 110
4.3 预测分析法 112
4.4 状态矩阵分析法 117
习题 119
第五章 简单优先分析技术 120
§1 前言 120
1.1 自底向上分析技术 120
1.2 讨论的前提 120
§2 优先关系与优先文法 122
2.1 寻找句柄的基本思想 122
2.2 优先关系及其应用 123
2.3 优先关系的形式定义 125
2.4 优先关系构造法 126
2.5 简单优先文法 130
3.1 实现思想 132
§3 简单优先分析技术的实现 132
3.2 识别算法流程图 133
3.3 优先关系与文法规则的表示法 134
§4 优先函数 135
4.1 优先函数的引进 135
4.2 构造优先函数 136
4.3 优先函数的其它构造法 142
4.4 优先函数的不足 146
5.2 （1,2）（2,1）优先分析技术 147
5.1 局限性 147
§5 简单优先分析技术的局限性及克服 147
5.3 （m,n）优先分析技术 152
习题 153
第六章 其它的自底向上分析技术 156
§1 算符优先分析技术 156
1.1 算符优先分析技术的引进 156
1.2 算符文法 157
1.3 算符优先关系与算符优先文法 158
1.4 算符优先文法句型的识别 162
1.5 实际应用中的算符优先技术 166
1.6 算符优先技术与简单优先技术的比较 167
§2 转换矩阵分析技术 168
2.1 概况 168
2.2 转换矩阵分析技术的形式描述 175
2.3 转换矩阵技术与算符优先技术的比较 181
习题 181
1.2 LR（k）文法的意义 183
1.1 LR（k）技术的提出 183
§1 LR（k）分析技术 183
第七章 识别程序的自动构造 183
1.3 LR（k）文法的若干性质 184
1.4 LR识别程序及识别算法 185
1.5 判定文法是LR（k）文法 190
1.6 对LR（k）方法的评价 193
§2 简单LR分析技术（SLR） 193
2.1 SLR分析技术的引进 193
2.2 SLR识别程序的构造 202
3.1 自动构造的基本思想 206
§3 LR（k）识别程序的自动构造 206
2.3 SLR（k）技术与LR（k）技术的比较 206
3.2 LR（k）技术不适用的情况 207
3.3 一个识别程序自动生成程序 209
§4 LL（k）文法与LR（k）文法 210
4.1 LL（k）文法的定义 210
4.2 LL（k）文法与LR（k）文法的对照 210
习题 211
1.1 产生式语言PL 213
§1 概况 213
第八章 识别程序书写语言 213
1.2 PL程序 215
1.3 PL程序识别句子的例 220
§2 使用PL于分析技术 220
2.1 使用PL实现不带回溯的自顶向下分析技术 220
2.2 使用PL实现自底向上分析技术 224
2.3 使用PL进行程序设计 226
习题 228
总复习思考题 229