编译原理PDF电子书下载

第1章 引论 1

1.1语言处理器 1

1.2一个编译器的结构 2

1.2.1词法分析 3

1.2.2语法分析 4

1.2.3语义分析 5

1.2.4中间代码生成 5

1.2.5代码优化 5

1.2.6代码生成 6

1.2.7符号表管理 6

1.2.8将多个步骤组合成趟 6

1.2.9编译器构造工具 7

1.3程序设计语言的发展历程 7

1.3.1走向高级程序设计语言 7

1.3.2对编译器的影响 8

1.3.31.3节的练习 8

1.4构建一个编译器的相关科学 8

1.4.1编译器设计和实现中的建模 9

1.4.2代码优化的科学 9

1.5编译技术的应用 10

1.5.1高级程序设计语言的实现 10

1.5.2针对计算机体系结构的优化 11

1.5.3新计算机体系结构的设计 12

1.5.4程序翻译 13

1.5.5软件生产率工具 14

1.6程序设计语言基础 15

1.6.1静态和动态的区别 15

1.6.2环境与状态 15

1.6.3静态作用域和块结构 17

1.6.4显式访问控制 18

1.6.5动态作用域 19

1.6.6参数传递机制 20

1.6.7别名 21

1.6.81.6节的练习 22

1.7第1章总结 22

1.8第1章参考文献 23

第2章一个简单的语法制导翻译器 24

2.1引言 24

2.2语法定义 25

2.2.1文法定义 26

2.2.2推导 27

2.2.3语法分析树 28

2.2.4二义性 29

2.2.5运算符的结合性 29

2.2.6运算符的优先级 30

2.2.72.2节的练习 31

2.3语法制导翻译 32

2.3.1后缀表示 33

2.3.2综合属性 33

2.3.3简单语法制导定义 35

2.3.4树的遍历 35

2.3.5翻译方案 35

2.3.62.3节的练习 37

2.4语法分析 37

2.4.1自顶向下分析方法 38

2.4.2预测分析法 39

2.4.3何时使用？产生式 41

2.4.4设计一个预测分析器 41

2.4.5左递归 42

2.4.62.4节的练习 42

2.5简单表达式的翻译器 43

2.5.1抽象语法和具体语法 43

2.5.2调整翻译方案 43

2.5.3非终结符号的过程 44

2.5.4翻译器的简化 45

2.5.5完整的程序 46

2.6词法分析 47

2.6.1剔除空白和注释 48

2.6.2预读 48

2.6.3常量 49

2.6.4识别关键字和标识符 49

2.6.5词法分析器 50

2.6.6 2.6节的练习 53

2.7符号表 53

2.7.1为每个作用域设置一个符号表 54

2.7.2符号表的使用 56

2.8生成中间代码 57

2.8.1两种中间表示形式 57

2.8.2语法树的构造 58

2.8.3静态检查 61

2.8.4三地址码 62

2.8.52.8节的练习 66

2.9第2章总结 66

第3章 词法分析 68

3.1词法分析器的作用 68

3.1.1词法分析及语法分析 69

3.1.2词法单元、模式和词素 69

3.1.3词法单元的属性 70

3.1.4词法错误 71

3.1.53.1节的练习 71

3.2词法单元的规约 71

3.2.1串和语言 72

3.2.2语言上的运算 72

3.2.3正则表达式 73

3.2.4正则定义 74

3.2.5正则表达式的扩展 75

3.2.6 3.2节的练习 76

3.3词法单元的识别 78

3.3.1状态转换图 79

3.3.2保留字和标识符的识别 80

3.3.3完成我们的例子 81

3.3.4基于状态转换图的词法分析器的体系结构 82

3.3.53.3节的练习 84

3.4词法分析器生成工具Lex 86

3.4.1 Lex的使用 86

3.4.2 Lex程序的结构 87

3.4.3 Lex中的冲突解决 89

3.4.4向前看运算符 89

3.4.53.4节的练习 90

3.5有穷自动机 91

3.5.1不确定的有穷自动机 91

3.5.2转换表 92

