编程作业V

1. 简介

在本作业中，您将实现一个代码生成器。成功完成后，您将拥有一个功能齐全的Cool编译器！

代码生成器使用PA3中构造的AST和PA4中执行的静态分析。你的代码生成器应该产生MIPS汇编代码，忠实地实现任何正确的Cool程序。代码生成中没有错误恢复——所有错误的Cool程序都已被编译器的前端阶段检测到。

与静态分析任务一样，此任务具有相当大的设计决策空间。如果生成器生成的代码工作正常，则程序是正确的；如何实现这个目标取决于你自己。我们会建议一些我们认为会让你的生活更轻松的惯例，但你不必接受我们的建议。一如既往，在README文件中解释并证明您的设计决策。这个任务的代码量大约是前一个编程任务的两倍，尽管它们共享很多相同的基础结构。早点开始！

获得一个正确的代码生成器的关键是透彻地了解Cool构造的预期行为以及运行时系统和生成的代码之间的接口。Cool程序的预期行为由Cool参考手册第13节中给出的Cool操作语义定义。回想一下，这只是语言结构意义的说明，而不是如何实现它们。运行时系统和生成的代码之间的接口在Cool运行时系统（The Cool Runtime System）中给出。有关运行时系统对生成代码的要求的详细讨论，请参见该文档。本讲义和前面提到的文档中有很多信息，您需要了解其中的大部分内容才能编写正确的代码生成器。请仔细阅读。

2. 文件和目录

要开始编程任务，请从OpenClassroom网站下载启动程序代码，并将其解压缩到本地计算机上的目录中。确保下载与计算机体系结构匹配的压缩包。您也可以从“资源”页面单独下载此任务的各个部分，但我们强烈建议您按原样下载并使用完整的tarball。

有了编程作业的工作副本后，请转到当前分配的目录。对于作业的C++版本，请导航至

[cool root]/assignments/PA5/

对于Java，请导航至

[cool root]/assignments/PA5J/

（请注意路径名中的”J”。）在此目录中输入make将设置工作区并将许多文件复制到您的目录中。该目录中的某些文件是只读的（使用符号链接）。您不应该编辑这些文件，实际上，如果您制作和修改这些文件，可能会发现无法完成作业，请参见README文件中的说明。

我们现在描述项目的每个版本最重要的文件。

2.1 C++版本

这是您可能想要修改的文件列表。您应该已经熟悉以前作业中的大多数其他文件。有关其他文件的详细信息，请参阅README文件。

$\text{cgen.cc}$

这个文件将包含几乎所有的代码生成器代码。代码生成器的入口是$\text{program class::cgen(ostream&)}$方法，它在AST的root上调用。除了常用的常量之外，我们还提供了用于发出MIPS指令的函数、用于编码字符串、整数和布尔值，以及类表($\text{CgenClassTable}$) 的骨架。您可以使用提供的代码或将其替换为您自己的PA4继承图。
$\text{cgen.h}$

此文件是代码生成器的头文件。您可以在此文件中添加任何您喜欢的内容。它提供了用于实现继承图的类。您可以根据需要替换或修改它们。
$\text{emit.h}$

该文件包含用于发射MIPS指令等的各种代码生成宏。您可以修改此文件。
$\text{cool-tree.h}$

像往常一样，这些文件包含AST节点的类声明。您可以向$\text{cool-tree.h}$中的类添加字段或方法声明。方法的实现应该添加到$\text{cgen.cc}$。
$\text{cgen_supp.cc}$

此文件包含代码生成器的一般支持代码。您会在这里找到许多方便的函数。按照您认为合适的方式添加到文件中，但不要更改已经存在的任何内容。
$\text{example.cl}$

此文件应包含您自己设计的测试程序。尽可能多地测试代码生成器的功能。
$\text{README}$

该文件将包含您的作业的记录。解释设计决策、代码的结构以及为什么认为自己的设计是好的（即为什么它会导致正确和健壮的程序）至关重要。用文本解释事物以及注释代码是作业的一部分。

2.2 Java版本

这是您可能想要修改的文件列表。您应该已经熟悉以前作业中的大多数其他文件。有关附加文件的详细信息，请参阅 README 文件。

$\text{CgenClassTable.java}$和$\text{CgenNode.java}$这些文件为代码生成器提供了继承图的实现。您需要完成$\text{CgenClassTable}$才能构建您的代码生成器。您可以使用提供的代码或将其替换为您自己的PA4继承图。
$\text{StringSymbol.java, IntSymbol.java}$和$\text{BoolConst.java}$

这些文件提供对Cool常量的支持。您将需要完成生成常量定义的方法。
$\text{cool-tree.java}$

该文件包含AST节点的定义。您需要在这个文件中为Cool表达式添加代码生成例程（$\text{code(PrintStream)}$）。代码生成器通过调用类程序的$\text{cgen(PrintStream)}$方法调用。您可以添加新方法，但不要修改现有声明。
$\text{TreeConstants.java}$

和以前一样，这个文件定义了一些有用的符号常量。随意添加您自己的。
$\text{CgenSupport.java}$

该文件包含代码生成器的一般支持代码。您将在这里找到许多方便的函数，包括用于发出MIPS指令的函数。随意添加代码，但不要更改已经存在的任何内容。
$\text{example.cl}$

此文件应包含您自己设计的测试程序。尽可能多地测试代码生成器的功能。
$\text{README}$

该文件将包含您的作业的记录。解释设计决策、代码的结构以及为什么认为自己的设计是好的（即为什么它会导致正确和健壮的程序）至关重要。用文本解释事物以及注释代码是作业的一部分。

