下载掌阅APP，畅读海量书库
立即打开
本书除了介绍编译技术相关理论方法之外，也会引导实现一个完整的编译器。在实践过程中，我们需要用到若干使用较为广泛的工具，以提升编译器构建效率。现代编译技术通常使用 正则表达式（Regular Expression） 来描述语言词法中特定词素所对应的模式，使用 上下文无关文法（Context-Free Grammar） 以描述语言的语法。本书选择使用Flex和Bison，分别作为实现词法分析和语法分析的辅助工具。我们所实现的编译器在完成之后，能够将以一门类C语言（即C--语言）书写的源程序完整编译为目标语言MIPS的指令序列，并可以在相关MIPS模拟器上直接运行。本节将简要介绍本书中所涉及的语言和工具，包括源语言C--、目标语言MIPS，以及MIPS模拟器，而Flex和Bison这两项辅助工具将在后续章节中使用到它们时再介绍。
为了便于介绍编译器的构建过程，我们基于C语言设计了C--语言，作为本书的教学源语言。与C语言类似，C--也是过程式语言，支持结构化编程和词法作用域，使用静态类型系统。C--语言规模较小，高级特性需要借助函数或结构体来实现。C--语言中所有的可执行代码都被包含在函数里，其参数传递方式分为值传递和数组传递。C--也是自由形式语言，源代码缩进不影响程序功能，以分号作为语句结尾，以大括号表示代码块。具体而言，C--语言具有以下特征：
●基本的数据类型包括所有的32位无符号整数和浮点数，整数支持十进制、八进制和十六进制表示，浮点数符合IEEE 754单精度标准，并且支持科学记数法。
●复合数据类型包括数组和结构体，用于实现复杂的数据结构，结构体和数组元素的类型都可以是基本类型和复合类型的组合。
●程序的基本控制流包括语句块、 if 条件判断语句和 while 循环语句等，语句支持全局和局部变量定义、函数声明和定义，以及函数返回值。
●表达式包括一元运算符、二元运算符、函数调用、数组元素和结构体成员访问等，运算符的优先级和结合性与C语言相同。
●与C语言类似，C--语言也支持单行和多行注释。
●C--语言具有更少的关键字，语法简单，便于理解与使用。
●C--语言的程序分析与编译，相比于C语言更加简单，适用于教学。
●C--语法简单，易于阅读和理解，C--语言只支持int和float两种基本类型，不依赖于库函数，但是提供了 read 和 write 等少量内置的输入/输出（I/O）函数。
C--和ANSI C在数据类型和语法上存在一些差异。比如，C--支持的基本类型和复合类型较少，而ANSI C支持多种基本类型，如char、void和double等，还支持枚举和联合复合类型。除此之外，C--不支持指针，结构体域和数组元素的访问必须通过“.”和下标索引。对于基本类型数据的按位操作和复杂程序流程（如switch、goto和label定义），C--也不支持。对于关键字，C--支持7个，而ANSI C支持32个。不过，这些差异不影响C--语言的使用，并在很大程度上简化了语言的设计，也降低了实现的难度。
计算机主要组件包括CPU、I/O、存储器和控制器，计算机借助这些组件就可以执行程序，输出结果，完成特定的功能。其中，CPU能够识别由0和1组成的指令集合，指令的具体语义和格式由具体的指令集定义，MIPS32就是一种常见的指令集架构。 MIPS（Microprocessor without Interlocked Pipeline Stage） ，是一种采取 精简指令集（Reduced Instruction Set Computer，RISC） 的 指令集架构（Instruction Set Architecture，ISA） ，由美国MIPS计算机系统公司（现已改名为美普斯科技）开发。MIPS最初是为通用计算而设计的，在20世纪八九十年代常用于个人计算机、工作站和服务器。MIPS架构极大地影响了后来的精简指令集架构设计，比如Alpha等。如今，MIPS架构已经被广泛用于许多电子产品、网络设备、个人娱乐设备和商业设备。在一些大学和技术院校的计算机架构课程中，通常也会教授MIPS架构。最早的MIPS架构是32位，最新的版本是64位，接下来我们简单介绍32位MIPS架构中的数据类型、寄存器、指令、寻址方式和调用约定，更详细的MIPS介绍我们放在后续章节中。
数据是指令操作的主要对象，MIPS32定义了多种指令，每种指令要求的操作数的类型和长度各有不同。MIPS32定义的基本数据类型如下：
● 位（Bit） ：长度为1位，是最小的数据单元。
● 字节（Byte） ：长度为8位。
● 半字（Half Word） ：长度为16位。
● 字（Word） ：长度为32位。
● 双字（Double Word） ：长度为64位。
除此之外，MIPS32还定义了32位单精度浮点数和64位双精度浮点数等。基于定义的数据类型，指令可以操作数据，实现程序功能。MIPS32架构下数据读写依赖于寄存器，数据通常存放在寄存器内。接下来我们介绍MIPS32架构定义的寄存器。
MIPS架构的第一个版本是由MIPS计算机系统公司为其R2000微处理器设计的，这也是MIPS的第一个实现。MIPS采用“加载-存储”架构，即“寄存器-寄存器”架构。除了用于访问计算机存储器的加载/存储指令外，所有其他指令都对寄存器进行操作。MIPS有32个32位 通用寄存器（GPR） ，分别用$0，$1，…，$31表示。其中寄存器$0被硬编码为零，写入的任何内容都将被丢弃。寄存器$2和$3用于存储函数返回值，可以在函数内部使用。除此之外，还有一些寄存器用于存放函数参数，比如寄存器$4至$7。寄存器$31专门用来保存函数的返回地址。因此，我们实际能在目标代码中自由使用的寄存器的数目是很少的，只有寄存器$8至$15（别名为$t0至$t7）、$16至$23（别名为$s0至$s7）、$24至$25（别名为$t8至$t9）以及$30（别名为$sp或者$s8）这19个寄存器。MIPS32架构中定义了3个特殊寄存器，分别为 PC（程序计数器） 、 HI（乘除结果高位寄存器） 和 LO（乘除结果低位寄存器） 。MIPS32的指令长度为32位，因此MIPS的程序计数器PC也是32位的，其中低二位为零。HI和LO主要用于乘法和除法运算，保存运算结果。对于乘法运算，HI保存结果的高32位，LO保存结果的低32位；对于除法运算，HI保存余数，LO保存商。这些寄存器相互协作，支持MIPS32指令对数据的操作。
MIPS支持的CPU指令繁多，比如加法和减法指令、乘法和除法指令，以及分支延迟槽指令等。MIPS架构在演进过程中支持的指令数目不断增多，功能日益强大。整体而言，MIPS32指令可以分为三种类型： R型（Register） 、 I型（Immediate） 和 J型（Jump） 。这三种类型的指令的高6位定义 操作码（opcode） ，而低26位的结构和语义差异较大，如图1.4所示。
（1）R型指令用连续三个5位二进制码来表示三个寄存器的地址，然后用一个5位二进制码来表示移位的位数（对于非移位操作，这5位全置为0），最后6位的功能码和操作码共同决定R型指令的具体操作方式。
（2）I型指令用连续两个5位二进制码来表示两个寄存器地址，用一个16位二进制码来表示一个立即数的二进制码。
（3）J型指令用26位二进制码来表示跳转的目标指令的地址。
图1.4 MIPS32不同类型指令的格式
除了指令之外，MIPS32架构还支持四种寻址方式，包括寄存器寻址、立即数寻址、寄存器相对寻址和PC相对寻址，我们以寄存器相对寻址和PC相对寻址为例进行介绍。寄存器相对寻址主要用于加载和存储指令，通过对一个16位的立即数做符号扩展，然后与指定通用寄存器的值相加，从而得到有效地址；PC相对寻址主要用于转移指令，转移指令中也有一个16位的立即数，将其左移两位并做符号扩展之后与程序计数器PC的值相加，从而得到有效地址。
除了上述内容，MIPS32还定义了32位平台上的调用约定。MIPS最常用的 ABI（Application Binary Interface） 是O32 ABI，其严格基于堆栈，只有$4～$7四个寄存器用于传递参数，被调用者可以用堆栈上保留的空间保存其参数，返回值默认存储在寄存器$2中，第二个返回值可以存储在寄存器$3中。O32 ABI形成于1990年，最后一次更新在1994年，更新缓慢。它作为只支持16个寄存器的老式浮点模型，正在被不断涌现的功能更加强大的调用约定取代，比如GCC创建了一个名为O64的64位变体，其他的一些调用约定上的改进主要是增加了寄存器的个数以及支持64位指令。关于调用约定，后续章节的实践部分还会提及。
作为业界最为经典的精简指令集架构之一，MIPS在教学、生活和工业界都曾得到广泛关注并诞生了很多模拟器。SPIM Simulator是一个运行MIPS32程序的独立模拟器，其几乎实现了整个MIPS32汇编程序扩展指令集，但是省略了大多数浮点比较和舍入模式以及内存系统页表等功能。SPIM Simulator的正常模拟需要读入符合MIPS32汇编代码格式的文本文件（该文件通常以.s或者.asm作为后缀名），并提供了一个简单的调试器和最小的操作系统服务集。MIPS32汇编代码通常由若干个以.text开头的代码段以及若干个以.data开头的数据段组成。在本书介绍的整个编译器构建过程中，我们的目标是在MIPS模拟器上正常运行编译生成的代码。
考虑到运行时性能，MIPS32指令的操作数大部分都来自高访问性能的寄存器，因此编译后的汇编代码需要妥善分配MIPS32数量稀少的寄存器。MIPS32标准给出了一些寄存器使用的约定，除了硬件接地导致永远值为0的$0寄存器，还有一些为汇编器预留的寄存器（如$1）。如果在汇编代码中强制使用这些预留的寄存器，SPIM Simulator会报错。除了指令翻译之外，C--代码编译为MIPS32汇编代码时，还需要合理分配寄存器。现有的寄存器分配算法包括朴素寄存器分配方法、局部寄存器分配算法、图染色算法和活跃变量分析等（我们在后续章节中会介绍），这些算法可以降低MIPS32汇编代码生成的难度，并且可减少汇编代码的规模。当空余寄存器无法满足指令使用时，我们需要将寄存器中暂时用不到的数据保存到栈中，需要时再将其加载回寄存器。
C--语法简单，因而其对应汇编代码的生成相比于C语言难度较低。SPIM Simulator还提供了调试器用于查看代码段和数据段，以便定位缺陷。通过将C--源代码一步步翻译为MIPS32指令序列并在SPIM上执行，有助于学生理解编译器的工作原理和计算机的运行方式，实现理论与实践的有机结合。
本书讨论的编译器构建过程所涉及的代码，均假设将在如下环境中被编译并运行：
●GNU Linux Release: Ubuntu 20.04，kernel version 5.13.0-44-generic
●GCC version 7.5.0
●GNU Flex version 2.6.4
●GNU Bison version 3.5.1
●QtSpim version 9.1.9
建议读者在阅读后续章节之前，先准备好以上编译环境，以便开展后续的实践内容。需要说明的是，在不影响核心功能的前提下，软件版本略有差异不会造成很大的影响。