3.5.3自动机中输入字符串的接受 92

3.5.4确定的有穷自动机 93

3.5.53.5节的练习 93

3.6从正则表达式到自动机 94

3.6.1从NFA到DFA的转换 94

3.6.2最小化一个DFA的状态数 96

3.6.3从正则表达式构造NFA 99

3.6.4字符串处理算法的效率 101

3.6.53.6节的练习 103

3.7词法分析器生成工具的设计 103

3.7.1生成的词法分析器的结构 103

3.7.2词法分析器使用的DFA 105

3.7.3词法分析器的状态最小化 105

3.7.4实现向前看运算符 105

3.7.53.7节的练习 106

3.8第3章总结 107

3.9第3章参考文献 108

第4章 语法分析 110

4.1引论 110

4.1.1语法分析器的作用 110

4.1.2代表性的文法 111

4.1.3语法错误的处理 112

4.1.4错误恢复策略 112

4.2上下文无关文法 113

4.2.1上下文无关文法的正式定义 114

4.2.2符号表示的约定 114

4.2.3推导 115

4.2.4语法分析树和推导 116

4.2.5二义性 117

4.2.6验证文法生成的语言 118

4.2.7上下文无关文法和正则表达式 119

4.2.84.2节的练习 119

4.3设计文法 121

4.3.1词法分析和语法分析 121

4.3.2消除二义性 122

4.3.3左递归的消除 123

4.3.4提取左公因子 124

4.3.5非上下文无关语言的构造 125

4.3.64.3节的练习 126

4.4自顶向下的语法分析 126

4.4.1递归下降的语法分析 128

4.4.2 FIRST和FOLLOW 129

4.4.3 LL（1）文法 130

4.4.4非递归的预测分析 133

4.4.5预测分析中的错误恢复 134

4.4.64.4节的练习 136

4.5自底向上的语法分析 137

4.5.1归约 138

4.5.2句柄剪枝 138

4.5.3移入-归约语法分析技术 139

4.5.4移入-归约语法分析中的冲突 140

4.5.54.5节的练习 141

4.6 LR语法分析技术介绍：简单LR技术 142

4.6.1为什么使用LR语法分析器 142

4.6.2项和LR（0）自动机 143

4.6.3 LR语法分析算法 147

4.6.4构造SLR语法分析表 150

4.6.5可行前缀 152

4.6.64.6节的练习 153

4.7更强大的LR语法分析器 154

4.7.1规范LR（1）项 154

4.7.2构造LR（1）项集 155

4.7.3规范LR（1）语法分析表 158

4.7.4构造LALR语法分析表 159

4.7.5高效构造LALR语法分析表的方法 162

4.7.64.7节的练习 165

4.8使用二义性文法 165

4.8.1用优先级和结合性解决冲突 165

4.8.2“悬空-else”的二义性 167

4.8.3 LR语法分析中的错误恢复 168

4.8.44.8节的练习 169

4.9语法分析器生成工具 170

4.9.1语法分析器生成工具Yacc 170

4.9.2使用带有二义性文法的Yacc规约 173

4.9.3用Lex创建Yacc的词法分析器 175

4.9.4 Yacc中的错误恢复 175

4.9.54.9节的练习 176

4.10第4章总结 177

4.11第4章参考文献 178

第5章 语法制导的翻译 182

5.1语法制导定义 182

5.1.1继承属性和综合属性 183

5.1.2在语法分析树的结点上对SDD求值 184

5.1.35.1节的练习 186

5.2 SDD的求值顺序 186

5.2.1依赖图 186

5.2.2属性求值的顺序 187

5.2.3 S属性的定义 188

5.2.4 L属性的定义 188

5.2.5具有受控副作用的语义规则 189

5.2.65.2节的练习 190

5.3语法制导翻译的应用 191

5.3.1抽象语法树的构造 191

5.3.2类型的结构 194

5.3.35.3节的练习 195

5.4语法制导的翻译方案 195

5.4.1后缀翻译方案 195

5.4.2后缀SDT的语法分析栈实现 196

5.4.3产生式内部带有语义动作的SDT 197

