编译原理PDF电子书下载

第1章　预备知识 1

1.1 相关定义 1

1.1.1　字母表 1

1.1.2　符号串 1

1.2　高级语言的形式定义 4

1.3 分析树 9

1.3.1　分析树的定义 9

1.3.2　分析树与短语 10

1.3.3　分析树与推导 10

1.4　形式语言分类简介 11

习题一 13

第2章　编译程序概述 15

2.1　编译程序的组成 15

2.2　编译程序的构造途径 17

2.3　解释程序 19

习题二 19

第3章　词法分析与有限自动机 20

3.1　词法分析器的作用 20

3.2 词法分析器的构造方法 20

3.2.1　手工构造词法分析器 20

3.3 正则表达式和正则集合 29

3.3.1　正则表达式和正则集合的定义 29

3.3.2　用正则表达式描述单词 30

3.4　有限自动机 30

3.5　正则表达式与有限自动机的等价性 35

3.6　正则文法与有限自动机的等价性 37

3.7　确定的有限自动机的最小化 40

3.8 LEX简介 42

习题三 45

第4章　语法分析 48

4.1 上下文无关文法的等价变换 48

4.1.1　消除文法的二义性 48

4.1.2　删除文法中的无用符号及无用产生式 50

4.1.3　删除文法中的ε-产生式 51

4.1.4　删除文法中的单一产生式 52

4.1.5　消除文法中的左递归 53

4.2 自顶向下的语法分析 55

4.2.1　LL（1）文法 56

4.2.2　预测分析法 57

4.3 自底向上分析 64

4.3.1　算符优先分析法 64

4.3.2　LR分析 70

4.4　语法错误处理简介 87

4.5 YACC简介 87

习题四 91

第5章　属性文法和语法制导翻译 94

5.1　属性文法的定义 94

5.2　属性求值 97

5.3　S属性文法 100

5.4　L属性文法 102

5.5　翻译模式 103

5.6 自顶向下翻译 106

5.6.1　消除翻译模式中的左递归 106

5.6.2　预测翻译程序的设计 107

5.7 自底向上翻译 111

5.7.1　消除嵌入在产生式中间的动作 111

5.7.2　如何确定继承属性在分析栈中的位置 112

5.7.3 自底向上翻译程序代码的设计 115

习题五 117

第6章　语义检查 120

6.1　语义检查的内容 120

6.2 符号表 121

6.2.1　符号表在语义检查中的作用 121

6.2.2　符号表的实现 121

6.2.3　符号表的分类及表项内容 122

6.2.4　子程序嵌套情况下符号表的组织 122

6.3 类型检查 123

6.3.1　类型等价和类型相容 123

6.3.2　类型表达式 124

6.3.3　几个与类型相关的翻译模式 125

6.3.4　类型表达式的等价 128

6.4 类型转换 129

6.4.1　类型转换的起因 129

6.4.2　类型转换的时机 129

习题六 130

第7章　运行时的存储分配 132

7.1 存储布局 132

7.1.1　静态存储区 133

7.1.2　动态存储区 133

7.1.3　活动记录 134

7.2 内存分配策略 135

7.2.1　静态存储分配 135

7.2.2　动态栈式存储分配 137

7.2.3　动态堆式存储分配 139

7.3 对变量等数据的访问 143

7.3.1　对全局变量和静态变量的访问 143

7.3.2　对动态变量的访问 143

7.3.3　对不允许子程序嵌套定义的局部变量的访问 143

7.3.4　对嵌套子程序中外层变量的访问 143

7.4 参数传递 148

7.4.1　传值调用（call by value） 148

7.4.2　引用调用（call by reference） 148

7.4.3　复制-恢复调用 149

7.4.4　传名调用（call-by-name） 150

习题七 151

第8章 中间代码生成 153

8.1 中间代码的形式 153

8.2　说明的处理 157

8.3 赋值语句的翻译 161

8.3.1　关于简单类型变量的赋值语句的翻译 161

8.3.2　含有数组元素引用和记录变量域引用的赋值语句的翻译 164

8.4 布尔表达式的翻译 169

8.4.1　布尔表达式的求值翻译 169

8.4.2　作为控制条件的布尔表达式的翻译 170

8.5 控制语句的翻译 173

8.5.1　if语句和while语句的翻译 173

8.5.2　switch语句的翻译 176

8.5.3　repeat语句的翻译 179

8.5.4　转移语句和调用语句的翻译 180

8.6 自顶向下的分析翻译 182

习题八 183

第9章　代码优化 185

9.1 引言 185

9.1.1　代码优化准则 185

9.1.2　进行代码优化的阶段 186

9.1.3　进行代码优化的范围 187

9.1.4　优化程序的一般结构 187

9.1.5　基本块和流图 188

9.2　进行代码优化的几种主要方法 189

9.3 流图中的循环及其查找 195

9.3.1　控制结点 196

9.3.2　回边 197

9.3.3　循环的查找 197

9.3.4　可归约流图 199

9.3.5　流图的结点深度优先排序及其算法 200

9.4 数据流分析 201

9.4.1　到达-定值数据流分析 201

9.4.2　可用表达式数据流分析 205

9.4.3　活跃变量分析 207

9.4.4　定值-引用链（du链） 209

9.5 循环优化 209

9.5.1　代码外提 210

9.6　删除全局公共子表达式 215

9.7　复写传播 216

习题九 217

第10章 目标代码生成 223

10.1 目标计算机模型 223

10.2 目标代码生成方法 224

10.2.1　一个简单的寄存器分配方法 224

10.2.2　一个简单的代码生成算法 225

10.3 图着色法的寄存器分配 225

10.3.1　图着色法 226

10.3.2　图着色法分配寄存器算法 228

10.4 DAG（有向无环图）及其构造算法 230

10.4.1　DAG的表示方法 230

10.4.2　DAG的构造算法 230

10.4.3　由DAG生成目标代码 234

10.5　依赖于目标计算机的优化 238

习题十 239

参考文献 241