编译原理2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载

编译原理PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第1章编译简介1

1.1编译器1

1.1.1编译的分析－综合模型1

1.1.2编译器的前驱与后继3

1.2源程序分析3

1.2.1词法分析3

1.2.2语法分析3

1.2.3语义分析5

1.2.4文本格式器中的分析5

1.3编译器的各阶段6

1.3.1符号表管理7

1.3.2错误检测与报告7

1.3.3各分析阶段7

1.3.4中间代码生成9

1.3.5代码优化9

1.3.6代码生成10

1.4编译器的伙伴10

1.4.1预处理器10

1.4.2汇编器11

1.4.3两遍汇编12

1.4.4装配器和连接编辑器12

1.5编译器各阶段的分组13

1.5.1前端与后端13

1.5.2编译器的遍13

1.5.3减少编译的遍数14

1.6编译器的构造工具14

参考文献注释15

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

2.1概述17

2.2语法定义17

2.2.1分析树19

2.2.2二义性20

2.2.3操作符的结合规则20

2.2.4操作符的优先级21

2.3语法制导翻译22

2.3.1后缀表示22

2.3.2语法制导定义22

2.3.3综合属性23

2.3.4深度优先遍历24

2.3.5翻译模式25

2.3.6翻译的输出25

2.4语法分析26

2.4.1自顶向下语法分析27

2.4.2预测分析法29

2.4.3何时使用∈产生式30

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

2.4.5左递归31

2.5简单表达式的翻译器32

2.5.1抽象语法和具体语法32

2.5.2调整翻译模式33

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

2.5.4翻译器的优化35

2.5.5完整程序35

2.6词法分析37

2.6.1剔除空白符和注释37

2.6.2常数37

2.6.3识别标识符和关键字37

2.6.4词法分析器的接口38

2.6.5词法分析器38

2.7符号表40

2.7.1符号表接口40

2.7.2处理保留的关键字41

2.7.3符号表的实现方法41

2.8抽象堆栈机42

2.8.1算术指令42

2.8.2左值和右值43

2.8.3堆栈操作43

2.8.4表达式的翻译43

2.8.5控制流44

2.8.6语句的翻译44

2.8.7输出一个翻译45

2.9技术的综合46

2.9.1翻译器的描述46

2.9.2词法分析器模块lexer.c47

2.9.3语法分析器模块parser.c48

2.9.4输出模块emitter.c48

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

2.9.6错误处理模块error.c48

2.9.7编译器的建立48

2.9.8程序清单49

练习53

编程练习54

参考文献注释55

第3章词法分析57

3.1词法分析器的作用57

3.1.1词法分析中的问题58

3.1.2记号、模式、词素58

3.1.3记号的属性59

3.1.4词法错误60

3.2输入缓冲60

3.2.1双缓冲区61

3.2.2标志62

3.3记号的描述62

3.3.1串和语言62

3.3.2语言上的运算63

3.3.3正规表达式64

3.3.4正规定义65

3.3.5缩写表示法66

3.3.6非正规集66

3.4记号的识别67

3.4.1状态转换图68

3.4.2状态转换图的实现70

3.5词法分析器描述语言72

3.5.1 Lex说明72

3.5.2超前扫描操作75

3.6有穷自动机76

3.6.1不确定的有穷自动机77

3.6.2确定的有穷自动机78

3.6.3从NFA到DFA的变换79

3.7从正规表达式到NFA81

3.7.1从正规表达式构造NFA81

3.7.2 NFA的双堆栈模拟84

3.7.3时间空间的权衡85

3.8设计词法分析器的生成器85

3.8.1基于NFA的模式匹配86

3.8.2词法分析器的DFA88

3.8.3实现超前扫描操作88

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

3.9.1 NFA的重要状态89

3.9.2从正规表达式到DFA89

3.9.3最小化DFA的状态数93

3.9.4词法分析器的状态最小化95

3.9.5表压缩方法95

练习97

编程练习103

参考文献注释103

第4章语法分析105

4.1语法分析器的作用105

4.1.1语法错误的处理106

4.1.2错误恢复策略108

4.2上下文无关文法109

4.2.1符号的使用约定110

4.2.2推导110

4.2.3分析树和推导112

