编译原理PDF|Epub|txt|kindle电子书版本下载

编译原理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.3 1.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.8 1.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.7 2.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.6 2.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.6 2.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.5 3.1节的练习71

3.2输入缓冲71

3.2.1缓冲区对72

3.2.2哨兵标记72

3.3词法单元的规约73

3.3.1串和语言74

3.3.2语言上的运算75

3.3.3正则表达式75

3.3.4正则定义77

3.3.5正则表达式的扩展78

3.3.6 3.3节的练习78

3.4词法单元的识别80

3.4.1状态转换图82

3.4.2保留字和标识符的识别83

3.4.3完成我们的例子84

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

3.4.5 3.4节的练习86

3.5词法分析器生成工具Lex89

3.5.1Lex的使用89

3.5.2Lex程序的结构89

3.5.3Lex中的冲突解决91

3.5.4向前看运算符92

3.5.5 3.5节的练习92

3.6有穷自动机93

3.6.1不确定的有穷自动机93

3.6.2转换表94

3.6.3自动机中输入字符串的接受94

3.6.4确定的有穷自动机95

3.6.5 3.6节的练习96

3.7从正则表达式到自动机96

3.7.1从NFA到DFA的转换96

3.7.2NFA的模拟99

3.7.3NFA模拟的效率99

3.7.4从正则表达式构造NFA100

3.7.5字符串处理算法的效率103

3.7.6 3.7节的练习105

3.8词法分析器生成工具的设计105

3.8.1生成的词法分析器的结构105

3.8.2基于NFA的模式匹配106

3.8.3词法分析器使用的DFA107

3.8.4实现向前看运算符108

3.8.5 3.8节的练习109

3.9基于DFA的模式匹配器的优化109

3.9.1NFA的重要状态109

3.9.2根据抽象语法树计算得到的函数110

3.9.3计算nullable、firstpos及lastpos111

3.9.4计算followpos112

3.9.5根据正则表达式构建DFA113

3.9.6最小化一个DFA的状态数114

3.9.7词法分析器的状态最小化116

3.9.8DFA模拟中的时间和空间权衡116

3.9.9 3.9节的练习117

3.10第3章总结118

3.11第3章参考文献119

第4章 语法分析121

4.1引论121

4.1.1语法分析器的作用121

4.1.2代表性的文法122

4.1.3语法错误的处理123

4.1.4错误恢复策略123

4.2上下文无关文法124

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

4.2.2符号表示的约定125

4.2.3推导126

4.2.4语法分析树和推导127

4.2.5二义性128

4.2.6验证文法生成的语言129

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

4.2.8 4.2节的练习130

4.3设计文法132

4.3.1词法分析和语法分析132

4.3.2消除二义性133

4.3.3左递归的消除134

4.3.4提取左公因子135

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

4.3.6 4.3节的练习137

4.4自顶向下的语法分析137

4.4.1递归下降的语法分析139

4.4.2FIRST和FOLLOW140

4.4.3LL（1）文法141

4.4.4非递归的预测分析144

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

4.4.6 4.4节的练习147

4.5自底向上的语法分析148

4.5.1归约149

4.5.2句柄剪枝149

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

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

4.5.5 4.5节的练习152

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

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

4.6.2项和LR（0）自动机154

4.6.3LR语法分析算法158

4.6.4构造SLR语法分析表161

4.6.5可行前缀163

4.6.6 4.6节的练习164

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

4.7.1规范LR（1）项165

4.7.2构造LR（1）项集166

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

4.7.4构造LALR语法分析表170

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

4.7.6LR语法分析表的压缩176

4.7.7 4.7节的练习177

4.8使用二义性文法178

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

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

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

4.8.4 4.8节的练习182

4.9语法分析器生成工具183

4.9.1语法分析器生成工具Yacc183

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

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

4.9.4Yacc中的错误恢复188

4.9.5 4.9节的练习189

4.10第4章总结189

4.11第4章参考文献191

第5章 语法制导的翻译194

5.1语法制导定义194

5.1.1继承属性和综合属性195

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

5.1.3 5.1节的练习198

5.2SDD的求值顺序198

5.2.1依赖图198

5.2.2属性求值的顺序199

5.2.3S属性的定义200

5.2.4L属性的定义200

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

5.2.6 5.2节的练习202

5.3语法制导翻译的应用203

5.3.1抽象语法树的构造203

5.3.2类型的结构206

5.3.3 5.3节的练习207

5.4语法制导的翻译方案207

5.4.1后缀翻译方案207

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

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

5.4.4从SDT中消除左递归210

