编译方法 马知行 曹启君 机械工业出版社 编译原理演示文稿1

1、编译原理演示文稿第一章 语言处理程序的发展过程1.1 语言处理程序的发展过程 1.1.1 概述 语言处理工作起源于计算机软件设计者描述的在数据集合上的算法与运行该数据集合上的算法的计算机系统的差异。而早期的所用机器语言编制的程序不存在这种差异，因而不需要语言处理程序。随着汇编语言的产生这种差异也随之产生，程序设计者用符号指令代替目标机器指令来说明其算法，这样程序设计者的符号描述和目标机器的运行产生了差异，解决这种差异的就是第一种语言处理程序汇编程序。到了二十世纪五十年代中、后期大批如ForTran、Algol、Pascal的高级语言的相继出现，这样程序员描述的算法和实际运行的机器之差异越来越明

2、显，新的语言处理程序编译程序也就相继产生。随着计算机的应用的逐步扩大，软件已不是单纯的描述数据集合上的算法的程序，它还包括各种数据和文档。因此其程序设计语言发展到了八十年代，面向对象的程序设计语言也就相继产生，如：Delphi、C+，从而程序设计者描述的的有关计算机软件的特性及想法和在计算机系统的具体实现的差异变得也越来越大，填补这种差异的也是语言处理程序。定义定义1.11.1 语言处理程序是一种可以填补说明间距或执行语言处理程序间距的软件 对于应用领域的具体问题，可以用一种说明语言SL(源语言)来描述，SL可用经变换成等价的说明语言L1，L1经变换成L2，L2经变换成L3，Ln经变换成TL（

3、目标机器语言）。此时怎样来描述“说明间距”和“执行间距”的概念呢？其实相对于某个Li来说，从应用领域的具体问题到SL或Li语义间距都是说明间距，而从SL或任一个Li到TL都是执行间距。语言处理程序主要提供了一种语言到另一种语言的变换，由于高级语言使用方便，目前绝大多数用户使用高级语言设计应用软件。因此解释和说明高级语言是如何运行的，对理解语言处理程序来说是十分必要的。高级语言通过称为编译程序的语言处理程序把它们翻译成称为目标语言的机器语言或汇编语言一类低级语言，然后使用填补执行间距的软件得到机器语言程序，运行机器语言程序获得最终结果。 1.1.2 语言处理程序的工作 语言处理工作可以分为程序生

4、成工作和程序执行工作，它们分别来填补说明间距和执行间距。 程序生成工作的是将某一应用领域的源程序生成相应的目标程序。程序生成工作的目标是程序的自动生成(即程序生成器)。程序生成器是一种软件系统，它接受被生成程序的”说明”，并根据”说明”所描述的规则自动生成可以运行的程序。 程序执行工作是将目标程序装入运行的计算机系统，并按照程序的指令系列运行程序。目前目标语言是低级语言，故通常是面向过程的。例: 根据平面几何的命题生成作图程序。在一个输入环境中，输入：已知三角形的二条角平分线相等，求证：该三角形是等腰三角形。系统先检验其有效性，如：是否能构成二条角平分线相等的等腰三角形等。在说明有效的前提下产

5、生相应的若干画直线的语句的作图程序 。最后证明其结论。 这样程序生成器引出了一个新的领域，它介于应用域和说明域之间，称之为程序生成器说明域。从而说明间距变为从应用域到程序生成器说明域之间的间距。由于这一间距往往比从应用领域到说明域的间距要小得多，这样间距的缩小提高了程序的可靠性。由程序生成器域到目标程序域之间的大量工作量都是有生成器来完成的，减少了程序的测试工作、程序的正确性验证问题。程序执行工作的目标是完成程序的运行。 从目标程序的说明域到目标机器的执行域仍存在一定的间距，完成其工作的程序称为程序的执行。程序的执行主要包括：1.装入目标程序。2.取得一条语句或指令。3.分析该语句以及确定所操

6、作的数据集合。4.完成该语句的含义，对定义的数据集合产生相应的变换。 程序的执行工作的方式取决于目标代码的形式、运行的目标机器和执行时的资源开销（所占用的时间和存储空间）。如果目标程序是机器语言代码，则目标程序的执行效率是高的。它比其它非机器语言的目标代码的执行要快得多。因此目前的目标代码仍多数是类似于机器语言或汇编语言的一类低级语言。1.1.3 语言处理程序的形式 语言的处理形式主要是由填补说明间距和填补执行间距的程序两大类。 语言的翻译程序，如汇编程序、编译程序它填补了程序设计语言到计算机系统的语言(指令系统)的执行间距。反汇编程序、反编译程序则它填补了计算机系统的语言(指令系统)到程序设

