编译器工作原理(转)

逃离我推掉我的手 2022-10-02 07:44 248阅读 0赞

编译器，是将便于人编写，阅读，维护的高级[计算机][Link 1]语言翻译为计算机能识别，运行的低级机器语言的程序。编译器将[源程序][Link 2]（Source program）作为输入，翻译产生使用[目标语言][Link 3]（Target language）的等价程序。源程序一般为高级语言（High-level language），如Pascal，[C++][C]等，而目标语言则是汇编语言或目标机器的目标代码（Object code），有时也称作[机器代码（Machine code）。][Machine code]

一个现代编译器的主要工作流程如下：

源代码(sourcecode)→[预处理器][Link 4](preprocessor)→编译器(compiler)→[汇编][Link 5]程序(assembler)→目标代码(objectcode)→连接器(Linker)→可执行程序(executables)

编译语言与解释语言对比：

许多人将高级程序语言分为两类：编译型语言和解释型语言。然而，实际上，这些语言中的大多数既可用编译型实现也可用解释型实现，分类实际上反映的是那种[语言][Link 6]常见的实现方式。（但是，某些解释型语言，很难用编译型实现。比如那些允许在线代码更改的解释型语言。）

编译器是一种特殊的[程序][Link 7]，它可以把以特定编程语言写成的程序变为机器可以运行的[机器码][Link 8]。把一个程序写好，这时利用的环境是[文本编辑器][Link 9]。这时我程序把程序称为源程序。在此以后程序员可以运行相应的编译器，通过指定需要编译的文件的名称就可以把相应的源文件（通过一个复杂的过程）转化为机器码了。

## 编译器-工作原理 ##

翻译是从源代码（通常为高级语言）到能直接被计算机或 [虚拟机][Link 10] 执行的目标代码（通常为低级语言或机器言）。然而， 也存在从低级语言到高级语言的编译器，这类编译器中用来从由高级语言生成的低级语言代码重新生成高级语言代码的又被叫做[反编译器][Link 11]。也有从一种高级语言生成另一种高级语言的编译器，或者生成一种需要进一步处理的的中间代码的编译器（又叫级联）。

典型的编译器输出是由包含入口点的名字和地址以及外部调用（到不在这个目标文件中的[函数][Link 12]调用）的机器代码所组成的目标文件。一组目标文件，不必是同一编译器产生，但使用的编译器必需采用同样的输出格式，可以链接在一起并生成可以由用户直接执行的可执行程序。

![Center][]

## 编译器-种类概述 ##

编译器可以生成用来在与编译器本身所在的 [计算机][Link 1] 和操作系统（平台）相同的环境下运行的目标代码，这种编译器又叫做“ 本地”编译器。 另外，编译器也可以生成用来在其它平台上运行的目标代码，这种编译器又叫做 交叉编译器 。交叉编译器在生成新的硬件平台时非常有用。“ [源码][Link 13] 到源码编译器”是指用一种高级语言作为输入，输出也是高级语言的编译器。例如: 自动并行化编译器经常采用一种高级语言作为输入，转换其中的代码，并用并行代码注释对它进行注释（如OpenMP）或者用语言构造进行注释（如FORTRAN的DOALL [指令][Link 14] ）。

**预处理器：**预处理器（preprocessor）作用是通过代入预定义等程序段将源程序补充完整。

**编译器前端：**编译器前端（frontend），前端主要负责[解析][Link 15]（parse）输入的源程序，由词法分析器和语法分析器协同工作。词法分析器负责把源程序中的‘单词’（Token）找出来，语法分析器把这些分散的单词按预先定义好的语法组装成有意义的表达式，语句 ，函数等等。 例如“a = b + c；”前端词法分析器看到的是“a = b ； + c；”，语法分析器按定义的[语法][Link 16]，先把他们组装成表达式“b + c”，再组装成“a = b + c”的语句。 前端还负责语义（semantic checking）的检查，例如检测参与运算的变量是否是同一类型的，简单的错误处理。最终的结果常常是一个抽象的语法树（abstract syntax tree，或 [AST][]），这样后端可以在此基础上进一步优化，处理。

