新書推薦：
《
真希望父母能这样爱我
》
售價：HK$
54.8
《
动画视频+全彩图解 人工智能与无人驾驶汽车
》
售價：HK$
76.9
《
江恩时空理论：精华笔记图文版
》
售價：HK$
86.9
《
都市两极：北京14人
》
售價：HK$
74.8
《
时刻人文·1368：中国与现代世界之形成
》
售價：HK$
85.8
《
分歧与团结：以色列社会的运转逻辑和活力来源
》
售價：HK$
75.9
《
中国式管理（全集·全新）
》
售價：HK$
108.9
《
甲午战争中的北洋舰队
》
售價：HK$
63.8
|
| 編輯推薦： |
本书介绍了程序语言设计的基本方法，并以C、Pascal、MATLAB、C 语法为主，设计了一种语句形式丰富、书写简洁的编程语言，并给出了详细的语义计算规则。
本书对程序拓扑、数据流分析问题进行了详细展开，并在各类优化问题和目标代码生成中应用。
本书以x86为主，兼顾RISC架构，设计运行时空间分配策略，生成真实目标机器代码；对图着色、线性扫描等全局寄存器分配进行了实现层面的算法设计。
本书从基本原理入手，不依赖现有编译工具，试图手工构造整个编译器及编译所需工具。
|
| 內容簡介： |
本书聚焦编译器设计的难点、痛点，在第1 章概述编译器的基本构成，并从编译角度介绍高
來源：香港大書城megBookStore,http://www.megbook.com.hk
级程序设计语言、目标语言和中间语言；第2 章介绍文法的相关概念，以及如何进行程序语言设
计的问题；第3～9 章介绍编译器各组成部分的原理和设计，包括词法分析器、语法分析器、中间
代码生成器、中间代码优化器、目标代码生成器，以及符号表管理和运行时存储空间组织。
本书可以作为高等学校计算机专业本科生的教材，也可供从事计算机应用的工程技术人员或
其他自学者学习参考。本书力求使学生仅掌握一门高级语言，即可开发出一个完整可用的编译器，
从根本上解决国外技术依赖问题。
|
| 目錄：
|
第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
|
| 內容試閱：
|
编译器是将一种高级语言翻译成可以直接在机器上运行的低级语言的程
序，是芯片和操作系统生态中必不可少的基础软件之一。一个操作系统，需要有
可运行的编译器，程序员才能在上面开发各种应用软件，才能构建起应用生态。
编译原理与技术是讨论编译器设计与实现的课程，是一门理论性和实践
性都很强的学科，一直以来是计算机相关专业最难掌握的课程之一。编译器前
端的主要难点在于使用的形式语言与自动机相关理论，特别是有限自动机与
下推自动机的理论及其应用；从中间代码生成到编译器后端的主要难点在于，
它不是直接编码实现数据和硬件的操控，而是要编写程序生成代码，用生成的
代码操控数据和硬件，从而实现程序编写者的意图。
本书面向计算机专业学生和编译器开发者，从底层阐述编译器的基本原
理。在高级语言层面，引入目前流行的大部分语言特性，覆盖多种语言不同语
句的编译方法。在目标语言方面，以x86 为主，兼顾各种基于RISC 指令集的
架构，使编译的目标程序可以在真实机器上运行。在内容讲述方面，不仅介绍
原理，更注重可转换为代码的算法设计，使本书内容具有可实现性。
使用本书
本书从底层阐述编译器的基本原理，并且设计可转换为代码的算法，使
本书内容具有可实现性。高级语言层面，引入目前流行的大部分语言特性，覆
盖多种语言不同语句的翻译模式，如除常用的if 和while 语句外，还包括C 和
MATLAB 的for 语句、switch 语句、过程调用和返回、三元运算符、关系运算
符结合等。目标语言方面，以采用CISC 指令集的x86 架构为主，兼顾RISC 指
令集的其他架构，使编译的目标程序可以在真实机器上运行。代码优化方面，
对拓扑图构建和数据流分析进行了详细展开，设计了切实可行的全局优化和
循环优化算法。目标代码生成方面，除简单代码生成器外，也引入了完整的图
着色和线性扫描寄存器分配算法。
本书的教学参考学时数为64 学时。编译过程的每个环节，本书都可能会
有2～3 个相互独立的实现方法，通过选择性讲授部分内容，可以在48 学时内
实现一个完整的编译器设计的介绍。下面是各章的概要介绍。
? 第1 章给出编译器的基本概念、编译器组成的相关介绍；编译器涉及的
语言，包括高级程序设计语言、目标语言和中间语言，以及本书使用的
一些数学基础。
? 第2 章介绍文法和语言的基本概念、使用文法设计高级程序语言的基
本方法，以及一些文法等价变换方法。
? 第3 章讨论词法分析，主要涉及有限自动机、正规文法这些工具的相关理论和应用，
以及它们之间的相互转换。
? 第4 章讨论语法分析，包括自顶向下的LL(1) 分析法，以及自下而上的算符优先分
析法、LR 分析法。特别地，LL(1) 和LR 分析法都涉及了二义文法的处理。
? 第5 章介绍符号表管理，梳理了符号表应当记录的内容。
? 第6 章介绍运行时存储空间组织，包括目标代码运行时的活动、过程调用规范、运
行时库的构建和调用、堆式存储分配的管理等。
? 第7 章为语法分析配备各种动作，从而生成中间代码。
? 第8 章讨论中间代码优化，涉及程序拓扑结构的识别、局部优化技术、数据流分析
技术、全局优化和循环优化技术。
? 第9 章讨论目标代码生成。简单代码生成器中涉及了所有形式的中间代码的翻译、
基于语句重排的目标代码优化、面向循环的固定寄存器分配等内容。全局目标代码
生成器则着重介绍图着色寄存器分配和线性扫描寄存器分配。最后讨论了窥孔优
化。
一个48 学时甚至更少学时数的可行方案是：第1 章目标代码部分只介绍整型运算指令；
第2 章只介绍文法、语言、语法树和二义文法的概念；第3 章介绍从正规式转换到NFA，然
后确定为DFA，以及DFA 化简的内容；第4 章讨论LL(1) 和LR 分析法，甚至LL(1) 分析法
也可以不讲；第5 章只介绍符号表内容的部分；第6 章介绍栈帧结构、过程调用规范；第
7 章可以选择性地介绍一些代表性语句的翻译；第8 章可以只介绍流图构建和DAG 优化部
分，如果允许，可以介绍数据流分析；第9 章介绍简单代码生成器。
先修课
编译器的特点决定了学习它所需要的知识相当驳杂。学习本书的读者，应当拥有计算
机专业的一些综合知识，至少应当掌握两门程序设计语言，并掌握数据结构中线性表、栈、
队的相关知识。另外还需要一些其他课程的知识，如汇编程序设计、离散数学、计算机组
成原理、操作系统、数据结构的树和图等，相关内容会在使用前进行回顾性介绍。
致谢
本书稿撰写历时1 年8 个月零1 天，在这里，要感谢家人的支持。甚至家人可能比我更
想看到本书成稿。每当遇到困难，思及此，就能平静下来，切入技术部分的思考，督促我
完成了这项耗时且持久的工作。
另外，特别感谢我的学生们，同学们在科研方面的主动性使我可以有精力撰写本书。从
我的第一个学生起，把事情做好，而不是完成工作交差，就刻入每位学生的基因中。新同
学到来，学长学姐们会主动分享自己整理的学习资料，同学们看到好文章会主动做报告分
享；遇到问题，同学们会主动解决；如此种种，为我节省了相当多的时间。
在编写本书过程中，我找到了一个称为ElegantBook 的LaTeX 开源模板，为本书的排
版节省了大量时间和精力，感谢Ethan Deng 等作者。
郑艳伟
2025 年1 月23 日
|
|
購物車/收銀台(0) | 在線留言板
| 付款方式
| 運費計算
| 聯絡我們
| 幫助中心 |
加入書簽
HOME
新書上架
