编译原理简明教程（第3版）-课件 第9章 目标代码的生成

新工科建设·计算机类系列教材

免费提供编译原理16目录第一章概述第二章形式语言理论基础第三章自动机理论基础第四章词法分析第五章语法分析—自顶向下分析方法第六章语法分析—自底向上分析方法第七章语义分析及中间代码的生成第八章代码优化第九章目标代码的生成第十章符号表和出错处理第十一章

面向对象语言的编译第十二章

并行编译技术第十三章

软件构造22024/11/63学习目标了解和掌握目标代码生成程序中的有关问题了解和掌握虚拟机了解和掌握从中间代码生成目标代码9目标代码的生成重点：虚拟机、目标代码生成难点：从中间代码生成目标代码

目录9.1目标代码生成概述9.2一个计算机模型——虚拟机9.3从中间代码生成目标代码9.4目标程序运行时的存储管理9.5本章小结49.1目标代码生成概述目标代码生成是编译程序的最后一个工作阶段。它取先行阶段所产生的源程序的中间语言或优化后的中间语言表示作为输入，产生等价的目标代码作为输出，如下图所示。9.1目标代码生成概述好的代码生成程序:

生成的目标代码尽可能地短，

能较充分地发挥目标计算机可用资源的效率。熟悉目标机器和它的指令系统是设计一个好的代码生成程序的先决条件，不以某一台具体的计算机做背景，只是针对一个假想的计算机模型——虚拟机给出生成目标代码的算法。9.1.1目标代码的生成7①能够立即执行的机器语言代码，所有地址均已定位。即具有绝对地址的机器语言代码。

②待装配的机器语言模块。需要执行时，由连接装配程序把它们和某些运行程序连接起来，装配成可以执行的机器语言代码。即可浮动的机器语言代码。

代码生成程序的输出的形式一般有以下三种形式：③汇编语言形式的代码。需要经过汇编程序汇编转换成可执行的机器语言代码。9.1.1目标代码的生成8本章采用汇编语言代码作为目标代码，但不针对某种特定的目标机指令系统或汇编语言来生成目标代码，而是假设有一台计算机，其指令系统等均按某种需要而设定，为教学目的往往采取这种虚拟机目标代码形式。下面就以一种虚拟机指令系统来讨论目标代码的生成。9.1.2寄存器分配9

充分利用寄存器对生成高质量目标代码尤其重要。

寄存器的分配成为目标代码生成中的主要问题。

寄存器的分配策略与目标机的资源密切相关。

有些机器中的寄存器分为变址器和数据寄存器，还有些机器的寄存器可以通用。按用途不同，寄存器可分为作为变址器使用、专供操作系统使用、用于目标代码中存放引用次数最多的变量三类。9.1.2寄存器分配操作码操作数1操作数2执行代价OP寄存器寄存器1寄存器内存单元2寄存器寄存器间接地址2寄存器内存间接地址3根据访问内存数来定义每条指令的执行代价，则对于以下的一些操作有其相应的执行代价：

9.2一个计算机模型——虚拟机11

为了使下面的讨论比较简明和具有一般性，出于教学的目的，比较合适的是采取虚拟机目标代码形式，假设在某台虚拟的计算机上分析。9.2.1虚拟机9.2.1虚拟机虚拟机不是一台实际的机器，而是便于讨论的一台假想和抽象的计算机。假设这台虚拟机有如下特性：该虚拟机是一台地址单累加器的计算机，用“AC”表示该累加器；设OP为操作码，d为地址，则指令：

0Pd表示ACOPd=>AC9.2.1虚拟机9.2.2虚拟机的汇编指令1．填地址指令设有一维数组a：array[m..n]ofinteger；其元素有a[m],a[m+1],…,a[i],…,a[n]，一共需要n-m+1个存储单元：<a[m]>，<a[m+1]>，…，<a[i]>，…，<a[n]>一般有存储单元：<a[i]>=<a[m]>+i-m由于<a[0]>=<a[m]-m，所以有<a[m]>=<a[0]>+m。从而对于一维数组的存储单元，有公式：<a[i]>=<a[0]>+i其中<a[0]>称为数组的假头，<a[m]>称为数组的真头。9.2.2虚拟机的汇编指令2．按真转编写程序9.2.2虚拟机的汇编指令3．按假转编写程序9.3.1从逆波兰表生成目标代码例如，对于逆波兰表达式：ab*cd+e/-具体生成目标代码处理过程如表9.2所示。9.3.1从逆波兰表生成目标代码上面首先把简单表达式改造成中间语言的逆波兰形式，然后由逆波兰表达式生成目标代码。实际中也常把两步合为一步，根据运算符优先数的大小关系，直接对简单表达式进行语法语义分析。为了处理简单起见，规定被处理的简单表达式的前后都有特殊符号“#”，即呈下列形式：

#<简单表达式>#并把“#”视为优先数为0的运算符。同时引进运算符栈(栈)与运算分量栈(栈)，相应算法如下。9.3.1从逆波兰表生成目标代码9.3.2从四元式序列生成目标代码例如，对于中缀表达式“#a+(b-c)/d#”运用以上算法直接生成目标代码处理过程如表9.4所示。9.4目标程序运行时的存储管理21

编译程序目的是将源程序翻译成等价的目标程序，为此编译程序在工作过程中，必须为源程序中所出现的一些标识符(如常量、变量及数组等)分配运行时的存储空间。