**编译器后端：**编译器后端（backend）编译器后端主要负责分析，优化中间代码（Intermediate representation）以及生成机器代码（Code Generation）。

编译器分析，优化，变型都可以分成两大类： 函数内（intraprocedural）还是函数之间（interprocedural）进行。很明显，函数间的分析，优化更准确，但需要更长的时间来完成。对于函数内的优化，有可以根据优化施加的范围分为，全局的（global）和局部的（local）。其中全局的优化是指该优化需要使用到全局的[数据流][Link 17]和[控制流][Link 18]信息。而局部的优化是指指导优化的信息来自基本快。

## 编译器-代码分析 ##

编译器分析（compiler analysis）的对象是前端生成并传递过来的中间代码，现代的优化型编译器（optimizing compiler）常常用好几种层次的中间[代码][Link 19]来表示程序，高层的中间代码（high level IR）接近输入的源程序的格式，与输入语言相关（language dependent），包含更多的全局性的信息，和源程序的结构；中层的中间代码（middle level IR）与输入语言无关，低层的中间代码(Low level IR)与机器语言类似。 不同的分析，优化发生在最适合的那一层中间代码上。

常见的编译分析有[函数][Link 12]调用树（call tree），控制流程图（Control flow graph），以及在此基础上的 变量定义－使用，使用－定义链（define-use/use-define or u-d/d-u chain），变量别名分析（alias analysis），指针分析（pointer analysis），数据依赖分析（data dependence analysis）等。

程序分析结果是编译器优化（compiler optimization）和程序变形（compiler transformation）的前提条件。常见的优化和变新有：函数内嵌（inlining），无用代码删除（Dead code elimination），标准化循环结构（loop normalization），[循环][Link 20]体展开（loop unrolling），循环体合并，分裂（loop fusion，loop fission），数组填充（array padding），等等。 优化和变形的目的是减少代码的长度，提高[内存][Link 21]（memory），[缓存][Link 22]（cache）的使用率，减少读写磁盘，访问网络数据的频率。更高级的优化甚至可以把序列化的代码（serial code）变成并行运算，多线程的[代码][Link 19]（parallelized，multi-threaded code）。

机器代码的生成是优化变型后的中间代码转换成机器指令的过程。现代编译器主要采用生成汇编代码（assembly code）的策略，而不直接生成二进制的目标代码（binary object code）。即使在代码生成阶段，高级编译器仍然要做很多分析，优化，变形的工作。例如如何分配[寄存器][Link 23]（register allocatioin），如何选择合适的机器指令（instruction selection），如何合并几句代码成一句等等。

## 编译器-历史回溯 ##

20世纪50年代， [IBM][] 的John Backus带领一个研究小组对FORTRAN语言及其编译器进行开发。但由于当时人们对编译理论了解不多，开发工作变得既复杂又艰苦。与此同时，Noam Chomsky开始了他对自然语言结构的研究。他的发现最终使得编译器的结构异常简单，甚至还带有了一些自动化。Chomsky的研究导致了根据语言文法的难易程度以及识别它们所需要的算法来对语言分类。正如现在所称的Chomsky架构（Chomsky Hierarchy），它包括了文法的四个层次：0型文法、1型文法、2型文法和3型文法，且其中的每一个都是其前者的特殊情况。2型文法（或上下文无关文法）被证明是程序设计语言中最有用的，而且今天它已代表着程序设计语言结构的标准方式。分析问题（parsing problem，用于上下文无关文法识别的有效算法）的研究是在60年代和70年代，它相当完善的解决了这个问题。现在它已是编译原理中的一个标准部分。

