第1章 编译概述 1
1.1程序设计语言 1
1.2翻译程序 2
1.3编译程序的组成 3
1.3.1词法分析 4
1.3.2语法分析 4
1.3.3语义分析及中间代码生成 5
1.3.4代码优化 5
1.3.5目标代码生成 6
1.3.6符号表管理 6
1.4.2多遍编译程序 7
1.4.1单遍编译程序 7
1.4编译程序的结构 7
1.3.7错误处理 7
1.4.3编译程序分遍的优缺点 8
1.4.4“端”的概念 8
1.5编译程序的前后处理器 9
1.5.1预处理器 9
1.5.2汇编程序 9
1.5.3连接加载程序 10
1.6TEST语言与编译器 10
1.6.1TEST语言 10
1.6.2TEST编译器 11
1.6.3TEST机 11
习题 11
2.1.1字母表 12
第2章 文法和语言 12
2.1字母表和符号串 12
2.1.2 符号串 13
2.1.3符号串及其集合的运算 13
2.2 文法 14
2.2.1文法形式定义 14
2.2.2 文法的EBNF表示 16
2.3 推导 17
2.3.1直接推导定义 17
2.3.2 推导定义 17
2.3.3规范推导 18
2.4句型和句子 18
2.5语言 19
2.6递归规则与递归文法 20
2.6.1 递归规则 20
2.6.2 递归文法 20
2.7短语、简单短语和句柄 21
2.8语法树 21
2.9子树与短语 22
2.10由树构造推导过程 23
2.11文法的二义性 23
2.12有关文法的实用限制 25
2.13文法和语言分类 26
习题 27
3.1词法分析的功能 28
第3章 词法分析 28
3.2程序语言的单词符号种类及词法分析输出 29
3.3正则文法及状态图 30
3.3.1状态图 30
3.3.2状态图的用法 31
3.4词法分析程序的设计与实现 32
3.4.1TEST语言的词法规则及状态图 32
3.4.2TEST语言词法分析程序的构造 34
3.4.3TEST语言的词法分析程序实现 35
3.5正则表达式 37
3.5.1正则表达式定义 37
3.5.2正则文法到正则表达式的转换 38
3.6.1确定的有穷自动机 39
3.6有穷自动机 39
3.6.2不确定的有穷自动机 42
3.6.3 NFA到DFA的转化 43
3.6.4正则表达式与有穷自动机的等价性 46
3.6.5确定的有穷自动机的化简 48
3.6.6根据DFA构造词法分析程序 51
3.7词法分析程序的自动生成器LEX 52
3.7.1用LEX语言表达正则表达式 52
3.7.2 LEX源程序结构 54
3.7.3 使用LEX生成TEST语言的词法分析程序 57
习题 60
4.1自顶向下分析方法 61
第4章 语法分析——自顶向下分析 61
4.2FIRST集合和FOLLOW集合 62
4.2.1FIRST集合定义及构造方法 62
4.2.2FOLLOW集合定义及构造方法 63
4.3递归下降分析 64
4.3.1递归下降分析的基本方法 64
4.3.2递归下降分析中存在的问题及解决方法 64
4.3.3 TEST语言的递归下降分析实现 69
4.4 LL（1）分析方法 70
4.4.1LL（1）分析的基本方法 71
4.4.2LL（1）分析表的构造方法 74
4.4.3LL（1）分析的主要问题及解决方法 75
习题 76
第5章 语法分析——自底向上分析 78
5.1规范推导、规范句型和规范归约 78
5.2自底向上分析方法的一般过程 79
5.3LR分析方法 80
5.3.1LR分析器逻辑结构 80
5.3.2LR分析表构成 80
5.3.3LR分析过程 82
5.4 LR（0）分析器 83
5.4.1活前缀和可归前缀 83
5.4.2 LR（0）项目 84
5.4.3构造识别活前缀的有穷自动机 86
5.4.4 LR（0）分析表的构造 90
5.4.5 LR（0）分析器的工作过程 92
5.4.6LR（0）文法 93
5.5SLR（1）分析器 94
5.5.1SLR解决方法的基本思想 96
5.5.2SLR（1）分析表的构造 97
5.6LR（1）分析器 100
5.6.1LR（1）项目 102
5.6.2LR（1）项目集规范族构造算法 103
5.6.3LR（1）分析表的构造 107
5.7LALR（1）分析器 108
5.8语法分析程序的自动生成工具—YACC 112
5.8.2YACC源程序说明部分的组成 113
5.8.1YACC源程序结构 113
5.8.3YACC源程序的语法规则部分的组成 114
5.8.4YACC源程序的程序部分组成 115
5.8.5二义性文法的处理 117
5.8.6YACC示例运行 117
习题 118
第6章 语法制导翻译技术 120
6.1翻译文法 120
6.2语法制导翻译 122
6.3自顶向下语法制导翻译 123
6.3.1递归下降翻译 123
6.3.2 LL（1）翻译器 126
6.4.1综合属性 128
6.4属性翻译文法 128
6.4.2继承属性 130
6.4.3属性翻译文法定义 131
6.4.4属性翻译文法举例——算术表达式的翻译 132
6.5属性文法的自顶向下翻译 133
6.5.1 L－属性翻译文法 134
6.5.2L－属性翻译文法的翻译实现——递归下降翻译 135
6.5.3L－属性翻译文法的翻译实现——LL（1）法 139
6.6自底向上语法制导翻译 142
6.6.1波兰翻译 142
6.6.2S－属性文法 144
6.6.3S－属性波兰翻译文法的翻译实现 145
习题 147
第7章 符号表管理技术 149
7.1何时建立和访问符号表 149
7.2符号表的组织和内容 150
7.3符号表上的操作 152
7.4非块程序结构语言的符号表结构 153
7.5块程序结构语言的符号表组织 155
7.5.1块程序结构语言的概念 155
7.5.2栈式符号表 156
习题 157
第8章 程序运行时的存储组织及管理 158
8.1程序运行时的存储组织 158
8.2静态存储分配 159
8.3栈式动态存储分配 160
8.3.1活动记录 161
8.3.3递归过程的处理 163
8.3.2运行时的地址计算 163
8.4堆式动态存储分配 164
8.4.1堆分配方式 164
8.4.2堆式存储管理技术 165
习题 168
第9章 语义分析和代码生成 169
9.1语义分析的概念 169
9.2中间代码 170
9.2.1波兰后缀表示 170
9.2.2N－元表示 171
9.2.3栈式抽象机及其汇编指令 172
9.3.1符号常量 174
9.3声明的处理 174
9.3.2简单变量 175
9.3.3数组 177
9.3.4过程声明 180
9.4表达式语句 180
9.5if语句 185
9.6while语句 186
9.7for循环语句 188
9.8write 语句 190
9.9read语句 190
9.10过程调用和返回 191
9.10.1参数的基本传递形式 191
9.10.2过程调用 192
9.10.3过程定义的处理 193
9.10.4返回语句和过程终止语句 194
9.11语义分析及代码生成实现 194
9.12错误处理 194
习题 195
第10章 代码优化 196
10.1局部优化 196
10.1.1基本块的划分 197
10.1.2基本块的优化技术 198
10.1.3基本块的DAG表示 199
10.1.4基本块优化的实现 203
10.2.1循环结构的定义 205
10.2循环内的优化 205
10.2.2循环的查找 206
10.2.3循环优化的实现 207
习题 213
附录A TEST语言文法规则 214
A1 TEST语言词法规则 214
A2 TEST的语法规则 214
A3 TEST的语义和代码生成规则 216
附录B 词法分析程序 218
附录C 语法分析程序 221
附录D 语义及代码生成程序 231
附录E TEST抽象机模拟器完整程序 246
参考文献 251