在程序的执行过程中，程序中数据的存取就是通过对应的存储单元进行的。

对编译程序来说，存储的组织与分配是一个既复杂又十分重要的问题。

9.4.1程序运行时的存储组织

程序在运行时，系统将为其分配一块存储空间，该空间需容纳程序生成的目标代码以及目标代码运行时的各种数据。从用途上来看，存储空间可以划分为几个部分(如图所示)。①目标程序区，用来存放目标代码。②静态数据区，用来存放编译时就能确定存储空间的数据。③运行栈区，用来存放运行时才能确定存储空间的数据。④运行堆区，用来存放运行时用户动态申请存储空间的数据。9.4.1程序运行时的存储组织如果一个程序设计语言允许使用递归过程、可变数组或可变数据结构，那么就需要采用栈式、堆式的动态存储管理技术，程序运行时堆、栈的大小可随程序的运行而改变。图9.2所示为堆、栈共用一空白存储区，并使它们各自的增长方向相对，这样可以充分利用存储空间。编译程序所生成的目标代码的大小在编译时(最迟在连接之后)就可确定，因此编译程序可以把它放在一个静态确定的区域——目标程序区。9.4.2静态存储分配静态存储分配是一种最简单的分配方式。许多早期的程序语言，如Fortran、BASIC和COBOL等，都采用这种静态分配方式。所谓静态存储分配就是在编译时对所有的数据项分配固定的存储单元，且在运行时始终保持不变。具体地说，适用于静态存储分配的程序设计语言必须满足下列条件：不允许过程的递归调用；不允许含可变大小的数据(如数组的上下界必须是常数)；不允许用户动态地建立数据实体(如不允许那些需在运行时动态确定的数据项)。9.4.3栈式动态存储分配如果一个程序设计语言允许使用递归过程、可变数组或可变数据结构，则无法采用静态存储管理方法。因为对于这样的语言来说，程序在编译时无法确定它在运行时所需存储空间的大小，所以在程序运行时只能采用动态存储管理的方式，在程序运行时对存储空间进行动态分配。动态存储分配方式有两种，首先介绍栈式动态存储分配。栈式存储分配策略是将整个程序的数据空间设计为一个栈，每当程序调用一个过程时，就在栈顶为其分配数据空间，当调用结束时，就释放这部分空间。这种方式适用于C、Pascal、ALOGOL、PL/1语言。9.4.3栈式动态存储分配在C、Pascal等语言的实现系统中，使用栈的方式来管理整个过程的活动，为了管理一个过程在一次执行时所需要的信息，常使用一段连续的存贮区，这个存贮区称为活动记录(ActivationRecord，AR)，其结构如图9.5。图9.5活动记录的结构9.4.3栈式动态存储分配1．简单的栈式存储分配有一些语言虽然允许过程递归调用，但是不允许过程嵌套定义，也没有分程序结构，这些语言可以采用一种比较简单的栈式存储分配方式。例如，C语言就是这样一种语言。9.4.3栈式动态存储分配在上述C程序中，若主程序调用了过程P1，P1又调用了P2，那么在P2进入运行后的存储结构如图9.6(a)所示；若主程序调用了过程P2，P2又递归调用自己，在P2过程第二次进入运行后的存储结构如图9.6(b)所示。图9.6C程序的栈式存储分配

在简单栈式存储分配方法中，常用到两个指示器(SP和TOP)指向栈最顶端的数据区，其中SP指向最新的过程活动记录的起点，TOP则指向当前栈的栈顶单元。9.4.3栈式动态存储分配2．嵌套过程语言的栈式存储分配

Pascal等语言的程序结构中允许过程嵌套定义，因此这类语言的存储分配不能运用简单的栈式办法来实现。为了便于讨论，对Pascal语言中的一些数据类型(如“文件”和“指针”等)不予考虑，这样仍然可以采用栈式动态分配策略，只是在过程活动记录中需增加一些内容，用以解决对全局变量的引用问题。首先来看一个省略的Pascal程序，其中包含了该程序中各过程之间的嵌套关系以及各变量的作用域。9.4.3栈式动态存储分配9.4.3栈式动态存储分配讨论两种方法，一种是在过程活动记录中增设存取链(也称静态链)，指向包含该过程的直接外层过程的最新活动记录的地址，其过程活动记录的内容如图9.7所示。

另一种是在建立过程活动记录的同时建立一张嵌套层次显示表display图9.7过程活动记录的结构(嵌套定义过程)图9.9display表和运行栈9.4.4堆式动态存储分配堆式存储分配在运行时动态地进行，它是最灵活也是最昂贵的一种存储分配方式。假设程序运行时有一个大的存储空间，每当需要时就从这片空间中申请一块，不用时再释放给它。由于块可以按任意顺序释放，经过一段运行时间后，堆将被划分成若干块，这些块有些正在使用，是有用块，而有一些块是空闲的，是无用块，如图9.10所示。图9.10堆式存储分配过程中的内存状态9.4.4堆式动态存储分配堆式动态存储管理可以采取多种策略进行。介绍一种使用可利用空间表进行动态分配的方法。可利用空间表是指将所有空闲块用一张表记录下来，表的结构可以是目录表，也可以是链表，如图9.11所示。图9.11内存状态和可利用空间表9.5本章小结341．目标代码生成程序的输入是由先行端产生的源程序的中间代码表示，输出是目标代码2．按用途不同寄存器可以分为三类：寄存器作为变址器使有、专供操作系统使