编译原理第10章-目标代码生成
- 格式：pptx
- 大小：655.21 KB
- 文档页数：21
下载文档原格式
合集下载
编译原理目标代码生成
中间代码生成
探讨中间代码的概念、作用和生成方法，包括抽象语法 树、三地址代码等中间表示形式。
代码优化
介绍代码优化的原理和常用技术，如常量折叠、复制传 播、死代码删除等，以提高目标代码的质量。
目标代码生成
详细讲解目标代码生成的过程和方法，包括指令选择、 寄存器分配、汇编语言输出等关键步骤，以及针对不同 目标平台的优化策略。
语义分析
介绍了语义分析的基本任务，如类型 检查、控制流分析、数据流分析等。
中间代码生成
阐述了中间代码的概念、作用及生 成方法，包括抽象语法树、三地址 代码等。
目标代码生成
详细讲解了目标代码生成的过程， 包括指令选择、寄存器分配、优化 等。
对未来编译技术的展望
智能化编译技术
随着人工智能技术的发展，未来编译器可能具备更强的自 主学习能力，能够自动优化代码性能、提高编译效率。
01
指令选择算法
根据目标计算机的指令集和程序语义， 选择最合适的指令来实现程序功能。
02
03
代码优化算法
通过对生成的机器相关代码进行各种 优化（如常量折叠、循环展开等）， 提高其执行效率和资源利用率。
06
代码生成器的设计与实现
代码生成器的结构
中间代码生成器
将源程序转换为中间代码形式，便于后续优化和代码生成。
2
编译过程包括词法分析、语法分析、语义分析、 中间代码生成、代码优化和目标代码生成等阶段。
3
编译原理不仅关注如何生成高效的目标代码，还 关注如何提高编译器的可维护性、可移植性和可 扩展性。
目标代码生成的意义
提高程序执行效率
目标代码是计算机直接执行的指令，其执行效率远高于高级语言程序。通过优化目标代码 ，可以提高程序的执行速度。
计算机基础知识点编译原理代码生成
计算机基础知识点编译原理代码生成编译原理是计算机科学中非常重要的一门学科，它研究的是如何将高级语言编写的程序转化为机器可以执行的指令序列。
在编译过程中，代码生成是其中一个关键的步骤。
本文将介绍编译原理中的代码生成基础知识点。
一、代码生成概述代码生成是编译过程中的最后一个阶段，它的任务是将中间表示形式（如抽象语法树或中间代码）转化为目标机器代码，使得程序可以在计算机上运行。
代码生成的目标是产生高效且正确的机器指令序列，以最大程度地利用计算机的硬件资源。
代码生成的过程可以分为以下几个步骤：1. 寄存器分配：将变量和临时值分配到计算机的寄存器中，以便在指令中进行操作。
2. 指令选择：根据中间表示的特点和目标机器的指令集，选择适当的机器指令来实现所需的操作。
3. 指令调度：对指令进行重新排序，以减少指令相关性和提高执行效率。
4. 内存分配：将变量和临时值存储到内存中，以便在需要时可以进行访问。
5. 代码优化：对生成的机器指令进行优化，以减少执行时的开销和资源占用。
二、寄存器分配在代码生成的过程中，寄存器分配是一个非常重要的环节。
寄存器是计算机中的一种高速存储设备，可以用于存储和执行指令操作。
在生成的机器代码中，寄存器通常用于存储临时值和计算结果。
寄存器分配的目标是将变量和临时值存储到寄存器中，并进行相应的寄存器的分配和释放。
常见的寄存器分配算法有线性扫描分配算法、图着色分配算法等。
寄存器分配算法的选择通常取决于目标机器的寄存器数量和寄存器之间的互斥关系。
三、指令选择指令选择是代码生成的关键一环，它的任务是根据中间表示和目标机器的指令集，选择合适的机器指令来实现所需的操作。
指令选择的准则通常是从操作数和操作符的角度考虑，以及考虑目标代码的执行效率和可读性。
指令选择的过程中，需要考虑目标机器的指令格式、寻址方式、寄存器约束等因素。
对于一些特殊的操作，如函数调用、跳转指令等，还需要考虑目标代码的控制流程和程序执行的正确性。
优化和目标代码生成(PPT课件)
• 代码优化在整个编译过程的位置
源程序 编译前端 中间代码 中间代码生成 中间代码 目标代码生成 目标程序 中间代码 中间代码优化 目标代码优化
程序员和编译器可能改上程序的位置
源程序 编译前端 中间代码 目标代码生成 目标程序
程序员可以改进 算法，改变循环
编译器可以改进过程调 用、循环和地址计算
编译器可以利用寄存器， 选择指令和窥孔优转换
3
7.1.1 数据类型
类型的合法性检查是判断数据类型是否与上下文的要求一致 数据类型是对该类型数据（变量或常量）的取值是否合法以 及对该类型数据的运算是否合法的一种说明。
4
7.1.2 数据结构
一个程序设计语言如允许使用的数组、记录、字符串、 表、栈等形式的数据结构，在编译程序中应为它们提供相 应的翻译。 为了能对数据结构中的元素进行引用，必须完成从逻辑结 构到能够访问这些数据元素的物理结构的映射。应考虑： １映射算法相对简单，根据逻辑结构容易计算出物理地址 ２从逻辑结构投影到物理结构时，不至于超界或存储溢出 ３使用的数据结构承担这种程序设计语言的主要功能 ４在这些数据结构定义相关的运算
25
• 指令选择
– 一个编译程序可以看成是一个转换系统，它把源程序转换成 等价的目标代码，也就是说，对源语言种各种语言结构，依 据语义确定相应的目标代码结构，即确定源语言于目标语言 之间的对应关系，确保正确实现语义。显然，能否建立这样 的关系直接影响到编译程序的质量。 – 目标机器指令系统的性质决定了指令选择的难以程度，指令 系统的一致性和完备性直接影响到这种对应关系的建立。如 果目标机器能一致地支持各种数据类型和寻址方式，不需特 别处理例外，这种对应关系的建立就容易得多。 – 指令执行速度和机器特点对产生目标代码的质量也十分重要。 显然，如果指令集合丰富的目标机器对于某种操作可提供集 中处理的时候，应该选择效率高、执行速度快的一种。
编译原理作业参考答案
（2）
最左推导：NNDDD3D34
NNDNDDDDD5DD56D568
最右推导：NNDN4D434
NNDN8ND8N68D68568
2*．写出一个文法，使其语言是奇数集，且每个奇数是不以0开头。
答：
SCAB|B（考虑了正负号）
A1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | AA | A0 |
低级语言：机器语言和汇编语言。
高级语言：是人们根据描述实际问题的需要而设计的一个记号系统。如同自然语言（接近数学语言和工程语言）一样，语言的基本单位是语句，由符号组和一组用来组织它们成为有确定意义的组合规则。
翻译程序:能够把某一种语言程序（源语言程序）改变成另一种语言程序（目
标语言程序），后者与前者在逻辑上是等价的。其中包括：编译程序，解释程序，汇编程序。
{2,4}a = {1,0}，{2,4}b = {3,5}，无需划分
{3,5}a = {3,5}，{3,5}b = {2,4}，无需划分
{0,1}a = {1}，{0,1}b = {2,4}，无需划分
因此，最终的划分为：{0,1}、{2,4}和｛3,5｝，化简后的结果：
5．（P65，14）构造一个DFA M，它接受={0，1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。
T*(i+i)F*(i+i)i*(i+i)
⑵构造语法树
E最左推导构造语法树
E + T
E + T i
T i
i
3.（P36, 9）证明下面的文法是二义的：
SiSeS | iSi
答：对于句子iiiei有两棵不同的语法树。因此该文法是二义的。
SiSeSiiSeSiiieSiiiei
最左推导：NNDDD3D34
NNDNDDDDD5DD56D568
最右推导：NNDN4D434
NNDN8ND8N68D68568
2*．写出一个文法，使其语言是奇数集，且每个奇数是不以0开头。
答：
SCAB|B（考虑了正负号）
A1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | AA | A0 |
低级语言：机器语言和汇编语言。
高级语言：是人们根据描述实际问题的需要而设计的一个记号系统。如同自然语言（接近数学语言和工程语言）一样，语言的基本单位是语句，由符号组和一组用来组织它们成为有确定意义的组合规则。
翻译程序:能够把某一种语言程序（源语言程序）改变成另一种语言程序（目
标语言程序），后者与前者在逻辑上是等价的。其中包括：编译程序，解释程序，汇编程序。
{2,4}a = {1,0}，{2,4}b = {3,5}，无需划分
{3,5}a = {3,5}，{3,5}b = {2,4}，无需划分
{0,1}a = {1}，{0,1}b = {2,4}，无需划分
因此，最终的划分为：{0,1}、{2,4}和｛3,5｝，化简后的结果：
5．（P65，14）构造一个DFA M，它接受={0，1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。
T*(i+i)F*(i+i)i*(i+i)
⑵构造语法树
E最左推导构造语法树
E + T
E + T i
T i
i
3.（P36, 9）证明下面的文法是二义的：
SiSeS | iSi
答：对于句子iiiei有两棵不同的语法树。因此该文法是二义的。
SiSeSiiSeSiiieSiiiei
编译原理中的目标代码生成与优化
编译原理中的目标代码生成与优化编译原理是计算机科学中的一门重要课程，它研究的是将高级程序语言转化为机器语言的过程。
目标代码生成与优化是编译过程中的两个关键环节，本文将就这两个方面展开讨论。
一、目标代码生成目标代码生成是编译过程中的最后一步，它的任务是将中间代码转化为能够在目标机器上执行的机器代码。
目标代码生成的质量直接影响程序的执行效率和占用的存储空间。
1. 寄存器分配在进行目标代码生成之前，我们需要进行寄存器分配。
寄存器分配的目的是将中间代码中的临时变量分配到机器寄存器中，减少内存读写操作，提高程序的运行速度。
常用的寄存器分配算法有线性扫描算法和图着色法。
2. 目标代码生成技术目标代码生成的技术有很多，下面列举几种常见的技术：(1) 直接生成代码：直接将中间代码翻译为目标机器的指令序列。
这种方法简单直接，但生成的目标代码质量一般较低。
(2) 间接生成代码：先将中间代码翻译为一个中间形式，再将中间形式转化为目标机器的指令序列。
这种方法可以进行一些优化，生成的目标代码质量较高。
(3) 使用代码模板：事先定义一些目标机器的指令模板，并根据中间代码的特征选择合适的指令模板来生成目标代码。
这种方法可以充分利用目标机器的特性，生成的目标代码效率较高。
二、目标代码优化目标代码优化是指对生成的目标代码进行一系列的优化，以提高程序的运行效率和减少代码的空间占用。
1. 基本块优化基本块是由顺序执行的指令组成的，没有前驱指令和后继指令的指令序列。
基本块优化的目的是对基本块中的指令进行优化，以减少执行时间和空间开销。
常见的基本块优化技术有死代码删除、常量传播等。
2. 寄存器优化寄存器是计算机中的一块高速存储器，能够提供快速的数据访问速度。
寄存器优化的目的是将变量尽可能地存放在寄存器中，以减少内存读写操作，提高程序的执行效率。
常用的寄存器优化技术有寄存器分配、寄存器重命名等。
3. 循环优化循环是程序中的重要结构之一，对循环进行优化可以显著提高程序的执行效率。
程序设计语言编译原理第三版第10章
§10.2 局部优化
举例:考察下面的三地址代码程序
（1）Read X
（2）Read Y
B1
（3）R:=X mod Y （4）if R=0 goto (8) B2
（5）X:=Y
（6）Y:=R
B3
（7）goto(3)
（8）write Y B4
（9）halt
B1
B2
B3
B4
§10.2 局部优化
3.流图及其生成
标识符(包括常数)-结点 NODE(A)-描述上述对应关系的函数,其值或者是一个结点的编号,
或者无定义
(2)中间代码的三种形式:A:=B A:=op B A:=B op C 或 A:=B[C]
(3)构造算法: ①开始,DAG为空 ②对基本块中每一条中间代码式,依次执行以下步骤:
§10.2 局部优化
步骤: 1.如果NODE(B)无定义,则构造一标记为B的叶结点并定义
NODE(B)为这个结点 如果当前代码是0型,则记NODE(B)的值为n,转4 如果当前代码是1型,则转2(1) 如果当前代码是2型,则(ⅰ)如果NODE(C)无定义,则构造一标 记
为C的叶结点并定义NODE(C)为这个结点;(ⅱ)转2(2)
(1)T0:=3.14 (2)T1:=2*T0 (3)T2:=R+r (4)A:=T1*T2 (5)B:=A (6)T3:=2*T0 (7)T4:=R+r (8)T5:=T3*T4 (9)T6:=R-r (10)B:=T5*T6
(4)代数变换
§10.2 局部优化
二、基本块的DAG表示及其应用
1.基本块的DAG:
一种结点带有下述标记或附加信息的DAG
(1)图的叶结点以一标识符(变量名)或常数作为标记,表示该 结点代表该变量或常数的值。
编译原理 目标代码生成 流程代码解析
N
将栈中元素存到数 组，出栈
目标代码生成流程图：
6
开始 扫描逆波兰式
结束
Y
逆波兰式扫
描完
N
滤掉逆波兰式中 逗号
当前字符串为是否 不为运算分量,逗号
Y
当前字符存入数 组
Y N
当前字符串为是 否不为运算分量
N
当前字符串是 否为运算分量
N是否为寄存器， 用@等字符代表寄存器
MOV
传送字或字节.
算术运算指令
ADD
加法
算术运算指令
SUB
减法
算术运算指令
MUL
无符号乘法
算术运算指令
DIV
无符号除法
……
……
……
5. 实验代码
/******************************************************************************/ #include<iostream> #include<string> #include<stack> using namespace std; string temp1(8,0),temp2(8,0),value1; /******************************************************************************/ bool Ispair(string expre) { bool flag=true; stack<char> s; for(int i=0;i<expre.length();i++) { if(expre[i]=='(') s.push(expre[i]); if(expre[i]==')') { if(s.empty()) { flag=false; return flag; }
编译原理-第十章--代码优化
第十章代码优化某些编译程序在中间代码或目标代码生成之后要对生成的代码进行优化。
所谓优化，实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加大或占用存储空间少，或两者都有。
优化可在编译的不同阶段进行，对同一阶段，涉及的程序范围也不同，在同一范围内，可进行多种优化。
一般，优化工作阶段可在中间代码生成之后和（或）目标代码生成之后进行。
中间代码的优化是对中间代码进行等价变换。
目标代码的优化是在目标代码生成之后进行的，因为生成的目标代码对应于具体的计算机，因此，这一类优化在很大程度上依赖于具体的机器，我们不做详细讨论。
另外依据优化所涉及的程序范围，又可分为局部优化、循环优化和全局优化三个不同的级别。
局部优化指的是在只有一个入口、一个出口的基本程序块上进行的优化。
循环优化对循环中的代码进行的优化。
全局优化是在整个程序范围内进行的优化。
本章重点：局部优化基本块的DAG表示第一节优化技术简介为了说明问题，我们来看下面这个例子，源程序是：P :=0For I :=1 to 20 doP :=P+A[I]*B[I];经过编译得到的中间代码如图10-1-1所示，这个程序段由B1和B2两个部分组成，B2是一个循环，假定机器按字节编址。
那么，对于这个中间代码段，可进行如下这些优化。
1、删除多余运算（删除公共子表达式）优化的目的在于使目标代码执行速度较快。
图10-1-1中间代码（3）和（6）中都有4＊I的运算，而从（3）到（6）没有对I赋值，显然，两次计算机的值是相等的。
所以，（6）的运算是多余的。
我们可以把（6）变换成：T4 :=T1。
这种优化称为删除多余运算或称为删除公共子表达式。
2、代码外提减少循环中代码总数的一个重要办法是代码外提。
这种变换把循环不变运算，即其结果独立于循环执行次数的表达式，提到循环的前面。
使之只在循环外计算一次，上例中，我们可以把（4）和（7）提到循环外。
经过删除多余运算和代码外提后，代码变成图10-1-2。
编译原理第十篇目标代码生成
2020/12/4
过程、函数调用语句的翻译
• 过程、函数调用语句 (CALL , f , —, t ) 1. 生成填写变量访问环境指令 2. 把机器状态(寄存器内容)保存到活动记录的机 器状态区中,一般应生成一组存的指令 3. 要填写管理信息.首先填写过程层数.从过程f的 语义信息中取其层数,填入到2（top）中,生成指令 为 LD R , sem[f].level ST 2(top), R
// A+4
8. 如果是函数调用，则把函数值读到寄存器中
LD R ， 4(top)
// A+5
ST t , R
2020/12/4
LD R , A OUT R
2020/12/4
条件语句四元式的翻译
• （THEN, t,_ , _）生成的目标代码为： LD R , t JUMP0 R , __
• （ELSE,_,_,_）生成的目标代码为： JMP __ 同时回填JUMP0指令的目的地
址 • （ENDIF,_,_,_）不产生目标代码，只负
(＋,a,b,t1) LD R a; Add R b (*,X,t1,t2) ST R t1; Mult R X (*,t2,Y,t3) Mult R Y (*,t3,t1,t4 Mult R t1 )
输入/输出语句的翻译
• 输入语句：（READ， A ）
IN R ST A , R
• 输出语句：（WRITE，A ）
第十章 目标代码生成
目标代码
虚拟目标代码：虚拟机上的目标程序。 在本地机器上具备虚拟机的解释器。
实际目标代码：实际机器上的指令序列 绝对地址机器代码： 可重定位的机器代码： 汇编代码：
三种硬件地址模式
指令格式：
过程、函数调用语句的翻译
• 过程、函数调用语句 (CALL , f , —, t ) 1. 生成填写变量访问环境指令 2. 把机器状态(寄存器内容)保存到活动记录的机 器状态区中,一般应生成一组存的指令 3. 要填写管理信息.首先填写过程层数.从过程f的 语义信息中取其层数,填入到2（top）中,生成指令 为 LD R , sem[f].level ST 2(top), R
// A+4
8. 如果是函数调用，则把函数值读到寄存器中
LD R ， 4(top)
// A+5
ST t , R
2020/12/4
LD R , A OUT R
2020/12/4
条件语句四元式的翻译
• （THEN, t,_ , _）生成的目标代码为： LD R , t JUMP0 R , __
• （ELSE,_,_,_）生成的目标代码为： JMP __ 同时回填JUMP0指令的目的地
址 • （ENDIF,_,_,_）不产生目标代码，只负
(＋,a,b,t1) LD R a; Add R b (*,X,t1,t2) ST R t1; Mult R X (*,t2,Y,t3) Mult R Y (*,t3,t1,t4 Mult R t1 )
输入/输出语句的翻译
• 输入语句：（READ， A ）
IN R ST A , R
• 输出语句：（WRITE，A ）
第十章 目标代码生成
目标代码
虚拟目标代码：虚拟机上的目标程序。 在本地机器上具备虚拟机的解释器。
实际目标代码：实际机器上的指令序列 绝对地址机器代码： 可重定位的机器代码： 汇编代码：
三种硬件地址模式
指令格式：
2021-2022学年编译原理之目标代码生成(2)
⑴(> a(y) b(y) t1(y)) ①LD R,a ②GT R,b
⑵(if t1(n) _ _ ) ③FJ R,? ⑨
RDL SEM t1
③
⑶(+ a(y) b(y) t2(y)) ④LD R,a ⑤ADD R,b t2
⑷(* t2(n) c(y) x(y)) ⑥MUL R,c
x
⑸(el _ _ _ ) ⑦ST R,x ⑧JMP_,? 15
【习题9.5】简要叙述代码生成器(控制器)的过程； 【习题9.6】已知下列语句：
if(a+b<c) x=(a+b)/(c-d)+(a+b); ※ 试分别解答：
⑴ 写出优化的四元式序列； ⑵ 标记变量的活跃信息； ⑶ 描述单寄存器R下的目标代码生成过程。
※ 条件语句的四元式结构：
设 条件语句： if（E）S1 ; else S2 ;
⑹(+ t4(n)t5(n) x(y))
注
…
需要随时观察寄存器状态 ！
①LD R,a ②ADD R,b
③ST R,t1 ④LD R,c ⑤SUB R,d
⑥MUL R,t1 ⑦ ST R,t3 ⑧LD R,a ⑨SUB R,t3 ⑩ST R,t
11 LD R,t1 12 DIV R,2 13 ADD R,t4
译
⑹(* a(y) b(y) t3(y))
过
⑺(- 5 t3(n) x(y))
程
⑻(ie _ _ _ ) 注 需要及…时处理跳转地址返填 ！
①LD R,a ②GT R,b
待返 填1
③FJ R,⑨？ ④LD R,a ⑤ADD R,b
⑥MUL R,c ⑦ST R,x ⑧JMP_,1？5 ⑨ LD R,a ⑩MUL R,b
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
变量是否在寄存器中： 变量的现行值是否在内存中：
变量的值在其后是否还使用： 变量的下次引用距离：
状态描述形式（DL, SNS）
DL: 如果从下一位置开始，到变量A重新被赋值或基本 块结束，没有A的当前值的引用，则定义当前该变量的 DL为D;否则定义为L。表示此后变量的状态。 SNS: 如果A的值在寄存器但不在内存，而且当该寄存 器被剥夺时需要保存变量的值，则当前该变量的SNS的 值为S(Store)，否则取NS。
第十章 目标代码生成
目标代码 临时变量的存储空间分配 寄存器的分配和释放 基于三地址中间代码的目标代码生成
目标代码生成概述
目标代码生成器的输入和输出
输入：中间代码/TokenList+[符号表] 输出：
• 绝对机器代码：执行速度快，缺乏灵活性 • 可重定位机器代码：可分模块编译，需连接和装入 • 汇编代码：必须经过汇编程序汇编
循环语句的翻译
（WHILE,_,_,_）不产生目标代码，只用来标记 while语句的入口地址，将地址A入栈S;
（DO , t ,_ ,_）产生的目标代码为： LD R , t JUMP0 R , _
按共享法静态分配：
先计算出临时变量的空间，在过程调用时和源变量 一起申请空间。即调用时将临时变量安排在AR中
临时变量的静态分配
定值点：如果i中间代码给临时变量T定值， 则称i为临时变量T的定值点。
引用点：如果j中间代码使用T，则称j为T的 引用点。
活动区间：如果i是T的定值点，j是T的最后 引用点，则称[i, j]是T的活动区间。
的寄存器
四元式到目标代码的翻译
翻译过程：从头到尾逐条扫描四元式，每扫描完一条四元式就把它 翻译成对应的目标代码(一条四元式可能会对应若干条目标指令)
限定条件：目标机只有一个寄存器、不考虑效率、当前地址为A
表达式和赋值语句的翻译
表达式四元式：形如（Op，A，B，T）： 汇编指令：LD R，A； Op R，B;
从Source 读出送入R Source op R结果 送入R R的内容送入Target
三种硬件地址模式
硬件地址模式：#c d(R) R
指令格式：
Op #C R
----立即式 ----变址式 ----寄存式
（立即-பைடு நூலகம்---寄存器）
Op d(R1) R2 （存储器-----寄存器）
Op R1 R2
（寄存器-----寄存器）
Load A，B Op B，R 时： 把T(L, NS) 加入R的状态表中，从R中删除A项 申请寄存器时R的状态表为空，释放时表也为空 （可能生成一些store指令）。
寄存器的分配
分配原则：选择代价最小的寄存器 寄存器的选择代价：Store代价、Load代价
把寄存器中的现行值回送内存的Store指令总代价； 由于寄存器被剥夺，下次重新装入寄存器的Load指令 的总代价； 如果申请到的是未分配过的新寄存器，则代价为0。 释放代价： X (D, NS) ----0 X(D, S) ----0 X(L, NS) ----2 X(L, S) ----4 分配算法： 选择最小释放代价，下次引用距离最远
输出语句四元式形如：(WRITE,A,-,-） 汇编指令：LD R , A； OUT R
条件语句四元式的翻译
（THEN, t,_ , _）生成的汇编代码为： LD R，t JUMP0 R，__
（ELSE,_,_,_）生成的汇编代码为： JMP __ 同时回填JUMP0指令的目的地址
（ENDIF,_,_,_）不产生目标代码，只负责完成ELSE子句的地址 回填工作 。
活动区间[i, j]和[m, n]不严格相交：如果mj或i n。 空间分配：
如果两个临时变量的活动区间不严格相交，则可以 共享单元
例：
T1 T2
T3 T4
T5
Offset = m Offset = m+1
Offset = m+1 Offset = m Offset = m+1
变量的状态描述
变量：源变量和临时变量 描述内容：
几个常见指令的含义 ：
Load Source R
从Source 读出送入R
Op Source R Source op R结果 送入R
Store Target R R的内容送入Target.
临时变量
特点： 寿命短； 一次定义一次使用 存储空间分配：尽可能采用共享办法
随用随分配的动态分配：
调用一个过程时，分配一个新的AR空间(不包括临 时变量部分)，每当要保存一个临时变量时，动态 分配到栈区的可用单元中
寄存器
寄存器的分类：
可分配寄存器 保留寄存器 零用寄存器
寄存器的使用准则：
寄存器先行准则 寄存器活跃准则 寄存器多载准则
寄存器的状态描述：
占有该寄存器的所有变量状态描述的集合。
寄存器的状态变化
如果现行值已在内存中，则不需回送 现行值不在内存，但该值没有下次引用。不需回送
生成代码 Load B, R 时：构造R:{B(L/D, NS)} 生成(Op , A, B, T)的目标代码为：
衡量目标代码质量的标准
在保证语义相等的情况下，生成的目标指令的条数越少和执行速度越快
虚拟机
指令格式为：op destination source
其中destination和source不能同为存储字
虚拟机的寻址方式和相应的汇编语言表示形式
虚拟机的指令系统
LD R，Source Op R，Source ST Target，R
ST T, R 赋值语句四元式：形如(ASSIG,A,-，B)：
汇编指令：LD R，A； ST B，R
例：Z:= X*(a+b)* Y* (a+b)
(ADDI,a,b,t1)
LD R，a; Add R，b; ST t1,R
(MULTI,X,t1,t2) LD R,t1; MUlT R,X; ST t2,R
(MULTI,t2,Y,t3) LD R,t2; MUlT R,Y; ST t3,R
(MULTI,t3,t1,t4) LD R,t3; MUlT R,t1;ST t4,R;
(ASSIG,t4,-,Z) LD R, t4; ST Z,R
输入/输出语句的翻译
输入语句四元式形如：(READ, A,-,-） 汇编指令：IN R； ST A , R
变量的值在其后是否还使用： 变量的下次引用距离：
状态描述形式（DL, SNS）
DL: 如果从下一位置开始，到变量A重新被赋值或基本 块结束，没有A的当前值的引用，则定义当前该变量的 DL为D;否则定义为L。表示此后变量的状态。 SNS: 如果A的值在寄存器但不在内存，而且当该寄存 器被剥夺时需要保存变量的值，则当前该变量的SNS的 值为S(Store)，否则取NS。
第十章 目标代码生成
目标代码 临时变量的存储空间分配 寄存器的分配和释放 基于三地址中间代码的目标代码生成
目标代码生成概述
目标代码生成器的输入和输出
输入：中间代码/TokenList+[符号表] 输出：
• 绝对机器代码：执行速度快，缺乏灵活性 • 可重定位机器代码：可分模块编译，需连接和装入 • 汇编代码：必须经过汇编程序汇编
循环语句的翻译
（WHILE,_,_,_）不产生目标代码，只用来标记 while语句的入口地址，将地址A入栈S;
（DO , t ,_ ,_）产生的目标代码为： LD R , t JUMP0 R , _
按共享法静态分配：
先计算出临时变量的空间，在过程调用时和源变量 一起申请空间。即调用时将临时变量安排在AR中
临时变量的静态分配
定值点：如果i中间代码给临时变量T定值， 则称i为临时变量T的定值点。
引用点：如果j中间代码使用T，则称j为T的 引用点。
活动区间：如果i是T的定值点，j是T的最后 引用点，则称[i, j]是T的活动区间。
的寄存器
四元式到目标代码的翻译
翻译过程：从头到尾逐条扫描四元式，每扫描完一条四元式就把它 翻译成对应的目标代码(一条四元式可能会对应若干条目标指令)
限定条件：目标机只有一个寄存器、不考虑效率、当前地址为A
表达式和赋值语句的翻译
表达式四元式：形如（Op，A，B，T）： 汇编指令：LD R，A； Op R，B;
从Source 读出送入R Source op R结果 送入R R的内容送入Target
三种硬件地址模式
硬件地址模式：#c d(R) R
指令格式：
Op #C R
----立即式 ----变址式 ----寄存式
（立即-பைடு நூலகம்---寄存器）
Op d(R1) R2 （存储器-----寄存器）
Op R1 R2
（寄存器-----寄存器）
Load A，B Op B，R 时： 把T(L, NS) 加入R的状态表中，从R中删除A项 申请寄存器时R的状态表为空，释放时表也为空 （可能生成一些store指令）。
寄存器的分配
分配原则：选择代价最小的寄存器 寄存器的选择代价：Store代价、Load代价
把寄存器中的现行值回送内存的Store指令总代价； 由于寄存器被剥夺，下次重新装入寄存器的Load指令 的总代价； 如果申请到的是未分配过的新寄存器，则代价为0。 释放代价： X (D, NS) ----0 X(D, S) ----0 X(L, NS) ----2 X(L, S) ----4 分配算法： 选择最小释放代价，下次引用距离最远
输出语句四元式形如：(WRITE,A,-,-） 汇编指令：LD R , A； OUT R
条件语句四元式的翻译
（THEN, t,_ , _）生成的汇编代码为： LD R，t JUMP0 R，__
（ELSE,_,_,_）生成的汇编代码为： JMP __ 同时回填JUMP0指令的目的地址
（ENDIF,_,_,_）不产生目标代码，只负责完成ELSE子句的地址 回填工作 。
活动区间[i, j]和[m, n]不严格相交：如果mj或i n。 空间分配：
如果两个临时变量的活动区间不严格相交，则可以 共享单元
例：
T1 T2
T3 T4
T5
Offset = m Offset = m+1
Offset = m+1 Offset = m Offset = m+1
变量的状态描述
变量：源变量和临时变量 描述内容：
几个常见指令的含义 ：
Load Source R
从Source 读出送入R
Op Source R Source op R结果 送入R
Store Target R R的内容送入Target.
临时变量
特点： 寿命短； 一次定义一次使用 存储空间分配：尽可能采用共享办法
随用随分配的动态分配：
调用一个过程时，分配一个新的AR空间(不包括临 时变量部分)，每当要保存一个临时变量时，动态 分配到栈区的可用单元中
寄存器
寄存器的分类：
可分配寄存器 保留寄存器 零用寄存器
寄存器的使用准则：
寄存器先行准则 寄存器活跃准则 寄存器多载准则
寄存器的状态描述：
占有该寄存器的所有变量状态描述的集合。
寄存器的状态变化
如果现行值已在内存中，则不需回送 现行值不在内存，但该值没有下次引用。不需回送
生成代码 Load B, R 时：构造R:{B(L/D, NS)} 生成(Op , A, B, T)的目标代码为：
衡量目标代码质量的标准
在保证语义相等的情况下，生成的目标指令的条数越少和执行速度越快
虚拟机
指令格式为：op destination source
其中destination和source不能同为存储字
虚拟机的寻址方式和相应的汇编语言表示形式
虚拟机的指令系统
LD R，Source Op R，Source ST Target，R
ST T, R 赋值语句四元式：形如(ASSIG,A,-，B)：
汇编指令：LD R，A； ST B，R
例：Z:= X*(a+b)* Y* (a+b)
(ADDI,a,b,t1)
LD R，a; Add R，b; ST t1,R
(MULTI,X,t1,t2) LD R,t1; MUlT R,X; ST t2,R
(MULTI,t2,Y,t3) LD R,t2; MUlT R,Y; ST t3,R
(MULTI,t3,t1,t4) LD R,t3; MUlT R,t1;ST t4,R;
(ASSIG,t4,-,Z) LD R, t4; ST Z,R
输入/输出语句的翻译
输入语句四元式形如：(READ, A,-,-） 汇编指令：IN R； ST A , R