编译原理

第1章 绪论 计算机的诞生是科学发展史上的一个里程碑。经过半个多世纪的发展，计算机已经改变了人类生活、工作的各个方面，成为人类不可缺少的工具。计算机之所以能够如此广泛地被应用，应当归功于高级程序设计语言。计算机语言之所以能由*初单一的机器语言发展到现今数千种高级语言，就是因为有了编译程序。没有高级语言，计算机的推广应用是难以实现的；而没有编译程序，高级语言就无法使用。编译理论与技术也是计算机科学中发展得*迅速、*成熟的一个分支，它集中体现了计算机发展的成果与精华。 1.1 程序设计语言和编译程序 为了处理和解决实际问题，每一种计算机都具有其特定的功能，而这些功能是通过计算机执行一系列相应的操作来实现的。计算机所能执行的每一种操作称为一条指令，计算机能够执行的全部指令集合就是该计算机的指令系统。由于计算机硬件的器件特性，决定了计算机本身只能直接接受由O和1编码的二进制指令和数据，这种二进制形式的指令集和称为该计算机的机器语言，它是计算机唯一能够直接识别并接受的语言。 用机器语言编写程序很不方便且容易出错，编写出来的程序也难以调试、阅读和交流。为此，出现了用助记符代替机器语言二进制编码的男一种语言，这就是汇编语言。汇编语言是建立在机器语言之上的，因为它是机器语言的符号化形式，所以较机器语言直观；但是计算机并不能直接识别这种符号化语言，用汇编语言编写的程序必须翻译成机器语言之后才能执行，这种“翻译”是通过专门的软件——汇编程序实现的。 尽管汇编语言与机器语言相比在阅读和理解上有了长足的进步，但其依赖具体机器的特性是无法改变的，这给程序设计增加了难度。随着计算机应用需求的不断增长，出现了更加接近人类自然语言的功能更强、抽象级别更高的面向各种应用的高级语言。高级语言已经从具体机器中抽象出来，摆脱了依赖具体机器的问题。用高级语言编制的程序几乎能够在不改动的情况下在不同种类的计算机上运行且不易出错，这是汇编语言难以做到的，但高级语言程序翻译（编译）成*终能够直接执行的机器语言程序的难度却大大增加了。 由于汇编语言和机器语言一样都是面向机器的，故相对于面向用户的高级语言来说，它们都称之为低级语言，而FORTRAN、PASCAL、C、ADA、Java这类面向应用的语言则称之为高级语言。因此，编译程序就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序，见图1-1。 图1-1 编译程序的功能 一个高级语言程序的执行通常分为两个阶段，即编译阶段和运行阶段，如图1-2所示。编译阶段将源程序变换成目标程序；运行阶段则由所生成的目标程序连同运行系统（数据空间分配子程序、标准函数程序等）接受程序的初始数据作为输入，运行后输出计算结果。 图1-2 源程序的编译和运行阶段 如果编译生成的目标程序是汇编语言形式的，那么在编译与运行阶段之间还要添加一个汇编阶段，它将编译生成的汇编语言目标程序再经过汇编程序变换成机器语言目标程序，如图1-3所示。 图1-3 源程序的编译、汇编和运行阶段 用高级语言编写的程序也可通过解释程序来执行。解释程序也是一种翻译程序，它将源程序作为输入，一条语句一条语句地读入并解释执行，如图1-4所示。 1.2 编译程序的历史及发展 解释程序与编译程序的主要区别是：编译程序将源程序翻译成目标程序后再执行该目标程序；而解释程序则逐条读出源程序中的语句并解释执行，即在解释程序的执行过程中并不产生目标程序。典型的解释型高级语言是BASIC语言。 图1-4 解释程序解释执行过程示意 1.2 编译程序的历史及发展 20世纪40年代，由于冯 诺伊曼在存储一程序计算机方面的开创性工作，计算机可以执行编写的一串代码或程序，这些程序*初都是用机器语言(MachineLanguage)编写的。机器语言就是计算机能够执行的全部指令集合的二进制形式，例如：表示在IBM PC上使用的Intel 8x86处理器将数字2移至地址0000（1 6进制）的指令。用机器语言编写程序很不方便且容易出错，因此这种代码形式很快就被汇编语言(Assembly Language)取代。在汇编语言中，指令和存储地址都以符号形式给出。例如，汇编语言指令就与前面的机器指令等价（假设符号存储地址X是0000）。汇编程序(Assembler)特汇编语言的符号代码和存储地址翻译成与机器语言相对应的二进制代码。汇编语言大大提高了编程的速度和准确性，至今人们仍在使用它，在存储容量小和要求速度快时尤其如此。但是，汇编语言依赖于具体机器的特性是无法改变的，这给编程和调试增加了难度。很明显，编程技术发展的下一个重要步骤就是用更简洁的数学定义或白然语言来描述和编写程序，它应与任何机器无关，而且也可通过一个翻译程序将其翻译为可在计算机上直接执行的二进制代码。例如，前面的汇编语言代码MOV X，2可以写成一个简洁的与机器无关的形式X=2。 1954-1957年，IBM John Backus带领的一个研究小组对FORTRAN语言及其编译器进行了开发。但是，由于对编译程序的理论及技术的研究刚刚开始，这个语言的开发付出了巨大的辛劳。与此同时，波兰语言学家Noam Chomsky开始了他的自然语言结构研究。Noam Chomsky根据文法（Grammar，产生语言的规则）的难易程度及识别它们所需的算法对语言进行了分类，定义了O型、1型、2型和3型这四类文法及其相应的形式语言，并分别与相应的识别系统相联系。2型文法（上下文无关文法，Context-Free Grammar）被证明是程序设计语言中*有用的文法，它代表着目前程序设计语言结构的标准。Noam Chomsky的研究结果*终使得编译器结构异常简单，甚至还具有白动化功能。有限白动机(Finite Automata)和正规表达式(Regular Expression)与上下文无关文法紧密相关，它们与Noam Chomsky的3型文法相对应，并引出了表示程序设计语言的单词符号形式。接着又产生了生成有效目标代码的方法——这就是*初的编译器，它们被沿用至今。随着对语法分析研究的深入，重点转到编译程序的自动生成研究。开发的这种程序*初被称为编译程序的编译器，但因为它们仅仅能够白动完成编译器的部分工作，所以更确切地应称之为分析程序生成器(Parser Generator)。这些程序中*著名的是Steve Johnson于1975年为UNIX系统编写的语法分析器自动生成工具YACC(Yet Another Compiler-Compiler)。类似地，有限自动机的研究也产生出另一种词法分析器白动生成工具(Scanner Generator) Lex。 20世纪70年代后期和80年代初，大量的研究都关注于编译器其他部分的白动生成，其中包括代码生成。这些努力并未取得多少成功，是由于这部分工作过于复杂，研究者对其本质不甚了解，在此不再赘述。 现今编译器的发展包括了更为复杂的算法应用程序，它用于简化或推断程序中的信息，这又与具有此类功能的更为复杂的程序设计语言发展结合在一起。其中典型的有用于函数语言编译Hindley-Milner类型检查的统一算法。目前，编译器已经越来越成为基于窗口的交互开发环境(Interactive Development Environ ment，IDE)的一部分，这个开发环境包括了编辑器、链接程序、调试程序以及项目管理程序。尽管近年来对IDE进行了大量的研究，但是基本的编译器设计在近20年中都没有多大的改变。 现代编译技术已转向并行编译的研究，由于本书重点是介绍经典的编译理论和技术，因此，对并行编译的发展仅做综述介绍。 1.3 编译过程和编译程序结构 编译程序的工作过程是指从输入源程序开始到输出目标程序为止的整个过程。此过程是非常复杂的。一般来说，整个编译过程可以划分成五个阶殷：词法分析阶段、语法分析阶段、语义分析和中间代码生成阶段、优化阶段和目标代码生成阶段。 1．词法分析 词法分析的任务是输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词符号，如基本字（if、for、begin等）、标识符、常数、运算符和界符（如“(”、“)”、“一”、“；”）等，将所识别出的单词用统一长度的标准形式（也称内部码）来表示，以便于后继语法工作的进行。因此，词法分析工作是将源程序中的字符串变换成单词符号流的过程，词法分析所遵循的是语言的构词规则。 2.语法分析 语法分析的任务是在词法分析的基础上，根据语言的语法规则（文法规则）把单词符号流分解成各类语法单位（语法范畴），如“短语”、“子句”、“句子（语句）”、“程序段”和“程序”。通过语法分析可以确定整个输入串是否构成一个语法上正确的“程序”。语法分析所遵循的是语言的语法规则，语法规则通常用上下文无关文法描述。 3．语义分析和中间代码生成 这一阶段的任务是对各类不同语法范畴按语言的语义进行初步翻译，包含两个方面的工作：一是对每种语法范畴进行静态语义检查，如变量是否定义、类型是否正确等；二是在语义检查正确的情况下进行中间代码的翻译。注意，中间代码是介于高级语言的语句和低级语言的指令之间的一种独立于具体硬件的记号系统，它既有一定程度的抽象，又与低级语言的指令十分接近，因此转换为目标代码比较容易。把语法范畴翻译成中间代码所遵循的是语言的语义规则，常见酌中间代码有四元式、三元式、间接三元式和逆波兰记号等。 4．优化 优化的任务是对前阶段产生的中间代码进行等价变换或改造，以期获得更为高效（节省时间和空间）的目标代码。常用的优化措施有删除冗余运算、删除无用赋值、合并已知量、循环优化等。例如，其值并不随循环而发生变化的运算可提到进入循环前计算一次，而不必在循环中每次循环都进行计算。优化所遵循的原则是程序的等价变换规则。 5．目标代码生成 这一阶段的任务是把中间代码（或经优化处理之后）变换成特定机器上的机器语言程序或汇编语言程序，实现*终的翻译工作。*后阶段的工作因为目标语言的关系而十分依赖硬件系统，即如何充分利用机器现有的寄存器，合理地选择指令，生成尽可能短且有效的目标代码，这些都与目标机器的硬件结构有关。 上述编译过程的五个阶段是编译程序工作时的动态特征，编译程序的结构可以按照这五个阶段的任务分模块进行设计。编译程序的结构示意如图1-5所示。 编译过程中源程序的各种信息被保留在不同的表格里，编译各阶段的工作都涉及构造、查找或更新有关的表格，编译过程的绝大部分时间都用在造表、查表和更新表格的事务上，因此，编译程序中还应包括一个表格管理程序。 出错处理与编诨的各个阶段都有联系，与前三个阶段的联系尤为密切。出错处理程序应在发现错误后，将错误的有关信息如错误类型、出错地点等向用户报源程序告。此外，为了尽可能多地发现错误，应在发现错误后还能继续编译下去，以便发现更多的错误。 一个编译过程可分为一遍、两遍或多遍完成，每一遍完成所规定的任务。例如，**遍只完成词法分析的任务，第二遍完成语法分析和语义加工工作并生成中间代码，第三遍再实现代码优化和目标代码生成。当然，也可一遍即完成整个编译工作。至于一个编译程序究竟应分为几遍，如何划分，这和源程序语言的结构与目标机器的特征有关。分多遍完成编译过程可以使整个编译程序的逻辑结构更清晰一点，但遍数多势必增加读写中间文件的次数，从而消耗过多的时间。 1.4 编译程序的开发 由于计算机语言功能的完善、硬件结构的发展、环境界面的友好等都对编译程序提出了更多、更高的要求，因而构造一个编译系统并非易事。虽然编译理论和编译技术的不断发展已使编译程序的生产周期不断缩短，但是