COOL 语义分析器实现

Posted on Sep 6, 2021

COOL 的语义分析主要对作用域和类型做了检测，这是两个必要的检测。未定义或重复定义的变量会对代码生成造成影响；类型不匹配也会造成各种未定义行为。

作用域

语义分析中需要对每个标识符（变量、函数）做检测，主要需要检查是否有未定义的标识符和重复定义的标识符。以 COOL 为例，通过维护一个符号表即可实现检测。这个检测过程可能需要对 AST 进行多次遍历，因为在 COOL 中，全局变量可以在声明前引用，所以至少需要先遍历一次并记录所有的全局变量，这样在第二次遍历时就可以正确判断变量是否有定义。

然后需要进行第二次遍历来处理每个变量的定义情况。考虑三个操作

search_symbol(identifier)，搜索符号表，在第一次找到符号时返回
add_symol(identifier)，向符号表中添加标识符
delete_symbol(identifier)，从符号表中删除标识符

由此已经可以判断标识符是否被定义，全局标识符已在第一次遍历时处理好了，每次遇到局部变量定义时就将该标识符加入到符号表中。碰到任何标识符时只要调用 search_symbol 就可以判断符号是否被定义。注意这里的第一次找到可以实现最小作用域原则，也就是对于

{
    x:Int;
    ..
    {
    	x:Int;
        ..
    }
}

在内层语句块中引用 x 时，将会引用在内层定义的 x。当然为了保证第一次找到的标识符是内层的，需要把符号表做成后进先出。

不过仅有上面三个操作会造成嵌套定义不合法，因为对符号表的查找没有分层，会一路查到最顶层，也就是上面的代码也会被检测出错。虽然我们一般会避免嵌套定义，但是从语法上来讲这是允许的，所以我们的符号表需要支持嵌套的定义，如此就需要添加两个功能

enter_scope() 进入一个新的嵌套作用域层级
exit_scope() 离开当前的作用域嵌套层级

然后 search_symbol 同样的也需要改为在当前嵌套层级搜索，当该层级搜索不到时才应该向低层级搜索，这里的返回结果一个有区别，这样才能良好地判断定义的有效性，考虑这样的代码

{
    x:Int;
    x:Int;
}

在同一作用域中重复定义了两次 x，这是不允许的，我们的符号表已经可以完成这个判断了：

在第一次发现 x 时搜索符号表，返回值告知我们当前作用域中没有 x，所以将它加入到符号表，然后第二次发现 x 时再搜索符号表，返回值告知当前作用域已经有了 x，由此就可以报错了。

同时这个符号表将不同嵌套层级分离，所以对于

{
    x:Int;
    ..
    {
    	x:Int;
        ..
    }
}

这样的代码，search_symbol 会告知我们虽然找到了 x，但是 x 不在当前作用域，所以不会报错。

类型

类型检测和类型推导其实是不一样的东西，但是许多地方都把两者混淆，不过这其实没有问题，因为为了检测类型，必然要做类型推导，而类型推导也（一部分）是为了检测类型。为了形式化地描述类型规则，慕课中使用了逻辑推理规则来描述，在 cool-manual 12.2 中可以看到全部规则。

实现

我对 AST 进行了四次遍历，完成类型判断和变量重复定义的检测，总结如下：

pass one：构建全局符号表同，判断类是否有重复定义。
pass two：构建继承图
判断是否存在继承错误（即环状继承）
pass three：构建方法、属性表，判断是否有重复定义
pass four：进行类型推导和判断

需要注意的是对于继承需要把基类的成员和方法都添加到子类的符号表中。

代码挺长的，我写的也挺烂的（越往后越觉得自己写的烂），我把他们放到了 GitHub 上。

在 cool-tree.h 中主要添加了许多 getter 方法，便于 typing 时对表达式等的处理。symtab.h 是慕课提供的一个符号表类模板，我给他添加了一个构造函数

   // this is added by me, for my need
   SymbolTable<SYM, DAT> (const SymbolTable<SYM, DAT>& table) { tbl = new ScopeList((Scope *) NULL, table.tbl); exitscope(); }

主要是为了继承时对符号表的处理。

semant.cc 和 semant.h 就是核心代码了。

我不准备具体说实现，一方面自己写的这么烂也不好意思多指点江山，另一方面其实大体定下了识别的过程后实现就只是体力活了。

前段时间在游戏上花了许多时间，最近几天就一直在弄这个分析器，所以博客也是有一段时间没更新了。写了大概有六天吧，从一脸懵到胸有成竹再到最后完全实现，虽然挺累的，但是很有成就感，很值得。

在最后，自然还是用 life.cl 来测试一下啦

cheers！