编译原理PDF电子书下载

1.1　编译器 1

第1章　编译简介 1

1.1.1　编译的分析—综合模型 2

1.1.2　编译器的前驱与后继 3

1.2　编译器的各阶段 4

1.2.1　词法分析 4

1.2.2　语法分析 5

1.2.3　语义分析 5

1.2.4　中间代码生成 6

1.2.5　代码优化 6

1.3　编译器伙伴 7

1.2.6　符号表管理 7

1.2.7　错误检测与报告 7

1.3.1 预处理器 8

1.3.2　汇编器 8

1.3.3　装配器和连接编辑器 8

1.4　编译器各阶段的分组 9

1.4.1　前端与后端 9

1.4.2　编译器的遍 9

1.4.3　减少编译的遍数 10

1.5　编译器的构造工具 10

一、选择题 11

小结 11

综合练习一 11

二、填空题 12

三、应用题 12

第2章　简单的一遍编译器 13

2.1　概述 13

2.2　语法定义 13

2.2.1　分析树 15

2.2.2　二义性 16

2.2.3　操作符的结合规则 16

2.3　语法制导翻译 17

2.2.4　操作符的优先级 17

2.3.1　后缀表示 18

2.3.2　语法制导定义 18

2.3.3　综合属性 19

2.3.4　深度优先遍历 20

2.3.5　翻译模式 20

2.4　语法分析 20

2.4.1　自顶向下语法分析 21

2.4.2　预测分析法 22

2.4.3　何时使用ε产生式 24

2.5　简单表达式的翻译器 25

2.4.4　设计一个预测语法分析器 25

2.4.5　左递归 25

2.5.1　抽象语法和具体语法 26

2.5.2　调整翻译模式 27

2.5.3　非终结符expr、term和rest的过程 27

2.5.4　翻译器的优化 28

2.5.5　完整程序 29

2.6　词法分析 30

2.6.1　剔除空白符和注释 31

2.6.2　常数 31

2.6.3　识别标识符和关键字 31

2.6.5　词法分析器 32

2.6.4　词法分析器的接口 32

2.7　符号表 34

2.7.1　符号表接口 34

2.7.2　处理保留的关键字 35

2.7.3　符号表的实现方法 35

2.8　抽象堆栈机 36

2.8.1 算术指令 37

2.8.2　左值和右值 37

2.8.3　堆栈操作 37

2.8.4　表达式的翻译 37

2.8.5　控制流 38

2.8.7　输出一个翻译 39

2.8.6　语句的翻译 39

2.9　技术的综合 41

2.9.1　翻译器的描述 41

2.9.2　词法分析器模块lexer.c 42

2.9.3　语法分析器模块parser.c 42

2.9.6　错误处理模块error.c 43

2.9.7　编译器的建立 43

2.9.8　程序清单 43

2.9.5　符号表模块symbol.c和init.c 43

2.9.4　输出模块emitter.c 43

小结 48

综合练习二 48

一、选择题 48

二、填空题 49

三、应用题 49

第3章　词法分析 50

3.1　词法分析器的作用 50

3.1.1　词法分析中的问题 51

3.1.2　记号、模式、词素 51

3.1.3　记号的属性 52

3.1.5　输入缓冲 53

3.1.4　词法错误 53

3.2　记号的描述 56

3.2.1 串和语言 56

3.2.2　语言上的运算 56

3.2.3　正规表达式 57

3.2.4　正规定义 59

3.2.5　缩写表示法 60

3.2.6　非正规集 60

3.3　单词符号的识别 60

3.3.1　状态转换图 61

3.3.2　状态转换图的实现 64

3.4　有穷自动机 69

3.4.1 确定型有穷自动机（DFA） 70

3.4.2　不确定的有穷自动机（NFA） 72

3.4.3　从NFA到DFA的变换 74

3.5　词法分析器描述语言 76

3.5.1　正规表达式的Lex约定 77

3.5.2　Lex输入文件的格式 78

小结 84

综合练习三 84

一、选择题 84

三、应用题 85

二、填空题 85

第4章　语法分析 86

4.1 语法分析器的作用 86

4.1.1　语法错误的处理 86

4.1.2　错误恢复策略 87

4.2　上下文无关文法 88

4.2.1　符号的使用约定 89

4.2.2　推导 90

4.2.3　分析树和推导 91