4.2.4二义性113

4.3文法的编写113

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

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

4.3.3消除二义性115

4.3.4消除左递归116

4.3.5提取左因子117

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

4.4自顶向下语法分析120

4.4.1递归下降语法分析法120

4.4.2预测语法分析器121

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

4.4.4非递归的预测分析123

4.4.5 FIRST和FOLLOW124

4.4.6预测分析表的构造125

4.4.7 LL（1）文法126

4.4.8预测分析的错误恢复127

4.5自底向上语法分析128

4.5.1句柄129

4.5.2句柄裁剪130

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

4.5.4活前缀133

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

4.6算符优先分析法134

4.6.1使用算符优先关系135

4.6.2从结合律和优先级获得算符优先关系136

4.6.3处理一元操作符137

4.6.4优先函数137

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

4.7 LR语法分析器142

4.7.1 LR语法分析算法142

4.7.2 LR文法145

4.7.3构造SLR语法分析表146

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

4.7.5构造LALR语法分析表155

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

4.7.7 LR语法分析表的压缩161

4.8二义文法的应用163

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

4.8.2悬空else的二义性164

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

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

4.9语法分析器的生成器168

4.9.1语法分析器的生成器Yacc169

4.9.2用Yacc处理二义文法171

4.9.3用Lex建立Yacc的词法分析器173

4.9.4 Yacc的错误恢复174

练习174

参考文献注释182

第5章语法制导翻译185

5.1语法制导定义185

5.1.1语法制导定义的形式186

5.1.2综合属性186

5.1.3继承属性187

5.1.4依赖图187

5.1.5计算顺序189

5.2语法树的构造189

5.2.1语法树190

5.2.2构造表达式的语法树190

5.2.3构造语法树的语法制导定义191

5.2.4表达式的无环有向图192

5.3自底向上计算S属性定义194

5.4 L属性定义195

5.4.1 L属性定义196

5.4.2翻译模式196

5.5自顶向下翻译198

5.5.1从翻译模式中消除左递归198

5.5.2预测翻译器的设计201

5.6自底向上计算继承属性202

5.6.1删除嵌入在翻译模式中的动作202

5.6.2分析栈中的继承属性203

5.6.3模拟继承属性的计算204

5.6.4用综合属性代替继承属性206

5.6.5一个难计算的语法制导定义207

5.7递归计算207

5.7.1从左到右遍历207

5.7.2其他遍历方法208

5.8编译时属性值的空间分配209

5.8.1在编译时为属性分配空间209

5.8.2避免复制211

5.9编译器构造时的空间分配211

5.9.1从文法中预知生存期212

5.9.2不相重叠的生存期214

5.10语法制导定义的分析215

5.10.1属性的递归计算216

5.10.2强无环的语法制导定义216

5.10.3环形检测217

练习219

参考文献注释221

第6章类型检查223

6.1类型系统224

6.1.1类型表达式224

6.1.2类型系统225

6.1.3静态和动态类型检查226

6.1.4错误恢复226

6.2一个简单的类型检查器的说明226

6.2.1一种简单语言226

6.2.2表达式的类型检查227

6.2.3语句的类型检查228

6.2.4函数的类型检查228

6.3类型表达式的等价229

6.3.1类型表达式的结构等价229

6.3.2类型表达式的名字231

6.3.3类型表示中的环232

6.4类型转换233

6.5函数和运算符的重载234

6.5.1子表达式的可能类型的集合235

6.5.2缩小可能类型的集合236

6.6多态函数237

6.6.1为什么要使用多态函数237

6.6.2类型变量238

6.6.3包含多态函数的语言239

6.6.4代换、实例和合一240

6.6.5多态函数的检查241

6.7合一算法244

练习247

参考文献注释251

第7章运行时环境253

7.1源语言问题253

7.1.1过程253

7.1.2活动树253

7.1.3控制栈255

7.1.4声明的作用域256

7.1.5名字的绑定256

7.1.6一些问题257

7.2存储组织257

7.2.1运行时内存的划分257

7.2.2活动记录258

7.2.3编译时的局部数据布局259

7.3存储分配策略260

7.3.1静态存储分配260

7.3.2栈式存储分配262

7.3.3悬空引用265

