MP1.3 Cool Parser

本次实验中，你将在MP1.2的实验成果基础上，使用 Bison 为 Cool 语言构造一个 parser，它接受 MP1.1 构造的lexer 输出的 token 序列，根据你在文法描述文件中定义好的文法，为符合文法规定的 token 序列产生对应的抽象语法树 (AST)。

1. 实验准备

在 mp1/src/ 目录下, 执行

$ make parser

会编译生成 parser 可执行文件。 然后是用管道, 运行程序 :

./lexer bison_test_file.cl | ./parser

本次实验你需要修改

• cool.y
  一个Cool分析器的文法描述文件。你需要在其中添加规则。该文件中，声明部分已基本完整，你只需要在这部份中为新的非终结符增加类型声明；规则部分很不完整，需要你补充。
• bison_test_good.cl 和 bison_test_bad.cl
  这两个文件是用于测试文法特征的。你需要在 bison_test_good.cl 中增加测试程序测试文法中的每一种合法语言构造，在 bison_test_bad.cl 中增加测试程序测试尽可能多种类的分析错误。

在修改上述文件之前，你需要做以下准备：

a. 阅读 A Tour of the Cool Support Code 的第6节

阅读理解它是如何自动产生各个 AST 节点类的，并理解各节点类的构造方法、层次关系、接口。你应当可以人工产生一棵正确的 AST。

b. 理解和使用 bison

你需要阅读 Bison 手册和2015 年编译课使用的实验教程及comppub git 库中的表达式示例，了解 Bison 的基本工作原理、Bison 源文件的基本格式、各部分的含义等。

c. 阅读 src/cool.y并思考

这个模板目前可以做什么？如果要构建一个完整的 Cool parser，你还需要做哪些工作？

2. 实验要求

本次实验分基础要求和扩展要求两部分，你可以只做基础要求。良好完成扩展要求有额外加分。

a. 基础要求

你的程序应当能够处理lexer的输出，对于正确的输入，你的程序应当打印输出整个AST。打印工作已经在cool-support/src/parser-phase.cc中做了，因此，你只要在 cool.y 中正确地构造好 ast_root 即可。为了最后的评测，你不需要、也不应该修改输出的格式或者错误报告的格式。

你需要定义具有正确行为的LALR文法。有时你所编写的文法文件会包含有移进-归约冲突或者归约-归约冲突。原则上，你可以通过修改文法来避免它们，然而在保证你理解Bison针对冲突的默认处理规则的情况下，你可以在文法中保留部分冲突。

注意: 为了证明冲突及其默认的处理是 feature 而不是 bug，你需要将对冲突行为的分析写在 mp1/answers.txt 中。

你的 parser 需要能够进行简单的错误恢复，也就是要在遇到一些预先想到的错误后能够继续解析。你的parser至少需要能够从如下两种错误中恢复：

• 如果在一个class定义中遇到错误，这个类定义应能被正确终止，并且你的parser要能够继续解析下一个类定义（如果有）。

• 类似地，你的parser要能从feature、let语句、{...}中的表达式中发生的错误中恢复，并跳到下一个对应层次的语法结构继续解析。

注意：你不需要太过在意错误输出的行号。对于多行的情况，默认返回的是该语法结构的最后一行。

b. 扩展要求

观察提供的 reference-binaries/parser，以及 clang 等编译器的错误恢复，并为你的编译器实现更多、粒度更细的错误恢复特性。

你需要将你实现的特性写在 answers.txt 中，并提供测试样例。

3. 一些提示

• 你可能需要用到 bison 的优先级机制。仔细阅读 bison 文档中有关 precedence 的说明。对于 expression 的文法，使用这一机制可以简单地避免移进-归约冲突。然而这个方法不是万能的，不能一碰到移进-归约冲突就使用 precedence。

• Cool语言的 let 结构本身是有二义的，文档中增加了规定来消除歧义。这个问题在 bison 中会反映成一个移进-归约冲突。想要解决这个问题，你可以查看 bison 是如何为产生式（而不只是操作符）指定优先级、结合性的。

• 对于终结符和非终结符，如果你需要使用它们的属性，你必须在bison中声明 它们的类型，比如：%type <program> program. 尖括号中的类型必须出现在开头的 union 定义中。这是由于 bison 生成的代码需要多态，而 C 的类似多态的机制就是union。请注意不要忽视 bison 或者 g++ 关于类型问题的警告。

4. 提交说明

本次实验你需要提交一份cool.y的代码。提交之前请保证make parser能够运行并产生一个可用的parser文件。你需要对提供的例子（bison_test_good.cl、bison_test_bad.cl）做测试。你还需要在 bison_test_good.cl 中增加测试程序测试文法中的每一种合法语言构造，在 bison_test_bad.cl 中增加测试程序测试尽可能多种类的分析错误。样例要精简但是有代表性，能够对尽可能多的特性做测试。

提交目录：

mp1/ 
 ├── answers.txt 
 ├── cool-support/ 
 ├── reference-binaries/ 
 └── src/ 
      ├── ...   
      ├── cool.y                 mp1.3的代码
      ├── bison_test_good.cl     
      └── bison_test_bad.cl      测试样例