《编译系统概述》PPT课件.ppt

《《编译系统概述》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《编译系统概述》PPT课件.ppt（40页珍藏版）》请在三一办公上搜索。

1、2023/7/29,为什么学习编译,编译程序构造的原理和技术一直属于计算机科学必备的专业基础知识。是计算机科学中一个非常成功的分支，也是最早获得成功的分支之一。它所建立的理论、技术和方法值得深入研究和学习。编译构造正确地建立了研究的问题领域和研究方式。,2023/7/29,为什么学习编译,针对编译程序构造的某些部分已经开发了标准的形式化技术，包括有限自动机理论、上下文无关文法、正规表达式、属性文法、机器代码描述、数据流分析方程式等。编译程序包含许多普遍使用的数据结构和算法，例如散列法（哈希算法）、栈机制、堆机制、垃圾收集、集合算法、表驱动算法。编译程序的许多构造技术已经得到了广泛的应用。学习编

2、译原理和技术还有助于我们理解程序设计语言，编写优秀的软件。,2023/7/29,什么叫编译程序,概念翻译程序或翻译器是把一种语言（源语言）转换成等价的另外一种语言（目标语言）的程序。如果源语言是高级编程语言，目标语言是机器代码和汇编语言这样的低级语言，这类翻译程序就叫做编译程序或编译器。,2023/7/29,第1章 编译系统概述,1.1程序设计语言的发展 1.2基本术语解释1.3编译过程概述1.4出错处理1.5编译程序的前端和后端1.6编译程序的实现方式,2023/7/29,1.1 从面向机器的语言到面向人类的语言,计算机的硬件只能识别由0、1字符串组成的机器指令序列，即机器指令程序。在计算机

3、刚刚问世的年代，人们只能向计算机输入机器指令程序来指挥它进行简单的数学计算。机器指令程序是最基本的计算机语言。由于机器指令程序不易理解，用它编写程序既困难又容易出错，于是人们就用容易记忆的符号来代替0、1字符串。用符号表示的指令被称为汇编指令，汇编指令的集合被称为汇编语言，由汇编语言编写的指令序列被称为汇编语言程序。虽然汇编指令比机器指令在阅读和理解上有了长足进步，但是二者之间并无本质区别，它们均要求程序设计人员根据指令工作的方式思考、解决问题。因此，人们称这类语言为面向机器的语言或低级语言。,2023/7/29,随着计算机应用需求的不断增长，人们希望能有功能更强、抽象级别更高的语言来支持程序

4、设计，于是就产生了面向各类应用的程序设计语言。这些语言的共同特征是便于人类的理解与使用，因此被称为面向人类的语言或高级语言。表1.1列出了几种面向机器和面向人类的语言及其表现形式。,2023/7/29,表1.1 面向机器和面向人类语言举例,2023/7/29,1通用程序设计语言 通用程序设计语言是继汇编语言之后发展起来的应用最广的一类语言，如人们常用的FORTRAN、Pascal、C/C+、Ada83/Ada95、Java等语言。这类语言的特征是：语言结构符合人类的思维特征，如直接使用表达式进行数学运算；具有很高抽象程度，如引入过程与类等机制；程序设计中强调逻辑过程，即程序员要考虑事情的前因后

5、果，不但要设计做什么，还要考虑怎么做，如条件或循环的判断等。,2023/7/29,2数据查询语言 与通用程序设计语言相比，数据查询语言的抽象程度更高，它只要求程序员具有清晰的逻辑思维能力，设计好做什么，而忽略怎么做这样的实现细节，从而使得对大量复杂数据的处理变得轻松简单。,2023/7/29,3形式化描述语言 形式化描述语言的代表之一是编译器构造中常用的工具YACC的语言。这类语言的核心部分是基于数学基础的产生式，设计人员只需利用产生式描述语言结构的文法，就可以构造出识别该语言结构的识别器。,2023/7/29,4其他面向特定应用领域的语言 随着计算机应用领域的不断拓展，先后出现了多种面向特定

6、应用领域的高级语言，如面向互联网应用的HTML、XML，面向计算机辅助设计的MATLAB，面向集成电路设计的VHDL、Verilog，面向虚拟现实的VRML等等。这些形形色色、多不胜数的计算机语言推动了计算机应用的飞速发展，使得计算机成为人类生活中不可缺少的重要部分。,2023/7/29,1.1 程序设计语言的发展,汇编语言(Assemble Language),机器语言(Machine Language),程序设计语言(Programming Language),2023/7/29,例计算表达式3*16+2的值，实现该计算的机器语言程序、汇编语言程序和程序设计语言（C语言）程序如下所示。目标

