“编译技术”课程提供了理解程序如何被计算机执行的理论基石和关键技术。本书内容组织严密，循序渐进地介绍编译技术核心环节。第 1 章为绪论，第 2 章为高级语言设计基础，第 3 章为词法分析，第 4 章为自上而下的语法分析，第 5 章为自下而上的语法分析，第 6 章为语法制导的翻译，第 7 章为中间代码生成，第 8 章为过程存储分配，第 9 章为目标代码生成，第 10 章为国产编译器进展，第 11 章为词法分析工具 Lex，第 12 章为语法分析工具 yacc。本书为国家一流课程“编译技术”的配套教材，本书配套的视频课程在中国大学慕课平台开设，对应的实验已经放置在头歌实践教学平台。本书可作为高等院校软件工程专业及相关专业“编译原理”“编译技术”课程的教材。

江贺，教授、博导，辽宁省政协委员，国家高层次人才、国家优秀青年科学基金获得者（优青）、教育部新世纪人才。担任大连理工大学信息学部副主任委员，大连理工大学人工智能大连研究院院长，全国编译技术虚拟教研室副主任委员、教育部101计划课程建设组专家、计算机学会软件工程专委会常务委员、计算机学会青年科学家学术前沿探索丛书编委会委员、中国信标委软件与系统工程分技术委员会委员、大连YOCSEF主席（2021-2022）。