7、计语言执行间距。语言转换程序填补的是两个程序设计语言之间的说明间距。 由于预处理程序是将用户提供的源程序处理成另种符号程序，它是在说明域之后的语义间距，则它提供了执行间距的一部分，但它不属于翻译程序。解释程序是将源程序装入后逐步取语句并解释其含义执行之，因此它提供了执行间距。 随着软件开发工具的不断完善，面向问题的语言开始问世。面向问题的语言提供了与应用域完全等同或接近的说明域，使得其说明间距越来越小，而执行间距却越来越大，但整个执行间距的填补都是由语言处理程序来完成的，这对软件提高软件开发的质量和降低软件的开发成本有着及其积极的意义。对于程序设计者来说也是降低了劳动强度、提高了工作效率和设计

8、出的软件的具有较高的可靠性。可以预期今后还会产生更接近应用域的说明语言，甚至用自然语言直接可以描述应用领域的问题，此时说明间距接近零，全部工作都是由填补执行间距的软件来完成。 1.2 高级语言的翻译 程序设计语言的本质是(能把初始状态的数据转变为某个终止状态的)算法的一种描述工具，。高级语言的翻译程序就是对程序设计语言寻找一种等价的变换使得变换后的程序对初始状态的数据能变换为终止状态。通常高级语言的翻译方式有两种：解释程序，编译程序。1.2.1 解释 对于任一种程序设计语言PL，可以定义一种抽象机，PL的运算，数据结构和控制结构的存储元素的指令，在这样的机器上执行用PL写的算法称为解释，通常，

9、这种抽象机是由软件实现的，即程序设计语言和机器语言之间的间距是由软件来填补的，这样的软件叫做解释器又称解释程序,是一种能能逐条取出高级语言源程序语句解释执行得到结果加工程序(软件) 。图1-2为解释程序的执行图解。 由于解释执行它不直接产生目标代码它运行时所需的内存相对较少，而且源程序修改后，又可立即重新执行，但是解释程序在执行重复语句时，需多次重复解释执行，其运行速度相对较慢。故目前采用解释执行的高级语言较少。 1.2.2编译 编译器又称编译程序,是一种能将高级语言源程序翻译成等价的目标语言形式的程序的加工程序(软件)，所得到的目标程序由机器硬件解释执行，或由其它软件进一步处理。 能够完成一

10、种语言到另一种语言变换的软件称为翻译器。编译器是翻译器的一种类型。编译由于它产生目标代码尽管可能占用的存储空间要比解释方式多，但它能多次运行目标代码，得到不同的运行结果，仅需一次翻译。由于编译程序的以上优点，目前大多数编译程序采用的是编译方式。如图1-3为编译程序的翻译和运行的图解。 编译和解释的关系与英语中的口译和笔译的关系类似，口译翻译直接翻译，它不需记录介质。用户如有疑问，可以立即提问而得到答案。但当用户需多次获得译文时，需多次翻译。笔译时虽然需要介质记录翻译结果，但对于用户多次获得译文时，仅需一次翻译。因此编译的优点是显而易见的。 1.3 编译程序的结构1.3.1 编译的逻辑结构和工作

11、过程 一 编译程序的逻辑结构 一个典型的编译程序分成如图1-4所示的七个逻辑部分. 二 编译程序的工作过程 一个编译过程可以分成若干个阶段，每一阶段完成特定的任务。典型的编译过程划分成了词法分析、语法分析、语义分析和中间代码生成，代码优化和目标代码生成五个阶段。现将其工作过程与英(文)译中(文)比较如下: 英(文)译中(文) 编译过程 识别单词 词法分析 单词组成短语或句子 语法分析 分析确定短语或句子含义 语义分析与中间代码生成 调整修饰形成草稿 代码优化 謄写定稿 目标代码生成 另外还需说明的是编译的每个阶段都和表格管理和出错管理都有联系。编译过程中源程序的各种信息被保留在相应的表格中，如

12、：标识符的先说明后使用问题、过程式或函数的形式参数和实在参数的个数和类型的一致性问题通常都是通过填查表来解决的。 因此编译各阶段的工作都会涉及到构造、查找或更新有关的表格内容，也就需要有表格管理的工作；如果编译过程中发现源程序有错误，从用户的角度来看，希望编译程序能指出错误的位置和性质，以便方便快速地查找自已的错误。因此编译程序应尽可能地报告错误的性质和错误发生的位置，可能的话自动校正错误或者从错误的状态恢复成可以其余部分能继续编译下去，并将相关联的错误缩小到尽可能小的范围内，这些工作称之为出错处理。词法分析词法分析 词法分析又称线性分析或扫描，它是整个编译程序的第一个阶段，其主要任务是从左到

