课程主页：

课程视频：

https://www.bilibili.com/video/BV1NE411376V?p=20&t=6

这部分对PA4进行翻译。

编程作业 IV

1. 简介

在此作业中，您将实现Cool的静态语义分析。您将使用解析器构建的抽象语法树（AST）来检查程序是否符合Cool规范。您的静态语义组件应拒绝错误的程序；对于正确的程序，它必须收集某些信息以供代码生成器使用。语义分析器的输出将是带注释的AST，供代码生成器使用。

与以前的作业相比，这次作业具有更大的设计决策空间。如果语义分析器根据规格检查程序，则它是正确的。这次作业没有标准的正确答案，但是可以检查出错误答案。我们认为许多标准做法会使此次作业更轻松，我们将尝试将这些方法传达给您。但是，您所做的主要是取决于您。无论您决定做什么，都应证明并解释您的解决方案。

您将需要参考《Cool参考手册》中定义的输入规则，标识符作用域规则和其他有关Cool的限制。您还需要为此阶段将方法和数据成员添加到AST类定义中。抽象语法树包提供的函数记录在Cool支持代码中。

本讲义中有很多信息，您需要了解其中的大部分内容才能编写有效的语义分析器，请仔细阅读讲义。在较高的级别上，您的语义检查器将必须执行以下主要任务：

查看所有类并构建一个继承图。
检查图是否是构建正确。
对于每个类
- (a) 遍历AST，将所有可见的声明收集在符号表中。
- (b) 检查每个表达式的类型正确性。
- (c) 用类型注释AST。

这份任务清单并不详尽，您有责任忠实地执行手册中的规定。

2. 文件和目录

要开始编程作业，请从OpenClassroom网站下载启动程序代码，并将其解压缩到本地计算机上的合适目录中。确保下载与特定机器体系结构匹配的tarball。您也可以从参考资料页下载本作业的各个部分，但我们强烈建议您按原样下载并使用完整的tarball。

一旦有了编程作业的工作副本，就可以切换到当前作业的目录中。对于C++版本的作业，导航到

[cool root]/assignments/PA4/

对于Java，导航到

[cool root]/assignments/PA4J/

（注意路径名中的“J”）。在此目录中输入$\text{make}$将设置工作区并将一些文件复制到您的目录中。目录中的一些文件将是只读的（使用符号链接），你不应该编辑这些文件。事实上，如果你修改了这部分文件，可能会发现无法完成作业。请参阅$\text{README}$中的说明。

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

2.1 C++版本

这是您可能要修改的文件列表。

$\text{cool-tree.h}$

此文件是包含用户定义的抽象语法树节点扩展。您可能需要添加其他声明，但不要修改现有声明。
$\text{semant.cc}$

这是实现语义分析阶段的主要文件。它包含一些为方便起见而定义的符号，以及表示继承图的$\text{ClassTable}$实现的开始。您可以选择使用或忽略这些。

语义分析器是通过调用$\text{program_class}$方法$\text{semant()}$来调用的。$\text{program_class}$的类声明在$\text{cool-tree.h}$中。您添加到$\text{cool-tree.h}$的任何方法声明都应在此文件中实现。
$\text{semant.h}$

该文件是$\text{semant.cc}$的头文件。您可以在此处添加所需的任何其他声明（不在$\text{cooltree.h}$中）。
$\text{good.cl}$和$\text{bad.cl}$

这些文件测试了一些语义特征。您应该添加测试，以确保$\text{good.cl}$包含尽可能多的合法语义组合，而$\text{bad.cl}$包含尽可能多的语义错误。不可能一次完成所有可能的组合；您仅负责获得合理的覆盖。在这些文件中说明您的测试，并在$\text{README}$文件中添加所有总体注释。
$\text{README}$

此文件将包含您作业书写部分的内容。对于此任务，至关重要的是要解释设计决策，代码的结构以及为什么您认为自己的设计是一个好的（即为什么它会导致正确而健壮的程序）。这是作业的一部分，目的是解释文本内容并注释您的代码。

2.2 Java版本

