编译原理第一章2005

《编译原理第一章2005》由会员分享，可在线阅读，更多相关《编译原理第一章2005（19页珍藏版）》请在金锄头文库上搜索。

1、 编译原理上海交通大学张冬茉Email:zhang-2005年2月1课程目的编译原理是计算机专业设置的一门 重要的专业课程。虽然只有少数人 从事编译方面的工作，但是这门课 在理论、技术、方法上都对学生提 供了系统而有效的训练，有利于提 高软件人员的素质和能力。2第一章 引 论 1.1 编译程序是一种特定的翻译程序基本概念:翻译（translation）和翻译程序(translator) ：描述算法的语 言可有很多种，将一种语言写的程序转换成另一种语言写的程 序，这就是翻译（translation），实现这种功能的程序便是翻 译程序(translator)，显然翻译前的程序与翻译后的程序两者应

2、等价。计算（computing）：描述“计算“（computing）过程通常借 助于一种程序设计语言，这种“计算“过程包含了从初始状态转 变为终止状态的一系列的操作。语言:交流的工具 语言的分类:自然语言和人工语言3源程序(source code)和目标程序(object code)：翻译前的程 序为源语言程序，简称源程序(source code)，翻译后的程序 为目标语言程序，简称目标程序(object code)。汇编程序：将可直接执行的机器语言的指令系统符号化， 这便是汇编语言，当然汇编语言程序也必须转换成机器语 言程序才能执行，这种转换程序便是汇编程序(assembly program

3、)。汇编程序也是一种翻译程序。 编译程序(compiler)：将高级语言程序翻译成低级语言程 序，这种翻译程序，便是编译程序(compiler)。显然编译程 序是翻译程序中的一类。 解释程序(interpreter)：解释执行是将源程序中的语句按 动态顺序，逐句逐段翻译成可执行代码，一旦具备执行条 件(获得必要的初始数据等)立即将这一段代码执行得到部 分结果。完成这样功能的程序称为解释程序(interpreter) 4源程序S （以高级语言写） ）目标程序T （以机器语言写） ）计算机编译程序C编译阶段初始数据计算结果计算机目标程序T运行阶段运行系统图1.1 程序的编译执行目标程序T （以汇编

4、语言写） ）目标程序T （以机器语言写） ）计算机汇编程序A图1.2 汇编阶段源程序S （以高级语言写） ）计算结果计算机解释程序I图1.3 程序的解释执行初始数据5如果我们把源程序记为S，目标程序记为T，编译程序记 为C，那么可以将编译看成一个函数,一种映射: T=C(S)61.2 编译程序的结构编译程序将源程序变换成目标程序，这是个复杂的过程，通 常分成五个阶段和两个附加部分：一、词法分析阶段 对组成源程序的字符串进行扫描和识别，识别出一个个具 独立意义的单词(或称符号)，如基本字(if, for, begin等)、标 识符、常数、运算符、界符(括号，=，；等)，将识别出的 单词用统一长度

5、的标准形式(也可称为内部码)来表示，对 以后的变换来说，这种标准形式对区分单词和单词的属性 应是十分方便的。因此词法分析是将字符串变换成单词符 号流。二、语法分析阶段 在词法分析输出的单词流基础上，根据源语言的语法规 则分析这种单词流是否正确地组成了各类语法单位，如 短语、子句、程序段和程序等。例如2*3.1416*R*R是表 达式，单词符号:=后应跟着一个表达式作为赋值语句的 右部等。 7三、语义分析、中间代码生成阶段 经过语法分析的单词流若在语法结构上是正确的，就可 以在这个基础上做实质性的翻译工作，虽然可以直接翻 译成可执行代码(机器语言或汇编语言程序)，但通常是将 单词流翻译成在语义上

6、等价的中间语言程序。中间语言 是介于高级语言和低级语言之间、但并不面向具体机器 、语言结构又十分接近低级语言的一种中间代码形式。 中间语言相对于低级语言而言，既有一定程度的抽象， 又有一定程度的对应。中间语言程序到目标语言的转换 是容易的，因此语义上的等价变换主要在语义分析阶段 进行。其任务是根据语言的语义规则，将语法单位逐一 翻译成中间语言代码，这通常称为是语法制导翻译。8四、优化阶段 前一阶段产生的中间代码是以语法单位这样的局部区间 为单位而产生的，不能保证效率是高的，有必要进行等 价变换，使程序占用空间少，运行时间短。常用的优化 措施有删除冗余运算，删除无用赋值，合并已知量，循 环优化等

7、，有些优化措施效果很明显，例如循环中参于 运算的运算量，如其值并不随着循环而发生变化，这类 运算称为循环不变运算，它完全不必每次循环都计算一 次，将它们提到进入循环前计算一次即可。9五、目标代码生成阶段 将中间代码转换成机器语言程序或汇编语言程序，最后完 成了翻译，这阶段的工作因为目标语言的关系而十分依赖 于硬件系统，如何充分利用寄存器、合理选择指令、生成 尽可能短而有效的目标代码，都与目标机的结构有关。 生成的目标代码如果是汇编语言程序，则需经由汇编程序 汇编后才能执行。生成的目标代码如果是绝对指令代码， 则已可直接投入运行。如果是可重定位的指令代码，那么 目标代码只是一个代码模块，必须由连