5.4.4从SDT中消除左递归 198

5.4.5 L属性定义的SDT 200

5.4.65.4节的练习 204

5.5实现L属性的SDD 204

5.5.1在递归下降语法分析过程中进行翻译 205

5.5.2边扫描边生成代码 207

5.5.3 L属性的SDD和LL语法分析 208

5.5.4 L属性的SDD的自底向上语法分析 212

5.5.55.5节的练习 214

5.6第5章总结 215

5.7第5章参考文献 216

第6章 中间代码生成 217

6.1语法树的变体 218

6.1.1表达式的有向无环图 218

6.1.2构造DAG的值编码方法 219

6.1.36.1节的练习 220

6.2三地址代码 221

6.2.1地址和指令 221

6.2.2四元式表示 223

6.2.3三元式表示 223

6.2.4静态单赋值形式 225

6.2.56.2节的练习 225

6.3类型和声明 225

6.3.1类型表达式 226

6.3.2类型等价 227

6.3.3声明 227

6.3.4局部变量名的存储布局 227

6.3.5声明的序列 229

6.3.6记录和类中的字段 230

6.3.76.3节的练习 230

6.4表达式的翻译 231

6.4.1表达式中的运算 231

6.4.2增量翻译 232

6.4.3数组元素的寻址 233

6.4.4数组引用的翻译 234

6.4.56.4节的练习 235

6.5类型检查 236

6.5.1类型检查规则 236

6.5.2类型转换 237

6.5.3函数和运算符的重载 238

6.5.46.5节的练习 239

6.6控制流 239

6.6.1布尔表达式 240

6.6.2短路代码 240

6.6.3控制流语句 240

6.6.4布尔表达式的控制流翻译 242

6.6.5避免生成冗余的goto指令 244

6.6.6布尔值和跳转代码 245

6.6.76.6节的练习 246

6.7回填 246

6.7.1使用回填技术的一趟式目标代码生成 246

6.7.2布尔表达式的回填 247

6.7.3控制转移语句 249

6.7.4 break语句、continue语句和goto语句 250

6.7.56.7节的练习 251

6.8 switch语句 252

6.8.1 switch语句的翻译 252

6.8.2 switch语句的语法制导翻译 253

6.8.36.8节的练习 254

6.9过程的中间代码 254

6.10第6章总结 255

6.11第6章参考文献 256

第7章 运行时刻环境 258

7.1存储组织 258

7.2空间的栈式分配 259

7.2.1活动树 260

7.2.2活动记录 262

7.2.3调用代码序列 263

7.2.4栈中的变长数据 265

7.2.57.2节的练习 266

7.3栈中非局部数据的访问 267

7.3.1没有嵌套过程时的数据访问 267

7.3.2和嵌套过程相关的问题 267

7.3.3一个支持嵌套过程声明的语言 268

7.3.4嵌套深度 268

7.3.5访问链 269

7.3.6处理访问链 270

7.3.7过程型参数的访问链 271

7.3.8显示表 272

7.3.97.3节的练习 273

7.4堆管理 274

7.4.1存储管理器 274

7.4.2一台计算机的存储层次结构 275

7.4.3程序中的局部性 276

7.4.4碎片整理 278

7.4.5人工回收请求 280

7.4.67.4节的练习 282

7.5垃圾回收概述 282

7.5.1垃圾回收器的设计目标 282

7.5.2可达性 284

7.5.3引用计数垃圾回收器 285

7.5.47.5节的练习 286

7.6基于跟踪的回收的介绍 286

7.6.1基本的标记-清扫式回收器 287

7.6.2基本抽象 288

7.6.3标记-清扫式算法的优化 289

7.6.4标记并压缩的垃圾回收器 290

7.6.5复制回收器 292

7.6.6开销的比较 293

7.6.77.6节的练习 294

7.7第7章总结 294

7.8第7章参考文献 295

第8章 代码生成 298

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

8.1.1代码生成器的输入 299

8.1.2目标程序 299

8.1.3指令选择 300

8.1.4寄存器分配 301

8.1.5求值顺序 302