7、计算机的系统结构和汇编语言的使用方法详见本书第7章。,22038210260261011000f000,Load R0,3Mul R0,10Load R1,2Add R0,R1Write R0Halt,void main(void)cout3*16+2;,注：10表示16,2023/7/29,机器语言 机器指令集合称为机器语言。机器指令即二进制数，通常由若干字节构成。优点计算机可直接识别执行可充分利用硬件特性,缺点可读性差指令系统随机种而异由于机器指令直接或间接含有绝对地址，增加或减少一条指令，可能会引起多条指令的修改。编程者需协调内存的使用 所以，机器语言形式的程序编制和维护困难，限制了计算

8、机的推广和应用。,2023/7/29,汇编语言 用记忆符取代二进制位，存储地址和汇编语句的序号可用符号名表示。优点用符号取代二进制数，提高了程序的可理解性。性能较好的汇编语言，可用符号名来表示存储地址和汇编语句序号，这样避免了在汇编语句中绝对地址的出现。可充分利用硬件特性 所以，汇编语言在一定程度上降低了程序编制和维护的难度。,缺点汇编语句和机器指令基本上是一对一的，所以汇编语言的编程效率并没有质的提高。和机器语言一样，汇编语言依附于目标计算机。需汇编程序，将汇编语言译成机器语言。,2023/7/29,程序设计语言 程序设计语言又称高级语言。程序设计语言接近于英语，相当于工程语言。目前计算机系

9、统一般含有多个程序设计语言的翻译程序（例VC、VB等），甚至对同一个程序设计语言配备了多个不同性能的翻译程序，供用户选择使用。优点独立于具体计算机，面向过程（函数）或对象。程序设计语言接近于英语，可理解性好。数据类型丰富，各种功能的语句齐备，一条语句至少相当于几十条汇编语句。所以，程序设计语言极大地提高了编程效率，大幅度地降低了编程难度。缺点需翻译程序，将高级语言译成机器语言或汇编语言。对硬件操作困难，高级语言通常提供汇编语言接口。,2023/7/29,1.2 基本术语解释,源语言和源程序(Source Language and Source Program)用程序设计语言书写的程序，称为源程

10、序，该程序设计语言称为源语言。源程序通常用编缉程序输入，用字符(ASCII码)表示，以文本文件形式存储。文本文件(Text File)文本文件的内容由94个图形字符!-(33-126)和4个控制字符换行(10)、回车(13)、空格(32)、TAB(9)构成，文本文件又称为ASCII码文件，扩展名通常为TXT，文件尾用控制字符EOF(26)指示。当换行和回车二个控制字符从文本文件读入内存，在C语言中是用一个字符（换行）表示。,2023/7/29,目标语言和目标程序(Target Language and Target Program)目标语言可以是机器语言(二进制数)，也可以是汇编语言(字符)，

11、或者是其它中间语言(字符)，但最终结果必定是机器语言。机器语言程序用二进制文件存储，汇编语言或中间语言程序用文本文件存储。目标程序是经翻译程序加工后用目标语言表示的程序。二进制文件(Binary File)二进制文件由机器指令即二进制数构成，因二进制数可能是26，故文件尾用文件长度(文件的字节数)指示，扩展名通常为EXE。,2023/7/29,翻译程序(Translator)将源程序译成逻辑上等价的目标程序的程序。翻译程序有二种工作方式：编译和解释。,解释程序 Interpreter,源程序,结果,输入数据,解释、执行,解释方式主要特点是：用户程序是消极的。用户程序运行时，控制点在解释程序，即

12、用户程序的执行离不开解释程序。,解释方式(Interpret)以源程序作为输入，输入一句解释执行一句，不产生完整的目标程序，相应的翻译程序称为解释程序(Interpreter)。,工作方式如下图所示：,2023/7/29,编译方式(Compile)将源程序全部译为目标程序，该目标程序可在操作系统环境下直接执行，相应的翻译程序称为编译程序(Compiler)，工作方式如下图所示：,编译程序Compile,连接程序Link,装入运行Run,编辑程序Edit,ASCII码,二进制(整体未定位),二进制(整体定位),源程序,结果,输入数据,2023/7/29,编辑程序的工作结果是ASCII码形式的源程

