编译原理及实现PDF电子书下载

第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.3.7 错误处理 7

1.4 编译程序的结构 7

1.4.1 单遍编译程序 7

1.4.2 多遍编译程序 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.6 TEST语言与编译器 10

1.6.1 TEST语言 10

1.6.2 TEST编译器 11

1.6.3 TEST机 11

习题 11

第2章 文法和语言 12

2.1 字母表和符号串 12

2.1.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 推导定义 18

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 语法树 22

2.9 子树与短语 22

2.10 由树构造推导过程 23

2.11 文法的二义性 23

2.12 有关文法的实用限制 25

2.13 文法和语言分类 26

习题 27

第3章 词法分析 29

3.1 词法分析的功能 29

3.2 程序语言的单词符号种类及词法分析输出 30

3.3 正则文法及状态图 31

3.3.1 状态图 31

3.3.2 状态图的用法 32

3.4 词法分析程序的设计与实现 33

3.4.1 TEST语言的词法规则及状态图 33

3.4.2 TEST语言词法分析程序的构造 35

3.4.3 TEST语言的词法分析程序实现 36

3.5 正则表达式 38

3.5.1 正则表达式定义 38

3.5.2 正则文法到正则表达式的转换 39

3.6 有穷自动机 40

3.6.1 确定的有穷自动机 40

3.6.2 不确定的有穷自动机 42

3.6.3 NFA到DFA的转化 44

3.6.4 正则表达式与有穷自动机的等价性 47

3.6.5 确定的有穷自动机的化简 49

3.6.6 根据DFA构造词法分析程序 51

3.7 词法分析程序的自动生成器LEX 52

3.7.1 用LEX语言表达正则表达式 53

3.7.2 LEX源程序结构 54

3.7.3 使用LEX生成TEST语言的词法分析程序 58

习题 60

第4章 语法分析——自顶向下分析 62

4.1 自顶向下分析方法 62

4.2 FIRST集合和FOLLOW集合 63

4.2.1 FIRST集合定义及构造方法 63

4.2.2 FOLLOW集合定义及构造方法 64

4.3 递归下降分析 65

4.3.1 递归下降分析的基本方法 65

4.3.2 递归下降分析中存在的问题及解决方法 65

4.3.3 TEST语言的递归下降分析实现 69

4.4 LL（1）分析方法 72

4.4.1 LL（1）分析的基本方法 72

4.4.2 LL（1）分析表的构造方法 75

4.4.3 LL（1）分析的主要问题及解决方法 76

习题 78

第5章 语法分析——自底向上分析 80

5.1 规范推导、规范句型和规范归约 80

5.2 自底向上分析方法的一般过程 81

5.3 LR分析方法 82

5.3.1 LR分析器逻辑结构 82

5.3.2 LR分析表构成 82

5.3.3 LR分析过程 84

5.4 LR（0）分析器 85

5.4.1 活前缀和可归前缀 85

5.4.2 LR（0）项目 86

5.4.3 构造识别活前缀的有穷自动机 88

5.4.4 LR（0）分析表的构造 92

5.4.5 LR（0）分析器的工作过程 94

5.4.6 LR（0）文法 95

5.5 SLR（1）分析器 96

5.5.1 SLR解决方法的基本思想 98

5.5.2 SLR（1）分析表的构造 98

5.6 LR（1）分析器 102

5.6.1 LR（1）项目 104

5.6.2 LR（1）项目集规范族构造算法 105

5.6.3 LR（1）分析表的构造 108

5.7 LALR（1）分析器 110

5.8 语法分析程序的自动生成工具——YACC 114

5.8.1 YACC源程序结构 115

5.8.2 YACC源程序说明部分的组成 115

5.8.3 YACC源程序的语法规则部分的组成 116

5.8.4 YACC源程序的程序部分的组成 117

5.8.5 二义性文法的处理 119

5.8.6 YACC示例运行 119

习题 120

第6章 语法制导翻译技术 122

6.1 翻译文法 122

6.2 语法制导翻译 124

6.3 自顶向下语法制导翻译 125

6.3.1 递归下降翻译 125

6.3.2 LL（1）翻译器 128

6.4 属性翻译文法 130

6.4.1 综合属性 130

6.4.2 继承属性 132

6.4.3 属性翻译文法定义 133

6.4.4 属性翻译文法举例——算术表达式的翻译 134

6.5 属性文法的自顶向下翻译 136

6.5.1 L－属性翻译文法 136

6.5.2 L－属性翻译文法的翻译实现——递归下降翻译 137

6.5.3 L－属性翻译文法的翻译实现——LL（1）法 142

6.6 自底向上语法制导翻译 146

6.6.1 波兰翻译 146

6.6.2 S－属性文法 148

6.6.3 S－属性波兰翻译文法的翻译实现 149

习题 151

第7章 符号表管理技术 153

7.1 何时建立和访问符号表 153

7.2 符号表的组织和内容 154

7.3 符号表上的操作 156

7.4 非块程序结构语言的符号表结构 157

7.5 块程序结构语言的符号表组织 159

7.5.1 块程序结构语言的概念 159

7.5.2 栈式符号表 160

习题 161

第8章 程序运行时的存储组织及管理 162

8.1 程序运行时的存储组织 162

8.2 静态存储分配 163

8.3 栈式动态存储分配 164

8.3.1 活动记录 165

8.3.2 运行时的地址计算 167

8.3.3 递归过程的处理 167

8.4 堆式动态存储分配 168

8.4.1 堆分配方式 168

8.4.2 堆式存储管理技术 169

习题 172

第9章 语义分析和代码生成 173

9.1 语义分析的概念 173

9.2 中间代码 174

9.2.1 波兰后缀表示 174

9.2.2 N－元表示 175

9.2.3 栈式抽象机及其汇编指令 176

9.3 声明的处理 178

9.3.1 符号常量 178

9.3.2 简单变量 179

9.3.3 数组 181

9.3.4 过程声明 184

9.4 表达式语句 184

9.5 if语句 189

9.6 while语句 191

9.7 for循环语句 192

9.8 write_语句 194

9.9 read_语句 195

9.10 过程调用和返回 196

9.10.1 参数的基本传递形式 196

9.10.2 过程调用 197

9.10.3 过程定义的处理 197

9.10.4 返回语句和过程终止语句 199

9.11 语义分析及代码生成实现 199

9.12 错误处理 199

习题 200

第10章 代码优化 201

10.1 局部优化 201

10.1.1 基本块的划分 202

10.1.2 基本块的优化技术 203

10.1.3 基本块的DAG表示 204

10.1.4 基本块优化的实现 209

10.2 循环内的优化 210

10.2.1 循环结构的定义 210

10.2.2 循环的查找 211

10.2.3 循环优化的实现 212

习题 218

附录A TEST语言文法规则 219

A.1 TEST语言词法规则 219

A.2 TEST的语法规则 219

A.3 TEST的语义和代码生成 221

附录B 词法分析程序 223

B.1 词法分析程序 223

B.2 主程序 225

附录C 语法分析程序 227

C.1 语法分析程序 227

C.2 主程序 236

附录D 语义及代码生成程序 237

D.1 语法、语义及代码生成程序 237

D.2 主程序 250

附录E TEST抽象机模拟器完整程序 251

E.1 TESTmachine函数 251

E.2 主程序 256