编译原理( 陈火旺)第1章 引论

1、第1章 引论2v 教材 程序设计语言编译原理(第3版) 陈火旺 国防工业出版社v 课程内容 程序设计语言编译程序构造的基本原理和基本实现技术v 课程地位：编译理论与方法 计算机科学与技术中理论和实践相结合的最好典范 ACM图灵奖，授予在计算机技术领域作出突出贡献的科学家 程序设计语言、编译理论与方法约占1/33v 自20世纪50年代以来，世界上公布的程序设计语言已有上千种之多，但是只有很小一部分得到了广泛的应用。v 从发展历程来看，程序设计语言可以分为4代：v 第一代语言(机器语言)1. 机器语言是由二进制0、1代码指令构成，不同的CPU具有不同的指令系统。机器语言程序难编写、难修改、难维护，

2、需要用户直接对存储空间进行分配，编程效率极低。目前，这种语言已经被淘汰4v 第二代语言(汇编语言) 汇编语言指令是机器指令的符号化，与机器指令存在着直接的对应关系，所以汇编语言同样存在着难学难用、容易出错、维护困难等缺点 但是汇编语言也有自己的优点：可直接访问系统接口，汇编程序翻译成的机器语言程序的效率高 从软件工程角度来看，只有在高级语言不能满足设计要求，或不具备支持某种特定功能的技术性能(如特殊的输入输出)时，汇编语言才被使用5v 第三代语言(高级语言) 高级语言是面向用户的、基本上独立于计算机种类和结构的语言 其最大的优点是：形式上接近于算术语言和自然语言，概念上接近于人们通常使用的概念

3、。高级语言的一个命令可以代替几条、几十条甚至几百条汇编语言的指令。因此，高级语言易学易用，通用性强，应用广泛。 高级语言种类繁多，可以从以下两方面对其进一步分类： 从应用角度分类 从客观系统的描述分类6v 第三代语言(高级语言) 从应用角度分类 可以分为基础语言、结构化语言和专用语言 基础语言 基础语言也称通用语言。它历史悠久，流传很广，有大量的已开发的软件库，拥有众多的用户，为人们所熟悉和接受。属于这类语言的有 BASIC、FORTRAN、COBOL、ALGOL等 BASIC 语言是在 20 世纪 60 年代初为适应分时系统而研制的一种交互式语言，可用于一般的数值计算与事务处理。BASIC

4、语言结构简单，易学易用，并且具有交互能力，成为许多初学者学习程序设计的入门语言7v 第三代语言(高级语言) 从应用角度分类 基础语言 FORTRAN（FORmula TRANslation，公式翻译程序设计语言，20世纪50年代）是世界上最早出现的计算机高级程序设计语言，广泛地应用于数值计算领域，积累了大量高效而可靠的源程序。Fortran语言与JAVA、C#等语言相比缺乏创造力。但是，像ANSYS和Marc等优秀的工程计算软件都运用Fortran语言编写，MATLAB的早期版本主要是为两个著名的Fortran函数包提供程序接口，因此Fortran在工程计算领域长期处于统治地位8v 第三代语言

5、(高级语言) 从应用角度分类 基础语言 COBOL(COmmon Business Oriented Language)是数据处理领域最为广泛的程序设计语言 COBOL主要是应用于银行、金融和会计行业等非常重要的商业数据处理领域。 在企业管理中，数值计算并不复杂，但数据处理信息量却很大 世界上70%的数据都是用COBOL语言处理的，并且90%的ATM事务处理用的都是COBOL语言。500强中有492家使用了COBOL语言，目前在COBOL方面的投资已经超过3万亿美元。据称用COBOL书写的程序超过了1000亿行，并以每年约50亿行代码的速度增长 只要大型机存在，COBOL就不会消失9v 第三代

6、语言(高级语言) 从应用角度分类 结构化语言 20世纪70年代以来，结构化程序设计和软件工程的思想日益为人们所接受。出现了一些很有影响的结构化语言，如PASCAL、C、Ada就是它们的突出代表 PASCAL的取名是为了纪念十七世纪法国数学家Blaise Pascal。PASCAL是第一个系统地体现结构化程序设计概念的现代高级语言。IOI(国际奥林匹克信息学竞赛)和NOI(全国奥林匹克信息学竞赛)都指定C，C+，Free Pascal作为三种程序设计语言。在大学中Pascal语言也常常被用作学习数据结构与算法的教学语言10v 第三代语言(高级语言) 从应用角度分类 结构化语言 C语言功能丰富，表