3. 设计

在继续之前，我们建议您阅读The Cool Runtime System以熟悉运行时系统对代码生成器的要求。

在高层次上考虑您的设计，您的代码生成器将需要执行以下任务：

确定并发出全局常量（例如原型对象）的代码。
确定并发出全局表的代码，例如$\text{class_nameTab}$、类$\text{class_objTab}$和分派表。
为每个类的初始化方法确定并发出代码。
为每个方法定义确定并发出代码。

有许多可能的方法来编写代码生成器。一种合理的策略是分两次执行代码生成。第一遍决定每个类的对象布局，特别是每个属性存储在对象中的偏移量。使用此信息，第二遍递归遍历每个特征并为每个表达式生成堆栈机器代码。

在设计代码生成器时，您必须牢记以下几点：

您的代码生成器必须与Cool运行时系统一起正常工作，这在Cool Runtime System 手册中进行了解释。
您应该清楚地了解Cool程序的运行时语义。Cool参考手册的第一部分非正式地描述了语义，手册的第13节给出了Cool程序应该如何运行的精确描述。
您应该了解MIPS指令集。类网页上的 spim文档中提供了MIPS操作的概述。
您应该决定您生成的代码将观察和期望哪些不变量（即，哪些寄存器将被保存，哪些可能会被覆盖等）。您可能还会发现参考讲义中有关代码生成的信息很有用。

您不需要生成与coolc相同的代码。coolc包括一个非常简单的寄存器分配器和此作业不需要的其他小更改。唯一的要求是生成与运行时系统一起正确运行的代码。

3.1 运行时错误检查

Cool手册的结尾列出了六个会终止程序的错误。其中，您生成的代码应该捕获前三个——对void分派、对void使用case和缺少分支——并在中止之前打印合适的错误消息。您可以允许SPIM捕捉除以零。捕获最后两个错误——子字符串超出范围和堆溢出——是 trap.handler中的运行时系统的责任。请参阅 Cool Runtime System手册的图 4，了解为您显示错误消息的函数列表。

3.2 垃圾收集

您的代码生成器必须与Cool运行时系统中的分代垃圾收集器一起正常工作。骨架包含函数$\text{code_select_gc(C++)}$和$\text{CgenClassTable.codeSelectGc(Java)}$，它们生成代码，如果从命令行设置标志GC。影响垃圾回收的命令行标志是-g,-t,-T。默认情况下禁用垃圾收集；标志-g启用它。启用后，垃圾收集器不仅会回收内存，还会验证“-1”是否将堆中的所有对象分开，从而检查程序（或收集器！）是否不小心覆盖了对象的末尾。-t和-T标志用于附加测试。使用-t，收集器会非常频繁地执行收集（在每次分配时）。垃圾收集器不直接使用-T；在coolc 中，-T选项会导致生成额外的代码来执行更多的运行时有效性检查。您可以随意使用（或不使用）-T。

对于您的实现，最简单的开始方法是根本不使用收集器（这是默认设置）。当您决定使用收集器时，请务必仔细查看 Cool Runtime System手册中描述的垃圾收集接口。确保您的代码生成器在所有情况下都能正确地与垃圾收集器一起工作并非易事。

4. 测试和调试

您将需要一个正常工作的扫描器、解析器和语义分析器来测试您的代码生成器。您可以使用自己的组件或来自coolc的组件。默认情况下，使用coolc组件。要改变这一点，用您自己scanner/parser/semantic analyzer替换lexer、parser和/或semant可执行文件（它们是项目目录中的符号链接）。即使您使用自己的组件，最好至少用coolc扫描程序、解析器和语义分析器测试一次代码生成器。

您将使用mycoolc运行代码生成器，mycoolc是一个shell脚本，它将代码生成器与其他编译器阶段“粘合”在一起。注意mycoolc使用-c标志来调试代码生成器；使用此标志只会导致CGEN调试（C++版本中的全局变量和java版本中的类标志的静态字段）被设置。添加实际代码以生成有用的调试信息取决于您。有关详细信息，请参见README。

4.1 Coolaid

CoolRuntime系统手册提到了Coolaid，这是一个用于验证Cool代码生成器生成的MIPS汇编代码的某些属性的工具。为了做到这一点，Coolaid对汇编代码施加了超出运行时系统要求的额外限制。课程工作人员不支持Coolaid，它也不是项目所必需的，因此可以安全地忽略CoolRuntime系统手册中列出的任何Coolaid特定限制。但是，即使不使用Coolaid，在决定如何构造汇编代码时，您也会发现这些附加限制很有用。

4.2 Spim和XSpim

可执行文件Spim和XSpim（位于[cool root]/bin/）是MIPS体系结构的模拟器，您可以在其上运行生成的代码。程序xspim的工作原理与spim类似，它允许您运行MIPS汇编程序。但是，它有许多特性，这些特性允许您检查虚拟机的状态，包括程序的内存位置、寄存器、数据段和代码段。您还可以设置断点和单步执行程序。spim/xspim的文档在课程网页上。

警告。使用spim进行调试比较困难的一点是spim是汇编代码的解释器，而不是真正的汇编程序。如果代码或数据定义引用了未定义的标签，则仅当执行的代码实际引用了此类标签时，才会显示错误。此外，只有出现在程序代码部分的未定义标签才会报告错误。如果您引用了未定义标签的常量数据定义，spim不会告诉您任何事情。对于这些未定义的标签，它只假设值为0。