【CS 143 Compiler 编译原理】Assignment 3：静态语义 ...

BlaXuan

代码地址：casual-lab/stanford-cool: CS142 Compilers Assignments Solutions (github.com)
这节 Assignment 真折磨。。
理解任务内容

从哪里开始：程序入口函数

Assignment Handout 中过于抽象，不够具体。
通过分析 Makefile 可知，全局的入口函数是 semant-phase.cc 中的 main 函数（但这个文件不应该修改）。需要修改的是在 main 中被调用的 program_class::semant 函数。
// semant-phase.cc
int main(int argc, char *argv[]) {
  handle_flags(argc,argv);
  ast_yyparse();
  ast_root->semant();
  ast_root->dump_with_types(cout,0);
}
几种编程实践的实例演示

初始的 Supporting Code 用 dumb_with_types 打印所有语法元素的例子，说明（建议）了一种 实现抽象语法树遍历分析的方法 。
所有语法树节点都继承自公共父类 tree_node ，

• 递归遍历：以 dump_with_type 为例子。
  
  
  
  • 每个语法树节点基类（Phylum）声明一个虚拟函数（virtual method），子类提供具体实现。virtual 关键字使得当使用指针调用 dump_with_type 方法时，会选择指针具体指向的具体类的实现。即使指针类型声明为基类。
    
  • 具体见 dumptype.cc 中的注释
    
  
  

• 注释语法树：以 type 字段为例，通过定义 Attributes 实现 “注释”。每个 Expression 类型都有这个域（field），用来表示这个表达式的类型。
  

虚拟函数 就是实现 外部声明的类型相同（比如都是Expression 或都是 Feature），但内部行为不同。这样可以实现运行时区分 不同的 Expression（比如 loop_expr 或 assign_expr 等）
// defined in Expression_class
virtual char* get_expr_constructor() = 0;
// defined in plus_class
char* get_expr_constructor(){ return "plus"; }           
// defined in sub_class
char* get_expr_constructor(){ return "sub"; }           
// defined in mul_class
char* get_expr_constructor(){ return "mul"; }           
// defined in divide_class
char* get_expr_constructor(){ return "divide"; }
要做什么

对代码作最后的静态检查。生成注释树为代码生成做准备。

• 对所有类定义进行检查 ：重复定义检查、父类未定义检查、构建依赖图、循环依赖检查
  
• 语法检查与静态语义分析 ：变量命名和作用域、表达式类型确定、类型检查。静态语义分析在 Assignment 中具体就是指 表达式 数据类型 的分析。
  

所以 ClassTable 构造函数中，剔除和修正非法定义的 class，解析和检查依赖关系（构建依赖图）。
semant_walk 是所有 tree_node 都实现的用来递归下降遍历的方法。
void program_class::semant()
{
    initialize_constants();

    // 1) ClassTable constructor:
    //      discard invalid class definition & check inheritance
    ClassTableP ctp = new ClassTable(classes);

    // 2) recursive downward traversal
    semant_walk(ctp);

    if (ctp->errors()) {
    cerr << "Compilation halted due to static semantic errors." << endl;
    exit(1);
    }
}
类定义检查（ClassTable 构造）

总的来说分为 建立依赖图（build_inherit_graph）、验证无环（verify_acyclic）两步。
ClassTable::ClassTable(Classes classes) : semant_errors(0), error_stream(cerr){
    install_basic_classes();
    build_inherit_graph(classes);
    if(semant_debug) {
        cout<<"# After build inherit graph."<<endl;
        print_inherit_graph();
        print_type_nodes();
    }
    verify_acyclic();
}
install_basic_class 将基础类（如 Object、IO、Int、String）预先加入，和用户定义的 Class 一并处理。
类定义的检查和依赖图构造

依赖图的构造遵顼一个 先定义节点再连线 的顺序。（因为建立继承关系时需要维护父节点的入度，这就需要父节点已经存在，所以需要所有节点定义完成后在连线。）
定义节点的过程嵌入重复定义的检查，只留下去重的 class 集合。
之后验证继承关系正确、父类存在且可以被继承，再在数据结构上建立继承关系。
void ClassTable::build_inherit_graph(Classes &classes){
    // 1) Ensure: type_nodes/inherit_graph only contain unique classes.
    for (int i = classes->first(); classes->more(i); i = classes->next(i)){
        Class_ cls = classes->nth(i);
        if(cls->get_name() == SELF_TYPE){
            semant_error(cls)<<"SELF_TYPE cannot be redefined."<<endl;
            continue;
        }
        bool inserted = type_nodes.emplace(cls->get_name(), cls).second;
        if(! inserted){
            semant_error(cls)<<cls->get_name()->get_string()<<" cannot be redefined."<<endl;
        }
        inherit_graph.emplace(cls->get_name(), *(new InheritElem(Object)));
    }
    // 2) try to establish inheritance relationship.
    //    Invalid parents will be replaced with 'Object'
    for (auto p : type_nodes){
        if(p.second->get_name() == Object) continue;
        Class_ cls = p.second;
        InheritElem elm = inherit_graph.at(cls->get_name());

        verify_inheritance(cls);
    }
}
循环依赖检测

