编译原理 第十一章 目标代码生成

5. 目标代码生成本章实验为实验四，是最后一次实验，其任务是在词法分析、语法分析、语义分析和中间代码生成程序的基础上，将C 源代码翻译为MIPS32指令序列（可以包含伪指令），并在SPIM Simulator上运行。

当你完成实验四之后，你就拥有了一个自己独立编写、可以实际运行的编译器。

选择MIPS作为目标体系结构是因为它属于RISC范畴，与x86等体系结构相比形式简单便于我们处理。

如果你对于MIPS体系结构或汇编语言不熟悉并不要紧，我们会提供详细的参考资料。

需要注意的是，由于本次实验的代码会与之前实验中你已经写好的代码进行对接，因此保持一个良好的代码风格、系统地设计代码结构和各模块之间的接口对于整个实验来讲相当重要。

5.1 实验内容5.1.1 实验要求为了完成实验四，我们建议你首先下载并安装SPIM Simulator用于对生成的目标代码进行检查和调试，SPIM Simulator的官方下载地址为：/~larus/spim.html。

这是由原Wisconsin-Madison的Jame Larus教授（现在在微软）领导编写的一个功能强大的MIPS32汇编语言的汇编器和模拟器，其最新的图形界面版本QtSPIM由于使用了Qt组件因而可以在各大操作系统平台如Windows、Linux、Mac等上运行，推荐安装。

我们会在后面介绍有关SPIM Simulator的使用方法。

你需要做的就是将实验三中得到的中间代码经过与具体体系结构相关的指令选择、寄存器选择以及栈管理之后，转换为MIPS32汇编代码。

我们要求你的程序能输出正确的汇编代码。

“正确”是指该汇编代码在SPIM Simulator（命令行或Qt版本均可）上运行结果正确。

因此，以下几个方面不属于检查范围：1)寄存器的使用与指派可以不必遵循MIPS32的约定。

只要不影响在SPIM Simulator中的正常运行，你可以随意分配MIPS体系结构中的32个通用寄存器，而不必在意哪些寄存器应该存放参数、哪些存放返回值、哪些由调用者负责保存、哪些由被调用者负责保存，等等。

编译原理中的目标代码生成与优化编译原理是计算机科学中的一门重要课程，它研究的是将高级程序语言转化为机器语言的过程。

目标代码生成与优化是编译过程中的两个关键环节，本文将就这两个方面展开讨论。

一、目标代码生成目标代码生成是编译过程中的最后一步，它的任务是将中间代码转化为能够在目标机器上执行的机器代码。

目标代码生成的质量直接影响程序的执行效率和占用的存储空间。

1. 寄存器分配在进行目标代码生成之前，我们需要进行寄存器分配。

寄存器分配的目的是将中间代码中的临时变量分配到机器寄存器中，减少内存读写操作，提高程序的运行速度。

常用的寄存器分配算法有线性扫描算法和图着色法。

2. 目标代码生成技术目标代码生成的技术有很多，下面列举几种常见的技术：(1) 直接生成代码：直接将中间代码翻译为目标机器的指令序列。

这种方法简单直接，但生成的目标代码质量一般较低。

(2) 间接生成代码：先将中间代码翻译为一个中间形式，再将中间形式转化为目标机器的指令序列。

这种方法可以进行一些优化，生成的目标代码质量较高。

(3) 使用代码模板：事先定义一些目标机器的指令模板，并根据中间代码的特征选择合适的指令模板来生成目标代码。

这种方法可以充分利用目标机器的特性，生成的目标代码效率较高。

二、目标代码优化目标代码优化是指对生成的目标代码进行一系列的优化，以提高程序的运行效率和减少代码的空间占用。

1. 基本块优化基本块是由顺序执行的指令组成的，没有前驱指令和后继指令的指令序列。

基本块优化的目的是对基本块中的指令进行优化，以减少执行时间和空间开销。

常见的基本块优化技术有死代码删除、常量传播等。

2. 寄存器优化寄存器是计算机中的一块高速存储器，能够提供快速的数据访问速度。

寄存器优化的目的是将变量尽可能地存放在寄存器中，以减少内存读写操作，提高程序的执行效率。

常用的寄存器优化技术有寄存器分配、寄存器重命名等。

3. 循环优化循环是程序中的重要结构之一，对循环进行优化可以显著提高程序的执行效率。

第一章：编译过程的六个阶段：词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成解释程序：把某种语言的源程序转换成等价的另一种语言程序——目标语言程序，然后再执行目标程序。

解释方式是接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执行结果，然后再接受下一句。

编译程序：就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序(机器语言程序或汇编语言程序)。

解释程序和编译程序的根本区别：是否生成目标代码第三章：Chomsky对文法中的规则施加不同限制，将文法和语言分为四大类：0型文法（PSG）◊ 0型语言或短语结构语言文法Ｇ的每个产生式α→β中：若α∈Ｖ*ＶNＶ*, β∈(ＶN∪ＶT)* ，则Ｇ是0型文法，即短语结构文法。

1型文法（CSG）◊ 1型语言或上下文有关语言在0型文法的基础上：若产生式集合中所有|α|≤|β|，除Ｓ→ε(空串)外，则Ｇ是１型文法,即：上下文有关文法另一种定义：文法G的每一个产生式具有下列形式：αAδ→αβδ，其中α、δ∈V*，A∈VN，β∈V+；2型文法（CFG）◊ 2型语言或上下文无关语言文法Ｇ的每个产生式A→α，若A∈ＶN ,α∈(ＶN∪ＶT)*，则Ｇ是２型法，即：上下文无关文法。