8、接装配程序，将输 入/输出模块，标准函数等系统模块与目标代码模块连接在 一起，确定数据对象和各程序点的位置(即代真)才可能形 成一个绝对指令代码程序供运行。10以上五个阶段反映了编译程序的动态特征，但编译的实现还有赖于 符号表管理和出错管理。六、符号表管理 源程序中的有关数据对象的信息和程序信息是编译各阶段 要经常使用的，因此编译程序中还应包括一个符号表管理 程序，它涉及到符号表的构造，查询和更新等各种操作， 提供用户命名的标识符的各种属性、存储位置、类型、作 用域等信息，对这些信息的操作，是频繁的，占了编译时 间的很大一个比例，因此符号表的结构，符号表上各种操 作的算法必须精心设计。11七、

9、出错管理程序 编译的各个阶段都可能遇到错误。出错管理程序应在发现 错误后，将错误的有关信息如错误类型、错误地点向用户 报告。为了尽可能多地发现错误，在发现了错误后还应继 续编译下去，因此要设法将错误造成的影响限制在尽可能 小的范围中，发现错误后能自动校正错误当然最好，只是 在大部分情况下，校正的代价太大，而且效果也未必尽如 人意。 12符号表管理器词法分析器语法分析器语义分析、中间代码生成器优化目标代码生成器出错管理器单词流语法单位中间代码序列中间代码序列目标程序源程序字符串图1.4 编译程序总框图13编译阶段的前端和后端编译的前三个阶段(词法分析、语法分析、语义分析和中 间代码生成)称为编译

10、的前端。它其实还可分成分析(词 法分析、语法分析、语义分析)和综合(代码生成)两个过 程。而目标代码生成则是编译的后端。中间代码的优化 可归入前端。很明显编译后端是面向目标语言的，而编 译前端则不是，它几乎独立目标语言。遍 在编译过程中，从头至尾地扫描一个输入文件，经过程 序变换形成一个输出文件，这个过程称为编译的一遍。 编译过程一般可用两遍或三遍完成。141.3 编译程序的生成一个编译系统的构造并非易事，现在有各个层次的生成 工具： lex、 yacc、 make要构造一个完全独立的全新的编译器可能性很小，大部 分可在现有编译器的基础上扩展： 自展的方式， 移植的方式。15自展 一个编译程序

11、一般涉及三种语言： 语言I，称它为编译的实现语言 源语言 S， 目标语言T 对一个相当规模的语言L，想用目标语言在目标机A上 构造一个编译程序是十分困难的。为此，我们首先可 以选择L的一个子集S，子集的规模只要达到具有足够 的描述能力即可。相对而言于L而言，S的编译程序就 容易写得多，不妨认为它可以用手工完成。 第二步，我们可以用S语言来写一个L A的编译程序，相 对于A语言来说，用S语言写这样的编译程序也会容易得多 。然后将这个S语言的程序作为S A的编译程序的输入。 其输出当然是A语言的程序，并且由于保证这种变换的等 价性，因此输出程序将保持输入程序的功能，即将L语言 程序等价变换成A语言

12、程序，故输出程序是一个A语言书 写的程序，其功能为将L语言程序等价变换成A语言的程序 ，即L A的编译程序，这便是我们所要求的 16移植 已有L语言在A机器上的编译器，想借助于它 ，得到L语言在B机器上的编译器，这便是移 植。也即将A机器上的L语言的编译移植到B机 器上。 做法是：首先用L语言写一个L B的编译程序 ，将这个L语言程序作为L语言在A机器上的编 译器的输入，输出为用A语言写的将L语言翻 译成B语言上的编译器 这种在A机器上生成B机器的目标代码的编译 称为交叉编译 。 第二步将用L语言写一个L B的编译程序作为 交叉编译的输入，其输出即为所求。 17对编译程序的评价正确性:即源程序

13、到目标程序变换的等价性。 生成目标质量:这主要用目标代码运行时间的长短，占用 空间的大小来评定。 编译程序本身的质量:这主要用编译速度的快慢，编译占 用空间的大小，以及编译程序本身的结构是否良好，可读 性、可维护性如何来评定。 要提高目标程序的质量，所选择的编译的方法，算法当然 很重要，特别优化是不容忽视的，但是提高目标程序质量 的种种措施都是需要代价的，它们会影响编译程序本身的 质量，这两方面的要求应有所权衡。需要指出的是片面追 求目标质量而忽视编译本身的质量，以致要花很长时间才 能将一个源程序编译成目标程序，这样会使用户失去信心 。另外编译程序的可移植性与可维护性也应重视181.4 编译程序的学习编译课程中所介绍的一些原理和方法、算法并不局限于编 译。有限自动机的原理，形式描述的方法，自动生成的方 法，数据流和控制流分析的方法等对提高一个软件人员的 素质是极为有益的。而且对一个大型的复杂的软件的构造 过程，编译提供了一个具体的实例，这也是对软件人员的 一个重要的能力训练。何况或多或少地做些解释、翻译工 作的可能是始终存在的。 编译程序是一个系统性很强的软件。在课程中我们按阶段 地进行讨论，但在学习这些内容时读者心中一定要有系统 的概念，才不致将所学的内容孤立化。因此建议读者找一 个小型的语言，尝试用学过的方法，自行组织构造一个编 译程序，这对融会贯通这些内容是有益的。19