基本概念
编译器是将一种语言翻译为另一种语言的计算机程序。编译器将源程序(source language) 编写的程序作为输入,而产生用目标语言(target language )编写的等价程序。通常地,源程序为高级语言(high-level language ),如C或C + + ,而目标语言则是目标机器的目标代码 (object code,有时也称作机器代码(machine code )),也就是写在计算机机器指令中的用于运行的代码。这一过程可以表示为:源程序→编译器 →目标程序
发展历程
在20世纪40年代,由于冯·诺伊曼在存储-程序计算机方面的先锋作用,编写一串代码或程序已成必要,这 编译原理实验程序样计算机就可以执行所需的计算。开始时,这些程序都是用机器语言 (machine language )编写的。机器语言就是表示机器实际操作的数字代码,例如:C7 06 0000 0002 表示在IBM PC 上使用的Intel 8x86处理器将数字2移至地址0 0 0 0 (16进制)的指令。
但编写这样的代码是十分费时和乏味的,这种代码形式很快就被汇编语言(assembly language )代替了。在汇编语言中,都是以符号形式给出指令和存储地址的。例如,汇编语言指令 MOV X, 2 就与前面的机器指令等价(假设符号存储地址X是0 0 0 0 )。汇编程序(assembler )将汇编语言的符号代码和存储地址翻译成与机器语言相对应的数字代码。
汇编语言大大提高了编程的速度和准确度,人们至今仍在使用着它,在编码需要极快的速度和极高的简洁程度时尤为如此。但是,汇编语言也有许多缺点:编写起来也不容易,阅读和理解很难;而且汇编语言的编写严格依赖于特定的机器,所以为一台计算机编写的代码在应用于另一台计算机时必须完全重写。
这些程序最初被称为编译程序-编译器,但更确切地应称为分析程序生成器 (parser generator ),这是因为它们仅仅能够自动处理编译的一部分。这些程序中最著名的是 Yacc (yet another compiler- compiler),它是由Steve Johnson在1975年为Unix系统编写的。
类似地,有穷自动机的研究也发展了另一种称为扫描程序生成器 (scanner generator )的工具,Lex (与Yacc同时,由Mike Lesk为Unix系统开发的)是这其中的佼佼者。 在20世纪70年代后期和80年代早期,大量的项目都关注于编译器其他部分的生成自动化,这其中就包括代码生成。这些尝试并未取得多少成功,这大概是因为操作太复杂而人们又对其不甚了解。
编译器设计最近的发展包括:首先,编译器包括了更为复杂的算法的应用程序,它用于推断或简化程序中的信息;这又与更为复杂的程序设计语言(可允许此类分析)的发展结合在一起。其中典型的有用于函数语言编译的Hindle y - Milner类型检查的统一算法。
其次,编译器已越来越成为基于窗口的交互开发环境(interactive development environment,IDE )的一部 分,它包括了编辑器、链接程序、调试程序以及项目管理程序。这样的IDE的标准并没有多少, 但是已沿着这一方向对标准的窗口环境进行开发了。
相关程序
(1)解释程序(interpreter)
解释程序是如同编译器的一种语言翻译程序。它与编译器的不同之处在于:它立即执行源程序而不是生成在翻译完成之后才执行的目标代码。从原理上讲,任何程序设计语言都可被解释或被编译,但是根据所使用的语言和翻译情况,很可能会选用解释程序而不用编译器。例如, 我们经常解释BASIC语言而不是去编译它。类似地,诸如LISP 的函数语言也常常是被解释的。
解释程序也经常用于教育和软件的开发,此处的程序很有可能被翻译若干次。而另一方面,当执行的速度是最为重要的因素时就使用编译器,这是因为被编译的目标代码比被解释的源代码要快得多,有时要快10倍或更多。但是,解释程序具有许多与编译器共享的操作,而两者之间也有一些混合之处。
(2) 汇编程序(assembler)
汇编程序是用于特定计算机上的汇编语言的翻译程序。正如前面所提到的,汇编语言是计算机的机器语言的符号形式,它极易翻译。有时,编译器会生成汇编语言以作为其目标语言, 然后再由一个汇编程序将它翻译成目标代码。
(3) 连接程序(linker)
编译器和汇编程序都经常依赖于连接程序,它将分别在不同的目标文件中编译或汇编的代码收集到一个可直接执行的文件中。在这种情况下,目标代码,即还未被连接的机器代码,与可执行的机器代码之间就有了区别。连接程序还连接目标程序和用于标准库函数的代码,以及连接目标程序和由计算机的操作系统提供的资源(例如,存储分配程序及输入与输出设备)。 连接程序现在正在完成编译器最早的一个主要活动(这也是“编译”一词的用法, 即通过收集不同的来源来构造)。连接过程对操作系统和处理器有极大的依赖性,。
(4)装入程序(loader)
编译器、汇编程序或连接程序生成的代码经常还不完全适用或不能执行,但是它们的主要存储器访问却可以在存储器的任何位置中且与一个不确定的起始位置相关。这样的代码被称为是可重定位的(relocatable ),而装入程序可处理所有的与指定的基地址或起始地址有关的可重定位的地址。装入程序使得可执行代码更加灵活,但是装入处理通常是在后台(作为操作环境的一部分)或与连接相联合时才发生,装入程序极少会是实际的独立程序。
(5) 预处理器(preprocessor )
预处理器是在真正的翻译开始之前由编译器调用的独立程序。预处理器可以删除注释、包含其他文件以及执行宏(宏macro是一段重复文字的简短描写)替代。预处理器可由语言(如 C )要求或以后作为提供额外功能(诸如为FORTRAN提供Ratfor预处理器)的附加软件。
(6) 编辑器(editor)
编译器通常接受由任何生成标准文件(例如ASCII文件)的编辑器编写的源程序。现在, 编译器已与另一个编辑器和其他程序捆绑进一个交互的开发环境-IDE中。此时,尽管编辑器仍然生成标准文件,但会转向正被讨论的程序设计语言的格式或结构。这样的编辑器称为基于结构的(structure based ),且它早已包括了编译器的某些操作;因此,程序员就会在程序的编写时而不是在编译时就得知错误了。从编辑器中也可调用编译器以及与它共用的程序,这样程序员无需离开编辑器就可执行程序。
(7) 调试程序(debugger )
调试程序是可在被编译了的程序中判定执行错误的程序,它也经常与编译器一起放在IDE 中。运行一个带有调试程序的程序与直接执行不同,这是因为调试程序保存着所有的或大多数源代码信息(诸如行数、变量名和过程)。它还可以在预先指定的位置(称为断点(breakpoint )) 暂停执行,并提供有关已调用的函数以及变量的当前值的信息。为了执行这些函数,编译器必须为调试程序提供恰当的符号信息,而这有时却相当困难,尤其是在一个要优化目标代码的编译器中。因此,调试又变成了一个编译问题。
(8) 描述器(profiler)
描述器是在执行中搜集目标程序行为统计的程序。程序员特别感兴趣的统计是每一个过程的调用次数和每一个过程执行时间所占的百分比。这样的统计对于帮助程序员提高程序的执行速度极为有用。有时编译器也甚至无需程序员的干涉就可利用描述器的输出来自动改进目标代码。
(9)项目管理程序(project manager)
现在的软件项目通常大到需要由一组程序员来完成,这时对那些由不同人员操作的文件进行整理就非常重要了,而这正是项目管理程序的任务。例如,项目管理程序应将由不同的程序员制作的文件的各个独立版本整理在一起,它还应保存一组文件的更改历史,这样就能维持一个正在开发的程序的连贯版本了(这对那些由单个程序员管理的项目也很有用)。项目管理程序的编写可与语言无关,但当其与编译器捆绑在一起时,它就可以保持有关特定的编译器和建立一个完整的可执行程序的链接程序操作的信息。在Unix系统中有两个流行的项目管理程序: sccs (source code control system )和rcs (revision control system )。
步骤
编译器内部包括了许多步骤或称为阶段源代码 (phase),它们执行不同的逻辑操作。将这些阶设想为编译器中一个个单独的片断是很有用的, 尽管在应用中它们是经常组合在一起的,但它们扫描程序确实是作为单独的代码操作来编写的。
扫描程序
(scanner)
在这个阶段编译器实际阅读源程序(通常以析程序字符流的形式表示)。扫描程序执行词法分析注释树符号表 (Lexical analysis ):它将字符序列收集到称作记号错误处 (token )的有意义单元中,记号同自然语言,如英源代码理器语中的字词相似。因此可以认为扫描程序执行与优化程序拼写相似的任务。 中间代码例如在下面的代码行(它可以是C程序的一部分)中: 代码生成器 a [index] = 4 + 2 这个代码包括了1 2个非空字符,但只有 8个目标代码记号: a 标识符目标代码优化程序 [ 左括号 i n d e x 标识符 ] 右括号 = 赋值目标代码 4 数字编译器的阶段 + 加号 2 数字 每一个记号均由一个或多个字符组成,在进一步处理之前它已被收集在一个单元中。 扫描程序还可完成与识别记号一起执行的其他操作。例如,它可将标识符输入到符号表中, 将文字(litral)输入到文字表中(文字包括诸如3 . 1415926535的数字常量,以及诸如“Hello , world ! ”的引用字符串)。
语法分析程序
语法分析程序从扫描程序中获取记号形式的源代码,并完成定义程序结构的语法分析 (syntax analysis ),这与自然语言中句子的语法分析类似。语法分析定义了程序的结构元素及其关系。通常将语法分析的结果表示为分析树(parse tree)或语法树(syntax tree)。 例如,还是那行C代码,它表示一个称为表达式的结构元素,该表达式是一个由左边为下标表达式、右边为整型表达式的赋值表达式组成。这个结构可按下面的形式表示为一个分析树: 请注意,分析树的内部节点均由其表示的结构名标示出,而分析树的叶子则表示输入中的记号序列(结构名以不同字体表示以示与记号的区别)。 分析树对于显示程序的语法或程序元素很有帮助,但是对于表示该结构却显得力不从心了。 分析程序更趋向于生成语法树,语法树是分析树中所含信息的浓缩(有时因为语法树表示从分析树中的进一步抽取,所以也被称为抽象的语法树(abstract syntax tree ))。下面是一个C赋值语句的抽象语法树的例子: 请注意,在语法树中,许多节点(包括记号节点在内)已经消失。例如,如果知道表达式是一个下标运算,则不再需要用括号“[”和“]”来表示该操作是在原始输入中。
语义分析程序
程序的语义就是它的“意思”,它与语法或结构不同。程序的语义确定程序的运行,但是大多数的程序设计语言都具有在执行之前被确定而不易由语法表示和由分析程序分析的特征。 这些特征被称作静态语义(static semantic),而语义分析程序的任务就是分析这样的语义(程序的“动态”语义具有只有在程序执行时才能确定的特性,由于编译器不能执行程序,所以它不能由编译器来确定)。一般的程序设计语言的典型静态语义包括声明和类型检查。由语义分析程序计算的额外信息(诸如数据类型)被称为属性(attribute),它们通常是作为注释或“装 饰”增加到树中(还可将属性添加到符号表中)。 在正运行的C表达式 a [index] = 4 + 2 中,该行分析之前收集的典型类型信息可能是:a是一个整型值的数组,它带有来自整型子范围的下标;index则是一个整型变量。接着,语义分析程序将用所有的子表达式类型来标注语法树,并检查赋值是否使这些类型有意义了,如若没有,则声明一个类型匹配错误。在上例中, 所有的类型均有意义,有关语法树的语义分析结果可用以下注释了的树来表示。
源代码优化程序
编译器通常包括许多代码改进或优化步骤。绝大多数最早的优化步骤是在语义分析之后完 成的,而此时代码改进可能只依赖于源代码。这种可能性是通过将这一操作提供为编译过程中的单独阶段指出的。每个编译器不论在已完成的优化种类方面还是在优化阶段的定位中都有很大的差异。 在上例中,我们包括了一个源代码层次的优化机会,也就是:表达式4 + 2可由编译器计算先得到结果。当然,还会有更复杂的情况。还是在上例中,通过将根节点右面的子树合并为它的常量值,这个优化就可以直接在(注释)语法树上完成: 尽管许多优化可以直接在树上完成,但是在很多情况下,优化接近于汇编代码线性化形式的树更为简便。这样节点的变形有许多,但是三元式代码(three-address code )(之所以这样称呼是因为它在存储器中包含了3个(或3个以上)位置的地址)却是标准选择。另一个常见的选 择是P -代码(P - code ),它常用于Pascal编译器中。 在前面的例子中,原先的C表达式的三元式代码应是: t = 4 + 2 a [ index] = t (请注意,这里利用了一个额外的临时变量t 存放加法的中间值)。这样,优化程序就将这个代码改进为两步。首先计算加法的结果: t = 6 a [index] = t 接着,将t替换为该值以得到三元语句 a [index] = 6 ,指出源代码优化程序可能通过将其输出称为中间代码(intermediate code )来使用三元式代码。中间代码一直是指一种位于源代码和目标代码(例如三元式代码或类似的线性表示)之间的代码表示形式。但是,我们可以更概括地认为它是编译器使用的源代码的任何一个内部表示。此时,也可将语法树称作中间代码,源代码优化程序则确实能继续在其输出中使用这个表示。有时,这个中间代码也称作中间表示(intermediate representation,IR)。