这是您可能要修改的文件列表。

$\text{cool-tree.java}$

该文件包含AST节点的定义，是您实现语义分析阶段的主要文件。您需要在此文件中添加语义分析阶段的代码。通过调用类$\text{program}$的方法$\text{semant()}$来调用语义分析器。不要修改现有的声明。
$\text{ClassTable.java}$

这个类是一些有用方法（包括错误报告和基本类的初始化）的占位符。您可能希望增强它以在您的分析器中使用。
$\text{TreeConstants.java}$

这个文件定义了一些有用的符号常量。
$\text{good.cl}$和$\text{bad.cl}$

这些文件测试一些语义特征。您应该添加测试以确保$\text{good.cl}$执行尽可能多的合法语义组合，而$\text{bad.cl}$执行尽可能多的语义错误。不可能一次完成所有可能的组合；您仅负责获得合理的覆盖。在这些文件中说明您的测试，并在$\text{README}$文件中添加所有总体注释。
$\text{README}$

这个文件将包含你的作业的记录。对于这项作业，您必须解释设计决策、代码的结构以及您认为设计是好的原因（即，为什么它会导致正确且健壮的程序）。用文本解释事物以及注释代码是作业的一部分。

3. 树遍历

作为作业III的结果，您的解析器将构建抽象语法树。在大多数AST节点上定义的$\text{dump_with_types}$说明了如何遍历AST并从中收集信息。这种算法风格——一种复杂树结构的递归遍历——非常重要，因为这是在AST上构造许多计算的非常自然的方式。

您为此任务的编程任务是

(1) 遍历树；
(2) 管理从树中收集的各种信息，以及
(3) 使用该信息来增强Cool的语义。

AST的一次遍历称为“pass”。您可能需要至少对AST进行两次pass才能检查所有内容。

您很可能需要将自定义信息附加到AST节点。为此，您可以直接编辑$\text{cool-tree.h}$（C ++）或$\text{cool-tree.java}$（Java）。在C++版本中，您要添加的方法实现应放入$\text{semant.cc}$。

4. 继承

继承关系是指定类依赖关系的有向图。大多数具有继承特性语言的典型要求是，继承图是无环的。您的语义检查器可以强制执行此要求，一种相当简单的方法是构造类型图的表示，然后检查环。

此外，Cool在从基本类继承方面有限制（请参见手册）。如果类A继承自类B，但未定义类B，这也是一个错误。

项目框架包括所有基本类的适当定义。您将需要将这些类合并到继承层次结构中。

我们建议您将语义分析阶段分为两个较小的部分。首先，检查继承图是否定义正确，这意味着满足所有对继承的限制。如果继承图定义不正确，则可以中止编译（当然，在打印相应的错误消息之后！）。其次，检查所有其他语义条件。如果知道继承图并且它是合法的，则实现第二个组件要容易得多。

5. 名称和作用域

任何语义检查器的主要部分是名称的管理。该特定的问题是确定每次使用标识符时要使用哪个声明，尤其是在名称可以重用的时候。例如，如果在两个$\text{let}$表达式中声明了$\text{i}$，一个嵌套在另一个$\text{let}$表达式中，则无论在哪里引用$\text{i}$，该语言的语义都会指定要执行的声明。语义检查器的工作是跟踪名称所引用的声明。

正如在课堂上讨论的那样，符号表是用于管理名称和作用域的便捷数据结构。您可以在项目中使用符号表的实现。我们的实现提供了根据需要进入，退出和扩大范围的方法。当然，您也可以自由地实现自己的符号表。

除了在每个类中隐式绑定的标识符self之外，还可以通过以下四种方法在Cool中引入对象名称：

属性定义；
方法的形式参数；
let表达式；
case语句的分支。

除了对象名称之外，还有方法名称和类名称。使用没有匹配声明的任何名称都是错误的。但是，在这种情况下，语义分析器在发现此类错误后不应中止编译。请记住，在使用之前，无需声明类，方法或属性。考虑一下这对您的分析有何影响。

6. 类型检查