[有限状态自动机][Link 24]（Finite Automaton）和[正则表达式][Link 25]（Regular Expression）同上下文无关文法紧密相关，它们与Chomsky的3型文法相对应。对它们的研究与Chomsky的研究几乎同时开始，并且引出了表示程序设计语言的单词的符号方式。

人们接着又深化了生成有效目标代码的方法，这就是最初的编译器，它们被一直使用至今。人们通常将其称为优化技术（Optimization Technique），但因其从未真正地得到过被优化了的目标代码而仅仅改进了它的有效性，因此实际上应称作代码改进技术（Code Improvement Technique）。

当分析问题变得好懂起来时，人们就在开发程序上花费了很大的功夫来研究这一部分的编译器自动构造。这些程序最初被称为编译器的编译器（Compiler-compiler），但更确切地应称为分析程序生成器（Parser Generator），这是因为它们仅仅能够自动处理[编译][Link 26]的一部分。这些程序中最著名的是Yacc（Yet Another Compiler-compiler），它是由Steve Johnson在1975年为[Unix][]系统编写的。类似的，有限状态自动机的研究也发展了一种称为扫描程序生成器（Scanner Generator）的工具，Lex（与Yacc同时，由Mike Lesk为Unix系统开发）是这其中的佼佼者。

在70年代后期和80年代早期，大量的项目都贯注于编译器其它部分的生成自动化，这其中就包括了代码生成。这些尝试并未取得多少成功，这大概是因为操作太复杂而人们又对其不甚了解。

编译器设计发展包括：首先，编译器包括了更加复杂[算法][Link 27]的应用程序它用于推断或简化程序中的信息；这又与更为复杂的程序设计语言的发展结合在一起。其中典型的有用于函数语言编译的Hindley-Milner类型检查的统一算法。其次，编译器已越来越成为基于窗口的交互开发环境（Interactive Development Environment，IDE）的一部分，它包括了编辑器、连接程序、调试程序以及项目管理程序。这样的[IDE][]标准并没有多少，但是对标准的窗口环境进行开发已成为方向。另一方面，尽管近年来在编译原理领域进行了大量的研究，但是基本的编译器设计原理在近20年中都没有多大的改变，它现在正迅速地成为计算机科学课程中的中心环节。

在90年代，作为[GNU][]项目或其它开放源代码项目的一部分，许多免费编译器和编译器开发工具被开发出来。这些工具可用来编译所有的计算机程序语言。它们中的一些项目被认为是高质量的，而且对现代编译理论感性趣的人可以很容易的得到它们的免费源代码。

大约在1999年，[SGI][]公布了他们的一个工业化的并行化优化编译器[Pro64][]的源代码，后被全世界多个编译器研究小组用来做研究平台，并命名为Open64。Open64的设计结构好，分析优化全面，是编译器高级研究的理想平台。

## 编译器-工作方法 ##

首先编译器进行语法分析，也就是要把那些 [字符串][Link 28] 分离出来。

然后进行语义分析，就是把各个由语法分析分析出的语法单元的意义搞清楚。

最后生成的是目标文件，也称为[obj][]文件。

再经过链接器的链接就可以生成最后的可执行代码了。

有些时候需要把多个文件产生的目标文件进行链接，产生最后的代码。这一过程称为[交叉链接][Link 29]。

![Center 1][]

