COOL Compiler-Part3

PA3

这个作业写 Parser。主要问题依然来自于 bison 工具不会用以及各种奇形怪状的 edge case，折磨程度和前一个差不多，写了3天的样子。写的时候一直在想如果有 ANTLR 就好了，之前玩过，感觉比 Flex + Bison 这种老古董要舒服多了。

Bison 踩坑

前期主要是 Bison 不会用，这里记录一些坑。基本上的工作就是在翻译手册上的 BNF 然后写 semantic action。写着写着突然发现它的课上好像根本没讲这玩意，就挺抽象的。

一开始需要了解的东西（不至于迷惑）：$$ $[1-n] 分别表示 : 左边的 non-terminal 和右边的第n个符号所关联的值，这些值可以理解为树的结点。这些东西是有类型的，所有可用类型定义在 %union 里面，对应到产生式上需要单独指定（貌似新版的 bison 提供了推导功能，但是这个实验在设计的时候显然没有）。对于终结符（这里就是那些 TOKEN），默认 int，如果带 lexeme 值的需要特别指定 %token<typename> token-name 这种；对于非终结符，需要指定 %type<typename> non-terminal-name，这里就类似于 non-terminal 的声明。bison 会检查这些所有的类型是不是匹配，当然这里的检查只是检查这些语法符号之间的类型匹配，具体到 C++ 的函数调用还是交给编译器。@$ @[1-n] 是行号相关的东西。详细的信息似乎在 bison 文档里面有一个单独的小节列出了符号的含义来着，忘了。

关于 Bison 手册的阅读：这里我直接用的最新的3.8.2，直接看最新的文档就行了。
1. 1.1-1.4，简单了解一下；第2章可以看，也可以去看看《Flex与Bison》，都是用例子讲解；然后就是具体的东西，3.2-3.4，3.7，5.1-5.7这些都会用到；看看这些基本上就能把框架搭起来了。
2. 然后到了第一次编译，第8章关于 debug 的说明还是可以看看的
3. 最后是看第6章关于错误处理的说明，虽然这个说明也没啥大用。
框架代码会导致 Shift-Reduce Conflict：如果是框架提供的那种、用空规则定义各种 xx_list 的写法，会出现 SR Conflict。虽然实际上应该是可以用的（大雾）（因为有一些 bison 的默认行为会使得这么做能够得到正常的结果），但是我还是把它拆掉了（不像看到 warning），也就是把用到 xx_list 的地方写成有 xx_list 和无 xx_list 两种，而不是交给 xx_list 这个 nterm 来处理空的情况。这样就没有 warning 了。
一些东西是 bison 的扩展，因为开了兼容性警告 -Wyacc，所以用了会 warning，比如 %empty %precedence 这种。

剩下的倒是没啥，因为没有用旧版本的东西，所以没有出现 flex 那么多奇怪的东西。

基础设施说明

这里的代码库主要是他们自己写的奇怪的 AST 的东西，虽然用起来也没啥大问题，不过总觉得有点抽象。这里主要参考 cool-tour.pdf 的第6节，描述还算是比较详细的。

具体的东西没必要了解，也不需要修改它的结构，说一下基本的逻辑就能上手写 semantic action 了。

首先它的功能是提供一种 AST 的描述方法，定义了一堆不同类型的 node，写语义动作的过程就是用这些 node 来组装一个 AST。
用到的接口基本上就是类似于构造函数一类的东西（这么理解其实对于写这个 lab 而言没有任何问题），每种 node 都有一个自己的类型，能够接收一组特定类型的参数进行构造。不同的类型通过 bison 文件前面的 %union 进行定义，构造器就是在填当前 node（$$）的信息和子节点关系。写文法就类似于递归下降（虽然实际上 bison 用的是 LALR），一种自然的构造语法树的过程。
node 主要有两种，一种是 list，另一种是单独的 node。list 表达的是一堆同类型的子节点，构造的时候和链表类似，这个在 skeleton 里面有例子（class list）。然后我们在定义的时候，可以参考着写。
除了简单看一看那个 cool-tour，具体的定义去看那个 aps 文件，描述了详细的参数类型。
这个实验只需要用构造器函数就行了，生成 C++ 时候添加的方法用不到，是给后面计算 AST 用的。

