本书主要介绍程序设计语言的编译程序的设计技术，主要由编译程序的基本结构、形式语言和自动机理论的基础知识、编译过程各阶段的工作原理和实现方法三部分构成。
无
编译原理是计算机专业开设的一门重要的专业课程，旨在介绍程序设计语言的编译程序的构造过程、原理和方法。从教学角度来说，编译原理与程序设计基础、离散数学和数据结构等课程联系紧密，它作为后几门课程的综合应用，能够对相关课程内容的深入理解和巩固发挥良好的作用。从技术角度来说，程序设计语言的编译过程涉及的理论与技术有利于更好地形成计算机软件到硬件乃至软硬件协同的概念，也适用于各种系统软件、应用软件的设计和实现。从思维角度来说，编译原理涉及的形式语言理论和自动机理论建立了一种对问题进行抽象、描述和识别，进而从本质上认识、分析和解决问题的思维方法，对工科学生和技术人员抽象思维能力的培养有积极的意义。本书适合作为高等院校计算机专业本科生教材，亦可供准备参加硕士研究生入学考试的考生及从事计算机应用和软件开发工作的工程技术人员参考。
编译原理相关理论的专业性强，内容抽象、难理解，因此本书在编写过程中始终坚持以通俗易懂的语言表达实现对学生抽象思维能力的培养。本书在阐释编译各阶段涉及的原理、方法和技术的过程中，对算法的思想、设计过程和具体内容均给出了详细的说明，引导读者设身处地，一步一步地体会其分析和实现过程，整个过程强调问题的抽象描述和分析思路。在厘清、弄透算法知识的同时，提升读者分析问题、解决问题的能力。
全书共10章。第1章简单介绍编译的基本概念、过程和编译程序的生成，并对形式语言和文法的相关知识进行说明。从第2章开始，按编译的过程逐一介绍编译各阶段的任务、原理和基本实现技术，包括词法分析、语法分析、语义分析、中间代码生成、运行时存储空间的组织、代码优化、目标代码生成等内容。
为帮助读者巩固知识点，把握重点和难点，掌握解题方法，本书在每章最后都给出了精选的习题。书中的例题和习题均以C语言为背景，算法也以C语言的格式给出，从而做到了与程序设计基础、数据结构等先修课程的较好融合。
后续将出版与本书配套的学习辅导和实验用书，为本书的每一章配套内容矩阵、例题分析和练习测试。实验包括独立的局部算法实验和综合实验。
本书第1～5章由史涯晴独自编写，第6～10章由贺汛、史涯晴共同编写。由于编者水平有限，书中难免存在不当和疏漏之处，敬请广大读者批评指正。
编 者
2020年5月26日于南京
计算机\编译
本书以程序设计语言的编译程序的设计实现过程为主线，循序渐进地介绍了编译各阶段的原理与方法，强调抽象思维能力的培养，可帮助读者逐步掌握复杂问题的抽象描述和分析思路。
本书特色
语言表达通俗易懂。本书阐释专业性强、内容抽象、难于理解的编译各阶段的原理、方法和技术实现，用通俗易懂的语言引导读者逐步体会、分析算法的设计和实现过程。
培养抽象思维能力。本书可帮助读者掌握对问题进行抽象、描述和识别，进而从本质上认识、分析和解决问题的思维方法，对工科学生和技术人员抽象思维能力的培养有着积极的意义。
读者对象广泛。本书适合作为高等院校计算机专业本科生编译原理课程的教材，也可以作为有一定基础的计算机应用和软件开发工程技术人员的参考书。
前言
教学建议
第1章 引论 1
1.1 编译概述 1
1.2 编译的过程 2
1.2.1 高级语言程序的处理过程 2
1.2.2 编译的过程 3
1.3 编译程序的生成 7
1.3.1 编译程序的组合方式 7
1.3.2 编译程序的生成方式 9
1.4 基本知识 11
1.4.1 形式语言 11
1.4.2 文法 14
1.5 练习 24
第2章 词法分析 26
2.1 词法分析概述 26
2.2 单词的表示 27
2.2.1 单词的种别 27
2.2.2 属性 28
2.3 单词的形式描述 29
2.3.1 正规式描述 30
2.3.2 正规文法描述 32
2.3.3 正规式与正规文法的等价性 33
2.4 有穷自动机 38
2.4.1 不确定的有穷自动机 38
2.4.2 确定的有穷自动机 40
2.4.3 NFA与DFA的等价性 41
2.4.4 DFA的化简 45
2.4.5 正规式和FA的等价性 47
2.4.6 正规文法和FA的等价性 53
2.5 词法分析程序的构造 56
2.5.1 单词识别程序的构造 56
2.5.2 词法分析程序的自动生成工具LEX简介 59
2.6 练习 62
第3章 自顶向下的语法分析法 64
3.1 语法分析概述 64
3.2 自顶向下语法分析的实现 65
3.2.1 推导树与语法树 65
3.2.2 二义性 66
3.2.3 确定与不确定的自顶向下语法分析 67
3.3 确定的自顶向下的语法分析条件 70
3.3.1 LL(1)文法 70
3.3.2 非LL(1)文法到LL(1)文法的等价变换 75
3.4 自顶向下语法分析程序的构造 80
3.4.1 预测分析法 80
3.4.2 递归下降分析法 83
3.5 练习 85
第4章 自底向上的语法分析法 88
4.1 自底向上语法分析的实现 88
4.1.1 归约 88
4.1.2 短语和句柄 90
4.2 简单优先分析法 92
4.2.1 简单优先文法 92
4.2.2 简单优先分析算法 94
4.3 算符优先分析法 96
4.3.1 算符优先文法 96
4.3.2 算符优先分析算法 100
4.3.3 优先函数 103
4.4 练习 105
第5章 LR分析法 108
5.1 LR分析法概述 108
5.2 LR(0)分析 110
5.2.1 LR(0)项目集规范族 110
5.2.2 LR(0)文法 116
5.2.3 LR(0)分析器的工作过程 119
5.3 SLR(1)分析 120
5.3.1 SLR(1)文法 120
5.3.2 SLR(1)分析表的构造 121
5.4 LR(1)分析 123
5.4.1 LR(1)文法 123
5.4.2 LR(1)项目集规范族的构造 125
5.4.3 LR(1)分析表的构造 126
5.5 LALR(1)分析 127
5.5.1 LALR(1)文法 127
5.5.2 LALR(1)分析表的构造 128
5.6 语法分析程序的自动生成工具YACC简介 130
5.6.1 YACC对语言的要求 130
5.6.2 YACC的输入输出 130
5.6.3 YACC源程序 131
5.7 练习 132
第6章 语义分析 135
6.1 语义分析概述 135
6.2 语法制导的语义计算 135
6.2.1 属性文法 136
6.2.2 语义计算 138
6.3 符号表 140
6.3.1 符号表的概述 140
6.3.2 符号表的定义 141
6.3.3 符号表的组织 145
6.3.4 符号表的管理 153
6.4 练习 154
第7章 中间代码生成 156
7.1 中间代码生成概述 156
7.2 中间代码 156
7.2.1 逆波兰式 156
7.2.2 树代码 158
7.2.3 三地址码 159
7.3 自底向上的语法制导翻译 161
7.3.1 说明语句的翻译 161
7.3.2 含简单变量的赋值语句的翻译 164
7.3.3 含数组元素的赋值语句的翻译 167
7.3.4 布尔表达式的翻译 168
7.3.5 控制语句的翻译 174
7.3.6 过程调用 182
7.4 练习 183
第8章 运行时存储空间的组织 185
8.1 运行时存储空间的划分 185
8.2 数据空间的存储分配策略 186
8.2.1 静态存储分配策略 186
8.2.2 动态存储分配策略 186
8.3 栈式存储分配 190
8.3.1 简单程序设计语言的栈式存储分配 190
8.3.2 嵌套过程语言的栈式存储分配 193
8.4 练习 199
第9章 代码优化 201
9.1 代码优化概述 201
9.2 局部优化 201
9.2.1 基本块及其划分 202
9.2.2 基本块的优化技术 205
9.2.3 基本块优化技术的实现 207
9.3 循环优化 212
9.3.1 程序中的循环 212
9.3.2 循环的优化技术及其实现 217
9.4 练习 221
第10章 目标代码生成 224
10.1 目标代码生成概述 224
10.2 模型计算机的指令系统 225
10.2.1 寻址方式 225
10.2.2 指令系统 225
10.3 一种简单的代码生成算法 226
10.3.1 寄存器的使用原则 226
10.3.2 待用信息和活跃信息 227
10.3.3 寄存器描述和变量地址描述 231
10.3.4 基本块的代码生成算法 231
10.4 DAG的目标代码生成 234
10.5 练习 235
参考文献 237
