China-pub.com 下载 第1章概 论 本章要点 ·为什么要用编译器 ·编译器结构中的其他问题 ·与编译器相关的程序 ·自举与移植 ·翻译步 ·TNY样本语言与编译器 ·编译器中的主要数据结构 ·C-Minus:编译器项目的一种语言 编译器是将一种语言翻译为另一种语言的计算机程序。编译器将源程序(source language) 编写的程序作为输入，而产生用目标语言(target language)编写的等价程序。通常地，源程 序为高级语言(high-level language),如C或c++,而目标语言则是目标机器的目标代码 (object code,有时也称作机器代码(machine code),也就是写在计算机机器指令中的用于运 行的代码。这一过程可以用下图表示： 源程序一编译器一目标程序 编译器是一种相当复杂的程序，其代码的长度可从10000行到1000000行不等。编写甚至 读懂这样的一个程序都非易事，大多数的计算机科学家和专业人员也从来没有编写过一个完整 的编译器。但是，几乎所有形式的计算均要用到编译器，而且任何一个与计算机打交道的专业 人员都应掌握编译器的基本结构和操作。除此之外，计算机应用程序中经常遇到的一个任务就 是命令解释程序和界面程序的开发，这比编译器要小，但使用的却是相同的技术。因此，掌握 这一技术具有非常大的实际意义。 也正因为这一点，本书不仅仅要讲解基础知识，还为读者提供了所有必要的工具和设计编 写真正的编译器的实践。要做到这些，就必须学习各项理论知识，而这主要应从自动机原理 (它使编译器结构合理)着手。在讲述时我们假设读者并不了解自动机原理。当然，此处的观 点与标准的自动机原理论著有所不同，这些论著特别强调编译过程：但是，学过自动机原理的 读者就会发现对这些理论材料很熟悉，这部分阅读起来也十分迅速。特别是对于那些十分了解 自动机原理背景的读者来说，对2.2节、2.3节、2.4节和3.2节就不必细读了。无论怎样，读者都 应知道基本的数据结构和离散数学。机器结构和汇编语言的相关知识也很重要，在第8章“代 码生成”中尤为如此 实际编码技术的研究本身就要求认真规划，这是因为即使有很好的理论基础，编码的细节 也可能会复杂得令人不知如何操作。本书包括了有关程序设计语言结构的一系列简单示例，并 利用它们针对该项技术进行详细描述，讨论中使用到的语言被称作TNY。此外，附录A还提供 了一个更泛的示例，它包括了一个小小的但却非常复杂的适用于分类项目的C子集（称作C Mius)。本书还有大量的练习，这其中包括简单的笔头训练、文本中的代码扩充，以及更多的 相关编码练习。 总之，在编译器结构和被编译的程序设计语言的设计之间存在着一个很重要的交互。在本 书中，只是附带着讲解了一下语言设计问题，而是着重于程序设计语言的概念和设计问题（参
下载 第1章 概 论 本章要点 • 为什么要用编译器 • 编译器结构中的其他问题 • 与编译器相关的程序 • 自举与移植 • 翻译步骤 • TINY样本语言与编译器 • 编译器中的主要数据结构 • C-Minus：编译器项目的一种语言 编译器是将一种语言翻译为另一种语言的计算机程序。编译器将源程序（ source language） 编写的程序作为输入，而产生用目标语言（ t a rget language）编写的等价程序。通常地，源程 序为高级语言（ high-level language），如C或C + +，而目标语言则是目标机器的目标代码 （object code，有时也称作机器代码（machine code）），也就是写在计算机机器指令中的用于运 行的代码。这一过程可以用下图表示： 编译器是一种相当复杂的程序，其代码的长度可从 10 000行到1 000 000行不等。编写甚至 读懂这样的一个程序都非易事，大多数的计算机科学家和专业人员也从来没有编写过一个完整 的编译器。但是，几乎所有形式的计算均要用到编译器，而且任何一个与计算机打交道的专业 人员都应掌握编译器的基本结构和操作。除此之外，计算机应用程序中经常遇到的一个任务就 是命令解释程序和界面程序的开发，这比编译器要小，但使用的却是相同的技术。因此，掌握 这一技术具有非常大的实际意义。 也正因为这一点，本书不仅仅要讲解基础知识，还为读者提供了所有必要的工具和设计编 写真正的编译器的实践。要做到这些，就必须学习各项理论知识，而这主要应从自动机原理 （它使编译器结构合理）着手。在讲述时我们假设读者并不了解自动机原理。当然，此处的观 点与标准的自动机原理论著有所不同，这些论著特别强调编译过程；但是，学过自动机原理的 读者就会发现对这些理论材料很熟悉，这部分阅读起来也十分迅速。特别是对于那些十分了解 自动机原理背景的读者来说，对2 . 2节、2 . 3节、2 . 4节和3 . 2节就不必细读了。无论怎样，读者都 应知道基本的数据结构和离散数学。机器结构和汇编语言的相关知识也很重要，在第 8章“代 码生成”中尤为如此。 实际编码技术的研究本身就要求认真规划，这是因为即使有很好的理论基础，编码的细节 也可能会复杂得令人不知如何操作。本书包括了有关程序设计语言结构的一系列简单示例，并 利用它们针对该项技术进行详细描述，讨论中使用到的语言被称作 T I N Y。此外，附录A还提供 了一个更广泛的示例，它包括了一个小小的但却非常复杂的适用于分类项目的 C子集（称作C - M i n u s）。本书还有大量的练习，这其中包括简单的笔头训练、文本中的代码扩充，以及更多的 相关编码练习。 总之，在编译器结构和被编译的程序设计语言的设计之间存在着一个很重要的交互。在本 书中，只是附带着讲解了一下语言设计问题，而是着重于程序设计语言的概念和设计问题（参 源程序 → 编译器 → 目标程序
2 编译原理及实践 China-pub.co 下载 见本章最后的“注意与参考”部分) 首先将简要地介绍编译器的历史及其存在目的与理由，以及与编译器相关的程序描述。接 着讲解编译器的结构、各种翻译过程和相关的数据结构，并联系一个简单的具体示例来示范这 个结构。最后，再概括地讲述一下编译器结构的其他问题，这包括自举和移植，以及本书后面 用到的主要语言的描述。 1.1为什么要用编译器 在本世纪40年代，由于冯·诺伊曼在存储-程序计算机方面的先锋作用，编写一串代码或 程序已成必要，这样计算机就可以执行所需的计算。开始时，这些程序都是用机器语言 (machine language)编写的。机器语言就是表示机器实际操作的数字代码，例如： c70600000002 表示在IBM PC.上使用的8x86处理器将数字2移至地址00o0（16进制)的指令。当然，编写 这样的代码是十分费时和乏味的，这种代码形式很快就被汇编语言(assembly language)代替 了。在汇编语言中，都是以符号形式给出指令和存储地址的。例如，汇编语言指令 MOV X, 就与前面的机器指令等价（假设符号存储地址X是0O00)。汇编程序(assembler)将汇编语言 的符号代码和存储地址翻译成与机器语言相对应的数字代码。 汇编语言大大提高了编程的速度和准确度，人们至今仍在使用着它，在编码需要极快的速 度和极高的简洁程度时尤为如此。但是，汇编语言也有许多缺点：编写起来也不容易，阅读和 理解很难：而且汇编语言的编写严格依赖于特定的机器，所以为一台计算机编写的代码在应用 于另一台计算机时必须完全重写。很明显，发展编程技术的下一个重要步骤就是以一个更类似 于数学定义或自然语言的简洁形式来编写程序的操作，它应与任何机器都无关，而且也可由 个程序翻译为可执行的代码。例如，前面的汇编语言代码可以写成一个简洁的与机器无关的形式 ■2 起初人们担心这是不可能的，或者即使可能，目标代码也会因效率不高而没有多大用处 在1954年至1957年期间，IBM的John Backusi带领的一个研究小组对FORTRAN语言及其编 译器的开发，使得上面的担忧不必要了。但是，由于当时处理中所涉及到的大多数程序设计语 言的翻译并不为人所掌握，所以这个项目的成功也伴随着巨大的辛劳。 几乎与此同时，人们也在开发着第一个编译器，Noam Chomsky开始了他的自然语言结 构的研究。他的发现最终使得编译器结构异常简单，甚至还带有了一些自动化。 Chomsky的 研究导致了根据语言文法（grammar,指定其结构的规则)的难易程度以及识别它们所需的 算法来为语言分类。正如现在所称的一与乔姆斯基分类结构(Chomsky hierarchy)一样一 包括了文法的4个层次：0型、1型、2型和3型文法，且其中的每一个都是其前者的专门化。2 型（或上下文无关文法(context--free grammar)被证明是程序设计语言中最有用的，而且 今天它已代表着程序设计语言结构的标准方式。分析问避(parsing problem,用于限定上下 文无关语言的识别的有效算法)的研究是在60年代和70年代，它相当完善地解决了这一问题， 现在它已是编译理论的一个标准部分。本书的第3、4和5章将研究上下文无关的语言和分析 算法。 有穷自动机(finite automata)和正则表达式(regular expression)同上下文无关文法紧密 相关，它们与乔姆斯基的3型文法相对应。对它们的研究与乔姆斯基的研究几乎同时开始，并 且引出了表示程序设计语言的单词（或称为记号）的符号方式。第2章将讲述有穷自动机和正
见本章最后的“注意与参考”部分）。 首先将简要地介绍编译器的历史及其存在目的与理由，以及与编译器相关的程序描述。接 着讲解编译器的结构、各种翻译过程和相关的数据结构，并联系一个简单的具体示例来示范这 个结构。最后，再概括地讲述一下编译器结构的其他问题，这包括自举和移植，以及本书后面 用到的主要语言的描述。 1.1 为什么要用编译器 在本世纪4 0年代，由于冯·诺伊曼在存储 -程序计算机方面的先锋作用，编写一串代码或 程序已成必要，这样计算机就可以执行所需的计算。开始时，这些程序都是用机器语言 （machine language）编写的。机器语言就是表示机器实际操作的数字代码，例如： C7 06 0000 0002 表示在IBM PC上使用的Intel 8x86处理器将数字2移至地址0 0 0 0（1 6进制）的指令。当然，编写 这样的代码是十分费时和乏味的，这种代码形式很快就被汇编语言（ assembly language）代替 了。在汇编语言中，都是以符号形式给出指令和存储地址的。例如，汇编语言指令 MOV X, 2 就与前面的机器指令等价（假设符号存储地址 X是0 0 0 0）。汇编程序（a s s e m b l e r）将汇编语言 的符号代码和存储地址翻译成与机器语言相对应的数字代码。 汇编语言大大提高了编程的速度和准确度，人们至今仍在使用着它，在编码需要极快的速 度和极高的简洁程度时尤为如此。但是，汇编语言也有许多缺点：编写起来也不容易，阅读和 理解很难；而且汇编语言的编写严格依赖于特定的机器，所以为一台计算机编写的代码在应用 于另一台计算机时必须完全重写。很明显，发展编程技术的下一个重要步骤就是以一个更类似 于数学定义或自然语言的简洁形式来编写程序的操作，它应与任何机器都无关，而且也可由一 个程序翻译为可执行的代码。例如，前面的汇编语言代码可以写成一个简洁的与机器无关的形式 x = 2 起初人们担心这是不可能的，或者即使可能，目标代码也会因效率不高而没有多大用处。 在1 9 5 4年至1 9 5 7年期间，I B M的John Backus带领的一个研究小组对F O RT R A N语言及其编 译器的开发，使得上面的担忧不必要了。但是，由于当时处理中所涉及到的大多数程序设计语 言的翻译并不为人所掌握，所以这个项目的成功也伴随着巨大的辛劳。 几乎与此同时，人们也在开发着第一个编译器， Noam Chomsky开始了他的自然语言结 构的研究。他的发现最终使得编译器结构异常简单，甚至还带有了一些自动化。 C h o m s k y的 研究导致了根据语言文法（ g r a m m a r，指定其结构的规则）的难易程度以及识别它们所需的 算法来为语言分类。正如现在所称的 — 与乔姆斯基分类结构（ Chomsky hierarchy）一样 — 包括了文法的4个层次：0型、1型、2型和3型文法，且其中的每一个都是其前者的专门化。 2 型（或上下文无关文法（ context-free grammar））被证明是程序设计语言中最有用的，而且 今天它已代表着程序设计语言结构的标准方式。分析问题（ parsing problem，用于限定上下 文无关语言的识别的有效算法）的研究是在 6 0年代和7 0年代，它相当完善地解决了这一问题， 现在它已是编译理论的一个标准部分。本书的第 3、4和5章将研究上下文无关的语言和分析 算法。 有穷自动机（finite automata）和正则表达式（regular expression）同上下文无关文法紧密 相关，它们与乔姆斯基的 3型文法相对应。对它们的研究与乔姆斯基的研究几乎同时开始，并 且引出了表示程序设计语言的单词（或称为记号）的符号方式。第 2章将讲述有穷自动机和正 2 编译原理及实践 下载
China-pub.com 第1章腰论了 下载 则表达式。 人们接着又深化了生成有效的目标代码的方法，这就是最初的编译器，它们被一直使用至 今。人们通常将其误称为优化技术(optimization technique),但因其从未真正地得到过被优化 了的目标代码而仅仅改进了它的有效性，因此实际上应称作代码改进技术(code improvement technique)。第8章将讲述该技术的基础知识 当分析问题变得好懂起来时，人们就在开发程序上花费了很大的功夫来研究这一部分的编 译器的自动构造。这些程序最初被称为编译程序-编译器，但更确切地应称为分析程序生成器 (parser generator),这是因为它们仅仅能够自动处理编译的一部分。这些程序中最著名的是 Yacc(yet another compiler-compiler),它是由Steve Johnson在1975年为Unix系统编写的，我们将 在第5章中再次谈到它。类似地，有穷自动机的研究也发展了另一种称为扫描程序生成器 (scanner generator)的工具，Lex(与Yacc同时，由Mike Lesk为Unix系统开发的)是这其中的 佼佼者。读者将在第2章中学到Lex。 在70年代后期和80年代早期，大量的项目都关注于编译器其他部分的生成自动化，这其中 就包括了代码生成。这些尝试并未取得多少成功，这大概是因为操作太复杂而人们又对其不甚 了解，本书也就不详细谈它了 编译器设计最近的发展包括：首先，编译器包括了更为复杂的算法的应用程序，它用于推 断和/或简化程序中的信息：这又与更为复杂的程序设计语言（可允许此类分析）的发展结合 在一起。其中典型的有用于函数语言编译的HindIey-Milner类型检查的统一算法。其次，编译 器已越来越成为基于窗口的交互开发环境(interactive development environment,IDE)的一部 分，它包括了编辑器、链接程序、调试程序以及项目管理程序。这样的DE的标准并没有多少 但是已沿着这一方向对标准的窗口环境进行开发了。这一专题的研究超出了本书的范围（但是 读者可以参阅下一节中有关DE部件的内容)。读者可以参阅本章末尾的“注意与参考”中的 文献内容。尽管近年来对此进行了大量的研究，但是基本的编译器设计在近20年中都没有多大 的改变，而且它们正迅速地成为计算机科学课程中的中心一环。 1.2与编译器相关的程序 本节主要描述与编译器有关或专编译器一同使用的其他程序，以及那些在一个完整的语言 开发环境中与编译器一同使用的程序（有一些已在前面提到过）。 ()解释程序(interpreter) 解释程序是如同编译器的一种语言翻译程序。它与编译器的不同之处在于：它立即执行源 程序而不是生成在翻译完成之后才执行的目标代码。从原理上讲，任何程序设计语言都可被解 释或被编译，但是根据所使用的语言和翻译情况，很可能会选用解释程序而不用编译器。例如， 我们经常解释BASIC语言而不是去编译它。类似地，诸如LISP的函数语言也常常是被解释的。 解释程序也经常用于教育和软件的开发，此处的程序很有可能被翻译若干次。而另一方面，当 执行的速度是最为重要的因素时就使用编译器，这是因为被编译的目标代码比被解释的源代码 要快得多，有时要快10倍或更多。但是，解释程序具有许多与编译器共享的操作，而两者之间 也有一些混合之处。本书后面也将会提到解释程序，但重点仍是编译。 (2)汇编程序(assembler) 汇编程序是用于特定计算机上的汇编语言的翻译程序。正如前面所提到的，汇编语言是计 算机的机器语言的符号形式，它极易翻译。有时，编译器会生成汇编语言以作为其目标语言， 然后再由一个汇编程序将它翻译成目标代码
则表达式。 人们接着又深化了生成有效的目标代码的方法，这就是最初的编译器，它们被一直使用至 今。人们通常将其误称为优化技术（ optimization technique），但因其从未真正地得到过被优化 了的目标代码而仅仅改进了它的有效性，因此实际上应称作代码改进技术（ code improvement t e c h n i q u e）。第8章将讲述该技术的基础知识。 当分析问题变得好懂起来时，人们就在开发程序上花费了很大的功夫来研究这一部分的编 译器的自动构造。这些程序最初被称为编译程序 -编译器，但更确切地应称为分析程序生成器 （parser generator），这是因为它们仅仅能够自动处理编译的一部分。这些程序中最著名的是 Ya c c（yet another compiler- c o m p i l e r），它是由Steve Johnson在1 9 7 5年为U n i x系统编写的，我们将 在第 5章中再次谈到它。类似地，有穷自动机的研究也发展了另一种称为扫描程序生成器 （scanner generator）的工具，L e x（与Ya c c同时，由Mike Lesk为U n i x系统开发的）是这其中的 佼佼者。读者将在第2章中学到L e x。 在7 0年代后期和8 0年代早期，大量的项目都关注于编译器其他部分的生成自动化，这其中 就包括了代码生成。这些尝试并未取得多少成功，这大概是因为操作太复杂而人们又对其不甚 了解，本书也就不详细谈它了。 编译器设计最近的发展包括：首先，编译器包括了更为复杂的算法的应用程序，它用于推 断和/或简化程序中的信息；这又与更为复杂的程序设计语言（可允许此类分析）的发展结合 在一起。其中典型的有用于函数语言编译的 H i n d l e y - M i l n e r类型检查的统一算法。其次，编译 器已越来越成为基于窗口的交互开发环境（ interactive development environment，I D E）的一部 分，它包括了编辑器、链接程序、调试程序以及项目管理程序。这样的 I D E的标准并没有多少， 但是已沿着这一方向对标准的窗口环境进行开发了。这一专题的研究超出了本书的范围（但是 读者可以参阅下一节中有关 I D E部件的内容）。读者可以参阅本章末尾的“注意与参考”中的 文献内容。尽管近年来对此进行了大量的研究，但是基本的编译器设计在近 2 0年中都没有多大 的改变，而且它们正迅速地成为计算机科学课程中的中心一环。 1.2 与编译器相关的程序 本节主要描述与编译器有关或专编译器一同使用的其他程序，以及那些在一个完整的语言 开发环境中与编译器一同使用的程序（有一些已在前面提到过）。 (1) 解释程序（i n t e r p re t e r） 解释程序是如同编译器的一种语言翻译程序。它与编译器的不同之处在于：它立即执行源 程序而不是生成在翻译完成之后才执行的目标代码。从原理上讲，任何程序设计语言都可被解 释或被编译，但是根据所使用的语言和翻译情况，很可能会选用解释程序而不用编译器。例如， 我们经常解释B A S I C语言而不是去编译它。类似地，诸如 L I S P的函数语言也常常是被解释的。 解释程序也经常用于教育和软件的开发，此处的程序很有可能被翻译若干次。而另一方面，当 执行的速度是最为重要的因素时就使用编译器，这是因为被编译的目标代码比被解释的源代码 要快得多，有时要快1 0倍或更多。但是，解释程序具有许多与编译器共享的操作，而两者之间 也有一些混合之处。本书后面也将会提到解释程序，但重点仍是编译。 (2) 汇编程序（a s s e m b l e r） 汇编程序是用于特定计算机上的汇编语言的翻译程序。正如前面所提到的，汇编语言是计 算机的机器语言的符号形式，它极易翻译。有时，编译器会生成汇编语言以作为其目标语言， 然后再由一个汇编程序将它翻译成目标代码。 第 1章 概 论 3 下载
编译原理及实践 China-pub.C 下载 (3)连接程序(linker) 编译器和汇编程序都经常依赖于连接程序，它将分别在不同的目标文件中编译或汇编的代 码收集到一个可直接执行的文件中。在这种情况下，目标代码，即还未被连接的机器代码，与 可执行的机器代码之间就有了区别。连接程序还连接目标程序和用于标准库函数的代码，以及 连接目标程序和由计算机的操作系统提供的资源（例如，存储分配程序及输入与输出设备）。 有趣的是，连接程序现在正在完成编译器最早的一个主要活动（这也是“编译”一词的用法， 即通过收集不同的来源来构造)。因为连接过程对操作系统和处理器有极大的依赖性，本书也 就不研究它了。我们也对不细分连接的目标代码和可执行的代码，这是因为对于编译技术而言， 这个区别并不重要 (④装入程序(loader) 编译要、厂编得常或连接程序生成的代码经常还不完全话用或不能抽行，但是它们的主要 存储器访问却可以在存储器的任何位置中且与一个不确定的起始位置相关。这样的代码被称为 是可重定位的(relocatable),而装入程序可处理所有的与指定的基地址或起始地址有关的可重 定位的地址。装入程序使得可执行代码更加灵活，但是装入处理通常是在后台（作为操作环境 的一部分)或与连接相联合时才发生，装入程序极少会是实际的独立程序。 ()预处理器(preprocessor) 预处理器是在真正的翻译开始之前由编译器调用的独立程序。预处理器可以别除注释、包 含其他文件以及执行宏（宏macro是一段重复文字的简短描写）替代。预处理器可由语言（如 C)要求或以后作为提供额外功能（诸如为FORTRAN提供Ratfor预处理器）的附加软件， (6)编辑器(editor) 编译器通常接受由任何生成标准文件（例如ASCⅡ文件）的编辑器编写的源程序。最近， 编译器已与另 个编辑器和其他程序捆绑进一个交互的开发环境 IDE中。此时，尽管编辑 器仍然生成标准文件，但会转向正被讨论的程序设计语言的格式或结构。这样的编辑器称为基 于结构的(structure based),且它早已包括了编译器的某些操作：因此，程序员就会在程序的 编写时而不是在编译时就得知错误了。从编辑器中也可调用编译器以及与它共用的程序，这样 程序员无需离开编辑器就可执行程序。 ()调试程序(debugger 调试程序是可在被编译了的程序中判定执行错误的程序，它也经常与编译器一起放在DE 中。运行一个带有调试程序的程序与直接执行不同，这是因为调试程序保存着所有的或大多数 源代码信息（诸如行数、变量名和过程）。它还可以在预先指定的位置（称为断点(breakpoint) 暂停执行，并提供有关已调用的函数以及变量的当前值的信息。为了执行这些函数，编译器必 须为调试程序提供恰当的符号信息，而这有时却相当困难，尤其是在一个要优化目标代码的编 译器中。因此，调试又变成了一个编译问题，本书的内容就不涉及它了。 ()⑧描述器(prof) 描述器是在执行中搜集目标程序行为统计的程序。程序员特别感兴趣的统计是每一个过程 的调用次数和每一个过程执行时间所占的百分比。这样的统计对于帮助程序员提高程序的执 行速度极为有用。有时编译器也甚至无需程序员的干涉就可利用描述器的输出来自动改进目 标代码。 (9)项目管理程序(project mana ager 现在的软件项目通常大到需要由一组程序员来完成，这时对那些由不同人员操作的文件进 行整理就非常重要了，而这正是项目管理程序的任务。例如，项目管理程序应将由不同的程序
(3) 连接程序（l i n k e r） 编译器和汇编程序都经常依赖于连接程序，它将分别在不同的目标文件中编译或汇编的代 码收集到一个可直接执行的文件中。在这种情况下，目标代码，即还未被连接的机器代码，与 可执行的机器代码之间就有了区别。连接程序还连接目标程序和用于标准库函数的代码，以及 连接目标程序和由计算机的操作系统提供的资源（例如，存储分配程序及输入与输出设备）。 有趣的是，连接程序现在正在完成编译器最早的一个主要活动（这也是“编译”一词的用法， 即通过收集不同的来源来构造）。因为连接过程对操作系统和处理器有极大的依赖性，本书也 就不研究它了。我们也对不细分连接的目标代码和可执行的代码，这是因为对于编译技术而言， 这个区别并不重要。 (4) 装入程序（l o a d e r） 编译器、汇编程序或连接程序生成的代码经常还不完全适用或不能执行，但是它们的主要 存储器访问却可以在存储器的任何位置中且与一个不确定的起始位置相关。这样的代码被称为 是可重定位的（r e l o c a t a b l e），而装入程序可处理所有的与指定的基地址或起始地址有关的可重 定位的地址。装入程序使得可执行代码更加灵活，但是装入处理通常是在后台（作为操作环境 的一部分）或与连接相联合时才发生，装入程序极少会是实际的独立程序。 (5) 预处理器（p re p ro c e s s o r） 预处理器是在真正的翻译开始之前由编译器调用的独立程序。预处理器可以删除注释、包 含其他文件以及执行宏（宏 m a c r o是一段重复文字的简短描写）替代。预处理器可由语言（如 C）要求或以后作为提供额外功能（诸如为F O RT R A N提供R a t f o r预处理器）的附加软件。 (6) 编辑器（e d i t o r） 编译器通常接受由任何生成标准文件（例如 A S C I I文件）的编辑器编写的源程序。最近， 编译器已与另一个编辑器和其他程序捆绑进一个交互的开发环境—— I D E中。此时，尽管编辑 器仍然生成标准文件，但会转向正被讨论的程序设计语言的格式或结构。这样的编辑器称为基 于结构的（structure based），且它早已包括了编译器的某些操作；因此，程序员就会在程序的 编写时而不是在编译时就得知错误了。从编辑器中也可调用编译器以及与它共用的程序，这样 程序员无需离开编辑器就可执行程序。 (7) 调试程序（d e b u g g e r） 调试程序是可在被编译了的程序中判定执行错误的程序，它也经常与编译器一起放在 I D E 中。运行一个带有调试程序的程序与直接执行不同，这是因为调试程序保存着所有的或大多数 源代码信息（诸如行数、变量名和过程）。它还可以在预先指定的位置（称为断点（b r e a k p o i n t）） 暂停执行，并提供有关已调用的函数以及变量的当前值的信息。为了执行这些函数，编译器必 须为调试程序提供恰当的符号信息，而这有时却相当困难，尤其是在一个要优化目标代码的编 译器中。因此，调试又变成了一个编译问题，本书的内容就不涉及它了。 (8) 描述器（p ro f i l e r） 描述器是在执行中搜集目标程序行为统计的程序。程序员特别感兴趣的统计是每一个过程 的调用次数和每一个过程执行时间所占的百分比。这样的统计对于帮助程序员提高程序的执 行速度极为有用。有时编译器也甚至无需程序员的干涉就可利用描述器的输出来自动改进目 标代码。 (9) 项目管理程序（p roject manager） 现在的软件项目通常大到需要由一组程序员来完成，这时对那些由不同人员操作的文件进 行整理就非常重要了，而这正是项目管理程序的任务。例如，项目管理程序应将由不同的程序 4 编译原理及实践 下载
China-pub.com 下载 第1章餐论了 员制作的文件的各个独立版本整理在一起，它还应保存一组文件的更改历史，这样就能维持 个正在开发的程序的连贯版本了（这对那些由单个程序员管理的项目也很有用）。项目管理程 序的编写可与语言无关，但当其与编译器捆绑在一起时，它就可以保持有关特定的编译器和建 立一个完整的可执行程序的链接程序操作的信息。在Uix系统中有两个流行的项目管理程序： sces (source code control system)res (revision control system). 1.3翻译步骤 编译器内部包括了许多步骤或称为阶段 源代码 (phase),它们执行不同的逻辑操作。将这些阶段 设想为编译器中一个个单独的片断是很有用的， 尽管在应用中它们是经常组合在一起的，但它们 确实是作为单独的代码操作来编写的。图1-1是编 译器中的阶段和与以下阶段（文字表、符号表和 错误处理器)或其中的一部分交互的3个辅助部件 这里只是简要地描述一下每个阶段，今后大家还 会更详细地学到它们（文字表和符号表在1.4节中， 错误处理器在1.5节)。 法 ()扫描程序(scanner) 在这个阶段编译器实际阅读源程序（通常以 文字表 字符流的形式表示)。扫描程序执行词法分析 注释 符号表 (Lexical analysis):它将字符序列收集到称作记号 (token)的有意义单元中，记号同自然语言，如英 语中的字词相似。因此可以认为扫描程序执行与 拼写相似的任务 例如在下面的代码行（它可以是C程序的一部 分)中： a【index】=4+2 这个代码包括了12个非空字符，但只有8个 记号： 标识符 左括号 index 标识符 右括号 赋值 日标代码 4 数字 加号 图1-1编译器的阶段 3 数字 每一个记号均由一个或多个字符组成，在进一步处理之前它已被收集在一个单元中。 扫描程序还可完成与识别记号一起执行的其他操作。例如，它可将标识符输入到符号表中， 将文字(literal)输入到文字表中（文字包括诸如3.1415926535的数字常量，以及诸如“Hello world!”的引用字符串)。 (2)语法分析程序（parser)
员制作的文件的各个独立版本整理在一起，它还应保存一组文件的更改历史，这样就能维持一 个正在开发的程序的连贯版本了（这对那些由单个程序员管理的项目也很有用）。项目管理程 序的编写可与语言无关，但当其与编译器捆绑在一起时，它就可以保持有关特定的编译器和建 立一个完整的可执行程序的链接程序操作的信息。在 U n i x系统中有两个流行的项目管理程序： s c c s（source code control system）和r c s（revision control system）。 1.3 翻译步骤 编译器内部包括 了许多步骤或称 为阶段 （p h a s e），它们执行不同的逻辑操作。将这些阶段 设想为编译器中一个个单独的片断是很有用的， 尽管在应用中它们是经常组合在一起的，但它们 确实是作为单独的代码操作来编写的。图 1 - 1是编 译器中的阶段和与以下阶段（文字表、符号表和 错误处理器）或其中的一部分交互的3个辅助部件。 这里只是简要地描述一下每个阶段，今后大家还 会更详细地学到它们（文字表和符号表在 1 . 4节中， 错误处理器在1 . 5节）。 (1) 扫描程序（s c a n n e r） 在这个阶段编译器实际阅读源程序（通常以 字符流的形式表示）。扫描程序执行词法分析 （Lexical analysis）：它将字符序列收集到称作记号 （t o k e n）的有意义单元中，记号同自然语言，如英 语中的字词相似。因此可以认为扫描程序执行与 拼写相似的任务。 例如在下面的代码行（它可以是 C程序的一部 分）中： a [index] = 4 + 2 这个代码包括了 1 2个非空字符，但只有 8个 记号： a 标识符 [ 左括号 i n d e x 标识符 ] 右括号 = 赋值 4 数字 + 加号 2 数字 每一个记号均由一个或多个字符组成，在进一步处理之前它已被收集在一个单元中。 扫描程序还可完成与识别记号一起执行的其他操作。例如，它可将标识符输入到符号表中， 将文字（l i t e r a l）输入到文字表中（文字包括诸如 3 . 1 4 1 5 9 2 6 5 3 5的数字常量，以及诸如“H e l l o , w o r l d !”的引用字符串）。 (2) 语法分析程序（p a r s e r） 第 1章 概 论 5 下载 扫描程序 语法分 析程序 语义分 析程序 源代码 优化程序 代码 生成器 目标代码 优化程序 记号 源代码 语法树 注释树 中间 代码 目标 代码 目标代码 符号表 错误处 理器 文字表 图1-1 编译器的阶段
6 编译原理及实线 China-pub.C 下载 语法分析程序从扫描程序中获取记号形式的源代码，并完成定义程序结构的语法分析 (syntax analysis),这与自然语中句子的语法分析类以。语法分析定义了程序的结构元素及 其关系。通常将语法分析的结果表示为分析树(parse tree)或语法树(syntax tree)。 例如，还是那行C代码，它表示一个称为表达式的结构元素，该表达式是一个由左边为 下标表达式、右边为整型表达式的赋值表达式组成。这个结构可按下面的形式表示为一个分 析树： expression sign-expression subscript-expression 请注意，分析树的内部节点均由其表示的结构名标示出，而分析树的叶子则表示输入中的 记号序列（结构名以不同字体表示以示与记号的区别）。 分析树对于显示程序的语法或程序元素很有帮助，但是对干表示该结构却显得力不从心了 分析程序更趋向于生成语法树，语法树是分析树中所含信息的浓缩（有时因为语法树表示从分 析树中的进一步抽取，所以也被称为抽象的语法树(abstract syntax tree)。下面是一个C赋值 语句的抽象语法树的例子： assign-expression subscripi-expression 请注意，在语法树中，许多节点（包括记号节点在内）已经消失。例如，如果知道表达式 是一个下标运算，则不再需要用括号“【”和“1”来表示该操作是在原始输入中。 (③)语义分析程序(semantic analyzer) 程序的语义就是它的“意思”，它与语法或结构不同。程序的语义确定程序的运行，但是 大多数的程序设计语言都具有在执行之前被确定而不易由语法表示和由分析程序分析的特征。 这些特征被称作静态语义(static semantic),而语义分析程序的任务就是分析这样的语义（程 序的“动态”语义具有只有在程序执行时才能确定的特性，由于编译器不能执行程序，所以它 不能由编译器来确定)。一般的程序设计语言的典型静态语义包括声明和类型检查。由语义分 析程序计算的额外信息（诸如数据类型）被称为属性(attribute),它们通常是作为注释或“装 饰”增加到树中（还可将属性添加到符号表中）。 在正运行的C表达式
语法分析程序从扫描程序中获取记号形式的源代码，并完成定义程序结构的语法分析 （syntax analysis），这与自然语言中句子的语法分析类似。语法分析定义了程序的结构元素及 其关系。通常将语法分析的结果表示为分析树（ parse tree）或语法树（syntax tree）。 例如，还是那行 C代码，它表示一个称为表达式的结构元素，该表达式是一个由左边为 下标表达式、右边为整型表达式的赋值表达式组成。这个结构可按下面的形式表示为一个分 析树： 请注意，分析树的内部节点均由其表示的结构名标示出，而分析树的叶子则表示输入中的 记号序列（结构名以不同字体表示以示与记号的区别）。 分析树对于显示程序的语法或程序元素很有帮助，但是对于表示该结构却显得力不从心了。 分析程序更趋向于生成语法树，语法树是分析树中所含信息的浓缩（有时因为语法树表示从分 析树中的进一步抽取，所以也被称为抽象的语法树（ abstract syntax tree））。下面是一个C赋值 语句的抽象语法树的例子： 请注意，在语法树中，许多节点（包括记号节点在内）已经消失。例如，如果知道表达式 是一个下标运算，则不再需要用括号“[”和“]”来表示该操作是在原始输入中。 (3) 语义分析程序（semantic analyzer） 程序的语义就是它的“意思”，它与语法或结构不同。程序的语义确定程序的运行，但是 大多数的程序设计语言都具有在执行之前被确定而不易由语法表示和由分析程序分析的特征。 这些特征被称作静态语义（ static semantic），而语义分析程序的任务就是分析这样的语义（程 序的“动态”语义具有只有在程序执行时才能确定的特性，由于编译器不能执行程序，所以它 不能由编译器来确定）。一般的程序设计语言的典型静态语义包括声明和类型检查。由语义分 析程序计算的额外信息（诸如数据类型）被称为属性（ a t t r i b u t e），它们通常是作为注释或“装 饰”增加到树中（还可将属性添加到符号表中）。 在正运行的C表达式 6 编译原理及实践 下载
China-pub.com 下载 第1京樱论7 a【index】=4+2 中，该行分析之前收集的典型类型信息可能是：a是一个整型值的数组，它带有来自整型子范 围的下标：1ndx则是一个整型变量。接着，语义分析程序将用所有的子表达式类型来标注语 法树，并检查赋值是否使这些类型有意义了，如若没有，则声明一个类型匹配错误。在上例中， 所有的类型均有意义，有关语法树的语义分析结果可用以下注释了的树来表示： assign-statement additive. identifier identifier number array of intege index intege intege intege (4)源代码优化程序(source code optimizer) 编译器通常包括许多代码改进或优化步骤。绝大多数最早的优化步骤是在语义分析之后完 成的，而此时代码改进可能只依赖于源代码。这种可能性是通过将这一操作提供为编译过程中 的单独阶段指出的。每个编译器不论在已完成的优化种类方面还是在优化阶段的定位中都有很 大的差异。 在上例中，我们包括了一个源代码层次的优化机会，也就是：表达式4+2可由编译器计算 先得到结果6（这种优化称为常量合并(onstant foin)。当然，还会有更复杂的情况（有 些将在第8章中提到)。还是在上例中，通过将根节点右面的子树合并为它的常量值，这个优化 就可以直接在（注释）语法树上完成： assign-statement bnegnan integer idontifier identifior aray of integer 尽管许多优化可以直接在树上完成，但是在很多情况下，优化接近于汇编代码线性化形式 的树更为简便。这样节点的变形有许多，但是三元式代码(three-address code)(之所以这样称 呼是因为它在存储器中包含了3个（或3个以上）位置的地址)却是标准选择。另一个常见的选 择是P.代码(P-code),它常用于Pascal编译器中。 在前面的例子中，原先的C表达式的三元式代码应是： t=4+2 a【index】=t (请注意，这里利用了一个额外的临时变量t存放加法的中间值)。这样，优化程序就将这个代 码改进为两步。首先计算加法的结果： t=6 a【1ndex】=t
a [index] = 4 + 2 中，该行分析之前收集的典型类型信息可能是： a是一个整型值的数组，它带有来自整型子范 围的下标；i n d e x则是一个整型变量。接着，语义分析程序将用所有的子表达式类型来标注语 法树，并检查赋值是否使这些类型有意义了，如若没有，则声明一个类型匹配错误。在上例中， 所有的类型均有意义，有关语法树的语义分析结果可用以下注释了的树来表示： (4) 源代码优化程序（s o u rce code optimizer） 编译器通常包括许多代码改进或优化步骤。绝大多数最早的优化步骤是在语义分析之后完 成的，而此时代码改进可能只依赖于源代码。这种可能性是通过将这一操作提供为编译过程中 的单独阶段指出的。每个编译器不论在已完成的优化种类方面还是在优化阶段的定位中都有很 大的差异。 在上例中，我们包括了一个源代码层次的优化机会，也就是：表达式 4 + 2可由编译器计算 先得到结果6（这种优化称为常量合并（ constant folding））。当然，还会有更复杂的情况（有 些将在第8章中提到）。还是在上例中，通过将根节点右面的子树合并为它的常量值，这个优化 就可以直接在（注释）语法树上完成： 尽管许多优化可以直接在树上完成，但是在很多情况下，优化接近于汇编代码线性化形式 的树更为简便。这样节点的变形有许多，但是三元式代码（ three-address code）（之所以这样称 呼是因为它在存储器中包含了3个（或3个以上）位置的地址）却是标准选择。另一个常见的选 择是P -代码（P - c o d e），它常用于P a s c a l编译器中。 在前面的例子中，原先的C表达式的三元式代码应是： t = 4 + 2 a [ index] = t （请注意，这里利用了一个额外的临时变量 t 存放加法的中间值）。这样，优化程序就将这个代 码改进为两步。首先计算加法的结果： t = 6 a [index] = t 第 1章 概 论 7 下载
8 编译原理及实线 China-pub.co 下载 接着，将t替换为该值以得到三元语句 a【1ndex】=6 图1-l已经指出源代码优化程序可能通过将其输出称为中间代码(intermediate code)来使 用三元式代码。中间代码一直是指一种位于源代码和目标代码（例如三元式代码或类似的线性 表示)之间的代码表示形式。但是，我们可以更概括地认为它是编译器使用的源代码的任何一 个内部表示。此时，也可将语法树称作中间代码，源代码优化程序则确实能继续在其输出中使 用这个表示。有时，这个中间代a码也称作中间表示(intermediate representation,R)。 (5)代码生成器(code generator) 代码生成器得到中间代码(R),并生成目标机器的代码。尽管大多数编译器直接生成目 标代码，但是为了便于理解，本书用汇编语言来编写目标代码。正是在编译的这个阶段中，目 标机器的特性成为了主要因素。当它存在于目标机器时，使用指令不仅是必须的而且数据的形 式表示也起着重要的作用。例如，整型数据类型的变量和浮点数据类型的变量在存储器中所占 的字节数或字数也很重要。 在上面的示例中，现在必须决定怎样存储整型数来为数组索引生成代码。例如，下面是所 给表达式的一个可能的样本代码序列（在假设的汇编语言中）： 1, App 1R0 MoV ★R1.6 :constant 6->address in Rl 在以上代码中，为编址模式使用了一个类似C的协定，因此sa是a的地址（也就是数组的 基地址)，*1则意味着间接寄存器地址（因此最后一条指令将值6存放在R1包含的地址中）。 这个代码还假设机器执行字节编址，并且整型数占据存储器的两个字节（所以在第2条指令中 用2作为乘数)。 (⑥目标代码优化程序(target code optimizer) 在这个阶段中，编译器尝试着改进由代码生成器生成的目标代码。这种改进包括选择编址 模式以提高性能、将速度慢的指令更换成速度快的，以及别除多余的操作。 在上面给出的样本目标代码中，还可以做许多更改：在第2条指令中，利用移位指令替代 乘法（通常地，乘法很费时间），还可以使用更有效的编址模式（例如用索引地址来执行数组 存储)。使用了这两种优化后，目标代码就变成： index M0a【R01,6 s->add 到这里，对编译器阶段的简要描述就结束了，但我们还应特别强调这些讲述仅仅是示意性 的，也无需表示出正在工作中的编译器的实际结构。编译器在其结构细节上确实差别很大，然 而，上面讲到的阶段总会出现在几乎所有的编译器的某个形式上。 我们还谈到了用于维持每一个阶段所需信息的数据结构，例如语法树、中间代码（假设它 们并不相同)、文字表和符号表。下一节是编译器中的主要数据结构的概览。 1.4编译器中的主要数据结构 当然，由编译器的阶段使用的算法与支持这些阶段的数据结构之间的交互是非常强大的。 编译器的编写者尽可能有效实施这些方法且不引起复杂性。理想的情况是：与程序大小成线性
接着，将t替换为该值以得到三元语句 a [index] = 6 图1 - 1已经指出源代码优化程序可能通过将其输出称为中间代码（ intermediate code）来使 用三元式代码。中间代码一直是指一种位于源代码和目标代码（例如三元式代码或类似的线性 表示）之间的代码表示形式。但是，我们可以更概括地认为它是编译器使用的源代码的任何一 个内部表示。此时，也可将语法树称作中间代码，源代码优化程序则确实能继续在其输出中使 用这个表示。有时，这个中间代码也称作中间表示（ intermediate representation, I R）。 (5) 代码生成器（code generator） 代码生成器得到中间代码（ I R），并生成目标机器的代码。尽管大多数编译器直接生成目 标代码，但是为了便于理解，本书用汇编语言来编写目标代码。正是在编译的这个阶段中，目 标机器的特性成为了主要因素。当它存在于目标机器时，使用指令不仅是必须的而且数据的形 式表示也起着重要的作用。例如，整型数据类型的变量和浮点数据类型的变量在存储器中所占 的字节数或字数也很重要。 在上面的示例中，现在必须决定怎样存储整型数来为数组索引生成代码。例如，下面是所 给表达式的一个可能的样本代码序列（在假设的汇编语言中）： M O V R0, index ;; value of index -> R0 M U L R0, 2 ;; double value in R0 M O V R1, &a ;; address of a -> R1 A D D R1, R0 ;; add R0 to R1 M O V *R1, 6 ;; constant 6 -> address in R1 在以上代码中，为编址模式使用了一个类似 C的协定，因此& a是a的地址（也就是数组的 基地址），* R 1则意味着间接寄存器地址（因此最后一条指令将值 6存放在R 1包含的地址中）。 这个代码还假设机器执行字节编址，并且整型数占据存储器的两个字节（所以在第 2条指令中 用2作为乘数）。 (6) 目标代码优化程序（target code optimizer） 在这个阶段中，编译器尝试着改进由代码生成器生成的目标代码。这种改进包括选择编址 模式以提高性能、将速度慢的指令更换成速度快的，以及删除多余的操作。 在上面给出的样本目标代码中，还可以做许多更改：在第 2条指令中，利用移位指令替代 乘法（通常地，乘法很费时间），还可以使用更有效的编址模式（例如用索引地址来执行数组 存储）。使用了这两种优化后，目标代码就变成： MOV R0, index ;; value of index -> R0 SHL R0 ;; double value in R0 MOV &a[R0], 6 ;; constant 6 -> address a + R0 到这里，对编译器阶段的简要描述就结束了，但我们还应特别强调这些讲述仅仅是示意性 的，也无需表示出正在工作中的编译器的实际结构。编译器在其结构细节上确实差别很大，然 而，上面讲到的阶段总会出现在几乎所有的编译器的某个形式上。 我们还谈到了用于维持每一个阶段所需信息的数据结构，例如语法树、中间代码（假设它 们并不相同）、文字表和符号表。下一节是编译器中的主要数据结构的概览。 1.4 编译器中的主要数据结构 当然，由编译器的阶段使用的算法与支持这些阶段的数据结构之间的交互是非常强大的。 编译器的编写者尽可能有效实施这些方法且不引起复杂性。理想的情况是：与程序大小成线性 8 编译原理及实践 下载
China-pub.com 第1章概论 9 下载 比例的时间内编译器，换言之就是，在0(n)时间内，是程序大小的度量（通常是字符数）。 本节将讲述一些主要的数据结构，它们是其操作部分阶段所需要的，并用来在阶段中交流信 息。 (1)记号(token) 当扫描程序将字符收集到一个记号中时，它通常是以符号表示这个记号：这也就是说，作 为一个枚举数据类型的值来表示源程序的记号集。有时还必须保留字符串本身或由此派生出的 其他信息（例如：与标识符记号相关的名字或数字记号值）。在大多数语言中，扫描程序一次 只需要生成一个记号（这称为单符号先行(single symbol lookahead)。在这种情况下，可以用 全程变量放置记号信息：而在别的情况（最为明显的是FORTRAN)下，则可能会需要一个记 号数组。 (2)语法树(syntax tree) 如果分析程序确实生成了语法树，它的构造通常为基于指针的标准结构，在进行分析时动 态分配该结构，则整棵树可作为一个指向根节点的单个变量保存。结构中的每一个节点都是 个记录，它的域表示由分析程序和之后的语义分析程序收集的信息。例如，一个表达式的数据 类型可作为表达式的语法树节点中的域。有时为了节省空间，这些域也是动态分配或存放在诸 如符号表的其他数据结构中，这样就可以有选择地进行分配和释放。实际上，根据它所表示的 语言结构的类型（例如：表达式节点对于语句节点或声明节点都有不同的要求），每一个语法 树节点本身都可能要求存储不同的属性。在这种情况下，可由不同的记录表示语法树中的每个 节点，每个节点类型只包含与本身相关的信息。 (3)符号表(symbol table) 这个数据结构中的信息与标识符有关：函数、变量、常量以及数据类型。符号表几乎与编 译器的所有阶段交互：扫描程序、分析程序或将标识符输入到表格中的语义分析程序：语义分 析程序将增加数据类型和其他信息：优化阶段和代码生成阶段也将利用由符号表提供的信息选 出恰当的代码。因为对符号表的访问如此频繁，所以插入、删除和访问操作都必须比常规操作 更有效。尽管可以使用各种树的结构，但杂凑表却是达到这一要求的标准数据结构。有时在 个列表或栈中可使用若干个表格。 (④常数表(literal table) 常数表的功能是存放在程序中用到的常量和字符串，因此快速插入和查找在常数表中也十 分重要。但是，在其中却无需删除，这是因为它的数据全程应用于程序而且常量或字符串在该 表中只出现一次。通过允许重复使用常量和字符串，常数表对于缩小程序在存储器中的大小显 得非常重要。在代码生成器中也需要常数表来构造用于常数和在目标代码文件中输入数据定义 的符号地址。 (⑤中间代码(intermediate code) 根据中间代码的类型（例如三元式代码和P一代码）和优化的类型，该代码可以是文本电 的数组、临时文本文件或是结构的连接列表。对于进行复杂优化的编译器，应特别注意选择允 许简单重组的表示。 (O临时文件(temporary file) 计算机过去一直未能在编译器时将整个程序保留在存储器中。这一问题已经通过使用临时 文件来保存翻译时中间步骤的结果或通过“匆忙地”编译（也就是只保留源程序早期部分的足 够信息用以处理翻译)解决了。存储器的限制现在也只是一个小问颗了，现在可以将整个编译 单元放在存储器之中，特别是在可以分别编译的语言中时。但是偶尔还是会发现需要在某些运
比例的时间内编译器，换言之就是，在 0 ( n）时间内，n是程序大小的度量（通常是字符数）。 本节将讲述一些主要的数据结构，它们是其操作部分阶段所需要的，并用来在阶段中交流信 息。 (1) 记号（t o k e n） 当扫描程序将字符收集到一个记号中时，它通常是以符号表示这个记号；这也就是说，作 为一个枚举数据类型的值来表示源程序的记号集。有时还必须保留字符串本身或由此派生出的 其他信息（例如：与标识符记号相关的名字或数字记号值）。在大多数语言中，扫描程序一次 只需要生成一个记号（这称为单符号先行（ single symbol lookahead））。在这种情况下，可以用 全程变量放置记号信息；而在别的情况（最为明显的是 F O RT R A N）下，则可能会需要一个记 号数组。 (2) 语法树（syntax tre e） 如果分析程序确实生成了语法树，它的构造通常为基于指针的标准结构，在进行分析时动 态分配该结构，则整棵树可作为一个指向根节点的单个变量保存。结构中的每一个节点都是一 个记录，它的域表示由分析程序和之后的语义分析程序收集的信息。例如，一个表达式的数据 类型可作为表达式的语法树节点中的域。有时为了节省空间，这些域也是动态分配或存放在诸 如符号表的其他数据结构中，这样就可以有选择地进行分配和释放。实际上，根据它所表示的 语言结构的类型（例如：表达式节点对于语句节点或声明节点都有不同的要求），每一个语法 树节点本身都可能要求存储不同的属性。在这种情况下，可由不同的记录表示语法树中的每个 节点，每个节点类型只包含与本身相关的信息。 (3) 符号表（symbol table） 这个数据结构中的信息与标识符有关：函数、变量、常量以及数据类型。符号表几乎与编 译器的所有阶段交互：扫描程序、分析程序或将标识符输入到表格中的语义分析程序；语义分 析程序将增加数据类型和其他信息；优化阶段和代码生成阶段也将利用由符号表提供的信息选 出恰当的代码。因为对符号表的访问如此频繁，所以插入、删除和访问操作都必须比常规操作 更有效。尽管可以使用各种树的结构，但杂凑表却是达到这一要求的标准数据结构。有时在一 个列表或栈中可使用若干个表格。 (4) 常数表（literal table） 常数表的功能是存放在程序中用到的常量和字符串，因此快速插入和查找在常数表中也十 分重要。但是，在其中却无需删除，这是因为它的数据全程应用于程序而且常量或字符串在该 表中只出现一次。通过允许重复使用常量和字符串，常数表对于缩小程序在存储器中的大小显 得非常重要。在代码生成器中也需要常数表来构造用于常数和在目标代码文件中输入数据定义 的符号地址。 (5) 中间代码（intermediate code） 根据中间代码的类型（例如三元式代码和P -代码）和优化的类型，该代码可以是文本串 的数组、临时文本文件或是结构的连接列表。对于进行复杂优化的编译器，应特别注意选择允 许简单重组的表示。 (6) 临时文件（t e m p o r a ry file） 计算机过去一直未能在编译器时将整个程序保留在存储器中。这一问题已经通过使用临时 文件来保存翻译时中间步骤的结果或通过“匆忙地”编译（也就是只保留源程序早期部分的足 够信息用以处理翻译）解决了。存储器的限制现在也只是一个小问题了，现在可以将整个编译 单元放在存储器之中，特别是在可以分别编译的语言中时。但是偶尔还是会发现需要在某些运 第 1章 概 论 9 下载
10 编译原理及实践 China-pub.C 下载 行步骤中生成中间文件。其中典型的是代码生成时需要反填(backpatch)地址。例如，当翻译 如下的条件语句时 if x =0 them 1 在知道else部分代码的位置之前必须由文本跳到else部分： CMP X,0 JNE NEXT ;location of NEXT not yet known code for then-part NEXT: code for else-part 通常，必须为NExT的值留出一个空格，一旦知道该值后就会将该空格填上，利用临时文 件可以很容易地做到这一点 1.5编译器结构中的其他问题 可从许多不同的角度来观察编译器的结构。13节已讲术了它的阶段一一用来表示编译器的 逻辑结构。此外，还有其他一些可能的观点：编译器的物理结构、操作的顺序等等。由于编译 器的结构对其可靠性、有效性、可用性以及可维护性都有很大的影响，所以编译器的编写者应 熟悉尽可能多的有关编译器结构的观点。本节将考虑编译器结构的其他方面以及每一个观点是 如何应用的。 高→智除路、 中间 ()分析和综合 在这个观点中，已将分析源程序以计算其特性的编译器操作归为编译器的分析(analysis) 部分，而将生成翻译代码时所涉及到的操作称作编译器的综合(synthesis)部分。当然，词法 分析、语法分析和语义分析均属于分析部分，而代码生成却是综合部分。在优化步骤中，分析 和综合都有。分析正趋向于易懂和更具有数学性，而综合则要求更深的专业技术。因此，将分 析步骤和综合步骤两者区分开来以便发生变化时互不影响是很有用的： (2)前端和后端 本观点认为，将编译器分成了只依赖于源语言（前端(front end)的操作和只依赖于目 标语言（后端(back end)的操作两部分。这与将其分成分析和综合两部分是类似的：扫描 程序、分析程序和语义分析程序是前端，代码生成器是后端。但是一些优化分析可以依赖于目 标语言，这样就是属于后端了，然而中间代码的综合却经常与目标语言无关，因此也就属于前 端了。在理想情况下，编译器被严格地分成这两部分，而中间表示则作为其间的交流媒介。 这一结构对于编译器的可移植性(portability)十分重要，此时设计的编译器既能改变原 代码（它涉及到重写前端），又能改变目标代码（它还涉及到重写后端）。在实际中，这是很难 做到的，而且称作可移植的编译器仍旧依赖于源语言和日标语言。其部分原因是程序设计语言 和机器构造的快速发展以及根本性的变化，但是有效地保持移植一个新的目标语言所需的信息 或使数据结构普遍地适合改变为一个新的源语言所需的信息却十分困难。然而人们不断分离前 端和后端的努力会带来更方便的可移植性。 (3)遍 编译器发现，在生成代码之前多次处理整个源程序很方便。这些重复就是遍(pss)。首 遍是从源中构造一个语法树或中间代码，在它之后的遍是由处理中间表示、向它增加信息、更
行步骤中生成中间文件。其中典型的是代码生成时需要反填（ b a c k p a t c h）地址。例如，当翻译 如下的条件语句时 if x = 0 then ... else ... 在知道e l s e部分代码的位置之前必须由文本跳到e l s e部分： CMP X, 0 JNE NEXT ;; location of NEXT not yet known N E X T : 通常，必须为N E X T的值留出一个空格，一旦知道该值后就会将该空格填上，利用临时文 件可以很容易地做到这一点。 1.5 编译器结构中的其他问题 可从许多不同的角度来观察编译器的结构。 1 . 3节已讲述了它的阶段——用来表示编译器的 逻辑结构。此外，还有其他一些可能的观点：编译器的物理结构、操作的顺序等等。由于编译 器的结构对其可靠性、有效性、可用性以及可维护性都有很大的影响，所以编译器的编写者应 熟悉尽可能多的有关编译器结构的观点。本节将考虑编译器结构的其他方面以及每一个观点是 如何应用的。 (1) 分析和综合 在这个观点中，已将分析源程序以计算其特性的编译器操作归为编译器的分析（ a n a l y s i s） 部分，而将生成翻译代码时所涉及到的操作称作编译器的综合（ s y n t h e s i s）部分。当然，词法 分析、语法分析和语义分析均属于分析部分，而代码生成却是综合部分。在优化步骤中，分析 和综合都有。分析正趋向于易懂和更具有数学性，而综合则要求更深的专业技术。因此，将分 析步骤和综合步骤两者区分开来以便发生变化时互不影响是很有用的。 (2) 前端和后端 本观点认为，将编译器分成了只依赖于源语言（前端（ front end））的操作和只依赖于目 标语言（后端（back end））的操作两部分。这与将其分成分析和综合两部分是类似的：扫描 程序、分析程序和语义分析程序是前端，代码生成器是后端。但是一些优化分析可以依赖于目 标语言，这样就是属于后端了，然而中间代码的综合却经常与目标语言无关，因此也就属于前 端了。在理想情况下，编译器被严格地分成这两部分，而中间表示则作为其间的交流媒介。 这一结构对于编译器的可移植性（ p o r t a b i l i t y）十分重要，此时设计的编译器既能改变源 代码（它涉及到重写前端），又能改变目标代码（它还涉及到重写后端）。在实际中，这是很难 做到的，而且称作可移植的编译器仍旧依赖于源语言和目标语言。其部分原因是程序设计语言 和机器构造的快速发展以及根本性的变化，但是有效地保持移植一个新的目标语言所需的信息 或使数据结构普遍地适合改变为一个新的源语言所需的信息却十分困难。然而人们不断分离前 端和后端的努力会带来更方便的可移植性。 (3) 遍 编译器发现，在生成代码之前多次处理整个源程序很方便。这些重复就是遍（ p a s s）。首 遍是从源中构造一个语法树或中间代码，在它之后的遍是由处理中间表示、向它增加信息、更 1 0 编译原理及实践 下载 前端 后端 源 代码 中间 代码 目标 代码