4.2.4　二义性 91

4.3　文法的编写 93

4.3.1 正规表达式和上下文无关文法的比较 94

4.3.2　验证文法所产生的语言 95

4.3.3　消除二义性 95

4.3.4　消除左递归 98

4.3.5　提取左因子 100

4.3.6　非上下文无关语言的结构 101

4.4 自顶向下语法分析 102

4.4.1　递归下降语法分析法 102

4.4.2　预测语法分析器 103

4.4.3　预测语法分析器的状态转换图 104

4.4.4　非递归的预测分析 105

4.4.5　FIRST集合和FOLLOW集合 107

4.4.6　预测分析表的构造 109

4.4.7　LL（1）文法 109

4.4.8　预测分析的错误恢复 111

4.5　自底向上语法分析 112

4.5.1　句柄 113

4.5.2　句柄裁剪 114

4.5.3　用栈实现移动归约分析 115

4.5.4　活前缀 116

4.5.5　移动归约分析过程中的冲突 116

4.6　算符优先分析法 118

4.6.1　算符优先文法的定义 119

4.6.2　算符优先关系表的构造 120

4.6.3　算符优先分析算法的设计 122

4.6.4　优先函数的构造 125

4.6.5　算符优先分析中的错误恢复 126

4.6.6　算符优先分析法的局限性 129

4.7　LR语法分析器 130

4.7.1　LR语法分析算法 130

4.7.2　LR文法 133

4.7.3　构造SLR语法分析表 134

4.7.4　构造规范LR语法分析表 139

4.7.5　构造LALR语法分析表 143

4.7.6　LALR语法分析表的有效构造 144

4.7.7　LR语法分析表的压缩 146

4.8　二义文法的应用 148

4.8.1 使用优先级和结合规则来解决分析动作的冲突 148

4.8.2　悬空else的二义性 150

4.8.3　特例产生式引起的二义性 151

4.8.4　LR语法分析中的错误恢复 153

4.9　语法分析器的生成器 155

4.9.1　语法分析器的生成器YACC 155

4.9.2　用YACC处理二义文法 157

4.9.3　用Lex建立YACC的词法分析器 159

4.9.4　YACC的错误恢复 160

小结 161

综合练习四 161

一、选择题 161

二、填空题 162

三、应用题 162

第5章　类型检查 163

5.1 类型系统 163

5.1.1　类型表达式 164

5.1.2　类型系统 165

5.1.3　静态和动态类型检查 165

5.2.1　一种简单语言 166

5.1.4　错误恢复 166

5.2　一个简单的类型检查器的说明 166

5.2.2　表达式的类型检查 167

5.2.3　语句的类型检查 167

5.2.4　函数的类型检查 168

5.3　类型表达式的等价 168

5.3.1　类型表达式的结构等价 169

5.3.2　类型表达式的名字 169

5.3.3　类型表示中的环 171

5.4　类型转换 172

5.5.1　子表达式的可能类型的集合 173

5.5 函数和运算符的重载 173

5.5.2　缩小可能类型的集合 174

5.6　多态函数 175

5.6.1 为什么要使用多态函数 175

5.6.2　类型变量 176

5.6.3　包含多态函数的语言 177

5.6.4　代换、实例和合一 179

5.6.5　多态函数的检查 180

5.7　合一算法 183

综合练习五 187

一、选择题 187

小结 187

二、填空题 188

三、应用题 188

第6章　语法制导翻译与中间代码生成 189

6.1　语法制导定义 189

6.1.1　语法制导定义的形式 190

6.1.2　综合属性 191

6.1.3　继承属性 191

6.1.4　依赖图 192

6.1.5　计算次序 193

6.2.1　语法树 194

6.2　S属性的自下而上计算 194

6.2.2　构造表达式的语法树 195

6.2.3　构造语法树的语法制导定义 196

6.2.4　表达式的无环有向图 197

6.2.5　S属性的自下而上计算 198

6.3　L属性定义 200

6.3.1　L属性定义 200

6.3.2　翻译方案 200

6.4　自上而下翻译 202

6.4.1 删除翻译方案的左递归 202

6.4.2　预测翻译器的设计 204

6.5.1　删除翻译方案中嵌入的动作 206

6.5　继承属性的自下而上计算 206

6.5.2　分析栈上的继承属性 207