13、序。编译程序以ASCII码形式的源程序为输入，它的工作结果是二进制形式的目标程序，但并未包括用户程序中所使用的系统函数的目标代码。从整体上来看，程序是不完整的，程序中的部分地址尚未确定（例系统函数的调用）。将二进制形式的用户程序和系统函数目标代码连接成一个程序，对未确定的地址进行定位。由操作系统将用户程序装入内存后运行。程序在运行过程中读入数据，经处理加工后输出计算结果。,编译方式主要特点是：用户程序是积极的。用户程序执行时，控制点在用户程序自身。除操作系统外，程序运行无需其它支撑软件。,2023/7/29,二种翻译方式比较 解释方式和编译方式的主要区别是：目标代码的执行方式不同，基本原理和方

14、法没有本质上的区别。1）解释方式的优点提供一种直接的交互调试功能，容易获得较好的动态调试效果。使用变量可不预先定义。变量性质可动态修改。2）解释方式的缺点在执行时需动态地对程序进行分析翻译，开销大，其执行速度相当于编译方式的1/10至1/100。解释方式占用内存大 显然解释程序的优点就是编译程序的缺点，反之亦然，对于编译程序的优缺点不再重复叙述。对任何一种高级语言，既可采用编译方式，也可采用解释方式，包括汇编语言在内（MASM方式和DEBUG方式）。,2023/7/29,2023/7/29,编译器的工作相当于在翻译一本原著，计算机运行编译后的目标程序，相当于阅读一本译著，原著(或原作者)和译著

15、者并不在场，主角是译著。而解释器的工作相当于在进行同声翻译，计算机运行解释器，相当于我们直接通过翻译听外宾讲话，外宾和翻译均需到场，主角是翻译。,2023/7/29,1.3编译过程概述,典型的编译程序工作过程是：输入源程序，对它进行加工处理，最后输出目标程序（机器语言或汇编语言形式）。整个过程相当复杂，从数据加工的角度来看，可将其分成4个逻辑阶段，它们是：词法分析语法分析语义分析（中间代码产生）目标代码生成,词法分析,语法分析,语义分析(中间代码产生),目标代码生成,源程序,目标程序,编译程序基本上是按照这个流程来设计的。,图示如下：,2023/7/29,以算术表达式3+abc*128为例，来

16、说明编译程序工作过程。词法分析(Lexical Analysis)执行词法分析任务的程序称为词法分析器。任务：字符串形式单词 编码形式单词内部码（二元式）依据：语言的构词规则二元式(Pair)(单词种别,单词值)单词种别：用整数码表示（为直观起见用字符表示），语法分析时用。单词值：在本书中用字符串表示，语义分析时用。当一个单词种别中可能有多个单词时，单词的值才有意义。为了便于输入处理，无意义的单词值用NUL表示。,2023/7/29,二元式编码,经词分析，算术表达式3+abc*128的单词内部码（二元式）为：(x,3)(+,NUL)(i,abc)(*,NUL)(x,128),2023/7/29

17、,语法分析(Parsing)执行语法分析任务的程序称为语法分析器。任务：检查源程序的语法结构是否正确 依据：语言的语法规则 在语法分析时，算术表达式3+abc*128的语法结构应表示为x+i*x，语法分析器最终应识别出这是一个算术表达式。识别过程相当于建立一棵语法树,+*x(整常数)x(整常数)i(标识符),2023/7/29,语义分析(Semantic Analysis)执行语义分析任务的程序称为语义分析器或中间代码产生器。任务：建立符号表和常数表，记录源程序中标识符属性和常数值，根据语言的语义规定生成中间代码。依据：语言的语义内涵语义分析（中间代码产生）主要工作为：语义正确性检查语义翻译语

18、义正确性检查例2：begin real A;integer B;B=A+B;end语法正确，不同的语言有不同的语义解释。标准Fortran语言认为是错误的，其不允许不同类型的量进行混合运算。C语言认为是正确的，允许混合运算，但需转换成相同类型的量，然后再进行运算。Pascal语言认为是错误的，虽允许混合运算，但不允许将实型量赋值于整型量。,2023/7/29,语义翻译 1)说明语句的翻译 将标识符及其属性填入符号表。2)执行语句的翻译根据不同语句的语义，生成逻辑上等价的中间代码。中间代码 结构简单、意义明确的记号系统，非常接近机器指令，又独立于具体机器。常用的中间代码有三元式和四元式。表达式3

19、+abc*128可译成如下四元式：(*,&abc,&128,&T1)(+,&3,&T1,&T2)其中，&abc表示标识符abc在符号表中入口（即地址）；T1和T2是在翻译过程中由编译程序引入的临时变量，&T1和&T2分别表示T1和T2在符号表中入口；而&128表示常数128在常数表中的地址。,2023/7/29,符号表(Symbol Table)符号表用于记录源程序中出现的标识符(Identifier)，一个标识符往往具有一系列的语义值，它包括标识符的名称、标识符的种属、标识符的类型、标识符值的存放地址等等。每个标识符在符号表中有一项记录，用于记录标识符的各种语义值，而在四元式中填写的是标识符

