编译原理-龙书2

1.2 编译器的结构

分析（analysis）

综合（synthesis）

一个编译器的各个步骤

1.2.1 词法分析

编译器的第一个步骤称为词法分析(lexical analysis)或扫描( scanning)。词法分析器读人组成源程序的字符流，并且将它们组织成为有意义的词素(lexeme)的序列。

1.2.2 语法分析

语法分析器使用由词法分析器生成的各个词法单元的第-一个分量来创建树形的中间表示。该中间表示给出了词法分析产生的词法单元流的语法结构。一个常用的表示方法是语法树( syntax tree), 树中的每个内部结点表示一个运算，而该结点的子结点表示该运算的分量。在图1-7中，词法单元流(1.2)对应的语法树被显示为语法分析器的输出。

1.2.3 语义分析

语义分析器(semanticanalyzer)使用语法树和符号表中的信息来检查源程序是否和语言定义的语义一-致。它同时也收集类型信息，并把这些信息存放在语法树或符号表中，以便在随后的中间代码生成过程中使用。

1.2.4 中间代码的生成

在把一个源程序翻译成目标代码的过程中，一个编译器可能构造出一个或多个中间表示。这些中间表示可以有多种形式。语法树是一种中间表示形式，它们通常在语法分析和语义分析中使用。

1.2.5 代码优化

机器无关的代码优化步骤试图改进中间代码，以便生成更好的目标代码。“更好”通常意味着更快,但是也可能会有其他目标，如更短的或能耗更低的目标代码。

1.2.6 代码生成

代码生成器以源程序的中间表示形式作为输人，并把它映射到目标语言。如果目标语言是机器代码,那么就必须为程序使用的每个变量选择寄存器或内存位置。然后，中间指令被翻译成为能够完成相同任务的机器指令序列。代码生成的一个至关重要的方面是合理分配寄存器以存放变量的值。

 1.2.7符号表管理

编译器的重要功能之--是记录源程序中使用的变量的名字，并收集和每个名字的各种属性有关的信息。这些属性可以提供-一个名字的存储分配、它的类型、作用域(即在程序的哪些地方可以使用这个名字的值)等信息。对于过程名字，这些信息还包括:它的参数数量和类型、每个参数的传递方法(比如传值或传引用)以及返回类型。

1.2. 8 将多个步骤组合成趟

前面关于步骤的讨论讲的是-一个编译器的逻辑组织方式。在-一个特定的实现中，多个步骤的活动可以被组合成一趟( pass)。每趟读人一个输人文件并产生-一个输出文件。比如，前端步骤中的词法分析、语法分析、语义分析，以及中间代码生成可以被组合在一.起成为- - 趟。代码优化可以作为一个可选的趟。然后可以有一个为特定目标机生成代码的后端趟。

1.2.9 编译器构造工具

这些工具使用专用的语言来描述和实现特定的组件，其中的很多工具使用了相当复杂的算法。其中最成功的工具都能够隐藏生成算法的细节，并且它们生成的组件易于和编译器的其他部分相集成。

一些常用的编译器构造工具包括:

1)语法分析器的生成器:可以根据一个程序设计语言的语法描述自动生成语法分析器。
2)扫描器的生成器:可以根据一个语言的语法单元的正则表达式描述生成词法分析器。
3)语法制导的翻译引擎:可以生成一组用于遍历分析树并生成中间代码的例程。
4)代码生成器的生成器:依据一组关于如何把中间语言的每个运算翻译成为目标机上的机器语言的规则，生成一个代码生成器。
5)数据流分析引擎:可以帮助收集数据流信息，即程序中的值如何从程序的一个部分传递到另一部分。 数据流分析是代码优化的-一个重要部分。
6)编译器构造工具集:提供了可用于构造编译器的不同阶段的例程的完整集合。

1.3 程序设计语言的发展历程

第一台电子计算机出现在20世纪40年代。它使用由0、1序列组成的机器语言编程，这个序列明确地告诉计算机以什么样的顺序执行哪些运算。运算本身也是很低层的:把数据从一个位置移动到另一个位置，把两个寄存器中的值相加，比较两个值，等等。不用说，这种编程速度慢且枯燥，而且容易出错。写出的程序也是难以理解和修改的。

1.3. 1 走向高级程序设计语言

当前有几千种程序设计语言。可以通过不同的方式对这些语言进行分类。方式之一是通过语言的代来分类。第一代语言是机器语言，第二代语言是汇编语言，而第三代语言是Fortran、Cobol、Lisp、C、C++、C#及Java这样的高级程序设计语言。第四代语言是为特定应用设计的语言，比如用于生成报告的NOMAD,用于数据库查询的SQL和用于文本排版的Postscript。术语第五代语言指的是基于逻辑和约束的语言，比如Prolog和OPS5。

1.3.2 对编译器的影响

40年代以来，计算机体系结构也有了很大的发展。编译器的设计者不仅需要跟踪新的语言特征，还需要设计出新的翻译算法，以便尽可能地利用新硬件的能力。

1.4 构建一个编译器的相关科学

编译器的设计中有很多通过数学方法抽象出问题本质从而解决现实世界中复杂问题的完美例子。这些例子可以被用来说明如何使用抽象方法来解决问题:接受一个问题，写出抓住了问题的关键特性的数学抽象表示，并用数学技术来解决它。
问题的表达必须根植于对计算机程序特性的深入理解，而解决方法必须使用经验来验证和精化。

1.4.1 编译器设计和实现中的建模

对编译器的研究主要是有关如何设计正确的数学模型和选择正确算法的研究。设计和选择时，还需要考虑到对通用性及功能的要求与简单性及有效性之间的平衡。最基本的数学模型是我们将在第3章介绍的有穷状态自动机和正则表达式。这些模型可以用于描述程序的词法单位(关键字、标识符等)以及描述被编译器用来识别这些单位的算法。最基本的模型中还包括上下文无关文法，它用于描述程序设计语言的语法结构，比如嵌套的括号和控制结构。我们将在第4章研究文法。类似地，树形结构是表示程序结构以及程序到目标代码的翻译方法的重要模型。我们将在第5章介绍这一概念。

 1.4.2 代码优化的科学

在编译器设计中，术语“优化”是指编译器为了生成比浅显直观的代码更加高效的代码而做的工作。“优化”这个词并不恰当,因为没有办法保证--个编译器生成的代码比完成相同任务的任何其他代码更快，或至少一样快。

1.5 编译技术的应用

编译器设计并不只是关于编译器的。很多人用到了在学校里研究编译器时学到的技术，但是严格地说，它们从没有为一个主流的程序设计语言编写过一个编译器(甚至其中的一部分)。编译器技术还有其他重要用途。另外，编译器设计影响了计算机科学中的其他领域。在本节,我们将回顾和编译技术有关的最重要的互动和应用。

1.5.1 高级程序设计语言的实现

一个高级程序设计语言定义了一个编程抽象:程序员使用这个语言表达算法，而编译器必须把这个程序翻译成目标语言。总的来说，用高级程序设计语言编程比较容易，但是比较低效,也就是说，目标程序运行较慢。使用低级程序设计语言的程序员能够更多地控制-一个计算过程，因此从原则上讲，可以产生更加高效的代码。遗憾的是,低级程序比较难编写，而且更糟糕的是可移植性较差，更容易出错，而且更加难以维护。优化编译器包括了提高所生成代码性能的技术，因此弥补了因高层次抽象而引人的低效率。

1.5.2 针对计算机体系结构的优化