转自：[http://www.cnblogs.com/zihuatanejo/articles/1390600.html][http_www.cnblogs.com_zihuatanejo_articles_1390600.html]

[Link 1]: http://www.hudong.com/wiki/%E8%AE%A1%E7%AE%97%E6%9C%BA
[Link 2]: http://www.hudong.com/wiki/%E6%BA%90%E7%A8%8B%E5%BA%8F
[Link 3]: http://www.hudong.com/wiki/%E7%9B%AE%E6%A0%87%E8%AF%AD%E8%A8%80
[C]: http://www.hudong.com/wiki/C++
[Machine code]: http://www.hudong.com/wiki/%E6%9C%BA%E5%99%A8%E4%BB%A3%E7%A0%81
[Link 4]: http://www.hudong.com/wiki/%E9%A2%84%E5%A4%84%E7%90%86%E5%99%A8
[Link 5]: http://www.hudong.com/wiki/%E6%B1%87%E7%BC%96
[Link 6]: http://www.hudong.com/wiki/%E8%AF%AD%E8%A8%80
[Link 7]: http://www.hudong.com/wiki/%E7%A8%8B%E5%BA%8F
[Link 8]: http://www.hudong.com/wiki/%E6%9C%BA%E5%99%A8%E7%A0%81
[Link 9]: http://www.hudong.com/wiki/%E6%96%87%E6%9C%AC%E7%BC%96%E8%BE%91%E5%99%A8
[Link 10]: http://www.hudong.com/wiki/%E8%99%9A%E6%8B%9F%E6%9C%BA
[Link 11]: http://www.hudong.com/wiki/%E5%8F%8D%E7%BC%96%E8%AF%91%E5%99%A8
[Link 12]: http://www.hudong.com/wiki/%E5%87%BD%E6%95%B0
[Center]: /images/20220113/6452b5d074d44651913bab612daee20d.png
[Link 13]: http://www.hudong.com/wiki/%E6%BA%90%E7%A0%81
[Link 14]: http://www.hudong.com/wiki/%E6%8C%87%E4%BB%A4
[Link 15]: http://www.hudong.com/wiki/%E8%A7%A3%E6%9E%90
[Link 16]: http://www.hudong.com/wiki/%E8%AF%AD%E6%B3%95
[AST]: http://www.hudong.com/wiki/AST
[Link 17]: http://www.hudong.com/wiki/%E6%95%B0%E6%8D%AE%E6%B5%81
[Link 18]: http://www.hudong.com/wiki/%E6%8E%A7%E5%88%B6%E6%B5%81
[Link 19]: http://www.hudong.com/wiki/%E4%BB%A3%E7%A0%81
[Link 20]: http://www.hudong.com/wiki/%E5%BE%AA%E7%8E%AF
[Link 21]: http://www.hudong.com/wiki/%E5%86%85%E5%AD%98
[Link 22]: http://www.hudong.com/wiki/%E7%BC%93%E5%AD%98
[Link 23]: http://www.hudong.com/wiki/%E5%AF%84%E5%AD%98%E5%99%A8
[IBM]: http://www.hudong.com/wiki/IBM
[Link 24]: http://www.hudong.com/wiki/%E6%9C%89%E9%99%90%E7%8A%B6%E6%80%81%E8%87%AA%E5%8A%A8%E6%9C%BA
[Link 25]: http://www.hudong.com/wiki/%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F
[Link 26]: http://www.hudong.com/wiki/%E7%BC%96%E8%AF%91
[Unix]: http://www.hudong.com/wiki/Unix
[Link 27]: http://www.hudong.com/wiki/%E7%AE%97%E6%B3%95
[IDE]: http://www.hudong.com/wiki/IDE
[GNU]: http://www.hudong.com/wiki/GNU
[SGI]: http://www.hudong.com/wiki/SGI
[Pro64]: http://www.hudong.com/wiki/Pro64
[Link 28]: http://www.hudong.com/wiki/%E5%AD%97%E7%AC%A6%E4%B8%B2
[obj]: http://www.hudong.com/wiki/obj
[Link 29]: http://www.hudong.com/wiki/%E4%BA%A4%E5%8F%89%E9%93%BE%E6%8E%A5
[Center 1]: /images/20220113/ecb85d2dffb44aadbbad58e08b1a9f4f.png
[http_www.cnblogs.com_zihuatanejo_articles_1390600.html]: http://www.cnblogs.com/zihuatanejo/articles/1390600.html