8.2目标语言 302

8.2.1一个简单的目标机模型 302

8.2.2程序和指令的代价 304

8.2.38.2节的练习 304

8.3目标代码中的地址 306

8.3.1静态分配 306

8.3.2栈分配 307

8.3.3名字的运行时刻地址 309

8.3.48.3节的练习 309

8.4基本块和流图 310

8.4.1基本块 311

8.4.2后续使用信息 312

8.4.3流图 312

8.4.4流图的表示方式 313

8.4.5循环 313

8.4.68.4节的练习 314

8.5基本块的优化 314

8.5.1基本块的DAG表示 314

8.5.2寻找局部公共子表达式 315

8.5.3消除死代码 316

8.5.4代数恒等式的使用 316

8.5.5数组引用的表示 317

8.5.6指针赋值和过程调用 318

8.5.7从DAG到基本块的重组 319

8.5.88.5节的练习 320

8.6一个简单的代码生成器 320

8.6.1寄存器和地址描述符 321

8.6.2代码生成算法 321

8.6.3函数getReg的设计 324

8.6.48.6节的练习 324

8.7窥孔优化 325

8.7.1消除冗余的加载和保存指令 325

8.7.2消除不可达代码 326

8.7.3控制流优化 326

8.7.4代数化简和强度消减 327

8.7.5使用机器特有的指令 327

8.7.68.7节的练习 327

8.8寄存器分配和指派 327

8.8.1全局寄存器分配 328

8.8.2使用计数 328

8.8.3外层循环的寄存器指派 330

8.8.4通过图着色方法进行寄存器分配 330

8.8.58.8节的练习 331

8.9通过树重写来选择指令 331

8.9.1树翻译方案 331

8.9.2通过覆盖一个输入树来生成代码 333

8.9.3通过扫描进行模式匹配 334

8.9.4用于语义检查的例程 335

8.9.5通用的树匹配方法 335

8.9.68.9节的练习 336

8.10表达式的优化代码的生成 337

8.10.1 Ershov数 337

8.10.2从带标号的表达式树生成代码 337

8.10.3寄存器数量不足时的表达式求值 338

8.10.48.10节的练习 340

8.11使用动态规划的代码生成 340

8.11.1连续求值 340

8.11.2动态规划的算法 341

8.11.38.11节的练习 343

8.12第8章总结 343

8.13第8章参考文献 344

第9章 机器无关优化 346

9.1优化的主要来源 346

9.1.1冗余的原因 346

9.1.2一个贯穿本章的例子：快速排序 347

9.1.3保持语义不变的转换 348

9.1.4全局公共子表达式 349

9.1.5复制传播 350

9.1.6死代码消除 350

9.1.7代码移动 351

9.1.8归纳变量和强度消减 351

9.1.9 9.1节的练习 353

9.2数据流分析简介 354

9.2.1数据流抽象 354

9.2.2数据流分析模式 355

9.2.3基本块上的数据流模式 356

9.2.4到达定值 357

9.2.5活跃变量分析 362

9.2.6可用表达式 363

9.2.7小结 365

9.2.89.2节的练习 365

9.3数据流分析基础 367

9.3.1半格 368

9.3.2传递函数 371

9.3.3通用框架的迭代算法 372

9.3.4数据流解的含义 374

9.3.59.3节的练习 375

9.4常量传播 376

9.4.1常量传播框架的数据流值 376

9.4.2常量传播框架的交汇运算 377

9.4.3常量传播框架的传递函数 377

9.4.4常量传递框架的单调性 378

9.4.5常量传播框架的不可分配性 378

9.4.6对算法结果的解释 379

9.4.79.4节的练习 380

9.5流图中的循环 380

9.5.1支配结点 380

9.5.2深度优先排序 382

9.5.3深度优先生成树中的边 384

9.5.4回边和可归约性 384

9.5.5流图的深度 385

9.5.6自然循环 385

9.5.7迭代数据流算法的收敛速度 386

9.5.89.5节的练习 388

9.6第9章总结 389

9.7第9章参考文献 391

附录一个完整的编译器前端 394