5.4.5L属性定义的SDT212

5.4.6 5.4节的练习216

5.5实现L属性的SDD216

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

5.5.2边扫描边生成代码219

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

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

5.5.5 5.5节的练习226

5.6第5章总结227

5.7第5章参考文献228

第6章 中间代码生成229

6.1语法树的变体230

6.1.1表达式的有向无环图230

6.1.2构造DAG的值编码方法231

6.1.3 6.1节的练习232

6.2三地址代码233

6.2.1地址和指令233

6.2.2四元式表示235

6.2.3三元式表示235

6.2.4静态单赋值形式237

6.2.5 6.2节的练习237

6.3类型和声明237

6.3.1类型表达式238

6.3.2类型等价239

6.3.3声明239

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

6.3.5声明的序列241

6.3.6记录和类中的字段242

6.3.7 6.3节的练习242

6.4表达式的翻译243

6.4.1表达式中的运算243

6.4.2增量翻译244

6.4.3数组元素的寻址245

6.4.4数组引用的翻译246

6.4.5 6.4节的练习247

6.5类型检查248

6.5.1类型检查规则248

6.5.2类型转换249

6.5.3函数和运算符的重载250

6.5.4类型推导和多态函数251

6.5.5一个合一算法254

6.5.6 6.5节的练习256

6.6控制流256

6.6.1布尔表达式257

6.6.2短路代码257

6.6.3控制流语句257

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

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

6.6.6布尔值和跳转代码262

6.6.7 6.6节的练习263

6.7回填263

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

6.7.2布尔表达式的回填264

6.7.3控制转移语句266

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

6.7.5 6.7节的练习268

6.8switch语句269

6.8.1switch语句的翻译269

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

6.8.3 6.8节的练习271

6.9过程的中间代码271

6.10第6章总结272

6.11第6章参考文献273

第7章 运行时刻环境275

7.1存储组织275

7.2空间的栈式分配276

7.2.1活动树277

7.2.2活动记录279

7.2.3调用代码序列280

7.2.4栈中的变长数据282

7.2.5 7.2节的练习283

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

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

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

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

7.3.4嵌套深度285

7.3.5访问链286

7.3.6处理访问链287

7.3.7过程型参数的访问链288

7.3.8显示表289

7.3.9 7.3节的练习290

7.4堆管理291

7.4.1存储管理器291

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

7.4.3程序中的局部性293

7.4.4碎片整理295

7.4.5人工回收请求297

7.4.6 7.4节的练习299

7.5垃圾回收概述299

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

7.5.2可达性301

7.5.3引用计数垃圾回收器302

7.5.4 7.5节的练习303

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

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

7.6.2基本抽象305

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

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

7.6.5拷贝回收器309

7.6.6开销的比较311

7.6.7 7.6节的练习311

7.7短停顿垃圾回收311

7.7.1增量式垃圾回收312

7.7.2增量式可达性分析313

7.7.3部分回收概述314

7.7.4世代垃圾回收315

7.7.5列车算法316

7.7.6 7.7节的练习318

7.8垃圾回收中的高级论题319

7.8.1并行和并发垃圾回收319

7.8.2部分对象重新定位321

7.8.3类型不安全的语言的保守垃圾回收321

7.8.4弱引用322

7.8.5 7.8节的练习322

7.9第7章总结322

7.10第7章参考文献324

第8章 代码生成326

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

8.1.1代码生成器的输入327

8.1.2目标程序327

8.1.3指令选择328

8.1.4寄存器分配329

8.1.5求值顺序330

8.2目标语言330

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

8.2.2程序和指令的代价332

8.2.3 8.2节的练习332

8.3目标代码中的地址334

8.3.1静态分配334

8.3.2栈分配335

8.3.3名字的运行时刻地址337

8.3.4 8.3节的练习337

8.4基本块和流图338

8.4.1基本块339

8.4.2后续使用信息340

8.4.3流图340

8.4.4流图的表示方式341

8.4.5循环341

8.4.6 8.4节的练习342

8.5基本块的优化342

8.5.1基本块的DAG表示342

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

8.5.3消除死代码344

8.5.4代数恒等式的使用344

8.5.5数组引用的表示345

8.5.6指针赋值和过程调用346

8.5.7从DAG到基本块的重组347

8.5.8 8.5节的练习348

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

8.6.1寄存器和地址描述符349

8.6.2代码生成算法349

8.6.3函数getReg的设计352

8.6.4 8.6节的练习352

8.7窥孔优化353

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

8.7.2消除不可达代码354

8.7.3控制流优化354

8.7.4代数化简和强度消减355

