前言

编译器是将一种高级语言翻译成可以直接在机器上运行的低级语言的程

序，是芯片和操作系统生态中必不可少的基础软件之一。一个操作系统，需要有

可运行的编译器，程序员才能在上面开发各种应用软件，才能构建起应用生态。

编译原理与技术是讨论编译器设计与实现的课程，是一门理论性和实践

性都很强的学科，一直以来是计算机相关专业最难掌握的课程之一。编译器前

端的主要难点在于使用的形式语言与自动机相关理论，特别是有限自动机与

下推自动机的理论及其应用；从中间代码生成到编译器后端的主要难点在于，

它不是直接编码实现数据和硬件的操控，而是要编写程序生成代码，用生成的

代码操控数据和硬件，从而实现程序编写者的意图。

本书面向计算机专业学生和编译器开发者，从底层阐述编译器的基本原

理。在高级语言层面，引入目前流行的大部分语言特性，覆盖多种语言不同语

句的编译方法。在目标语言方面，以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 日