实现说明

要修改的文件主要是 cool.y，但是为了处理行号的问题，还需要修改 /include/PA3/cool-parse.h:754。

最简单的部分是翻译文法定义，照着 manual 12节抄就行了。在此过程中，可选的部分要稍微处理一下，描述的时候拆成有和没有可选部分两条规则，然后还要填上默认值，比如省略初始化的时候需要填个 no_expr()、函数调用省略对象的时候需要补上默认的 object(idtable.add_string("self")) 。这里面唯一要动一动脑子的就是前面提到的 list 的书写方法，一方面是 Shift-Reduce Conflict 最好不要写空规则，另一方面就是链表的构造，不过这个可以抄前面的 class_list 的定义，不需要自己折腾了。

然后的是优先级定义，虽然也没啥好说的，照抄 manual 的优先级表。值得注意的是，这里不需要理会 dangling else 问题，因为文法不允许省略 else 子句；这种设计虽然对于 PA1 写代码很不友好，但是实现起来还是很舒服的。

比较头疼的是 let，这东西没办法写在 expression 规则里面，需要自己再开一个 non-terminal 来写递归。之所以麻烦，是因为它的定义列表是没有长度限制的，所以要用文法描述就必须通过递归。还有就是它需要把有多个符号定义的 let 转换为多个只有一个符号定义的 let 的嵌套。比较好理解的写法是写右递归，类似于 lisp 里面的链表，看到逗号就继续递归加尾巴，把 IN expression 作为终止条件。不过这个最后的 expression 会导致冲突，因为 let 本身就是一个 expr，所以你也不知道这个后面的东西是接在里面这个 expr 的后面还是接在 let 这个大的 expr 的后面。一个具体的例子：let id1:T1 in expression.f()，有两种加括号的方法 (let id1:T1 in expression).f() 和 let id1:T1 in (expression.f())，也就是在这个 . 的地方产生了 Shift-Reduce。根据提示，我们可以用 %prec 来解决问题，在优先级列表最低级里面加一个 LETEXPR，然后在 IN expr %prec LETEXPR，这样就会优先匹配其他的可能属于 expr 的产生式，最后再匹配 let 后面的那个。

写完以上这些东西，这个文法实际上已经完成了，能够解析所有合法的情况。

最麻烦的事情是错误恢复。不过说难也还好，关键是没个例子不知道咋写。基本的写法就是有一个内置的 terminal error，可以匹配所有的出错情况，然后就可以一直跳过直到我们指定的某一个 token。基本上就是在每个 list 那边加一条 | error ';' 类似的东西，这样就可以把错误跳过去直到一个合法的结束符（handout 里面的要求就是如果有合法的结束，那么从下一个同类型的结构继续）。不过 let 那边需要特别注意一下，因为除了中间的声明部分的情况，我们还希望继续检查最后的那个 expr，因此不能只写一个 error ','，如果只有一个变量声明的话，那么后面的 expr 就会无法匹配规则，因此还要写一个 error IN。

不过以上都是我的写法，我看 Github 上还有别的写法，有的有问题，有的写的不太好但是能过（就比如说用空规则），总之能用就行，我也不能保证我写的一定没问题，毕竟对于 bison 还不是很熟悉。

最后还有一个行号的问题，建议把所有的行号都设置成最后一个符号的行号，不过实际上可以不改。感觉需要改一下的是 cool-parse.h 那边，因为 no_expr 的行号设为0比较合理，我这里好像是会继承基类tree_node 的构造函数，把行号设置为当前的行号；但是其实应该写成0，我也不知道当年的编译器是咋做的。