7.3.4堆式存储分配265

7.4对非局部名字的访问266

7.4.1程序块267

7.4.2无嵌套过程的词法作用域268

7.4.3包含嵌套过程的词法作用域269

7.4.4动态作用域274

7.5参数传递275

7.5.1传值调用275

7.5.2引用调用276

7.5.3复制－恢复277

7.5.4传名调用277

7.6符号表278

7.6.1符号表表项278

7.6.2名字中的字符279

7.6.3存储分配信息280

7.6.4符号表的线性表数据结构280

7.6.5散列表281

7.6.6表示作用域的信息283

7.7支持动态存储分配的语言措施285

7.7.1垃圾单元285

7.7.2悬空引用286

7.8动态存储分配技术287

7.8.1固定块的显式分配287

7.8.2变长块的显式分配287

7.8.3隐式存储释放288

7.9 Fortran语言的存储分配288

7.9.1 COMMON域中的数据289

7.9.2一个简单的等价算法290

7.9.3 Fortran语言的等价算法292

7.9.4映射数据区294

练习294

参考文献注释298

第8章中间代码生成299

8.1中间语言299

8.1.1图表示299

8.1.2三地址码300

8.1.3三地址语句的类型301

8.1.4语法制导翻译生成三地址码302

8.1.5三地址语句的实现303

8.1.6表示方法比较：间址的使用305

8.2声明语句305

8.2.1过程中的声明语句305

8.2.2跟踪作用域信息306

8.2.3记录中的域名308

8.3赋值语句309

8.3.1符号表中的名字309

8.3.2临时名字的重用310

8.3.3寻址数组元素311

8.3.4数组元素寻址的翻译模式312

8.3.5赋值语句中的类型转换314

8.3.6记录域的访问315

8.4布尔表达式315

8.4.1翻译布尔表达式的方法316

8.4.2数值表示316

8.4.3短路代码317

8.4.4控制流语句317

8.4.5布尔表达式的控制流翻译319

8.4.6混合模式的布尔表达式321

8.5 case语句321

8.6回填323

8.6.1布尔表达式323

8.6.2控制流语句326

8.6.3翻译的实现方案326

8.6.4标号和goto327

8.7过程调用328

8.7.1调用序列328

8.7.2一个简单的例子328

练习329

参考文献注释331

第9章代码生成333

9.1代码生成器设计中的问题333

9.1.1代码生成器的输入333

9.1.2目标程序334

9.1.3存储管理334

9.1.4指令选择334

9.1.5寄存器分配335

9.1.6计算次序的选择336

9.1.7代码生成方法336

9.2目标机器336

9.3运行时存储管理338

9.3.1静态分配339

9.3.2栈式分配340

9.3.3名字的运行地址342

9.4基本块和流图343

9.4.1基本块343

9.4.2基本块的变换344

9.4.3保结构变换344

9.4.4代数变换345

9.4.5流图345

9.4.6基本块的表示345

9.4.7循环346

9.5下次引用信息346

9.5.1计算下次引用信息346

9.5.2临时名字的存储分配347

9.6一个简单的代码生成器347

9.6.1寄存器描述符和地址描述符348

9.6.2代码生成算法348

9.6.3函数getreg349

9.6.4为其他类型的语句生成代码350

9.6.5条件语句351

9.7寄存器分配与指派351

9.7.1全局寄存器分配352

9.7.2引用计数352

9.7.3外层循环的寄存器指派353

9.7.4图染色法寄存器分配354

9.8基本块的dag表示法354

9.8.1 dag的构造355

9.8.2 dag的应用357

9.8.3数组、指针和过程调用358

9.9窥孔优化359

9.9.1冗余加载与保存360

9.9.2不可达代码360

9.9.3控制流优化361

9.9.4代数化简361

9.9.5强度削弱361

9.9.6机器语言的使用362

9.10从dag生成代码362

9.10.1重排序362

9.10.2对dag的启发式排序362

9.10.3树的最优排序363

9.10.4标记算法364

9.10.5从标记树中产生代码364

9.10.6多寄存器操作367

9.10.7代数性质367

9.10.8公共子表达式368

9.11动态规划代码生成算法368

9.11.1一种寄存器计算机368

