程序可以运行之前，它首先需要被翻译成一种能被计算机执行的形式。
简单来讲，一个编译器就是一个程序，他可以阅读某一种语言(源语言)编写的程序，并把该程序翻译成为一个等价的、用另一种语言(目标语言)编写的程序，参见图 1-1。编译器的重要任务之一是报告它在翻译过程中发现的源程序中的错误。
图 1-1 一个编译器
如果目标程序是一个可执行的机器语言程序，那么它就可以被用户调用，处理输入并产生输出。参见图 1-2. 图 1-2 运行目标程序
解释器是另外一种常见的语言处理器。它并不通过翻译的方式生成目标程序。从用户的角度看，解释器直接利用用户提供的输入执行源程序中指定的操作。参见图 1-3. 图 1-3 一个解释器
再把用户输入映射成为输出的过程中，由一个编译器产生的机器语言目标程序通常比一个解释器快很多。然而，解释器的错误诊断效果通常比编译器更好，因为它逐个语句地执行源程序。
Java语言处理器结合了编译和解释过程。如图1-4所示。一个Java源程序首先被编译成一个成为字节码的中间表示形式。然后由一个虚拟机对得到的字节码加以解释运行。这样安排的好处之一是在一台机器上编译得到的字节码可以在另一台机器上解释执行。通过网络就可以完成机器之间的迁移。 为了更快的完成输入到输出的处理，有些被称为即时编译器的Java编译器在运行中间程序处理输入的前一刻把字节码翻译成为机器语言，然后再执行程序。 图 1-4 一个混合编译器
如图 1-5所示，除了编译器之外，创建一个可执行的目标程序还需要一些其他程序。一个程序可能被分割成为多个模块，并存放于独立的文件中。把源程序聚合在一起的任务有时会有一个被称为预处理器的程序独立完成。预处理器还负责把那些称为宏的缩写形式转换为源语言的语句。 然后，经过预处理器的源程序作为输入传递给一个编译器。编译器可能产生一个汇编语言程序作为其输出，因为汇编语言比较容易输出和调试。接着，这个汇编语言程序由称为汇编器的程序进行处理，并生成可重定位的机器代码。 大型程序经常被分成多个部分进行编译，因此，可重定位的机器代码有必要和其他可重定位的目标代码以及库文件连接到一起，形成真正在机器上运行的代码。一个文件中的代码可能指向另一个文件中的位置。最后，加载器把所有的可执行目标文件放在内存中执行。 图 1-5 一个语言处理系统
编译器映射过程 = 分析部分 + 综合部分
分析部分把源程序分解成为多个组成要素，并在这些要素之上加上语法结构。然后，它使用这个结构来创建该源程序的一个中间表示。如果分析部分检查出源程序没有按照正确的语法构成，或者语义上不一致，它就必须提供有用的信息，使得用户可以按此进行改正。分析部分还会收集有关源程序的信息，并把信息存放在一个称为符号表的数据结构中。符号表将和中间表示形式一起传送给综合部分。综合部分根据中间表示和符号表中的信息来构造用户期待的目标程序。分析部分经常被称为编译器的前端，而综合部分称为后端。 图 1-6 一个编译器的各个步骤 两个优化步骤之一可以被忽略。编译器的第一个步骤称为语法分析或扫描。词法分析器读入组成源程序的字符流，并且将它们组织称为有意义的词素的序列。对于每个词素，词法分析器产生如下形式的词法单元作为输出：
<token-name , attribute-value>这个词法单元被传送给向下一个步骤，即语法分析。在这个词法单元中，第一个分量token-name是一个由语法分析步骤使用的抽象符号，而第二个分量attribute-value指向符号表中关于这个词法单元的条目。符号表条目的信息会被语义分析和代码生成步骤使用。
编译器的第二个步骤称为语法分析或解析。语法分析器使用由词法分析器生成的各个词法单元的第一个分量来创建树形的中间表示。该中间表示给出了词法分析产生的词法单元流的语法结构。一个常用的表示方法是语法树，树中的每个内部节点表示一个运算，而该节点的子节点表示该运算的分量。在图 1-7中，词法单元流对应的语法树被显示为语法分析器的输出。
语义分析器使用语法树和符号表中的信息来检查源程序是否和语言定义的语义一致。它同时也收集类型信息，并把这些信息存放在语法树或符号表中，以便在随后的中间代码生成过程中使用。 语义分析的一个重要部分就是类型检查。编译器检查每个运算符是否具有匹配的运算分量。 程序设计语言可能允许某些类型转换，这被称为自动类型转换。
源程序翻译到目标程序的过程中，编译器可能会构造出一个或者多个中间表示。这些中间形式具有多种表现形式。语法树是中间表示形式的一种，它通常在语法分析和语义分析中使用。 在源程序的语法分析和语义分析完成之后，很多编译器生成一个明确的低级的或类机器语言的中间表示。我们可以把这个表示看作是某个抽象机器的程序。该中间表示应该具有两个重要的性质：他应该易于生成，且能够被轻松地翻译成目标机器上的语言
一个简单直接的算法会生成中间代码。他为由语义分析器得到的树形中间表示中的每个运算符都使用一个指令。 使用一个简单地中间代码生成算法，然后在进行代码优化步骤是生成优质目标代码的一个合理方法。 不同的编译器所做的代码优化工作量相差很大。那些优化工作做得最多的编译器，即所谓的**“优化编译器”**，会在优化阶段花相当多的时间。有些简单的优化方法可以极大地提高目标程序的运行效率而不会过多降低编译的速度。
代码生成器以源程序的中间形式作为输入，并把它映射到目标语言。如果目标语言是机器代码，那么就必须为程序使用的每个变量选择寄存器或内存位置。然后，中间指令被翻译成为能够完成相同任务的机器指令序列。代码生成的一个至关重要的方面是合理分配寄存器以存放变量的值。 对源程序中的标识符进行存储分配是个重要的问题。
编译器的重要功能之一是**记录源程序中使用的变量的名字，并收集和每个名字的各种属性有关的信息。**这些属性可以提供一个名字的存储分配、它的类型、作用域等信息。对于过程名字，这些信息还包括：它的参数数量、每个参数的传递方法以及返回类型。 符号表数据结构为每个变量名字创建了一个记录条目。 记录的字段就是名字的各个属性。整数据结构应该允许编译器迅速查找到每个名字的记录，并向记录中快速存放和获取记录中的数据。
就是将前几个步骤组合起来**，称之为趟。代码优化可以作为一个可选的趟**。然后可以有一个为特定目标机生成代码的后端趟。 我们可以将编译器的前端和后端进行分离，将不同的前端和后端进行结合，就可以为不同的源语言建立在不同目标机上的编译器。 有些编译器集合是围绕一组精心设计的中间表示形式而创建的，这些中间表示形式使得我们可以把特定语言的前端和特定目标机的后端相结合。
一些常用的编译器构造工具包括：
语法分析器的生成器： 可以根据一个程序设计语言的语法描述自动生成语法分析器。扫描器的生成器： 可以根据一个语言的语法单元的正则表达式描述生成词法分析器。语法制导的翻译引擎： 可以生成一组用于遍历分析树并生成中间代码的例程。代码生成器的生成器： 依据一组关于如何把中间语言的每个运算翻译成目标机上的机器语言的规则，生成一个代码生成器。数据流分析引擎： 可以帮助收集数据流信息，即程序中的值如何从程序的一个部分传递到另一部分。数据流分析是代码优化的一个重要部分。编译器的构造工具集： 提供了可用于构造编译器的不同阶段的例程的完整集合。电子计算机用机器语言编程，运算低级，编程速度慢，代码难以理解和修改。
通过语言的代分类： 第一代语言是机器语言，第二代语言是汇编语言，而第三代语言是Fortran，Cobol，Lisp，C，C++，C#及Java这样的高级程序设计语言。第四代语言是为特定应用程序设计的语言，比如用于生成报告的NOMAD，用于数据库查询的SQL和用于文本排版的Postscript。术语第五代语言指的是基于逻辑和约束的语言，比如Prolog和OPS5. 另一种语言分类方式把程序中指明如何完成一个计算任务的语言的称为强制式语言，而把程序中指明要进行哪些计算的语言称为声明式语言。 面向对象语言和脚本语言。
程序设计语言的设计和编译器是紧密相关的，程序设计语言的发展向编译器的设计者提出了新的要求。 他们必须设计相应的算法和表示方式来翻译和支持新的语言特征。 编译器的设计者不仅需要跟踪新的语言特性，还需要设计出新的翻译算法，以便尽可能地利用新硬件的能力。 通过降低用高级语言程序的执行开销，编译器还可以推动这些高级语言的使用。
编译器必须接受所有遵循语言规范的源程序。 源程序的集合是无穷的，而程序可能包含几百万行代码。在翻译一个源程序的过程中，编译器所做的任何翻译工作都不能改变被编译源程序的含义。 编译器设计者的工作不仅会影响到他们创建的编译器，还会影响到他们所创建的编译器所编译的全部内容。
对编译器的研究主要是有关如何设计正确的数学模型和选择正确算法的研究。 模型举例：
有穷状态机，正则表达式上下无关文法树形结构对于优化一词没有定性的描述，随着处理器体系结构变得更加复杂，也就有了更多改进代码执行方式的机会。 之所以更加重要，是因为巨型并发计算机要求实质性的优化，否则它们的性能会呈指数级地下降。 编译器优化必须满足下面的设计目标：
优化必须是正确的，也就是说，不能改变被编译程序的含义。优化必须能改善很多程序的性能。优化所需的时间必须保持在合理的范围内。所需要的工程方面的工作必须是可管理的。编译器设计并不只是关于编译器的。
一个高级程序设计语言定义了一个编程抽象：程序员使用这个语言表达算法，而编译器必须把这个程序翻译成目标语言。 优化编译器包括了提高所生成代码性能的技术，因此弥补了因高层次抽象而引入的低效率。
C语言的 register 关键字是编译器技术和语言发展互动的一个较早的例子。C语言最初创立时，人们认为有必要让程序员来控制哪个程序变量应该存放在寄存器中。当有效的寄存器分配技术出现以后，这个控制变得没有必要了，大多数现代的程序不再使用这个语言特性。
实际上，使用关键字 register 的程序还可能损失效率，因为寄存器分配是一类很低层次的问题，程序员常常不是最好的判断这类问题的人选，寄存器分配的最优选择很大程度上取决于一个机器的体系结构的特点。把低层次资源管理的决策，比如寄存器分配，写死在程序中反而有可能损害性能。当运行程序的计算机有别于当初设定的目标机时更是如此。
在实践中，所有的通用程序设计语言，包括C，Fortran和Cobol，都支持用户定义的聚合类型(如数组和结构)和高级控制流(比如循环和过程调用)。如果我们仅仅把每个高级结构和数据存取运算直接翻译成为机器代码，得到的代码将会非常低效。编译器优化的一个组成部分称为数据流优化，它可以对程序的数据流进行分析，并消除这些构造之间的冗余。
这两种特性都可以使得程序更加模块化和易于维护。面向对象程序和用很多其他语言编写的程序之间的不同在于它们由多得多的(但是较小)过程(方法)组成。因此，编译器优化技术必须能够很好地跨越源程序中的过程边界进行优化。过程内联技术(即把一个过程调用替换为相应的过程体)在这里是非常有用的。人们还开发了可以加速虚拟方法分发的优化技术。 Java用来支持可移植和可移动的代码。
几乎所有的高性能系统都利用了两种技术：并行和内存层次模型 1️⃣并行性 所有的现代微处理器都采用了指令集的并行性，这种并行性可以对程序员隐藏起来。硬件动态地检测顺序指令流之间的依赖关系，并且在有可能的时候并行的发出指令。 指令级的并行也显示的出现在指令集中。所有高性能通用微处理器还包含了可以同时对一个向量中的所有数据进行运算的指令。 程序员可以为多处理器编写多线程的代码，也可以通过编译器从传统的顺序程序自动生成并行代码。 2️⃣内存层次模型 并行性和内存层次结构的存在都会提高一个机器的潜在性能。但是，他们必须被编译器有效的利用才能够真正为一个应用提供高性能计算。 内存层次机构可已在所有的机器中找到。 和寄存器必须由软件明确管理不同，高速缓存和物理内存是对指令集合隐藏的，并由硬件管理。 我们可以改变数据的布局或数据访问代码的顺序来提高内存层次结构的效率。我们也可以通过改变代码的布局来提高指令高速缓存的效率。
计算机体系结构设计的早期， 编译器是在机器建造好之后在开发的。 现在，高级程序设计语言是一种规范，决定一个计算机系统性能的不是它的原始速度，还包括编译器能够以何种态度利用其特性。现代计算机体系结构的开发中， 编译器在处理器设计阶段就进行开发， 然后编译得到代码并运行于模拟机上。这些代码被用来评价提议的体系结构特征。 1️⃣RISC 精简指令集计算机，在发明RISC之前，趋势是开发指令集越来越复杂，以使得汇编程序变得更容易。 编译器优化经常能够消除复杂指令之间的冗余，把这些指令削减为少量较简单的运算。 2️⃣专用体系结构 由于规模经济效用，通用处理器的体系结构具有趋同性。而专用应用的处理器则与此相反，体现出了计算机体系结构的多样性。
我们通常把编译看作是从一个高级语言到机器语言的翻译过程。同样的技术也可以应用到不同种类的语言之间的翻译。 1️⃣二进制翻译 编译器技术可以用于把一个机器的二进制代码翻译成另一个机器的二进制代码，使在一个机器上运行原本为另一个指令集编译的程序。 2️⃣硬件合成 不仅仅大部分软件是用高级语言描述的，连大部分硬件设计也是使用高级硬件描述语言描述的。 硬件设计通常是在寄存器传输层RTL上描述的。在这个层中，变量代表寄存器，而表达式代表组合逻辑。硬件合成工具RTL描述自动翻译成门电路，而门电路在被翻译成晶体管，最后生成一个物理布局。 3️⃣数据查询解释器 除了描述软件和硬件，语言在很多应用中都是有用的。查询语言**(特别是SQL语言)** 被用来搜索数据库。数据库查询由包含了关系和布尔运算符的断言组成。它们可以被解释，也可以编译为代码，以便在一个数据库中搜索满足这个断言的记录。 4️⃣编译然后模拟 模拟是很多科学和工程领域内使用的通用技术。它用来理解一个现象或者验证一个设计。 模拟器的输入通常包括设计描述和某次特定模拟运行的具体输入参数。模拟可能会非常昂贵。 另一个放法不需要写一个模拟器来解释这些设计。他对设计进行编译并生成能过在机器上直接模拟特定设计的机器代码。
程序中可能会出现错误，其中有些可能是致命的。 一个很有意思且很有前景的辅助性方法是通过数据流分析技术静态地定位错误(即在程序运行之前)。数据流分析可以在所有可能执行路径上找到错误，而不是像程序测试的时候所做的那样，仅仅是在那些由输入数据组合执行的路径上找错误。
找到程序的所有错误是不可判定问题。优化器必须是保守的，在任何情况下都不能改变程序的语义。 1️⃣类型检查 它可以被用于捕捉程序中的不一致性。也可用来捕捉某种安全漏洞。 2️⃣边界检查 用来消除程序中的冗余区间检查的数据流分析技术也可以用来定位缓冲区溢出错误。 而最大的区别在于，没能消除某个区间检查仅仅会导致很小的额外运行时刻开销，而没有指出一个潜在的缓冲区溢出错误却可能危及系统的安全性。 3️⃣内存管理工具 垃圾收集机制是在效率和易编程及软件可靠性之间进行折中处理的另一个极好的例子。
在为一个语言设计一个编译器时，我们所面对的最重要的问题之一就是编译器能够对一个程序做出哪些判定。 如果一个语言使用的策略支持编译器静态决定某个问题，那么我们就说这个语言使用了一个静态策略，或者说这个问题可以在编译时刻决定。另一方面，一个只允许在运行程序的时候做出决定的策略被称为动态策略，或者被认为需要在运行时刻做出决定。 作用域 = 静态作用域 + 动态作用域 静态作用域： x的一个声明的作用域是指程序的一个区域，在其中对x的使用都指向这个声明。仅通过阅读程序就可以确定一个声明的作用域。 动态作用域： 当程运行时，同一个对x的使用会指向x的几个生命中的某一个。
在Java中，一个变量是用于存放数据值的某个内存位置的名字。这里，“static”指的并不是变量的作用域，而是编译器确定用于存放被声明变量的内存位置的能力。
public static int x;使得x成为一个类变量，也就是说不管创建了多少个这个类的对象，只存在一个x的拷贝。此外，编译器可以确定内存中的被用于存放整数x的位置。反过来，如果这个声明中省略了“static”，那么这个类的每个对象都会有它自己的用于存放x的位置，编译器没办法在运行程序之前预先确定所有这些位置。
名字和内存(存储)位置的关联，及之后和值的关联可以用两个映射来描述。
1️⃣环境是一个从名字到存储位置的映射。因为变量就是指内存位置，我们可以换一种方法，把环境定义为从名字刀变量的映射。 2️⃣状态是一个 从内存位置到它们的值的映射。
环境的改变需要遵守语言的作用与规则。
环境和状态映射是动态的。 1️⃣名字到位置的静态绑定与动态绑定。大部分从名字到位置的绑定是动态的。但某些声明(例如全局变量)可以在编译器生成目标代码时一劳永逸地分配一个存储位置。 2️⃣从位置到值的静态绑定与动态绑定。一般来说，位置到值的绑定也是动态的，因为我们无法在运行一个程序之前指出一个位置上的值。被声明的常量是一个例外。
#define ARRAYSIZE 1000把名字 ARRAYSIZE 静态绑定为值000.我们看到这个语句就可以知道这个绑定关系，并且知道在程序运行时刻这个绑定不可能改变。
C语言的作用域规则是基于程序结构的，一个声明的作用域由该声明在程序中出现的位置隐含地决定。 稍后出现的语言，比如C++、Java和C#，也通过诸如public、private、protected等关键字的使用，提供了队作用域的明确控制。
标识符是一个字符串，通常由字母和数字组成。所有的标识符都是名字，但不是所有的名字都是标识符。名字也可能是一个表达式。比如名字x.y可以表示x所指的一个结构中的字段y。这里，x和y是标识符，而x.y是一个名字。想x.y这样的复合名字被称为受限名字。 变量指向存储中的某个特定的位置。同一个标识符被声明多次是很常见的事情，每一个这样的声明引入一个新的变量。即使每个标识符只被声明一起，一个递归过程中的局部标识符将在不同的时刻指向不同的存储位置。
静态作用域策略： 1️⃣一个C程序由一个顶层的变量和函数声明的序列组成。 2️⃣函数内部可以声明变量，变量包括局部变量和参数。每个这样的声明的作用域被限制1在它们所出现的那个函数内。 3️⃣名字x的一个顶层声明的作用域包括其后的所有程序。但是如果一个函数中也有一个x的声明，那么函数中的那些语句就不在这个顶层声明的作用域当中。 块的语法： 1️⃣块是一种语句。块可以出现在其他类型的语句(比如赋值语句)所能够出现的任何地方。 2️⃣一个块包含了一个声明的序列，然后再跟着一个语句序列。这些生命和语句用一对括号包围起来。 注意，这个语法允许一个块嵌套在另一个块内。这个嵌套特性称为块结构。C族语言都是块结构，但是不能在一个函数内部定义另一个函数。
通过public、private和protected这样的关键字的使用，面向对象语言提供了对超类中的成员名字的显示访问控制。这些关键字通过限制访问来支持封装。
声明告诉我们事物的类型，而定义告诉我们它们的值。因此int i 是一个i的声明，而 i = 1 是i的一个定义(定值). 我们经常会看到在一个文件中定义了一个C语言的函数，然后在其他使用这个函数的文件中声明这个函数。
对于一个名字x的使用指向的是最近被调用但还没有终止且声明了x的过程中的这个说明。 例子：C预处理器中的宏扩展，以及面向对象编程中的方法解析。
#define a (x+1) int x = 2; void b(){ int x = 1; printf("%d\n",a);} void c(){ printf("%d\n",a)} void main(){b();c();} //一个其名字的作用域必须动态确定的宏在该程序中，标识符a是一个代表了表达式(x+1)的宏。但x到底是什么呢？我们不能够静态地（也就是说通过程序文本）解析x。 动态作用域解析对多态过程是必不可少的。所谓多态过程是对于同一个名字根据参数类型具有两个或多个定义的过程。
从某种意义上说，动态规则处理时间的方式类似于静态作用域处理空间的方式。静态规则让我们寻找的声明位于最内层、包含变量使用位置的单元（块）中；而动态规则则让我们寻找的声明位于最内层、包含了变量使用时间的单元（过程调用）中。
考虑实在参数（在调用过程时使用的参数）是如何与形式参数（在过程定义中使用的参数）关联起来的。 1️⃣值调用 在值调用中，会对实在参数区求值（如果它是表达式）或拷贝（如果它是变量）。这些值被放在属于被调用过程的相应形式参数的内存位置上。 C、C++和Java中作为参数传递的数组名字实际上向被调用过程传递了一个指向该数组本身的指针或引用。 Java中的很多变量实际上是对它们所代表的事物的引用，或者说指针。虽然Java只使用值传递，但只要我们把一个对象的名字传递给一个被调用过程，那个过程收到的值实际上是这个对象的指针。因此，被调用过程是可以改变这个对象本身的值。 2️⃣引用调用 在引用调用中，实在参数的地址作为相应的形式参数的值被传递给被调用者。 像Java这样的语言解决数组、字符串和其他对象的参数传递问题的方法是仅仅复制这些对象的引用。结果是，Java运行时就好像它对所有不是基本类型（比如整数。实数等）的参数都使用了引用调用。 3️⃣名调用 它要求被调用者的运行方式好像是用实在参数以字面的方式替换了被调用者的代码中的形式参数一样。这么做就好像形式参数是一个代表了实在参数的宏。 当实在参数是一个表达式而不是一个变量时，会发生一些和直觉不符的问题。这也是今天不在采用这种机制的原因之一。
别名对于程序的优化有很大影响。 引用调用或者其他类似的办法，比如像Java中那样把对象的引用当做值传递，会引起一个有趣的结果。 有可能两种形式参数指向同一个位置，这样的变量称为另一个变量的别名。结果是，任意两个看起来从两个不同的形式参数中获得值的变量也可能变成对方的别名。