3型文法（RG）◊ 3型语言或正则(正规)语言若Ａ、Ｂ∈ＶN，ａ∈ＶT或ε，右线性文法：若产生式为Ａ→ａＢ或Ａ→ａ左线性文法：若产生式为Ａ→Ｂａ或Ａ→ａ都是３型文法（即：正规文法）最左（最右）推导在推导的任何一步α⇒β，其中α、β是句型，都是对α中的最左（右）非终结符进行替换规范推导：即最右推导。

规范句型：由规范推导所得的句型。

句子的二义性（这里的二义性是指语法结构上的。

）文法G[S]的一个句子如果能找到两种不同的最左推导(或最右推导)，或者存在两棵不同的语法树，则称这个句子是二义性的。

文法的二义性一个文法如果包含二义性的句子，则这个文法是二义文法，否则是无二义文法。

深入学习：掌握编译原理与目标代码生成编译原理与目标代码生成是计算机科学与软件工程领域非常重要的一部分。

在这个领域中，我们研究的是将程序代码转换为可执行代码的过程，这涉及到了词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等一系列的技术和算法。

编译器是实现编译过程的工具，它将高级语言源代码转换为机器可执行的目标代码。

而编译过程中的关键环节即为目标代码生成，它是将中间代码转换为特定硬件平台上可执行的机器代码的过程。

编译原理的研究从上世纪50年代开始，经历了多个阶段的发展。

早期的编译器通过逐行读取源代码，然后将其转换为汇编语言或机器码。

随着计算机硬件的发展和编程语言的演化，编译器的设计和实现也发生了重大变化。

编译原理的核心概念之一是语法分析，它将源代码转换为抽象语法树（AST）。

语法分析器通过识别词法单元（如关键字、标识符、操作符等）来构建AST，并使用上下文无关文法来定义语法结构。

常见的语法分析算法有递归下降分析和LR分析。

语义分析是编译过程中的另一个重要环节，它确保程序在语义上是正确的。

语义分析器会检查源代码中的类型错误、作用域错误、类型转换错误等，并为后续的代码生成阶段提供必要的信息和约束条件。

中间代码生成是编译器的一个重要步骤，它将AST转换为一种中间表示形式，例如三地址码或者虚拟机指令。

中间代码是对源代码的一种抽象表示，它简化了后续代码生成和优化的过程，并为优化算法提供了更好的机会。

代码优化是编译过程中的重要环节，它旨在提高目标代码的性能和效率。

代码优化器使用各种技术和算法，例如常量折叠、循环优化、指令调度等，来改进目标代码的执行效率。

最后一个环节是目标代码生成，它将中间代码转化为特定硬件平台的机器代码。

目标代码生成器需要考虑到硬件平台的特点和限制，并根据目标机器的指令集架构来生成高效的机器代码。

目标代码生成是编译器的最终阶段，它决定了程序的最终执行效果。

一个好的目标代码生成器应该可以充分利用硬件资源，减少指令的数目和执行时间，从而提升程序的性能。

第十一章目标代码生成知识结构：代码生成概述可执行机器代码目标代码的形式汇编语言代码目标代码生成机器语言浮动模块目标机器模型代码生成算法第一节基本问题一、研究目标代码生成的关键问题充分利用硬件的有效资源生成有效的目标代码。

1、生成目标代码时如何选择指令,使生成的目标代码较短。

例：三地址代码a:=a+1翻译为：LD R0, a 或 INC aADD R0, #1ST R0, a2、如何充分利用寄存器，减少目标代码访问内存次数二、目标代码的形式1、可执行机器代码（静态定位）。

特点：①占用存储空间的固定位置，生成目标代码，就可直接执行；②不能进行各模块的独立编译，对源程序只能一次性编译；③灵活性较差。

2、机器语言浮动模块，由连接程序把某些运行程序连接起来，转换成机器语言。

特点：①生成目标代码有较大的灵活性，可以随机分配内存；②连接是消耗一些系统时间。

3、汇编语言代码。

特点：①是从汇编语言到目标代码的转换，实现比较容易，并有利于软件移植；②需要两次翻译过程。

三、代码生成器的输入代码生成器的输入包括源程序的中间表示以及符号表中的信息。

1、利用符号表中的信息来决定在中间代码中的名字所指示的数据对象的运行地址。

目标程序例 X ：=Y + Z 其中：X ，Y ，Z 对应的地址分别为t 0，t 0+1，t 0+2。

符号表 t 0 t 0+1 t 0+2 0 ADD R 0 ZST R 0 X —送数2、在语义检查时发现了一些明显的错误，并加入了类型转换操作，可假设代码生成阶段的输入没有错误。

四、指令的选择生成的代码质量取决于它的速度和大小，因此，指令集的一致性和完整性，指令速度和机器用语是非常重要的。

五、寄存器分配如何充分利用寄存器，对于生成好的代码是非常重要的。

1、在寄存器分配期间，为程序的某一点选择驻留在寄存器中的一组变量；2、在随后的寄存器指派阶段，挑出变量将要驻留的具体寄存器。

六、计算顺序选择计算的顺序会影响目标代码的有效性和代码的执行效率。