7、达能力强，有丰富的运算符和数据类型，使用灵活方便，应用面广，移植能力强，编译质量高，目标程序效率高，具有高级语言的优点。同时，C语言还具有低级语言的许多特点，如允许直接访问物理地址，能进行位操作，能实现汇编语言的大部分功能，可以直接对硬件进行操作等。用C语言编译程序产生的目标程序，其质量可以与汇编语言产生的目标程序相媲美，具有“可移植的汇编语言”的美称，成为编写应用软件、操作系统和编译程序的重要语言之一11v 第三代语言(高级语言) 从应用角度分类 专用语言 是为某种特殊应用而专门设计的语言，通常具有特殊的语法形式。一般来说，这种语言的应用范围狭窄，移植性和可维护性不如结构化程序设计语言 目前

8、使用的专业语言已有数百种，应用比较广泛的有APL语言、Forth语言、LISP语言12v 第三代语言(高级语言) 从客观系统的描述分类 可分为面向过程语言和面向对象语言 面向过程语言 以“数据结构+算法”程序设计范式构成的程序设计语言，称为面向过程语言。前面介绍的程序设计语言大多为面向过程语言 面向对象语言 以“对象+消息”程序设计范式构成的程序设计语言，称为面向对象语言。目前比较流行的面向对象语言有Java、C+、Delphi、Visual Basic等13v 第四代语言(简称4GL) 4GL是非过程化语言，编码时只需说明“做什么”，不需描述算法细节 数据库查询和应用程序生成器是 4GL 的

9、两个典型应用： 用户可以用数据库查询语言(SQL)对数据库中的信息进行复杂的操作。 用户只需将要查找的内容在什么地方、 据什么 根条件进行查找等信息告诉 SQL，SQL 将自动完成查找过程 应用程序生成器则是根据用户的需求“自动生成”满足需求的高级语言程序 真正的第四代程序设计语言应该说还没有出现。目前，所谓的第四代语言大多是指基于某种语言环境上具有4GL特征的软件工具产品14v 语言特性 强语言与弱语言分类： 是否要强制类型转化 灵活与规范 如： 强类型语言：JAVA、C+ 弱类型语言：大多数的脚本语言 安全与效率： JAVA与C 指针申请回收 堆、栈等内存空间分配 数组越界检查15v 1

10、什么叫编译程序v 2 编译过程概述v 3 编译程序结构v 4 编译程序与程序设计环境v 5 编译程序的生成16v 编译程序与程序员的关系？v 回顾程序执行的方式 解释型，如：BASIC 编译型，如：C 混合型，如：JAVAv 其中后两种都要使用编译程序（编译器）1 什么叫编译程序17v JAVA语言 Java编译器把Java代码翻译成独立于机器的Java“字节代码” 运行时，目标装置中的校验器便分析这些字节代码以确保代码的安全执行 在目标装置中，内置一个JVM（Java虚拟机）。该虚拟机用一个解释器或一个JIT（适时）编译器把字节代码翻译成目标处理器能够识别的机器语言 Java的传统环境如下图

11、所示：1 什么叫编译程序18v JAVA语言1 什么叫编译程序COMPILE-TIMEENVIRONMENTJAVASOURCE(.java)JAVACOMPILERJAVABYTE CODES(.class)RUNTIME ENVIRONMENT (JAVA PLATFORM)CLASS LOADERBYTE-CODEVERIFIERJAVA CLASSLIBRARIESJAVA VIRTUAL MACHIMEJAVAINTERPTETERJUST-IN-TIMECOMPILERHARDWAREJAVABYTE CODESMOVE LOCALLYOR THROUGHNETWORK19v 在计

12、算机上执行一个高级语言程序一般分两步： 用编译程序把高级语言翻译成机器语言程序 运行所得的机器语言程序求得计算结果1 什么叫编译程序20v 翻译程序 把某一种语言程序(称为源语言程序)等价地转换成另一种语言程序(称为目标语言程序)的程序1 什么叫编译程序源语言程序目标语言程序翻译程序翻译21v 编译程序(compiler) 把某一种高级语言程序等价地转换成另一种低级语言程序(如汇编语言或机器语言程序)的程序1 什么叫编译程序高级语言程序机器语言程序结果编译程序翻译运行22v 编译程序(compiler) 根据不同用途和侧重，编译程序的类型可分为： 诊断编译程序（Diagnostic Compi

