编译原理

第1章 引论 1.1 编译器 一种高级程序设计语言(简称高级语言)定义一个编程抽象，这个抽象可以使编程更容易，使编写的程序可读性更高、可移植性更好。然而，系统执行高级语言编写的程序时需要将程序转换成目标机能够识别的指令，并将这些指令按照一定的格式存储在存储器中。 图1-1所示的是一个C语言的示例程序test.c，经过gcc-5.4.0编译产生x86-64目标程序，该目标程序是一个二进制的文件。 图1-1 C语言的示例程序test.c 图1-2 目标代码示例 从上面的示例程序可以看出，编译器就是一个翻译程序，将一种语言编写的源程序翻译为另一种语言编写的目标程序。显然，识别并报告源程序中的错误也是编译器的一个重要任务。在大多数程序员的眼中，编译器可以看作图1-3所示的一个“黑箱”。 图1-3 编译器 编译器将源程序转换成目标程序，系统再将目标程序加载到内存中并运行，*终可以实现程序的输入处理和输出。解释器是另一种程序设计语言处理器，和编译器一样，解释器需要检查程序的正确性并分析程序的语法和语义。然而，与编译器不同，解释器不生成目标程序，而是直接根据源程序和用户输入执行程序。一般来说，编译器产生的目标程序执行比解释器快，但是解释器的错误诊断效果比编译器好。 将源程序转换成可执行目标程序时，编译器往往还需要和一些相关程序紧密结合，这些程序包括预处理器、汇编器、链接器等。预处理器、编译器、汇编器和链接器一起构成编译系统。预处理器是在翻译之前由编译器调用的独立程序，主要处理宏定义和文件包含等信息。汇编语言不仅容易转换成目标机指令，也容易调试，所以为编译器提供了通用的输出语言。然而，汇编语言程序还需要经过汇编器转换成目标代码。如果程序被分成多个部分进行编译，那么汇编器得到的多个汇编语言程序还需要通过链接器进行链接，*后才能得到可执行的目标文件。 1.2 编译器的结构 编译将一种语言编写的源程序映射成另一种语言编写的目标程序，但是将高级语言程序直接有效地转换为目标机代码的映射规则往往难以找到，所以“黑箱”中的映射过程可以分为前端和后端两个部分(图1-4)。 图1-4 编译器的前端和后端 前端把源程序分解为若干个组成元素，并对这些元素附加语法结构，然后根据这个结构构建源程序的中间表示(Intermediate Representation，IR)，同时收集源程序的信息并将其存入符号表。后端根据得到的中间表示和符号表中的信息构建目标程序。简单地说，前端致力于理解源程序，后端致力于把程序映射到目标机上。 事实上，编译器在生成目标代码之前可能使用多种中间表示。这些中间表示的使用可以使编译器的前端语言和后端机器相对独立，降低编译的难度，同时可以更好地支持编译器的移植。此外，引入中间表示可以将编译过程进一步细化为若干个转换阶段，每一个阶段将源程序由一种中间表示转换成另一种中间表示。一个典型的编译过程可以分解为词法分析、语法分析、语义分析、中间代码生成、中间代码优化、目标代码生成、目标代码优化，如图1-5所示。其中，中间代码优化和目标代码优化统称为代码优化，是可选的步骤。另外，中间表示不一定是被编译器明确地构建出来的。 图1-5 编译器的典型编译过程 1.2.1 词法分析 编译器的**个任务就是词法分析。词法分析的任务是从源程序的连续字符序列中识别出有意义的单词。 对于每个单词，词法分析程序将它转换为一种内部表示形式，称为词法单元。词法单元一般包括单词的词法记号和属性。词法记号是用于语法分析的抽象记号，可以理解为一类单词的标签。典型的词法记号包括关键字、整数、实数、标识符、运算符、分隔符等。单词*典型的属性是标识符的名字、整数的数值等。例如，示例程序(图1-1)中的int、main是关键字，3和2是整数，a和b是标识符，“=”和“;”分别是运算符和分隔符。 因此，每个词法单元可以表示为一个二元组。其中，tokenID表示词法记号，token_value表示单词属性。如果标识符、“=”和“+”的词法记号分别是id、becomes和addtoken，那么示例程序(图1-1)中语句sum=a+b经过词法分析可以输出如下词法单元序列： 词法分析中，对程序执行结果没有影响的元素将被忽略，如空格、回车符、换行符、制表符、注释等。此外，如果一个词法记号仅仅定义一个单词，那么没有必要同时使用tokenID和token_value。例如，假设addtoken仅仅是“+”的抽象，那么输出可以表示为。 1.2.2 语法分析 语法分析程序判定从词法分析输出的词法单元序列是否符合语言的语法结构，并构造其中间表示形式。一种常用的中间表示是树型结构，称为语法树。 示例程序(图1-1)中语句sum=a+b可以表示为图1-6所示的树型结构。其中，每个结点都表示一个语法元素。 语法树以一种层次定义关系忠实地反映语法元素之间的语法结构，但是语法树的具体形式依赖于语法元素之间的定义。例如，图1-6所示的语法树中，赋值语句通过表达式定义，表达式可以通过表达式递归定义，也可以通过标识符直接定义。这种语法关系将采用上下文无关文法进行描述，并进一步构造出有效的语法分析程序。 图1-6 语法树示例 1.2.3 语义分析 语法分析在词性和语法规则上确定句子的合法性，局限于拼写和语法范畴，但是语法分析忽略单词的含义。例如，sum=a+b和y=b+c在语法结构上是完全一样的。因此，在前端将源程序翻译成中间表示之后，编译器必须进行语义分析。 语义分析主要根据语言的语义约束检查程序的一致性，收集相关信息并将其存储到符号表或者语法树中。例如，程序(图1-1)将sum、a和b声明为整型变量，语义分析程序首先在处理声明时将这些信息填入符号表或者存储到语法树的相应结点中。 语义分析的一个主要任务是类型检查。例如，针对赋值语句sum=a+b(图1-1)，首先需要根据a和b的类型信息判断它们是否相容，并进一步确定a+b结果的类型；接着确定sum和a+b结果的类型是否相容。 语义分析和符号表密切相关，但是符号表不只和语义分析相关，它几乎与编译器的所有阶段都进行交互。词法分析阶段和语法分析阶段识别符号的名称与抽象的词法记号；语义分析阶段将增加数据类型和其他信息；代码生成阶段和代码优化阶段也将利用由符号表提供的信息选出恰当的代码。 1.2.4 中间代码生成 中间代码是在源语言和目标语言之间引入的一种中间表示形式，可以看作某种虚拟机的抽象。通过中间代码，编译器可以避开直接从源语言到目标语言翻译时较大的语义跨度。中间代码的引入使编译程序的逻辑结构更加简单明确，也有利于实现程序优化和编译器的移植。 中间代码一般具有两个重要的性质：容易生成，同时容易转换成目标机上的程序。树型结构和线性中间代码是两种*重要的中间表示形式。语法树和抽象语法树就是树型结构中间代码；三地址代码是一种线性中间代码，这种代码类似于汇编指令，每条代码有三个分量。例如，图1-1中的赋值语句sum=a+b可以表示为如下的三地址代码： 其中，T1是存储加法运算结果的临时变量。此外，从上面的三地址代码可以看出，每条指令只能有一个运算，所以指令顺序和运算顺序一致。更多形式的中间代码和处理技术将在第6章介绍。 1.2.5 代码优化 代码优化的目的是提高程序执行的时空效率，可以分为与机器有关的优化和与机器无关的优化。与机器无关的优化主要针对中间代码进行，也称为中间代码优化；与机器有关的优化主要针对目标代码进行，也称为目标代码优化。 把高级结构和数据存储运算直接翻译成代码，其运行的效率可能比较低。在图1-1中的sum=a+b，如果直接翻译，那么得到的目标程序每次运行不仅需要访问a和b的存储空间，还需要进行加法运算。如果考虑sum=a+b之前a和b的值是个常量，那么赋值号右边的a和b可以分别用2和3替换；此外，2+3可由编译器直接计算并得到结果5。因此，sum=a+b可以被优化为sum=5。 好的优化能够提高代码的质量。然而，引入优化使得源代码和目标代码之间的关系变得模糊，同时使得程序调试变得困难。其次，不管多么复杂的优化，都不能为所有的程序产生*优代码，而且很多编译优化问题都是不可判定的。此外，代码优化是以增加编译器的开销为代价的，所以优化工作量大势必会降低编译器编译源程序的效率。因此，不同的编译器会在编译效率和源程序执行效率之间进行权衡，并采用不同的优化策略和优化技术。 1.2.6 目标代码生成 代码生成器以源程序或者源程序的中间表示形式作为输入，并把它映射为目标机上的代码。代码生成与目标机的特性密切相关，目标机上的指令格式、寻址达式、寄存器分配、数据表示等都是影响代码生成的因素。 代码生成不仅需要确定选择哪些指令，还要确定指令高效执行的顺序，确定哪些值应该放入寄存器中，哪些值放入内存中。因此，指令选择、寄存器分配、指令的调度是代码生成的三个主要问题。这三个问题相互作用，对生成代码的质量有直接的影响。指令选择就是选择一组实现中间操作的目标指令集。因为寄存器是存储层次结构中访问速度*快的资源，所以操作数存储在寄存器中的指令比操作数存储在内存中的指令的执行速度快。然而，寄存器的数量有限，所以一些指令执行之后不得不将其操作数移入内存，为即将执行的指令空出寄存器。从寄存器移进内存或者从内存移进寄存器的指令将增加代码运行的开销，所以要充分考虑指令执行顺序及其操作数之间的关系，可以尽可能提高代码的性能。 和代码生成密切相关的一个问题是如何对源程序中的标识符进行存储分配，编译器将在中间代码或目标代码生成阶段做出存储分配的决定。 1.2.7 编译器的组织 编译器的结构强调编译程序的逻辑过程和步骤。在实现编译器的时候，可以将每个步骤组织为一遍，也可以将几个步骤组织为一遍。每遍读入一个输入文件并产生一个输出，将一种中间表示形式转换成另一种中间表示形式。例如，可以将词法分析、语法分析、语义分析和中间代码生成组织成一遍，代码生成和代码优化组织成一遍。 实际上，编译程序也可以通过一遍完成所有的编译步骤，这样的编译器称为单遍编译器。一个典型的单遍编译器可以按照图1-7所示的方式组织，其中的核心程序是语法语义分析程序，只有核心程序需要单词时才会调用词法分析程序识别一个单词，同样只有核心程序需要生成代码的时候才会调用代码生成程序。单遍编译器不用显式构造中间表示，适合实现翻译需求相对简单的程序设计语言。 图1-7 一个单遍编译器的模型 和单遍编译器相对的就是多遍编译器。在多遍编译器中，编译器围绕一组精心设计的中间表示形式进行组织，每一遍将源程序或一种中间表示形式转换成另一种表示形式。多遍编译器比较灵活，适合进行具有复杂语言功能的程序设计语言的翻译。此外，精心设计的中间表示形式使得编译器可以将不同的前端和不同的后端结合起来，提高编译器的可移植性。 1.3 GCC概述 GCC是一套GNU(GNU’s Not UNIX)开发的编译器环境，不仅支持多种语言，还支持多种硬件平台。 1.3.1 GCC的语言处理过程 高级程序设计语言程序只有转化为目标机上的代码才能执行。GCC将源程序转换成可执行文件的过程可以细分为4个阶段：预处理、编译、汇