9.11.2动态规划的原理369

9.11.3邻近计算369

9.11.4动态规划算法369

9.12代码生成器的生成器371

9.12.1采用重写树技术的代码生成371

9.12.2借助语法分析的模式匹配375

9.12.3用于语义检查的例程376

练习376

参考文献注释378

第10章代码优化381

10.1引言381

10.1.1代码改进变换的准则381

10.1.2性能的提高382

10.1.3优化编译器的组织383

10.2优化的主要种类384

10.2.1保持功能变换385

10.2.2公共子表达式386

10.2.3复制传播387

10.2.4无用代码删除387

10.2.5循环优化388

10.2.6代码外提388

10.2.7归纳变量和强度削弱388

10.3基本块的优化390

10.4流图中的循环392

10.4.1支配节点392

10.4.2自然循环393

10.4.3内循环393

10.4.4前置首节点394

10.4.5可约流图394

10.5全局数据流分析介绍395

10.5.1点和路径396

10.5.2到达定义396

10.5.3结构化程序的数据流分析397

10.5.4对数据流信息的保守估计399

10.5.5 in和out的计算400

10.5.6处理循环401

10.5.7集合的表示402

10.5.8局部到达定义403

10.5.9引用－定义链404

10.5.10计算顺序404

10.5.11一般控制流404

10.6数据流方程的迭代解405

10.6.1到达定义的迭代算法406

10.6.2可用表达式408

10.6.3活跃变量分析410

10.6.4定义－引用链411

10.7代码改进变换412

10.7.1全局公共子表达式删除412

10.7.2复制传播413

10.7.3循环不变计算的检测415

10.7.4代码外提415

10.7.5可选的代码外提方案417

10.7.6代码外提后对数据流信息的维护418

10.7.7归纳变量删除418

10.7.8带有循环不变表达式的归纳变量421

10.8处理别名422

10.8.1一种简单的指针语言422

10.8.2指针赋值的作用422

10.8.3利用指针信息424

10.8.4过程间的数据流分析425

10.8.5带有过程调用的代码模型425

10.8.6别名的计算426

10.8.7存在过程调用时的数据流分析427

10.8.8 change信息的用途428

10.9结构化流图的数据流分析429

10.9.1深度优先搜索429

10.9.2流图的深度优先表示中的边431

10.9.3流图的深度431

10.9.4区间432

10.9.5区间划分432

10.9.6区间图433

10.9.7节点分裂433

10.9.8 T1-T2分析434

10.9.9区域434

10.9.10寻找支配节点435

10.10高效数据流算法436

10.10.1迭代算法中的深度优先顺序436

10.10.2基于结构的数据流分析437

10.10.3对基于结构的算法的一些速度上的改进440

10.10.4处理不可约流图441

10.11一个数据流分析工具441

10.11.1数据流分析框架442

10.11.2数据流分析框架的公理443

10.11.3单调性和分配性444

10.11.4数据流问题的聚合路径解447

10.11.5流问题的保守解447

10.11.6通用框架的迭代算法448

10.11.7一个数据流分析工具448

10.11.8算法10.18的性质449

10.11.9算法10.18的收敛性449

10.11.10初始化的修正450

10.12类型估计450

10.12.1处理无穷类型集451

10.12.2一个简单的类型系统452

10.12.3前向方案452

10.12.4后向方案453

10.13优化代码的符号调试455

10.13.1基本块中变量值的推断456

10.13.2全局优化的影响459

10.13.3归纳变量删除459

10.13.4全局公共子表达式删除459

10.13.5代码外提459

练习460

参考文献注释465

第11章编写一个编译器469

11.1编译器设计469

11.1.1源语言问题469

11.1.2目标语言问题469

11.1.3性能标准469

11.2编译器开发方法470

11.3编译器开发环境472

11.4测试与维护474

第12章编译器实例475

12.1数学排版预处理器EQN475

12.2 Pascal编译器475

12.3 C编译器476

12.4 Fortran H编译器477

12.4.1 Fortran H中的代码优化478

12.4.2代数优化478

12.4.3寄存器优化478

12.5 BLISS/1 1编译器479

12.6 Modula-2优化编译器480

附录一个程序设计项目483

参考文献489

索引511