编程作业 III

1. 简介

在此作业中，您将为Cool编写一个解析器。该作业使用两种工具：解析器生成器（C++工具称为$\mathrm{bison}$； Java工具称为$\mathrm{CUP}$）和用于处理树的程序包。解析器的输出将是抽象语法树（AST）。您将使用解析器生成器的语义操作来构造此AST。

当然，您肯定需要参考Cool的语法结构，该语法结构在Cool参考手册的图1中（以及其他部分）中找到。 $\mathrm{bison}$和$\mathrm{CUP}$的文档可在线获得。Cool支持代码讲义中介绍了处理树的包的C++版本；Java版本的文档可在线获得。对于此作业和后续作业，您都需要了解树程序包。

本讲义中有很多信息，您需要了解其中的大部分才能编写一个有效的解析器，请仔细阅读讲义。

2. 文件和目录

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

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

[cool root]/assignments/PA3/

对于Java，导航到

[cool root]/assignments/PA3J/

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

cool.y (C++版本) / cool.cup (Java版本)

这个文件包含Cool的解析器描述的开始，声明部分基本上已经完成，但是需要为引入的新非终结符添加其他类型声明。我们已经提供了终止符的名称和类型声明，您可能还需要添加优先级声明。不过，规则部分相当不完整。我们提供了一些规则，您不需要修改此代码来获得有效的解决方案，但是如果您愿意，欢迎使用。注意，不要假设任何特定的规则是完整的。
good.cl和bad.cl

这些文件测试语法的一些功能。您应该添加测试，以确保good.cl行使语法的所有合法构造，而bad.cl则在单个文件中行使尽可能多的解析错误类型。在这些文件中说明您的测试，并将所有总体注释放在README文件中。
README

和往常一样，该文件里会有你作业的总结。解释您的设计决策、测试用例，以及为什么您认为您的程序是正确和健壮的。作业的一部分是解释文本中的内容，以及注释代码。

3. 测试解析器

您将需要一个扫描器来测试解析器，可以使用自己的扫描器或coolc扫描器。默认情况下，使用coolc扫描器；要更改此行为，请用自己的扫描器替换lexer可执行文件（项目目录中的符号链接）。不要假设扫描器（不管你用哪一个！）无bug——扫描器中的潜在bug可能会导致解析器出现神秘问题。

您将使用myparser运行解析器，myparser是一个shell脚本，它将解析器与扫描器“粘”在一起。注意，myparser使用-p标志调试解析器；使用这个标志在stdout上打印大量关于解析器正在做什么的信息。bison和CUP都在cool.output文件中生成了人类可读的LALR(1)解析表，检查此解析表对于调试解析器定义有时可能很有用。

您应该在好的和坏的输入上测试这个编译器，看看是否一切正常。记住，解析器中的bug可能会在任何地方出现。

4. 解析器输出

您的语义动作应建立一个AST， AST的根（并且只有根）应为program类型，对于成功解析的程序，解析器的输出是AST的列表。

对于有错误的程序，输出为解析器的错误消息。我们为您提供了一个错误报告例程，该例程以标准格式打印错误消息。请不要修改它。您不应该在语义动作中直接调用此例程。当检测到问题时，bison / CUP会自动调用它。

对于跨越多行的构造，您可以自由地将行号设置为该构造一部分的任何行。如果解析器报告的行与参考编译器不完全匹配，请不要担心。另外，您的解析器仅需要用于单个文件中包含的程序，不必担心会编译多个文件。

5. 错误处理

您应该使用error伪非终结符来在解析器中添加错误处理功能，error的目的是允许解析器在某些预期的错误之后继续。这不是万能的，解析器可能会变得完全混乱。请参阅bison/CUP文档以了解如何最好地使用error。在README文件中，描述您尝试捕获的错误。您的测试文件bad.cl应该具有一些实例，这些实例说明了解析器可以从中恢复的错误。您的解析器至少应在以下情况下恢复：

如果类定义中有错误，但该类正确终止，并且下一个类的语法正确，则解析器应该能够在下一个类定义时重新启动。
类似地，解析器应该从feature（继续到下一个feature）、let绑定（继续到下一个变量）和$\{\ldots \}$块中的表达式中的错误中恢复。

不要过分关注解析器生成的错误消息中出现的行号。如果解析器工作正常，行号通常是发生错误的行。对于跨越多行的错误构造，行号可能是该构造的最后一行。

6. 树程序包

在Cool文档的Tour部分中，对Cool抽象语法树的树包的C++版本进行了广泛的讨论；课程网页上提供了Java版本的文档，您将需要大部分信息来编写有效的解析器。

7. 附注

您可以使用优先级声明，但只能用于表达式。不要盲目使用优先声明（即不要通过添加优先规则直到语法消失来应对语法中的移进——规约（shift-reduce）冲突）。

Cool let构造在语言中引入了歧义（如果您不相信，请尝试构造一个示例）。手册通过说一个let表达式尽可能向右延伸来解决歧义。根据语法的编写方式，此歧义可能会在语法分析器中显示为移进——规约冲突，其中包括let的产生式。如果遇到这样的问题，您可能需要考虑使用bison/CUP特性来解决问题，该特性允许优先级与产生式（而不仅仅是运算符）相关联。有关如何使用此功能的信息，请参阅bison/CUP文档。

由于mycoolc编译器使用管道从一个阶段到下一个阶段进行通信，因此解析器产生的任何多余字符都可能导致错误。 特别是，语义分析器可能无法解析您的解析器生成的AST。

8. C++版本作业注释

如果您正在使用Java版本，请跳到下一节。

您必须为非终止符和具有属性的终止符声明bison “types”。例如，在cool.y中的声明是：
```
%type <program> program
```
此声明表示非终止符program具有类型$\text{}$。在这里使用“type”这个词是有误导性的；它真正的意思是非终止符program的属性存储在cool.y中union声明的program成员中，该声明具有Program类型。通过指定类型
```
%type <member_name> X Y Z ...
```
您可以指示bison，使得非终止符（或终止符）X，Y和Z的属性应具有适合于该union的成员名称的类型。

所有union成员及其类型在设计上都具有相似的名称。在上面的示例中，巧合的是，非终止符program与union成员具有相同的名称。

为语法符号的属性声明正确的类型是至关重要的；如果不这样做，实际上会使得解析器无法工作。不需要为语法中没有属性的符号声明类型。
在最初的框架上运行bison会产生一些关于“无用非终止符”和“无用规则”的警告。这是因为一些非终止符和规则将永远不会被使用，但是当解析器完成时，它们应该会消失。
如果使用了带有错误类型参数的树构造函数，g++类型检查器会抱怨。如果忽略这些警告，当构造函数注意到使用不正确时，程序可能会崩溃。此外，如果您输入错误，bison可能会抱怨。注意任何警告，如果当bison或g++提供警告消息时程序崩溃，请不要感到惊讶。

9. Java版本作业注释

如果您使用的是C++版本，请跳过本节。

您必须为非终止符和具有属性的终止符声明CUP “types”。例如，在框架cool.cup中有以下声明：
```
nonterminal program program;
```
该声明表示非终止符program具有program类型。为语法符号的属性声明正确的类型至关重要，不这样做会使得您的解析器将无法工作。您不需要为没有属性的语法符号声明类型。

如果您使用带有错误类型参数的树构造函数，则javac类型检查器会抱怨。如果您使用强制转换来修复错误，则当构造函数注意到使用不正确时，您的程序可能会抛出异常。此外，如果您输入错误，CUP可能会抱怨。