6.5.3　模拟继承属性的计算 208

6.5.4　用综合属性代替继承属性 210

6.5.5　一个困难的语法制导定义 211

6.6　递归计算 211

6.6.1 自左向右遍历 211

6.6.2　其他遍历方法 212

6.7　语法制导定义的分析 213

6.7.1　属性的递归计算 213

6.8 中间语言 215

6.7.2　强无环的语法制导定义 215

6.8.1 图表示 216

6.8.2　三地址码 216

6.8.3　三地址语句的类型 217

6.8.4　语法制导翻译生成三地址码 218

6.8.5　三地址语句的实现 219

6.8.6　表示方法比较：间址的使用 221

6.9　声明语句 221

6.9.1　过程中的声明语句 221

6.9.2　跟踪作用域信息 222

6.9.3　记录中的域名 223

6.10.1　符号表中的名字 224

6.10　赋值语句 224

6.10.2　临时名字的重用 225

6.10.3　定址数组元素 226

6.10.4　数组元素寻址的翻译模式 228

6.10.5　赋值语句中的类型转换 229

6.10.6　记录域的访问 230

6.11　布尔表达式 230

6.11.1　翻译布尔表达式的方法 231

6.11.2　数值表示 231

6.11.4　控制流语句 232

6.11.3　短路代码 232

6.11.5　布尔表达式的控制流翻译 234

6.11.6　混合模式的布尔表达式 235

6.12　case语句 236

小结 238

综合练习六 239

一、选择题 239

二、填空题 239

三、应用题 240

7.1　源语言问题 241

7.1.1　过程 241

第7章　运行时的环境 241

7.1.2　活动树 242

7.1.3　控制栈 242

7.1.4　声明的作用域 243

7.1.5　名字的结合 243

7.2　存储组织 244

7.2.1 运行时内存的划分 244

7.2.2　活动记录 245

7.2.3　编译时的局部数据安排 246

7.3.1 静态分配 247

7.3　存储分配策略 247

7.3.2　栈分配 248

7.3.3　悬空引用 251

7.3.4　堆分配 252

7.4　访问非局部名字 252

7.4.1 程序块 252

7.4.2　无过程嵌套的静态作用域 254

7.4.3　有过程嵌套的静态作用域 255

7.4.4　动态作用域 257

7.5　参数传递 258

7.5.1 值调用 259

7.5.2　引用调用 260

7.5.4　换名调用 261

7.5.3　复写—恢复 261

小结 262

综合练习七 262

一、选择题 262

二、填空题 262

三、应用题 263

8.1.1　代码生成器的输入 264

8.1.2　目标程序 264

8.1 代码生成器设计中的问题 264

第8章　代码生成 264

8.1.3　存储管理 265

8.1.4　指令选择 265

8.1.5　寄存器分配 266

8.1.6　计算次序选译 267

8.1.7　代码生成途径 267

8.2 目标机器 267

8.3　基本块和流图 269

8.3.1　基本块 269

8.3.2　基本块的变换 270

8.3.3　流图 272

8.4.2　临时名字的存储分配 273

8.4.1　计算下次引用信息 273

8.4　下次引用信息 273

8.5　一个简单的代码生成器 274

8.5.1 寄存器描述和地址描述 274

8.5.2　代码生成算法 275

8.5.3　函数getreg 275

8.5.4　为其他类型的语句产生代码 277

8.5.5　条件语句 277

小结 278

综合练习八 278

一、选择题 278

三、应用题 279

二、填空题 279

第9章　代码优化 280

9.1　优化技术简介 280

9.2　局部优化 283

9.2.1　基本块的划分 283

9.2.2　基本块的变换 284

9.2.3　基本块DAG表示 284

9.3　循环优化 285

9.3.1　程序流图与循环 285

9.3.2　循环 286

9.3.3　代码外提 287

9.3.4　强度削弱 289

9.3.5　删除归纳变量 290

9.4　数据流分析与全局优化 293

9.4.1　一些主要的概念 294

9.4.2　数据流方程的一般形式 294

9.4.3　到达一定值数据流方程 295

小结 299

综合练习九 299

一、选择题 299

三、应用题 300

二、填空题 300

参考答案 301

第1章 301

第2章 301

第3章 302

第4章 302

第5章 304

第6章 305

第7章 306

第8章 307

第9章 308

参考文献 310