编译原理及实现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.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