13、ler) 专门用于帮助程序开发和调试 优化编译程序（Optimizing Compiler) 着重提高代码效率 交叉编译程序(Cross Compiler) 产生不同于其宿主主机的机器代码 可变目标编译程序(Retargetable Compiler) 不需重写编译程序中与机器无关的部分就能改变目标机1 什么叫编译程序23v 解释程序 把源语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身1 什么叫编译程序源程序结果解释程序解释执行24v 1 什么叫编译程序v 2 编译过程概述v 3 编译程序结构v 4 编译程序与程序设计环境v 5 编译程序的生成25v 把英文翻译为中文 识

14、别出句子中的一个个单词 词法分析 分析句子的语法结构 语法分析 根据句子的含义进行初步翻译 语义分析与中间代码产生 对译文进行修饰 优化 写出最后的译文1. 目标代码生成2 编译过程概述26v 编译程序的工作一般分为五个阶段：v 词法分析v 语法分析v 语义分析与中间代码产生v 优化v 目标代码产生2 编译过程概述27v 词法分析v 任务： 输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词符号v 依循的原则： 词法规则v 描述工具： 正规式和有限自动机v 举例：2 编译过程概述FOR保留字I标识符:=赋值号1整常数TO保留字100整常数DO保留字28v 语法分析v 任务： 在词

15、法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位v 依循的原则： 语法规则v 描述工具： 上下文无关文法、语法树和抽象语法树v 举例： Z:=X+0.618*Y 赋值语句 其中X+0.618*Y 算术表达式2 编译过程概述:=Z+*X0.618Y:=+*IDEEEIDEEIDnumE29v 语义分析与中间代码产生v 任务： 对各类不同语法范畴按语言的语义进行初步翻译（产生中间代码）。工作包括：静态语义检查和中间代码翻译v 依循的原则： 语义规则v 描述工具： 属性文法v 举例： Z:=(X+0.418)*Y/W翻译成四元式序列为：2 编译过程概述ZWT2/(3)T2YT1*(

16、2)T10.418X+(1)结果右操作数左操作数算符序号30v 优化v 任务： 对前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效（节省时间和空间）的目标代码。优化的主要方面：公共子表达式提取、循环优化和删除无用代码等v 依循的原则： 程序的等价变换规则v 举例：FOR K:=1 TO 100 DOBEGINM := I + 10 * K;N := J + 10 * K;END2 编译过程概述31v 优化v 举例： 优化前中间代码：循环中需做300次加法和200次乘法2 编译过程概述(9)goto (2)(2)j(8)K:=K+1K1K+(7)N:=J+T2NT2J+(6)T2:=1

17、0*K；T2为临时变量T2K10*(5)M:=I+T1MT1I+(4)T1:=10*K；T1为临时变量T1K10*(3)if (100K) goto (9)(9)K100j(2)K:=1K1:=(1)注释RESULTARG2ARG1OP序号32v 优化v 举例： 优化后中间代码：循环中仅需做300次加法，无乘法2 编译过程概述(9)goto (4)(4)j(8)K:=K+1K1K+(7)N:=N+10N10N+(6)M:=M+10M10M+(5)if (100K) goto (9)(9)K100j(4)K:=1K1:=(3)N:=JNJ:=(2)M:=IMI:=(1)注释RESULTARG2A

18、RG1OP序号33v 目标代码产生v 任务： 把中间代码变换成特定机器上的目标代码，依赖于硬件系统结构和机器指令的含义。涉及到硬件系统功能部件的运用、机器指令的选择、存储空间分配和寄存器调度等v 目标代码三种形式： 绝对指令代码 可直接运行 汇编指令代码 需要进行汇编 可重新定位指令代码 需要连接装配2 编译过程概述34v 目标代码产生 可重新定位指令代码 在运行前必须借助一个连接装配程序把各个目标模块（包括系统提供的库模块）连接在一起，确定程序变量（或常数）在主存中的位置，装入内存中指定的起始地址，使之成为一个可以运行的绝对指令代码程序2 编译过程概述模块Aa模块Bb模块Cc模块Aa模块Bb

19、模块Cc模块Aa模块D模块Cc35v 目标代码产生v 举例： b=a+2v 翻译成汇编指令： MOV a，R1 ADD #2，R1 MOV R1，bv 把汇编指令翻译成机器代码： 0001 01 00 00000000 * 0011 01 10 00000010 0100 01 00 00000100 *2 编译过程概述36v 目标代码产生v 把汇编指令翻译成机器代码： 指令字的前4位：指令代码 0001、0011和0100分别代表装入、加和存储 5，6位：01为指定寄存器R1 7，8位：标志位，说明寻址方式 00：直接寻址，后8位为内存地址 10：立即数，后8位为操作数 星号*：重定位标志

