目录
第1 章编译器概述................................. 1
1.1 编译器的基本概念..................... 1
1.1.1 语言的分类..................... 1
1.1.2 程序设计语言分类........... 2
1.1.3 编译程序........................ 2
1.1.4 编译原理与技术的特点.... 3
1.1.5 编译程序的生成.............. 4
1.1.6 本书定位........................ 5
1.2 高级程序设计语言..................... 7
1.2.1 高级语言分类................. 7
1.2.2 程序结构...................... 10
1.2.3 数据类型...................... 13
1.2.4 语句形式...................... 15
1.3 目标语言................................. 20
1.3.1 CPU 架构和指令集........ 20
1.3.2 寄存器......................... 21
1.3.3 汇编程序结构............... 24
1.3.4 汇编指令...................... 26
1.3.5 寻址方式及记号约定..... 26
1.3.6 传送指令...................... 27
1.3.7 基本运算指令............... 28
1.3.8 转移指令...................... 31
1.3.9 栈操作指令................... 32
1.3.10 浮点指令.................... 33
1.4 中间语言................................. 36
1.4.1 后缀式......................... 36
1.4.2 图表示法...................... 37
1.4.3 三地址码...................... 38
1.5 编译器组成............................. 40
1.5.1 编译器框架................... 40
1.5.2 编译前端与后端.............................. 43
1.6 数学基础..... 44
1.6.1 数理逻辑和记号.............................. 44
1.6.2 集合论........................................... 45
1.6.3 图论. 46
第1 章习题...... 48
第2 章文法与语言设计.......................................... 49
2.1 文法和语言. 49
2.1.1 基本概念........................................ 49
2.1.2 文法. 50
2.1.3 推导和归约..................................... 52
2.1.4 语言. 53
2.1.5 文法的Chomsky 分类...................... 55
2.2 语法树与二义文法..................................... 56
2.2.1 短语和句柄..................................... 56
2.2.2 语法树........................................... 57
2.2.3 二义文法........................................ 58
2.3 程序语言设计............................................ 59
2.3.1 正规式........................................... 60
2.3.2 正规式等价变换.............................. 61
2.3.3 基本运算的文法设计....................... 61
2.3.4 连接-闭包和闭包-连接..................... 62
2.3.5 拆分括号对..................................... 63
2.3.6 表达式的优先级与结合性................. 64
2.4 文法的等价变换......................................... 65
2.4.1 消除无用产生式.............................. 65
2.4.2 消除单非产生式.............................. 69
2.4.3 消除空符产生式.............................. 72
第2 章习题...... 75
第3 章词法分析...... 76
3.1 词法分析器的设计..................................... 76
3.1.1 词法分析器的任务........................... 76
3.1.2 词法分析器设计需要考虑的问题....... 77
3.1.3 状态转换图..................................... 78
3.2 有限自动机. 79
3.2.1 确定有限自动机.............................. 79
3.2.2 非确定有限自动机........................... 84
3.2.3 非确定有限自动机确定化................. 85
3.2.4 确定有限自动机化简....................... 94
3.2.5 正规式与有限自动机的等价性.......... 98
3.3 正规文法.... 100
3.3.1 右线性文法转有限自动机................ 100
3.3.2 左线性文法转有限自动机................ 101
3.3.3 有限自动机转右线性文法................ 102
3.3.4 有限自动机转左线性文法................ 103
3.3.5 正规式转右线性文法...................... 104
3.3.6 正规式转左线性文法...................... 105
3.3.7 正规文法转正规式.......................... 106
3.3.8 3 种工具的转换.............................. 106
3.3.9 有限自动机转正规式...................... 107
3.4 词法分析器的实现.................................... 108
3.4.1 词法分析器边界............................. 108
3.4.2 单词正规式.................................... 109
3.4.3 识别单词的DFA ............................ 110
3.4.4 单词识别算法................................ 113
第3 章习题..... 115
第4 章语法分析..... 116
4.1 LL(1) 分析法............................................ 116
4.1.1 自上而下分析................................ 116
4.1.2 消除显式左递归............................. 119
4.1.3 消除隐含左递归............................. 120
4.1.4 消除左公因子................................ 121
4.1.5 首符集First .................................. 122
4.1.6 后继符集Follow ............................ 124
4.1.7 LL(1) 预测分析表........................... 127
4.1.8 LL(1) 分析程序.............................. 129
4.1.9 二义文法的LL(1) 分析................... 132
4.1.10 递归下降分析器........................... 134
4.2 算符优先分析法........................................ 136
4.2.1 算符优先文法................................ 136
4.2.2 首尾终结符集................................ 137
4.2.3 使用栈求首、尾终结符集................ 139
4.2.4 算符优先分析表............................. 143
4.2.5 算符优先分析程序.......................... 145
4.2.6 优先函数....................................... 149
4.2.7 用可达矩阵构造算符优先函数......... 150
4.3 LR 分析法.. 152
4.3.1 LR(0) 分析的基本思想.................... 152
4.3.2 拓广文法....................................... 157
4.3.3 LR(0) 项目集规范族....................... 157
4.3.4 LR(0) 项目集规范族的构造............. 158
4.3.5 LR(0) 分析表构造.......................... 161
4.3.6 LR 分析器..................................... 164
4.3.7 LR(0) 分析法的局限性.................... 166
4.3.8 SLR(1) 分析表构造........................ 171
4.3.9 SLR(1) 分析法的局限性.................. 173
4.3.10 LR(1) 项目集规范族的构造........... 177
4.3.11 LR(1) 分析表构造......................... 180
4.3.12 LALR(1) 项目集规范族的构造....... 184
4.3.13 二义文法的LR 分析...................... 186
第4 章习题..... 194
第5 章符号表管理.. 195
5.1 作用与操作 195
5.2 表项内容.... 195
5.2.1 变量 196
5.2.2 数组 196
5.2.3 结构体.......................................... 197
5.2.4 过程 198
5.2.5 标号 198
5.3 结构组织.... 198
5.3.1 嵌套定义过程................................ 198
5.3.2 符号表栈....................................... 201
5.3.3 非嵌套定义过程............................. 202
5.4 内容组织.... 203
5.4.1 表格组织....................................... 203
5.4.2 表记录组织.................................... 204
5.4.3 面向对象的组织............................. 206
5.5 排序与查找 207
5.5.1 线性组织....................................... 207
5.5.2 二叉树.......................................... 208
5.5.3 平衡二叉树.................................... 209
5.5.4 哈希表.......................................... 214
第5 章习题..... 217
第6 章运行时存储空间组织.................................. 218
6.1 目标代码运行时的活动.............................. 218
6.1.1 运行时存储空间访问...................... 218
6.1.2 栈帧结构....................................... 218
6.1.3 存储空间分配策略.......................... 221
6.2 过程调用规范........................................... 222
6.2.1 高级程序参数传递.......................... 222
6.2.2 std call .......................................... 224
6.2.3 C 调用规范.................................... 225
6.2.4 x64 调用规范................................. 226
6.2.5 寄存器保护.................................... 227
6.2.6 地址计算....................................... 227
6.2.7 ARM 规范..................................... 229
6.3 运行时库.... 229
6.3.1 使用C 运行时库输入/输出.............. 229
6.3.2 编译器生成输入/输出代码.............. 231
6.3.3 幂运算.......................................... 234
6.3.4 跨文件调用.................................... 237
6.3.5 封装库.......................................... 238
6.4 嵌套定义过程........................................... 239
6.4.1 静态链.......................................... 239
6.4.2 静态链构建.................................... 242
6.4.3 外层变量访问................................ 243
6.4.4 嵌套层次显示表............................. 244
6.4.5 display 表的构建............................ 246
6.4.6 通过display 访问变量..................... 246
6.5 堆式存储分配........................................... 247
6.5.1 堆区首地址.................................... 247
6.5.2 定长块管理.................................... 247
6.5.3 保留元数据.................................... 249
6.5.4 变长块管理.................................... 250
6.5.5 存储回收....................................... 254
第6 章习题..... 254
第7 章语法制导翻译与中间代码生成..................... 255
7.1 属性文法及其计算.................................... 256
7.1.1 属性翻译文法................................ 256
7.1.2 综合属性的自下而上计算................ 258
7.1.3 继承属性的自上而下计算................ 259
7.1.4 依赖图.......................................... 259
7.1.5 树遍历的计算方法.......................... 260
7.1.6 一遍扫描的处理方法...................... 263
7.2 S-属性文法. 263
7.2.1 S-属性文法的自下而上计算............. 263
7.2.2 构造表达式的抽象语法树................ 264
7.2.3 NFA 箭弧单符化............................ 266
7.3 L-属性文法. 269
7.3.1 翻译模式....................................... 270
7.3.2 L-属性文法自上而下计算................ 271
7.3.3 L-属性文法自下而上计算................ 275
7.3.4 综合属性代替继承属性................... 278
7.4 声明语句的翻译........................................ 279
7.4.1 Pascal 风格过程内声明语句............ 280
7.4.2 Pascal 风格过程定义与声明语句...... 283
7.4.3 Pascal 风格数组声明...................... 288
7.4.4 Pascal 风格结构体声明................... 293
7.4.5 C 风格函数定义与声明语句............. 297
7.5 表达式与赋值语句的翻译.......................... 305
7.5.1 算术表达式与赋值语句................... 305
7.5.2 Pascal 风格数组的引用................... 307
7.5.3 C 风格数组的引用.......................... 312
7.5.4 结构体的引用................................ 312
7.5.5 作为逻辑运算的布尔表达式............ 316
7.5.6 地址和指针的引用.......................... 319
7.6 控制语句的翻译........................................ 322
7.6.1 真、假出口链................................ 322
7.6.2 四元式链操作................................ 323
7.6.3 作为条件控制的布尔表达式............ 325
7.6.4 if 和while 语句............................... 329
7.6.5 C 风格for 语句............................... 335
7.6.6 MATLAB 风格for 语句................... 338
7.6.7 标号-goto 语句............................... 343
7.6.8 switch 语句.................................... 346
7.6.9 break 和continue 语句.................... 351
7.6.10 三元运算符.................................. 356
7.6.11 关系运算符的结合........................ 358
7.7 过程语句的翻译........................................ 361
7.7.1 过程的开始与结束标记................... 361
7.7.2 返回语句....................................... 361
7.7.3 过程调用....................................... 361
7.8 类型检查.... 363
7.8.1 类型表达式.................................... 363
7.8.2 翻译模式....................................... 364
7.8.3 隐式转换....................................... 367
7.8.4 显式转换....................................... 370
第7 章习题..... 370
第8 章中间代码优化............................................ 371
8.1 程序的拓扑结构........................................ 371
8.1.1 优化代码例子................................ 371
8.1.2 基本块划分.................................... 373
8.1.3 流图构建....................................... 375
8.1.4 支配结点....................................... 377
8.1.5 回边识别....................................... 379
8.1.6 循环识别....................................... 381
8.1.7 循环层次....................................... 384
8.1.8 支配树.......................................... 386
8.1.9 四元式编号调整............................. 389
8.2 常用优化技术........................................... 391
8.2.1 优化的基本概念............................. 391
8.2.2 删除公共子表达式.......................... 392
8.2.3 复写传播....................................... 393
8.2.4 删除无用赋值................................ 394
8.2.5 代码外提....................................... 394
8.2.6 强度削弱....................................... 395
8.2.7 合并已知常量................................ 395
8.2.8 删除归纳变量................................ 396
8.3 局部优化.... 397
8.3.1 基本块的DAG 表示........................ 397
8.3.2 DAG 优化的基本思想..................... 398
8.3.3 DAG 优化算法............................... 398
8.3.4 变量附加的处理............................. 405
8.3.5 数组的处理.................................... 406
8.4 数据流分析 407
8.4.1 任意路径反向流分析...................... 408
8.4.2 任意路径前向流分析...................... 413
8.4.3 全路径前向流分析.......................... 417
8.4.4 全路径反向流分析.......................... 422
8.4.5 数据流问题的分类.......................... 425
8.4.6 到达定值分析................................ 426
8.4.7 引用-定值链.................................. 430
8.4.8 带引用点的活跃变量分析................ 432
8.4.9 定值-引用链.................................. 435
8.5 全局优化.... 438
8.5.1 代码提升....................................... 438
8.5.2 全局公共子表达式删除................... 442
8.5.3 删除无用赋值................................ 447
8.5.4 未初始化变量检测.......................... 450
8.5.5 复写传播和常量传播...................... 452
8.6 循环优化.... 454
8.6.1 代码外提....................................... 454
8.6.2 归纳变量识别................................ 458
8.6.3 强度削弱....................................... 460
8.6.4 归纳变量删除................................ 462
第8 章习题..... 465
第9 章目标代码生成............................................ 466
9.1 基本问题.... 466
9.1.1 代码生成器的输入.......................... 466
9.1.2 目标程序的形式............................. 467
9.1.3 指令选择....................................... 467
9.1.4 指令调度....................................... 468
9.1.5 寄存器分配.................................... 469
9.2 简单代码生成器........................................ 469
9.2.1 代码书写约定................................ 469
9.2.2 待用信息....................................... 470
9.2.3 寄存器描述符和地址描述符............ 473
9.2.4 简单代码生成算法.......................... 474
9.2.5 局部寄存器分配............................. 477
9.2.6 释放寄存器.................................... 478
9.2.7 简单代码生成示例.......................... 479
9.3 目标代码映射........................................... 481
9.3.1 整型运算....................................... 481
9.3.2 浮点运算....................................... 482
9.3.3 数组 484
9.3.4 转移语句....................................... 484
9.3.5 地址和指针.................................... 485
9.3.6 类型转换....................................... 486
9.3.7 程序和过程.................................... 486
9.3.8 指令的执行代价............................. 487
9.4 基于DAG 的目标代码优化......................... 488
9.4.1 基本思想....................................... 488
9.4.2 DAG 结点重排............................... 489
9.5 面向循环的固定寄存器分配....................... 491
9.5.1 固定寄存器分配代价计算................ 492
9.5.2 循环代码生成................................ 494
9.6 图着色寄存器分配.................................... 497
9.6.1 算法框架....................................... 497
9.6.2 分配虚拟寄存器............................. 498
9.6.3 低级中间代码表示.......................... 501
9.6.4 构建冲突图.................................... 502
9.6.5 合并寄存器.................................... 509
9.6.6 构建邻接表.................................... 514
9.6.7 计算溢出代价................................ 517
9.6.8 修剪冲突图.................................... 521
9.6.9 图着色.......................................... 523
9.6.10 分配物理寄存器........................... 524
9.6.11 生成溢出代码............................... 525
9.7 线性扫描寄存器分配................................. 531
9.7.1 流图线性化.................................... 532
9.7.2 计算活跃区间................................ 532
9.7.3 分配物理寄存器............................. 536
9.8 全局目标代码生成.................................... 544
9.8.1 全局代码生成框架.......................... 544
9.8.2 操作数访问.................................... 545
9.8.3 运算指令....................................... 547
9.8.4 加载保存指令................................ 548
9.8.5 数组指令....................................... 549
9.8.6 地址指针指令................................ 550
9.8.7 转移指令....................................... 551
9.8.8 过程指令....................................... 551
9.8.9 过程调用指令................................ 553
9.8.10 代码生成示例............................... 554
9.9 窥孔优化.... 558
9.9.1 目标代码表示................................ 558
9.9.2 简单窥孔优化模式.......................... 558
9.9.3 真、假出口转移合并...................... 559
9.9.4 不可达代码删除............................. 561
9.9.5 控制流优化.................................... 562
9.9.6 窥孔优化框架................................ 564
第9 章习题..... 565
附录A 面向对象语言的翻译................................. 566