第１章 绪论 ................................................. 1
1.1 编译器的定义和功能 ................... 1
1.1.1 编译器的主要组件 ............. 1
1.1.2 编译器的工作流程 ............. 3
1.2 程序语言的类型 ........................... 3
1.2.1 机器语言、汇编语言和高级语言 ............................. 3
1.2.2 高级语言的类型 ................. 4
1.3 编译过程和编译器的结构 ........... 5
1.3.1 词法分析阶段 ..................... 5
1.3.2 语法分析阶段 ..................... 6
1.3.3 语义分析阶段 ..................... 7
1.3.4 中间代码生成 ..................... 8
1.3.5 代码优化阶段 ..................... 8
1.3.6 目标代码生成 ..................... 8
1.4 解释程序及软件工具 ................... 9
1.4.1 解释程序的功能与实例 ..... 9
1.4.2 软件工具 ........................... 10
1.5 编译技术的发展历程及典型编译器 .......................................... 10
1.5.1 编译技术的发展历程 ....... 10
1.5.2 典型编译器 ....................... 12
1.6 拓展阅读 ...................................... 14
1.7 习题 .............................................. 15
第 2 章 高级语言设计基础 ...................... 17
2.1 语言 .............................................. 17
2.1.1 文法的直观描述 ............... 17
2.1.2 字母表、符号串的定义 ................................... 19
2.1.3 语言的形式化定义 ........... 21
2.2 文法 .............................................. 22
2.2.1 文法的形式化定义 .......... 22
2.2.2 语法树 .............................. 26
2.2.3 文法二义性 ...................... 27
2.3 文法和语言的分类 ..................... 30
2.3.1 0 型文法 ........................... 30
2.3.2 上下文有关文法 .............. 31
2.3.3 上下文无关文法 .............. 33
2.3.4 正则文法 .......................... 34
2.3.5 四类文法的比较 .............. 35
2.4 高级语言设计 ............................. 36
2.4.1 程序语言的定义 .............. 36
2.4.2 高级语言的起源 .............. 37
2.4.3 数据类型 .......................... 38
2.4.4 语句和控制结构 .............. 38
2.4.5 语言设计的步骤 .............. 39
2.5 语言设计实例 ............................. 41
2.5.1 Simple 语言字符集的定义 .................................. 41
2.5.2 Simple 语言词法单元的定义 .................................. 42
2.5.3 Simple 语言数据类型的定义 .................................. 43
2.5.4 Simple 语言表达式的定义 .................................. 43
2.5.5 Simple 语言语句的定义 .. 44
2.5.6 Simple 语言程序体和程序的定义 ...................... 45
2.5.7 Simple 语言程序 .............. 46
2.6 仓颉语言介绍 ............................. 47
2.6.1 仓颉语言概述 .................. 47
2.6.2 仓颉语言的特点 .............. 49
2.6.3 仓颉语言示例代码及编译方法 ........................... 49
2.7 拓展阅读 ...................................... 50
2.8 习题 .............................................. 51
第 3 章 词法分析 ....................................... 52
3.1 词法分析基本思想 ..................... 52
3.1.1 词法分析任务 ................... 52
3.1.2 词法分析方式 ................... 53
3.2 词法单元的识别 ......................... 53
3.2.1 词法单元分类 ................... 53
3.2.2 词法单元的内部表示 ....... 54
3.2.3 词法单元的形式化描述 ... 55
3.3 有限自动机 .................................. 55
3.3.1 DFA ................................... 55
3.3.2 NFA ................................... 57
3.3.3 NFA 到 DFA 转换――子集构造法 ....................... 59
3.3.4 DFA 的化简 ...................... 62
3.4 正则式与有限自动机 ................. 66
3.4.1 正则式 ............................... 66
3.4.2 正则式与有限自动机的等价性 ............................... 67
3.4.3 正则文法与有限自动机的等价性 ............................... 72
3.5 词法分析器的设计及实现 ......... 73
3.5.1 词法分析器的输入 ........... 73
3.5.2 扫描缓冲区及其预处理 ... 74
3.5.3 由词法规则画出状态转换图 ............................... 75
3.5.4 词法单元对应状态转换图的实现 ................... 76
3.6 词法分析中的错误处理 ............. 77
3.7 拓展阅读 ...................................... 78
3.7.1 斯蒂芬?科尔?克莱尼：正则式 ............................... 78
3.7.2 迈克尔?拉宾和达纳?斯科特：有限自动机与其判定性问题 ................... 79
3.7.3 有限自动机在 KMP 算法中的应用 .................. 79
3.7.4 正则式的应用场景 .......... 81
3.8 习题 .............................................. 82
第 4 章 自上而下的语法分析.................. 85
4.1 语法分析基础 ............................. 85
4.1.1 语法分析的输入 .............. 85
4.1.2 语法分析的错误处理 ...... 85
4.1.3 语法分析方法的分类 ...... 88
4.2 自上而下语法分析中存在的问题 .............................................. 88
4.2.1 包含回溯的自上而下语法分析 .................................. 88
4.2.2 回溯产生的原因与解决方法 .................................. 91
4.3 自上而下语法分析方法 ............ 95
4.3.1 first 集合定义及构造方法 .................................. 95
4.3.2 follow 集合定义及构造方法 .................................. 96
4.3.3 递归下降分析法 .............. 97
4.3.4 递归下降分析的程序方法 .................................. 99
4.3.5 LL(1)分析法 ................... 103
4.4 Simple 语言自上而下语法分析器的设计 ........................... 108
4.5 自上而下语法分析中的错误处理 ............................................. 110
4.6 拓展阅读 .................................... 112
4.7 习题 ............................................. 112
第 5 章 自下而上的语法分析................. 114
5.1 自下而上分析 ............................ 114
5.1.1 移进-归约分析 ............... 114
5.1.2 归约与句柄 ..................... 116
5.2 LR 分析器 .................................. 119
5.2.1 LR 分析器的逻辑结构和工作过程 ......................... 119
5.2.2 LR 分析算法 ................... 122
5.2.3 LR 文法 ........................... 123
5.3 LR(0)分析表的构造 ................. 124
5.3.1 规范句型的活前缀 ......... 125
5.3.2 活前缀的含义 ................. 125
5.3.3 LR(0)项目 ....................... 126
5.3.4 闭包运算和 goto 函数 .... 128
5.3.5 LR(0)项目集规范族 ....... 129
5.3.6 LR(0)文法 ....................... 130
5.3.7 构造 LR(0)分析表 .......... 130
5.3.8 LR(0)分析的缺陷 ........... 133
5.4 SLR(1)分析法 ............................ 134
5.4.1 SLR(1)分析及 SLR(1) 分析表的构造 ................. 135
5.4.2 SLR(1)分析法的问题 ..... 137
5.5 LR(1)分析法 .............................. 139
5.5.1 LR(1)项目 ....................... 139
5.5.2 构造 LR(1)分析表 .......... 141
5.6 LALR(1)分析法 ........................ 142
5.6.1 同心项目集 ..................... 143
5.6.2 构造 LALR(1)分析表 ..... 144
5.6.3 几种 LR 分析法的对比 ................................. 146
5.7 LR 分析与二义性文法 ............. 147
5.7.1 非 LR 上下文无关结构 ................................. 147
5.7.2 二义性文法如何利用 LR 分析法 ............................. 148
5.8 拓展阅读 .................................... 151
5.9 习题 ............................................ 151
第 6 章 语法制导的翻译 ........................ 154
6.1 文法符号的属性 ....................... 154
6.1.1 语义规则和产生式的关系 ................................. 154
6.1.2 属性文法 ......................... 155
6.1.3 语义规则 ......................... 156
6.1.4 综合属性 ......................... 157
6.1.5 继承属性 ......................... 157
6.1.6 语义规则的计算顺序 .... 158
6.1.7 属性与分析过程的关系 ................................ 161
6.2 S 属性定义的自下而上计算 ... 163
6.2.1 抽象语法树 ........