编译原理简明教程（第3版）-课件 第9、10章 目标代码的生成、符号表和出错处理

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

免费提供编译原理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．按用途不同寄存器可以分为三类：寄存器作为变址器使有、专供操作系统使用、用于目标代码中存放引用次数最多的变量三类3．讨论了一个计算机模型—虚拟机，并在此基础上讨论了从逆波兰表示生成目标代码及从四元式序列生成目标代码4．存储分配是在目标程序运行阶段进行的5.存储的组织与分配的方式有：静态存储分配、栈式动态存储分配、堆式动态存储分配。35总结

本章我们学习了什么是目标代码的生成、一种计算机模型——虚拟机、从中间代码生成目标代码、目标程序运行时的存储管理等内容。

下一章将学习符号表和出错处理。THANKS36THANKS新工科建设·计算机类系列教材

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

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

并行编译技术第十三章

软件构造382024/11/639学习目标10符号表和出错处理

符号表在整个编译期间的作用主要有两条：一是辅助语义的（即上下文有关的）正确性检查；二是辅助代码生成。着重需要掌握以下内容符号表的作用符号表中的内容嵌套结构语言的栈式符号表

目录10.1符号表的结构与存放10.2符号表的建立10.3程序的错误10.4出错处理10.5本章小结40

符号表是一个包含程序中的变量、子程序、常量、过程定义、数组信息等内容的数据库。

一般地，符号表由一些表项组成二维表格。

名字域

—存放符号或其内部码每个表项

属性域

—存放属性和特征例如：

名字域属性域名字1属性1......名字n属性n10.1符号表的结构和存放符号表的组织方式简单方式：固定名字域和属性域的长度。

有的语言标识符长度不超过6个字符，可定为6位。间接方式：在符号表的名字域中存放一个指针或一个指针和一个整数，把标识符存放到一个字符串数组中。见图10.210.1.1符号表的组织和内容符号表的内容

属性域的内容因符号表名字域内容不同而不同。例如数组：维数、下标界偶、存储区域等信息数组信息向量表。如图10.3。

静态表（编译前事先构造好）：保留字表、标符号表

准函数名表等。

动态表（编译过程中根据需要构造的表）：变量名表数组信息表、过程信息表等。10.1.1符号表的组织和内容变量表

如图10.4线性表(无序符号表):按程序中符号出现的先后次序建立的表。如图10.5查找方式:只能线性查找，(查找效率低)，结构简单，节省空间，适合于比较小的表。10.1.2线性符号表名字类型地址SUM实型100AVER实型102COUNT整型104项数名字域属性域1a……2ave……3b1……4sum……………

有序符号表：按一定顺序(如字典顺序)排列符号。如图10.6、10.7查找:折半查找法,查找效率较高。

但填入表时会增加移动开销。10.1.3有序符号表项数名字域属性域1a……2ave……3b1……4sum……………

散列符号表（哈希符号表）：利用哈希函数值确定符号在表中的位置。hash函数性质：·函数值只依赖于对应符号·函数计算简单、高效·函数值能较均匀分布如:除法散列函数、乘法散列函数、多项式除法散列函数、平方取中散列函数等。“质数除余法”见图10.8查询效率较高，但要解决散列冲突问题。10.1.4散列符号表（哈希符号表）设计一个栈，新符号出现从栈顶压入。查找时从栈顶→栈底例

PASCAL语言分程序嵌套结构例10-1程序的栈式符号表如图10.9、10.10、10.11查找时，最新加入的符号总是最先查找。

适合嵌套结构的程序设计语言，但表太大时，查找速度较慢。10.1.5栈式符号表10.2.1符号表的建立48一、符号表的初始化渐增符号表。如线性符号表和有序符号表

定长符号表。如散列符号表在初始状态时，表的内容都应该为空。一般符号表在词法分析时创建，其它阶段都可能要填表。如图10.12、10.1310.2.2符号表的查填一、对符号表的操作

·对给定符号，查看是否是在表中

·对没查到的符号，向表中填入

·对已查到的符号，查询有关信息

·对已查到的符号，增加或更新有关信息

·删除一个或一组无用表项二、查填符号表的形式可分为两种情况：

1、隐式说明语言的符号表查填如FORTRAN“I–N”规则。语句中每出现一个符号均需查表，当第一次出现时填表。502、显式说明语言的符号表查填如Pascal、C语言

说明部分：出现的符号，先查表，若没有，则填表。语句部分：出现的符号，先查表，若查不到，到外层

查(对于分程序结构)，最后仍未查到，说明该符号未

定义，输出出错信息。10.2.2符号表的查填通常用程序设计语言编写的源程序往往包含一些错误，很少能一次在机器上通过，并算出预期结果，需要反复修改和调试。所以，人们希望编译程序能有较强的错误处理能力，能检查出程序中的各种错误，并准确无误地报告出这些错误的性质和位置。5110.3程序的错误

编译程序用来对源程序进行编译，当程序在语法(包括词法)上正确时，可以得到相应的等价的目标代码。当程序在语义上正确时，以正确的输入数据运行目标代码可以得到预期的输出结果。然而，一个程序，尤其是大型软件的程序，其中难免包含错误。5210.3.1错误存在的必然性5310.3.2错误的种类①词法错误。②语法错误。③语义错误。④违反环境限制的错误。程序错误的种类

在编译的过程中，发现源程序的错误时采取一定的措施，使得能继续编译下去，这称为错误复原。如果把所给不正确程序变换成正确的程序，则称之为错误校正。在错误复原时，应重视以下两个方面： 1.株连信息的遏止。 2.重复信息的遏止。5410.3.3错误复原词法的错误：词法分析时发现的词法错误大多是单词拼写错误语法的错误:不同的语法分析技术发现错误的手段和方式是不同的语义的错误:一般分为两类，一类是在编译时可以发现的静态语义错误，另一类是在运行时才能发现的动态语义错误。5510.4出错处理5610.4.1词法错误的处理

词法分析时发现的词法错误大多是单词拼写错误，这或者是因为书写错误，或者是因为输入错误假定不会有连续几个字符的错误，可以假定有如下几类词法错误：拼错一个字符，如RECORD错写成RCCORD。遗漏一个字符，如RE