13、右地对构成源程序的字符串进行扫描和分解，识别出一个个具有独立意义的单词（也称单词符号或符号）。这样的单词指逻辑上紧密相连的一组字符，在语法的角度来看，这些字符具有集体含义已不能再分了。比如标识符是中字母字符开头，后跟字母、数字字符的字符序列组成的一种单词、保留字（关键字或基本字）是一种单词，此外还有整数、算符、界符等等。例:某源程序段如下： var area, radius:real; begin read(radius); area:=3.141526*radius*radius end. 词法分析阶段将构成这段程序的字符组成了如下单词序列： 1 保留字 var 2 标识符 area 3 逗

14、号 , 4 标识符 radius 5 冒号 : 6 标识符 real 7 分号 ； 8 保留字 begin 9 保留宇 read 10 左括号 （ 11 标识符 radius 12 右括号 ） 13分号 ； 14 标识符 area 15赋值号 := 16 常量 3.1415926 17 乘号 * 18标识符 radius 19 乘号 * 20标识符 radius 21保留字 end 22 界符 .语法分析语法分析 语法分析是编译过程的第二个阶段。语法分析的工作是在词分析的基础上将识别单词序列是否能组成其语法成分，如“程序”，“分程序”，“条件语句”，“赋值语句”，“表达式”等等。这种语法成分，

15、也称语法单位。通过语法分析可以使分析者能得知其是输入符号串是否是语法上正确的“程序”。例: 对赋值语句area:=3.141526*radius*radius进行语法分析是由、:=和组成的；是+、*、或组成的；对于上述分析用如图1-5的一棵树来表示。 语义分析和中间代码生成语义分析和中间代码生成 语义分析和中间代码生成是编译程序的第三个阶段，它审查源程序有无语义错误，如：赋值类型的相容性问题，并为以后代码生成阶段收集类型信息。它确定了源程序的层次结构及标识如表达式和语句、运算符和运算对象之间的关系。语义分析的工作之一是进行类型检查，检查每个运算符的运算对象是否符合该语言规范，当不符合该语言规范

16、时，编译程序应报告错误。如有的编译程序要对字符型加整型的运算情况报告错误。但也有的语言规定运算对象可被强制转换，那么当二目运算+作用于整型和字符型时，编译程序应将字符型转换成整型，而不认为是源程序的错误。在语义分析之后，根据语义分析所得到的源程序的结构等信息用一种便于以后各阶段使用的形式来表示。如：将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或中间代码。 所谓“中间代码”是一种结构简单、含义明确的记号系统，它具有两个性质：一是容易生成这种代码，二是容易将它翻译成目标代码。中间代码的形式很多，主要有四元式、三元式、间接三元式、逆波兰式、树等。也可以语法树上增加一语义处理转换动作来表

17、示中间代码。 代码优化代码优化 由于编译所产生的目标程序，其运行的次数和编译次数无关，这样对于编译成功的目标程序可以多次执行，为此用户希望能产生质量较高的目标代码，也就是在运行是有占用的时间和空间较少。目前虽然没有一种通用的可以求出最简目标代码的算法，但仍可采用一些局部优化的策略使得在代码优化阶段可以对前阶段产生的中间代码进行变换或进行改造，相对减少目标代码的时间和空间。其常用的方法有公共子表达式的删除、强度削弱、循环不变量外提等优化手段。目标代码生成目标代码生成 整个编译的最后一个阶段也就是目标代码生成。这一阶段的工作是把中间代码变换成特定目标机器上的绝对指令代码或可重定位的指令代码或汇编指

