第1章 编译原理概述 1
1.1 翻译程序与编译程序 1
目录 1
1.2 编译过程和编译程序的基本结构 2
1.3 编译程序的生成方法 5
1.4 编译技术在软件开发的应用 6
1.5 编译器的构造工具 7
小结 7
习题一 8
参考答案 9
2.1.1 字母表和符号串 10
第2章 文法和语言基础 10
2.1 字母表和符号串的基本概念 10
2.1.2 符号串的运算 11
2.2 文法和语言的形式定义 12
2.2.1 形式语言 12
2.2.2 文法的形式定义 13
2.2.3 语言的形式定义 16
2.2.4 规范推导和规范归约 18
2.2.5 递归规则与文法的递归性 19
2.3 短语、直接短语和句柄 20
2.3.1 短语和直接短语 20
2.3.2 句柄 21
2.4 语法树与文法的二义性 22
2.4.1 推导与语法树 22
2.4.2 文法的二义性 24
2.4.3 文法二义性的消除 25
2.5 文法和语言的分类 26
2.6 有关文法实用中的一些说明 28
2.6.1 有关文法的使用限制 28
2.6.2 上下文无关文法中的ε规则 29
2.7 文法在内存中的表示 29
小结 30
习题二 31
参考答案 33
第3章 词法分析与有穷自动机 35
3.1 词法分析程序的设计 35
3.1.1 词法分析程序与语法分析程序的接口方式 35
3.1.2 词法分析程序的输出 35
3.1.3 将词法分析工作分离的考虑 36
3.2 语言单词符号的两种定义方式 37
3.2.1 正规式与正规集 37
3.2.2 正规文法与正规式 38
3.3 正规式与有穷自动机 41
3.3.1 确定有穷自动机（DFA） 41
3.3.2 非确定有穷自动机（NFA） 42
3.3.3 由正规表示式R构造NFA 43
3.3.4 NFA确定化为DFA的方法 44
3.3.5 DFA的化简 47
3.3.6 有穷自动机到正规式的转换 49
3.4 正规文法与有穷自动机 50
3.4.1 右线性正规文法到有穷自动机的转换方法 50
3.4.2 左线性正规文法到有穷自动机的转换方法 51
3.4.3 有穷自动机到正规文法的转换方法 52
3.5 词法分析程序设计 53
小结 56
习题三 56
参考答案 58
4.1.1 非确定的自上而下分析法 62
第4章 语法分析 62
4.1 自上而下语法分析法 62
4.1.2 文法的左递归性和回溯的消除 63
4.1.3 某些非LL（1）文法改写成LL（1）文法 67
4.1.4 递归下降分析法 68
4.1.5 预测分析法与预测分析表 70
4.2 自下而上的分析法 73
4.3 算符优先分析法 74
4.3.1 算符优先文法 74
4.3.2 算符优先关系表的构造 76
4.3.3 算符优先分析算法 77
4.3.4 优先函数 79
4.4 LR分析法 82
4.4.1 LR分析器的工作原理和过程 82
4.4.2 LR（0）分析法 85
4.4.3 SLR（1）分析法 89
4.4.4 LR（1）分析法 95
4.4.5 LALR（1）分析法 98
小结 101
习题四 103
参考答案 106
第5章 语法制导翻译和中间代码生成 118
5.1 属性文法 118
5.2 语法制导翻译概述 120
5.3 中间语言 122
5.3.1 逆波兰式 122
5.3.2 三元式和树形表示 123
5.3.3 四元式和三地址码 124
5.4 自底向上语法制导翻译 125
5.4.1 简单算术表达式和赋值语句的翻译 125
5.4.2 布尔表达式的翻译 127
5.4.3 控制语句的翻译 131
5.4.4 循环语句的翻译 133
5.4.5 简单说明语句的翻译 135
5.4.6 含数组元素的赋值语句的翻译 136
5.5 递归下降语法制导的翻译 139
习题五 141
小结 141
参考答案 142
第6章 符号表的组织和管理 144
6.1 符号表的内容与作用 145
6.1.1 符号表的内容 145
6.1.2 符号表的作用 145
6.2 符号表的组织 146
6.2.1 符号表的总体组织 146
6.2.2 表项属性信息组织 147
6.2.4 Pascal的符号表组织 148
6.2.3 符号表域的组织 148
6.3 符号表的建立与查找 152
6.3.1 符号表的建立 152
6.3.2 符号表的查找 152
小结 154
习题六 154
参考答案 155
第7章 代码优化 157
7.1.4 消除无用代码 158
7.1.2 删除公共子表达式 158
7.1.3 减少复写传播 158
7.1 优化概述 158
7.1.1 合并常量运算 158
7.1.5 削减运算强度 159
7.1.6 外提循环中的不变表达式 159
7.1.7 删除归纳变量 160
7.2 局部优化 160
7.2.1 划分基本块的方法 160
7.2.2 基本块的DAG表示 162
7.2.3 利用DAG进行基本块的优化处理 163
7.3 循环优化 166
7.3.1 程序流程图 166
7.3.3 循环优化 167
7.3.2 循环查找 167
7.4 窥孔优化 170
小结 171
习题七 171
参考答案 174
第8章 运行时存储空间组织 179
8.1 程序运行的存储分配知识 179
8.1.1 运行时存储空间划分 179
8.1.2 过程的活动 180
8.1.3 活动记录 181
8.1.4 存储分配策略 182
8.2 静态存储分配 182
8.3 栈式存储分配 183
8.3.2 允许过程嵌套定义语言的栈式存储分配 184
8.3.1 没有局部过程的栈式存储分配 184
8.4 堆式动态存储分配 187
8.5 参数传递机制 188
8.5.1 值传递 188
8.5.2 地址传递 189
8.5.3 值结果传递 189
8.5.4 名字传递 190
习题八 191
参考答案 193
9.1 概述 196
第9章 目标代码生成 196
9.2 假想的计算机模型 198
9.3 简单的代码生成器 200
9.3.1 待用信息和活跃信息 201
9.3.2 代码生成算法 202
9.3.3 寄存器分配 205
9.4 DAG的目标代码 208
小结 211
习题九 211
参考答案 212
A.1 简介 215
A.2 LEX词法分析自动生成程序 215
附录A LEX（Lexical Compiler）和YACC（Yet Another Compiler-Compiler）工具 215
A.2.1 语言LEX的一般描述 216
A.2.2 LEX的常规表达式 216
A.2.3 LEX编程 218
A.2.4 高级LEX 219
A.3 YACC语法分析自动生成程序 220
A.3.1 YACC规格说明 220
A.3.2 YACC编程 220
附录B 编译程序实验 223
B.1 选择实验题目的途径 223
实验二 224
实验一 224
B.2 实验题 224
实验三 225
实验四 225
实验五 226
实验六 226
B.3 实验报告范例 227
一、分析 228
二、算法 229
三、实现 229
四、总结 230
附录 231
参考文献 237