类型检查是语义分析器的另一个主要功能。语义分析器必须检查是否在需要的地方声明了有效的类型。例如，必须声明方法的返回类型。使用此信息，语义分析器还必须根据类型规则来验证每个表达式都具有有效的类型。类型规则在《 Cool参考手册》和课程讲义中有详细讨论。

一个困难的问题是，如果表达式没有符合规则的有效类型，该怎么办。首先，应该打印一条错误消息，其中包含行号和错误原因的描述。在语义分析阶段提供信息性错误消息相对容易，因为通常错误很明显，我们希望您能提供有用的错误消息。其次，语义分析器应尝试恢复并继续。我们确实希望您的语义分析器能够恢复，但是我们不希望它避免级联错误。一种简单的恢复机制是将Object类型分配给任何其他不能指定类型的表达式（我们在coolc中使用了此方法）。

7. 代码生成器接口

为了使语义分析器能够与coolc编译器的其余部分正常工作，必须注意遵守与代码生成器的接口。我们特意采用了一个非常简单，朴素的接口，以避免在语义分析中局限您的创造力。但是，您必须做一件事。对于每个表达式节点，必须将其类型字段设置为Symbol，以命名由类型检查器推断的类型。该Symbol必须是idtable的$\text{add_string}$（C ++）或$\text{addString}$（Java）方法的结果。必须为特殊表达式$\text{no_expr}$分配类型$\text{No_type}$，它是项目框架中的预定符号。

8. 期望的输出

对于错误的程序，语义分析的输出是错误消息。除了格式不正确的类层次结构之外，您应该从所有错误中恢复。你也应该产生完整的和有信息的错误。假设继承层次结构定义良好，语义检查器应该捕获并报告程序中的所有语义错误。您的错误消息不必与coolc的相同。

我们为您提供了简单的错误报告方法$\text{ostream&ClassTable::semant_error(Class_)}$（C++）和$\text{PrintStream ClassTable.semantError(class_)}$（Java）。这个例程采用$\text{Class_}$(C++)或$\text{class_}$（java）节点，并返回一个可以用来编写错误消息的输出流。因为解析器确保类/类节点存储在定义类的文件中（回想一下，类定义不能跨文件拆分），因此可以从检测到错误的AST节点获得错误消息的行号，并从封闭类获得文件名。

对于正确的程序，输出是带类型注释的抽象语法树。语义阶段应该正确地用类型注释AST，并且应该正确地使用coolc代码生成器。

9. 测试语义分析器

您将需要一个工作的扫描器和解析器来测试您的语义分析器。您可以使用自己的扫描器/解析器或coolc扫描器/解析器。默认情况下，使用coolc的部分。要更改此设置，请将lexer和/或parser可执行文件（在项目目录中为符号链接）替换为您自己的扫描器/解析器。即使您使用自己的扫描器和/或解析器，明智的做法是使用coolc扫描器和解析器至少测试一次语义分析器。

您将使用mysemant运行语义分析器，mysemant是将分析器与解析器和扫描器一起粘合在一起的shell脚本。请注意，mysemant使用-s标志调试分析器；使用此标志会导致$\text{semant_debug}$（这是C ++版本中的全局变量，以及Java类中$\text{Flags}$的静态字段）被设置。添加实际代码以生成有用的调试信息由您自己决定。有关详细信息，请参见项目$\text{README}$。

一旦确定语义分析器正在运行，请尝试运行mycoolc来与其他编译器阶段一起调用分析器。您应该同时在好输入和坏输入上测试此编译器，以查看一切是否正常。请记住，语义分析器中的错误可能会在代码生成中或仅当在spim下执行已编译的程序时才会出现。

10. 注释

到目前为止，语义分析阶段是编译器的最大组成部分。我们的解决方案是大约1300行良好注释的C ++。如果您花一些时间在编码之前设计语义检查器，则将使作业更容易。问问自己：

需要检查哪些要求？
什么时候需要检查需求？
何时会生成检查需求所需的信息？
我需要检查要求的信息在哪里？

如果您可以针对Cool的各个方面回答这些问题，则实现解决方案应该很简单。