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

BlaXuan · 发表于 2023-2-12 18:14

代码地址：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 &#34;plus&#34;; }
// defined in sub_class
char* get_expr_constructor(){ return &#34;sub&#34;; }
// defined in mul_class
char* get_expr_constructor(){ return &#34;mul&#34;; }
// defined in divide_class
char* get_expr_constructor(){ return &#34;divide&#34;; }
要做什么

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

对所有类定义进行检查 ：重复定义检查、父类未定义检查、构建依赖图、循环依赖检查
语法检查与静态语义分析 ：变量命名和作用域、表达式类型确定、类型检查。静态语义分析在 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 << &#34;Compilation halted due to static semantic errors.&#34; << 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<<&#34;# After build inherit graph.&#34;<<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)<<&#34;SELF_TYPE cannot be redefined.&#34;<<endl;
         continue;
      }
      bool inserted = type_nodes.emplace(cls->get_name(), cls).second;
      if(! inserted){
         semant_error(cls)<<cls->get_name()->get_string()<<&#34; cannot be redefined.&#34;<<endl;
      }
      inherit_graph.emplace(cls->get_name(), *(new InheritElem(Object)));
}
// 2) try to establish inheritance relationship.
// Invalid parents will be replaced with &#39;Object&#39;
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()<<&#34;There exist cyclic inheritance.&#34;<<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);
}

		自动登录	找回密码
密码			立即注册

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