18、令代码。该阶段要为源程序所用的每个对象分配存储单元，并把中间代码翻译成等价的机器指令程序。目标代码生成阶段由于它生成的是具体机器上的目标代码，因些它的工作与硬件系统结构和指令含义有关，它涉及到如何便用这些硬件系统以及如何选择机器指令等 。其产生的目标代码直接与目标程序的效率有关。综上所述一个编译程序工作过程可分为分析和综合两大部分：1.分析分析 揭示的结构和基本数据，决定它们的含义，建立源程序的中间表示2.综合综合 从源程序的中间表示建立和源程序等价的目标程序1.3.2阶段的组合 在编译程序的研制角度来分，可为前端（front end）和后端（back end）两部分。分别对应上述的分析(词法

19、分析、语法分析、语义分析和中间代码生成)与综合(代码优化和目标代码生成).定义1.2 前端指的是只依赖于源语言，几乎独立于目标机器的阶段或阶段的部分组成的；后端是指编译中只依赖于目标机器的部分，它们一般独立于源语言与中间语言有关。 这样对于在不同机型A、B、C上研制P语言的编译器只要开发同一个前端，不同的后端。对于同一机型上要开发X 、 Y 、 Z等不同的语言的编译程序，则只要开发不同的前端，共用相同的后端。 例:若要为A、B两机器研制a、b语言的编译器,则按常规需要开发A(a) 、A(b) 、B(a) 、B(b)四个编译器。实际上只需要开发A(a) 、B(b)两个就行了。剩下的A(b)和B(

20、a)可通过已有的部件组装得到： A(b)=B(b)前+A(a)后，B(a)=A(a)前+B(b)后。 即:分拆复制 A(a) =A(a)前+A(a)后 B(b) =B(b)前+B(a)后 组装得到 A(b) =B(b)前+A(a)后 B(a) =A(a)前+B(b)后 前端通常这些阶段包括词法分析、语法分析、语义分析和中间代码生成，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理工作。后端工作指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作，也可以包括代码优化的工作。 编译器中的部分工作是根据需要对源语言

21、或等价的中间语言程序从头到尾扫视并完成一定任务。定义定义1.31.3 把对源语言或等价的中间语言程序从头到尾扫描并完成规定的任务的过程称为“遍”,也可称作“趟”。 每一遍扫描可完成上述一个阶段或多个阶段的工作,也可完成阶段的部分工作。一个编译过程可由一遍、两遍或多遍完成。对于每一“遍”来说，前遍程序输出为后一遍程序的输入，第一遍的输入是源程序，最后一遍的输出是目标语言程序。一个编译程序的各个阶段的工作如何组合成编，即编译程序究竟分成几遍？怎样分遍？没有一个明确的论，但与下列因素有关。1.源语言和目标机器的特征2.编译程序工作的环境3.编译程序模块的软件接口 对于一些允许先使用后说明的名字的语言

22、，当编译程序发现该名字时，因不知道该名字的属性，不能直接生成相应的目标代码，这样的编译程序应分成至少二遍。另外根据目标机器的指令系统可以产生相对优化的目标代码，这可能要加入根据目标机器的指令系统的优化算法这一遍。对于目标机器的情况也影响编译程序的遍数的划分，如早期的计算机的内存资源匮乏，不得不将编译程序分批运行之，这也影响到编译的遍。对于若干研制编译程序的人员来说，总希望软件的接口清晰，让一个模块的输入为另一模块的输出。这样也可能会增加编译程序的遍数。一个多遍的编译程序可以较之一遍的编译程序少占内存，遍数多一点，整个编译程序的逻辑结构可能清晰些，但遍数越多，则增加读写中间文件的次数就越多，势必

23、消耗较多CPU时间，从而比一遍的编译要慢些。因此一个编译程序究竟分成几遍，应根据其实际情况而定。1.4 编译程序的相关软件和开发工具 随着计算机应用的逐步扩大，软件的需求日益增加，其规模也迅速扩大。如何保证软件质量和提高开发软件的效率，除了要遵循软件工程中的规范外，还尽量使用先进的软件开发技术和相应的软件工具，这些软件工具创造了良好的工作环境，从而保证了软件开发质量和提高了软件的生产率，促进了软件生产的发展。为了提高编程效率，缩短调试时间，软件工作人员应尽量使用这些对源程序处理的工具。当然，开发这些软件工具也要用到编译的技术和方法。 1.4.1语言的编辑器 要在某个语言上开发一个应用程序，首先

24、要在编辑程序支持下将源程序输入计算机，但在输入过程中常会发生一些不必要的输入错误，如：Pasal语言中的begin、end和C语言中的、配对问题，而且当源程序很大时，要化较多的精力来解决这种不匹配问题。如采用所谓的结构化编辑器来引导用户在语言的语法制导下编制程序，如当输入begin时，能自动地提供关键字和与其匹配的关键字end；输入if后必须有then输入 后自动跳出 ；输入左括号时必有右括号匹配等；使用了这样结构化编辑器不但可以减少语法上的输入错误，还可以使源程序的静态结构较清晰。从而降低了源程序的输入时间和源程序的调试时间，提高了软件开发效率和提高了软件的质量。其次，当发现源程序错误时，应