8.7.5使用机器特有的指令355

8.7.6 8.7节的练习355

8.8寄存器分配和指派355

8.8.1全局寄存器分配356

8.8.2使用计数356

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

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

8.8.5 8.8节的练习359

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

8.9.1树翻译方案359

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

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

8.9.4用于语义检查的例程363

8.9.5通用的树匹配方法363

8.9.6 8.9节的练习364

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

8.10.1Ershov数365

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

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

8.10.4 8.10节的练习368

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

8.11.1连续求值368

8.11.2动态规划的算法369

8.11.3 8.11节的练习371

8.12第8章总结371

8.13第8章参考文献372

第9章 机器无关优化374

9.1优化的主要来源374

9.1.1冗余的原因374

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

9.1.3保持语义不变的转换377

9.1.4全局公共子表达式377

9.1.5复制传播378

9.1.6死代码消除379

9.1.7代码移动379

9.1.8归纳变量和强度消减380

9.1.9 9.1节的练习381

9.2数据流分析简介382

9.2.1数据流抽象382

9.2.2数据流分析模式383

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

9.2.4到达定值385

9.2.5活跃变量分析390

9.2.6可用表达式391

9.2.7小结393

9.2.8 9.2节的练习394

9.3数据流分析基础395

9.3.1半格396

9.3.2传递函数399

9.3.3通用框架的迭代算法400

9.3.4数据流解的含义402

9.3.5 9.3节的练习404

9.4常量传播404

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

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

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

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

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

9.4.6对算法结果的解释407

9.4.7 9.4节的练习408

9.5部分冗余消除408

9.5.1冗余的来源408

9.5.2可能消除所有冗余吗410

9.5.3懒惰代码移动问题411

9.5.4表达式的预期执行412

9.5.5懒惰代码移动算法413

9.5.6 9.5节的练习418

9.6流图中的循环419

9.6.1支配结点419

9.6.2深度优先排序421

9.6.3深度优先生成树中的边423

9.6.4回边和可归约性423

9.6.5流图的深度424

9.6.6自然循环424

9.6.7迭代数据流算法的收敛速度425

9.6.8 9.6节的练习427

9.7基于区域的分析428

9.7.1区域429

9.7.2可归约流图的区域层次结构429

9.7.3基于区域的分析技术概述431

9.7.4有关传递函数的必要假设431

9.7.5一个基于区域的分析算法433

9.7.6处理不可归约流图436

9.7.7 9.7节的练习437

9.8符号分析437

9.8.1参考变量的仿射表达式438

9.8.2数据流问题的公式化440

9.8.3基于区域的符号化分析442

9.8.4 9.8节的练习445

9.9第9章总结445

9.10第9章参考文献448

第10章 指令级并行性450

10.1处理器体系结构450

10.1.1指令流水线和分支延时451

10.1.2流水线执行451

10.1.3多指令发送451

10.2代码调度约束452

10.2.1数据依赖452

10.2.2寻找内存访问之间的依赖关系453

10.2.3寄存器使用和并行性之间的折衷454

10.2.4寄存器分配阶段和代码调度阶段之间的顺序455

10.2.5控制依赖455

10.2.6对投机执行的支持456

10.2.7一个基本的机器模型457

10.2.8 10.2节的练习458

10.3基本块调度459

10.3.1数据依赖图459

10.3.2基本块的列表调度方法460

10.3.3带优先级的拓扑排序461

10.3.4 10.3节的练习461

10.4全局代码调度462

10.4.1基本的代码移动462

10.4.2向上的代码移动463

10.4.3向下的代码移动464

10.4.4更新数据依赖关系465

10.4.5全局调度算法465

10.4.6高级代码移动技术467

10.4.7和动态调度器的交互468

10.4.8 10.4节的练习468

10.5软件流水线化468

10.5.1引言468

10.5.2循环的软件流水线化470

10.5.3寄存器分配和代码生成471

10.5.4Do-Across循环472

10.5.5软件流水线化的目标和约束472

10.5.6一个软件流水线化算法474

10.5.7对无环数据依赖图进行调度475

10.5.8对有环数据依赖图进行调度476

10.5.9对流水线化算法的改进480

10.5.10模数变量扩展480

10.5.11条件语句482

10.5.12软件流水线化的硬件支持483

10.5.13 10.5节的练习483

10.6第10章总结484

10.7第10章参考文献485

第11章 并行性和局部性优化487

11.1基本概念488

11.1.1多处理器488

11.1.2应用中的并行性490

11.1.3循环层次上的并行性491

11.1.4数据局部性492