20、假设装载起始地址L=00001111，最终目标代码为 0001 01 00 00001111 0011 01 10 00000010 0100 01 00 000100112 编译过程概述37v 上述编译过程的五个阶段是一种典型分法。事实上，并非所有编译程序都分成这五阶段 有些编译程序对优化没什么要求，优化阶段就可以省去 在某些情况下，为了加快编译速度，中间代码产生阶段也可以去掉 有些最简单的编译程序实在语法分析阶段的同时产生代码v 但是，多数实用编译程序的工作过程大致都像上述编译过程的五个阶段2 编译过程概述38v 1 什么叫编译程序v 2 编译过程概述v 3 编译程序结构v 4 编译程序与

21、程序设计环境v 5 编译程序的生成39v 编译程序总框3 编译程序结构四元式单词符号语法单位四元式目标代码词法分析器语法分析器语义分析与中间代码生成器优化段源程序表格管理出错处理目标代码生成器40v 表格与表格管理v 常见的表格： 符号名表，常数表，标号表，入口名表，过程引用表v 格式：v 举例： PASCAL程序段PROCEDURE INCWAP(M，N:INTEGER);LABEL START;VAR K:INTEGER;BEGINSTART: K:=M+1; M:=N+4; N:=K;END.3 编译程序结构名字信息413 编译程序结构v 表格与表格管理423 编译程序结构v 表格与表格

22、管理43v 出错处理v 出错处理程序：发现源程序中的错误，把有关错误信息报告给用户v 语法错误 不符合语法（或词法）规则的错误，在词法分析或语法分析时发现，如： 词法分析阶段检查出：非法字符 语法分析阶段检查出：括号不匹配，缺少“；”等v 语义错误 不符合语义规则的错误，有的可以在语义分析阶段检查出，有的只能在运行时检查出。如：说明错误、作用域错误、类型不一致等3 编译程序结构44v 遍(pass)v 所谓“遍”，就是对源程序或源程序的中间表示从头到尾扫描一次，并完成相应处理，生成新的中间结果或目标程序。v 阶段与遍是不同的概念。一遍可以由若干段组成，一个阶段也可以分若干遍来完成v 词法分析可

23、以单独一遍，但常作为语法分析的子程序，与其安排在同一遍v 可以单遍编译，也可以多遍编译v 允许符号先使用后定义的语言至少需要2遍v 优化层次越深，所需遍数越多v 遍数越多，花的时间就越多3 编译程序结构45v 编译前端与后端v 编译前端： 与源语言有关。如词法分析，语法分析，语义分析与中间代码产生，优化阶段中与机器无关的优化v 编译后端： 与目标机有关。如与目标机有关的优化，目标代码产生v 编译区分前后端的优点： 减少对内存容量的要求，程序逻辑结构清晰 优化更充分，有利于移植v 编译区分前后端的不足： 编译程序运行的效率低3 编译程序结构源语言中间语言目标语言前端后端46v 编译前端与后端v

24、编译区分前后端的优点方便移植： 不同源语言，编译成相同的中间语言，即为不同前端，配以相同的后端，可生成在同一目标机器上的不同语言的编译程序 同一编译程序的前端，配以不同的后端，可生成在不同目标机器上的相同语言的编译程序 如：JAVA语言的操作平台无关性 JAVA定义一种虚拟机代码Bytecode 只要操作平台上实现了执行Bytecode的JAVA解释器，就可以执行各种Java程序3 编译程序结构47v 1 什么叫编译程序v 2 编译过程概述v 3 编译程序结构v 4 编译程序与程序设计环境v 5 编译程序的生成48v 程序设计环境 编辑程序 编译程序 连接程序 调试工具v 集成化的程序设计环境

25、4 编译程序与程序设计环境49v 编译器的上下文环境4 编译程序与程序设计环境预处理器编译器装配/连接器汇编器源程序骨架源程序目标汇编程序可重定位的机器代码绝对机器代码库、可重定位目标文件50v 预处理器的功能 产生编译器的输入 宏扩展 #define PI 3.1415926 加入头文件 如：C语言的#include “理性”预处理器 把现代控制流和数据结构机制添加到比较老式的语言中 语言扩充 通过大量的内部宏定义来增强语言的能力 如：嵌套在C语言中的数据库查询语言Equel4 编译程序与程序设计环境51v .NET Framework与VS.NET4 编译程序与程序设计环境Operating SystemCommon Language RuntimeADO.NET: Data and XMLASP.NET: Web Services & Web FormsWindowsFormsCommon Language SpecificationVisual Stud