25、立即启动或调入编辑程序并允许用户修改之。1.4.2 调试工具 随着软件的不断发展，软件已不能用简单的静态检查或用少量的输出语句可以发现其错误的。因此，用语言程序的调试工具调试软件成为了软件开发过程中的一个重要环节。结构化编辑器虽然能解决一些语法错误问题，但它不能解决语法上已通过编译，而计算结果与编程人员的意图是不一致的程序的问题。对于这些程序需进一步确认是否与编程人员的意图相一致，也就是判断程序的执行是否能实现预计的算法和功能。捕捉这种算法的功能的错误就需用调试器来协助解决。如使用跟踪、设置断点等方法来调试程序。调试器的功能越强，实现方法就越复杂，但它必须与语法分析、语义处理有紧密联系。 与语

26、言调试工具类似的语言程序测试工具语言，它同样是捕捉程序中算法的功能的错误的工具。程序的测试工具有两种：静态分析器和动态测试器。 静态分析器是对源程序进行静态地分析。它对源程序进行语法分析并用相应的表格表示，然后检查变量的定值与其引用的关系。如一个变量未被赋值就被引用，或定值后从未被引用，或程序中存在多余的源代码等一些编译程序的语法分析发现不了的错误，可以通过静态分析器检查出来。 动态测试工具是在源程序的必要的位置插入某些标记，并用测试实例记录该程序运行时的实际标记路径。将运行结果与期望的结果进行比较分析，帮助编程人员查找问题。从而达到捕捉错误的目的。1.4.3 预处理程序 预处理器实质上是将用

27、户输入的源程序处理成一个真正被编译的源程序。其目的是改进程序设计环境，提高编程效率。它必须在通常的词法分析、语法分析、优化和代码生成之前完成。预处理器通常有下列功能：宏处理宏处理 源程序为了书写方便将一些较长的结构用一种缩写代替。预处理器可以把缩写结构扩展成正文。文件包含文件包含 预处理器可以把文法包含声明扩展成正文，当语言中有语句#include 时，语言的预处理会用文件string.h来代替，一旦发现string.h中还有文件包含，则继续扩展，直至全部扩展为正文。这样可以大大地减少程序的输入量，提出高程序的易读性。语言的扩充语言的扩充 有些处理器可以对一些语言扩充新的功能。增加新的程序设计

28、处理语句，如某程序设计语言不含repeat语句，通过宏定义给出该语句的结构，把工作交给语言处理器去完成。对于语言预处理的宏定义，它有宏定义和宏引用两类语句。以相应的关键字开始，它包括了宏名和宏体，在宏替换中还允许在定义中使用形式参数。宏引用包括宏名和所需的实在参数。在这里宏定义和函数定义是二个完全不同的概念。宏名中的实在参数也就是形式参数的值。预处理器用实参数代替宏体中的形式参数，然后再变换后的宏体替换宏引用本身。函数调用是在程序运行时完成的，它是将程序的控制权交给了函数等函数结束后控制权再交回给调用者。1.4.4 汇编器 在编译程序生成的数据可以用各种表示法描述，不必去完成相应的各数制之间的

29、人工转达换。从而提高了目标程序的易读性。 汇编器通常用两遍扫描和单遍扫描二种形式。汇编器的两遍扫描翻译可以方便地处理向前引用的问题。在第一遍扫描中，进行内存单元器处理，并且把程序中定义的符号输入到符号表。第二遍扫描符号表中找到的地址信息综合出目标程序的形式。汇编器的单遍扫描方式，内存单元计数器处理和两遍扫描类似，主要是对向前引用（符号的先使用后定义）的问题是采用的所谓补丁的方法处理的。先包含向前引用指令的操作数字段保持空，当遇到向前引用符号的定义时再指导它的地址填入该空白段中。 为了提高编译程序的研制效率，可以将高级语言转换成汇编语言。由汇编器对这些代码作进一步处理。如产生可重定位的机器代码，

30、由装配器和连接器产生可运行的目标代码。 汇编语言是依赖于机器的低级程序设计语言而言，它是面向特定计算机系统的。使用汇编器产生目标代码与直接产生计算机器语言相比有以下几个优点：1. 使用助记符的操作码表示机器指令，目标程序的易读性好，在编译程序的调试过程中，还可以使用汇编器提供的帮助信息和汇编器提供的调试工具。2. 符号名可以与数据或指令相关联。这些符号名可以在汇编语句中作为操作数使用。汇编器对这些名字执行内存分配指定，编译程序设计者无须知道其内存分配及定位的具体细节。 3. 在编译程序生成的数据可以用各种表示法描述，不必去完成相应的各数制之间的人工转达换。从而提高了目标程序的易读性。 1.4.4 装配和连接器 装配器完成装配和连接两个功能。装入过程包括读入可重定位的机