无他，唯 拓扑排序 尔。须知 C++ 中 STL 容器赋值是浅拷贝。
void ClassTable::verify_acyclic(){
    std::map<Symbol, InheritElem> inherit_graph_cp = inherit_graph;
    std::stack<Symbol> stk;
    int n_nodes = inherit_graph_cp.size();
    for(auto itr = inherit_graph_cp.begin(); itr != inherit_graph_cp.end(); itr++){
        if(0 == itr->second.in_degrees){
            stk.push(itr->first);
            n_nodes --;
        }
    }
    while(stk.size() != 0){
        Symbol curve_from = stk.top();
        stk.pop();
        Symbol curve_to = inherit_graph_cp.at(curve_from).parent;
        if (curve_to && inherit_graph_cp.find(curve_to) != inherit_graph_cp.end()
            && 0 == --(inherit_graph_cp.at(curve_to).in_degrees)){
            stk.push(curve_to);
            n_nodes --;
        }
    }
    if(n_nodes != 0){
        semant_error()<<"There exist cyclic inheritance."<<endl;
    }
}
基于语法树的语法检查和静态语义分析

静态语义分析的内容，就是程序不运行就能分析出的信息，也即编译阶段就能发现的问题。
类型环境（Type Environment）

语法树的最底层不是 只具有字面值的 字符串、数字和运算符号，还有调用的方法、使用的变量。他们的值需要一个公共环境来保存和共享，以此推算表达式的类型。（详见 COOL 手册 章节 12 描述）它们包括：

• 变量环境（Object Env）
  
• 方法环境（Method Env，每个类都定义了那些方法可以使用）
  
• 当前代码所在 class（current class）：主要用于需要调用自身的方法以及确定 SELF_TYPE 的时候。
  

具体来说，Supporting Code 建议使用 ClassTable 保存这些环境。这个 ClassTable 作为一个容器保留所有数据结构，他的指针通过递归函数 semant_walk 入参实现共享。
//semant.h
class ClassTable {
public:
    Class_ cur_cls = NULL;
    SymbolTable<Symbol, SymbolInfo> obj_env;
    std::map<Symbol, MethodSignatures> method_env;

    std::map<Symbol, Class_> type_nodes;
    std::map<Symbol, InheritElem> inherit_graph;
}
符号表（Symbol Table）：表示变量环境的特殊结构

区别：Lexer 和 Parser 中的 String Tables 只是用来减少重复，包括 Identifier、字符串常量、布尔值三种。而 Symbol Table 是管理 Identifier 的作用域。
符号表（ include/PA4/symtab.h ） 是一个 List of List。其本身是一个 栈（用 List 实现），每个元素表示一层 Scope。这样，第一层的 list 实现了变量的作用域层级关系，便于实现变量屏蔽。
每个 Scope 是一个 List ，表示这个作用域中的所有变量名。addid 是在最上层 Scope 加入一个 符号。
List 并不是直接使用标准库的（ include/PA4/list.h ），实际上是 数据结构紫书（严蔚敏版）中的线性表：表头表示第一个元素，表尾用另一个相同的 List 实现，表示剩余的元素。
template <class T>
class List {
private:
  T *head;
  List<T>* tail;
public:
  List(T *h,List<T>* t = NULL): head(h), tail(t) { }

  T *hd() const       { return head; }  
  List<T>* tl() const { return tail; }
};
最小公共父类（lub）

特别提一下这块是因为，它可以抽象为找到 相交链表的交汇点：
160. 相交链表 - 力扣（LeetCode）
Symbol type_lub(Symbol a, Symbol b, Symbol cur_cls,
              const std::map<Symbol, InheritElem> &inherit_graph){
    if(a == b) return a;
    if(a == SELF_TYPE) return type_lub(cur_cls, b, cur_cls, inherit_graph);
    if(b == SELF_TYPE) return type_lub(a, cur_cls, cur_cls, inherit_graph);

    int al = inherit_len(a, inherit_graph), bl = inherit_len(b, inherit_graph);
    if(al < bl) {
        int tl = al; al = bl; bl = tl;
        Symbol t = a; a = b; b = t;
    }

    while(al > bl){
        a = inherit_graph.at(a).parent; al--;
    }
    while(a != b && a != No_class && b != No_class){
        a = inherit_graph.at(a).parent;
        b = inherit_graph.at(b).parent;
    }
    assert(a == b && a != No_class && b != No_class);
    return a;
}
Symbol type_lub(Symbol a, Symbol b, ClassTableP ctp){
    return type_lub(a, b, ctp->cur_cls->get_name(), ctp->inherit_graph);
}