20、在符号表中的记录地址，通常称为符号表入口。,符号表的结构示意如下：,2023/7/29,常数表(Constant Table)常数表用于记录在源程序中出现的常数。假定，每个整常数在常数表中占2个字节，每个实常数在常数表中占4个字节。,常数表的结构示意如下：,2023/7/29,目标代码生成(Code Generation)执行目标代码生成的程序称为目标代码生成器。任务：中间代码 目标代码（机器指令或汇编语言）依据：目标机器的系统结构 假设模型机器的指令格式为：op Ri,M（Ri）op（M）Riop Ri,Rj（Ri）op（Rj）Riop Ri,C（Ri）op C Ri 其中Ri表示寄存器，M

21、表示内存地址（可用符号表示），C表示常数。,表达式3+abc*128最终形成的汇编语言程序示意如下：Load R0,abcMul R0,128Store R0,T1Load R0,3Add R0,T1Store R0,T2,2023/7/29,编译程序在工作过程中可发现源程序中各种错误，错误类型及错误处理对策简述如下：错误类型词法错误（可在词法分析阶段发现）语法错误（可在语法分析阶段发现）语义错误（可在语义分析阶段发现）,1.4出错处理(Error Handle),出错处理一旦发现错误，暂停编译程序工作，指出错误的地点和类型。在发现错误后，不中断编译程序工作。采取某些措施（例错误局部化、错误校

22、正等），使得源程序的编译工作可继续下去，尽可能发现源程序中比较多的错误。,2023/7/29,1.5编译程序的前端和后端,由于在编译程序的内部引入了中间代码，这样可将编译程序分为二个相互独立部分。编译程序前端(The Front End)组成：词法分析器、语法分析器和中间代码产生器 特点：依赖于被编译的源语言，输出结果用中间代码描述，和目标机器无关。编译程序后端(The Back End)组成：目标代码生成器 特点：和源语言无关，以中间代码形式的源程序为输入进行处理，输出结果依赖于目标机器。,为一个源语言构造好前端，若要在某一个特定计算机上构造该源语言的编译程序，只要构造这个目标机器的后端即可

23、。相反，若已构造了一个高质量的后端，若要在同一台目标机器上为另一源语言构造编译程序时，只要构造该源语言的前端即可。,2023/7/29,1.6编译程序的实现方式,用机器指令或汇编语言手工编写 传统方式，能充分发挥机器的硬件性能，但费时，工作量大。用高级语言手工编写 利用已有的高级语言的编译系统，编写另一高级语言的全部或部分编译程序。自编译方式 先用机器或汇编语言构造一个小的编译程序（称为核），然后以此为工具，构造出一个能编译更多语法成分的编译程序，像滚雪球一样逐步扩大（实质上是上述二种方式的综合）。自动构造词法分析器的自动构造 输入词法规则，编译结果为词法分析器，例LEX系统(Lexical

24、Analyzer Generator)。语法分析器的自动构造 输入语法规则，编译结果为语法分析器，例YACC系统(Yet Another Compiler-Compiler)。,2023/7/29,1.7 编译系统以及其它相关程序,编译系统,预处理器,源程序,编辑器,修改后的源程序,汇编程序,可重定位的目标程序,可执行的目标程序,函数库,可重定位的目标文件,连接器与加载器,特性器,调试器,解释器,配置与版本控制器,源程序,汇编器,编译器,源程序,2023/7/29,1.7 编译系统以及其它相关程序,编辑器：程序员借助编辑器编写源程序，由编辑器产生出标准的正文文件（如ASCII文件）作为编译程序

25、的输入。预处理器：它是在编译程序真正开始翻译源程序之前调用的一个独立的程序，以便加快和简化翻译工作。汇编器：汇编器把汇编语言代码翻译成一个特定的机器指令序列。连接器：搜集和组织程序所需要的不同代码和数据，把它们连接成可以执行的目标代码的工具。,2023/7/29,1.7 编译系统以及其它相关程序,装载器：给程序在内存器中分配一个起始地址，载入目标机器，以便程序中的各个符号通过相对地址可以真实地访问存储器。调试器：用来确定编译过的程序在运行时的错误。特性器：这是搜集运行程序行为特征的统计数据的软件工具。配置与版本控制器：管理和维护每个独立的源程序模块、编译模块、数据文件及其每个文件的修改历史信息包括模块连接、加载的信息等的工具。,2023/7/29,结束,