11.1.5仿射变换理论概述493

11.2矩阵乘法：一个深入的例子495

11.2.1矩阵相乘算法495

11.2.2优化497

11.2.3高速缓存干扰499

11.2.4 11.2节的练习499

11.3迭代空间499

11.3.1从循环嵌套结构中构建迭代空间499

11.3.2循环嵌套结构的执行顺序501

11.3.3不等式组的矩阵表示方法501

11.3.4混合使用符号常量502

11.3.5控制执行的顺序502

11.3.6坐标轴的变换505

11.3.7 11.3节的练习506

11.4仿射的数组下标507

11.4.1仿射访问507

11.4.2实践中的仿射访问和非仿射访问508

11.4.3 11.4节的练习508

11.5数据复用509

11.5.1数据复用的类型509

11.5.2自复用510

11.5.3自空间复用513

11.5.4组复用514

11.5.5 11.5节的练习515

11.6数组数据依赖关系分析516

11.6.1数组访问的数据依赖关系的定义517

11.6.2整数线性规划518

11.6.3GCD测试518

11.6.4解决整数线性规划的启发式规则520

11.6.5解决一般性的整数线性规划问题522

11.6.6小结523

11.6.7 11.6节的练习523

11.7寻找无同步的并行性524

11.7.1一个介绍性的例子525

11.7.2仿射空间分划526

11.7.3空间分划约束527

11.7.4求解空间分划约束529

11.7.5一个简单的代码生成算法531

11.7.6消除空迭代533

11.7.7从最内层循环中消除条件测试535

11.7.8源代码转换537

11.7.9 11.7节的练习539

11.8并行循环之间的同步541

11.8.1固定多个同步运算541

11.8.2程序依赖图542

11.8.3层次结构化的时间543

11.8.4并行化算法544

11.8.5 11.8节的练习545

11.9流水线化技术545

11.9.1什么是流水线化545

11.9.2连续过松弛方法：一个例子546

11.9.3完全可交换循环547

11.9.4把完全可交换循环流水线化548

11.9.5一般性的理论549

11.9.6时间分划约束549

11.9.7用Farkas引理求解时间分划约束552

11.9.8代码转换554

11.9.9具有最小同步量的并行性557

11.9.10 11.9节的练习559

11.10局部性优化560

11.10.1计算结果数据的时间局部性560

11.10.2数组收缩560

11.10.3分划单元的交织562

11.10.4合成565

11.10.5 11.10节的练习566

11.11仿射转换的其他用途566

11.11.1分布式内存计算机566

11.11.2多指令发送处理器567

11.11.3向量和SIMD指令567

11.11.4数据预取567

11.12第11章总结568

11.13第11章参考文献570

第12章 过程间分析573

12.1基本概念573

12.1.1调用图573

12.1.2上下文相关574

12.1.3调用串576

12.1.4基于克隆的上下文相关分析577

12.1.5基于摘要的上下文相关分析578

12.1.6 12.1节的练习579

12.2为什么需要过程间分析580

12.2.1虚方法调用580

12.2.2指针别名分析581

12.2.3并行化581

12.2.4软件错误和漏洞的检测581

12.2.5SQL注入581

12.2.6缓冲区溢出582

12.3数据流的一种逻辑表示方式583

12.3.1Datalog简介583

12.3.2Datalog规则584

12.3.3内涵断言和外延断言585

12.3.4Datalog程序的执行587

12.3.5Datalog程序的增量计算588

12.3.6有问题的Datalog规则589

12.3.7 12.3节的练习590

12.4一个简单的指针分析算法591

12.4.1为什么指针分析有难度591

12.4.2一个指针和引用的模型592

12.4.3控制流无关性592

12.4.4在Datalog中的表示方法593

12.4.5使用类型信息594

12.4.6 12.4节的练习595

12.5上下文无关的过程间分析595

12.5.1一个方法调用的效果595

12.5.2在Datalog中发现调用图596

12.5.3动态加载和反射597

12.5.4 12.5节的练习597

12.6上下文相关指针分析598

12.6.1上下文和调用串598

12.6.2在Datalog规则中加入上下文信息600

12.6.3关于相关性的更多讨论600

12.6.4 12.6节的练习600

12.7使用BDD的Datalog的实现601

12.7.1分决策图601

12.7.2对BDD的转换602

12.7.3用BDD表示关系603

12.7.4用BDD操作实现关系运算603

12.7.5在指针指向分析中使用BDD605

12.7.6 12.7节的练习605

12.8第12章总结606

12.9第12章参考文献607

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

附录B 寻找线性独立解630