cs143:PA4,语义分析
这一部分无论是难度还是代码量都比前面要大很多.
关于语义分析,如果说语法分析是一种上下文无关的处理方式,主要是从格式上将token整理成一个个语法单元,最终汇集成一个ast.但是这个过程无法对一些语义性质上的东西进行处理.比如说赋值的类型是否匹配,class的继承体系中是否出现了环,该变量之前有没有定义等问题.除此之外,我们必须继续收集一些语义上的信息,比如说各某些表达式的返回值等等.简而言之,类型错误检查和语义信息收集是语义分析的核心任务,这些都是基于parser生成的ast继续进行的.
我最初在做这个PA的时候,遵循了一种由易到难的过程,我大致现将classtable的构造函数以及对于class相关的检查(是否有环,重定义等),然后写了检查attr相关的代码,还有一些比较简单的类型(比如说int_const,str_const等等),也就是不需要用到环境表的,然后在写的method检查相关的模块以及一些比较复杂的类型检查(比如说dispatch,static_dispatch等还有一些用到环境表的部分).
我的代码实现如下: github
1. 有关于Class的检查和信息载入
首先我们来看语义分析的总入口:
void program_class::semant()
{
initialize_constants();
classtable = new ClassTable(classes); // 根据classes的list可以得到一个ClassTable
classtable->check_and_install();
if (classtable->errors()) {
cerr << "Compilation halted due to static semantic errors." << endl;
exit(1);
}
}我在实现时,将ClassTable加入了一些有关于class的基本检查.其中包括:
- 首先检查是否出现重定义.
- 检查和Main相关的部分.
- 然后看是否出现父类未定义.
- 最后检查是否出现loop.
此外在第一遍检查时,还需要检查是否有不合法的定义及其父类的名称是否合法等,比如说父类不可以为Bool,Int,Str等basic
class.然后在关于Main相关的检查中,主要在于检查Main
class的数量(只可以为1),在Main中是否一定有main函数等问题.执行完check_main之后再次对class进行扫描,这次扫描是为了检查是否有父class没有定义的情况.至此,我们已经可以将合法的class构造成一个继承图,在这里我采用了下面这种数据结构来表示:
std::map<Symbol, std::list<Symbol>> class_graph_;关于loop的判断,可以对构造好的继承图采用拓扑排序来进行判断.
在上面的过程中,除了通过遍历寻找上面所出现的错误之外,还需要载入一些信息,可以被后续阶段所使用.比如:
std::list<Class_> valid_classes_;
std::map<Symbol, std::list<Symbol>> class_graph_;
std::map<Symbol, Class_> class_name_map_;以上数据结构均为ClassTable类的数据成员,valid_classes用来存储没有出现出现过错误的class,在check_loop之前可以说valid_classes建立完毕,之后再根据此建立class_graph_,至于class_name_map_再涉及到判断重定义的都在被使用,在后来也可以为用来通过Symbol快速地获取其Class_.
然后在调用install_methods_and_attrs(),这个函数作用主要在于遍历class并且填充下面两个数据结构:
std::map<Symbol, std::list<method_class*>> methods_table_;
std::map<Symbol, std::list<attr_class*>> attrs_table_;这其中也涉及了一些简单的check,比如说重定义之类的,不过这两个数据结构不包含从父类中继承的部分.
2. 环境表的实现与作用
首先我们需要明确一个问题,为什么在语义分析中需要用到环境表.因为在cool语言中,我们当前所检查到的ast节点中,此时我们需要了解我们可以访问的变量(比如attribute,函数formal,let定义的临时变量等等)并且记录其type,这使得对于引用某个变量时,我们可以通过环境表来查找出其type,此外变量可访问的情况与作用域息息相关,当进入某个新的作用域时,我们或许可以访问几个新的变量,当离开某个作用域时就意味着这层作用域中涉及到的变量失效了.
因此,环境表不仅仅能将声明的变量加入进去,还需要与我们语义分析时的作用域同步更新,比如说我将要对某个class进行分析,那么我们就创建一个对应了该class的作用域,并且将其attribute都加入进去,或者我要将对某个method进行语义分析,则需要创建新的作用域并且将formal中的变量加入到环境表中.
结合代码的话,下面是关于method相关的检查:
for (auto method : curr_methods) {
objectEnv.enterscope(); // 进入该method的scope之中
......
for (int i = curr_formals->first(); curr_formals->more(i) == TRUE; i = curr_formals->next(i)) {
......
objectEnv.addid(curr_formal->get_name(), new Symbol(formal_type));
// 将formal加入环境表中
}
......
objectEnv.exitscope(); // 离开该作用域,这一层scope的变量也会弹出
}所以我们再思考这个环境表应该怎样实现,其实使用该实验中提供的SymbolTable就好,其中kv类型为<Symbol,
Symbol>,分别表示的变量名和变量类型.其定义如下:
template <class SYM, class DAT>
class SymbolTable
{
typedef SymtabEntry<SYM,DAT> ScopeEntry;
typedef List<ScopeEntry> Scope;
typedef List<Scope> ScopeList;
private:
ScopeList *tbl;
public:
SymbolTable(): tbl(NULL) { } // create a new symbol table
// Create pointer to current symbol table.
SymbolTable &operator =(const SymbolTable &s) { tbl = s.tbl; return *this; }
void fatal_error(char * msg);
// Enter a new scope. A symbol table is organized as a list of
// lists. The head of the list is the innermost scope, the tail
// holds the outer scopes. A scope must be entered before anything
// can be added to the table.
void enterscope();
// Pop the first scope off of the symbol table.
void exitscope();
// Add an item to the symbol table.
ScopeEntry *addid(SYM s, DAT *i);
// Lookup an item through all scopes of the symbol table. If found
// it returns the associated information field, if not it returns
// NULL.
DAT * lookup(SYM s);
// probe the symbol table. Check the top scope (only) for the item
// 's'. If found, return the information field. If not return NULL.
DAT *probe(SYM s);
// Prints out the contents of the symbol table
void dump();
};简而言之其底层是一个链表的链表,相当于std::list<std::list>.其中每一个list都代表一个作用域(其中保存的是变量).enterscope的作用在于追加一个新的list,也就对应了进入到一个新的作用域,addid则表示在当前作用域上追加一个变量,lookup可以从当前作用域查找某个name的变量,并返回其值(类型).也可以说这是一个类似于栈,追踪作用域以及变量声明的数据结构.
由于这是一个模版类,因此我们使用的环境表是这样的:
typedef SymbolTable<Symbol, Symbol> ObjectEnvTable; // object表
ObjectEnvTable objectEnv;所以最后做出一点总结,当需要进入新的作用域时调用enterscope,离开作用域时调用exitscope,出现变量声明时(比如说attribute,
formal,
其他临时变量等)则addid,对于变量的引用,通过lookup查询其类型.
3. 对attribute以及method的检查
这一部分我认为整个实验的难点.这一部分的检查体现在函数check_and_install中,之前我也实现了一个install_methods_and_attrs函数,但是这只是填充了不考虑继承体系的method和attribute.因此对于attribute的检查还不够.这一部分的实现,总体来说,需要对每个class遍历:
- 先获取其完整的继承链.
- 根据继承链从而获取完整的attribute和method.
- 然后再对attribute和method进行检查.
说起来挺简单,但我认为这一部分涉及到的逻辑细节挺多,写起来也是又臭又长,很多细节最初写的时候根本想不到,只有运行测试用例时才会考虑到一些细节问题.还需要注意的是,这个过程需要涉及到对环境表的操作.
1) 对attribute的检查
这一部分涉及的细节大概有:
变量名不可以为self.
检查变量名是否重复.
对于有init表达式的,需要先调用init的check_type(这里可能会用到之前环境表所收集的信息,尤其是attribute).然后比对其类型是否合法.其相关的代码如下:
curr_attr_type = (curr_attr_type == SELF_TYPE) ? curr_class->get_name() : curr_attr_type; // 如果attr的类型是SELF_TYPE
init_type = (init_type == SELF_TYPE) ? curr_class->get_name() : init_type;
if (class_name_map_.find(init_type) == class_name_map_.end()) { // 表示attr中init对应的表达式根本不存在
semant_error(curr_class_) << "the attr " << curr_attr->get_name() << "'s init type is not defined\n";
} else if (!type_less_or_equal(init_type, curr_attr_type)) { // 不是 <=的关系
semant_error(curr_class_) << "the attr type is " << curr_attr_type << " the init type is " <<
init_type << " not satisfiy <=\n";
}2) 对method的检查
之前在install_methods_and_attrs()已经进行过关于method名字的一点检查(比如重名检查).
这里涉及的method检查有:
- 函数参数的检查.首先形参name不可以为self,形参之间不可以重名,对每个形参类型都要进行检查(不可为SELF_TYPE,必须存在这个类型).
- 比对返回值类型与函数体类型.其相关代码如下:
Symbol return_type = method->get_returntype();
Expression method_expr = method->get_expr();
Symbol expr_type = method_expr->check_type();
if (return_type != SELF_TYPE && class_name_map_.find(return_type) == class_name_map_.end()) { // 找不到这个type
semant_error(method) << "the method return_type "<< return_type
<<"is not defined\n";
} else if (!type_less_or_equal(expr_type, return_type)) {
semant_error(method) << "the expr type " << expr_type << " is not <= return type " << return_type << "\n";
}3) 所涉及的环境表操作
这里我在每当遍历一个class的时候就调用环境表的enterscope,当遍历完时调用环境表的exitscope.此外我也在别人的实现中见过有人对继承链中的每一层都创建一个作用域(enterscope),当遍历完之后再根据继承链的深度调用多次exitscope.这两种方式我认为都可以,或许后者更加严谨更加符合面向对象中的特点.举个简单的例子的话:
class A {
int a_0;
int a_1;
int a_2;
}
class B : public A {
int b_0;
int b_1;
}
class C : public B {
int c_0;
int c_1;
}前者的作用域视图大致是这样的{a_0, a_1, a_2, b_0, b_1,c_0, c_1 },后者则是{a_0,a_1,a_2{b_0, b_1{c_0, c_1}}}落实到环境表中前者则是这样的:{a_0, a_1, a_2, b_0, b_1,c_0, c_1},后者为{a_0,a_1,a_2}->{b_0, b_1}->{c_0, c_1},因此其lookup的结果并没有差别.
除了class的作用域的enter与exit,还需要将所有attribute都加入到作用域中,如下所示:
for (auto chain_node : chain) { // 从Object一直到该类自身,这一步仅仅是处理attr的声明,先加入符号表之中
class__class *chain_class = dynamic_cast<class__class*> (chain_node);
chain_symbol = chain_class->get_name();
const std::list<attr_class*>& chain_attrs = attrs_table_[chain_symbol];
for (auto attr : chain_attrs) {
if (attr->get_name() == self) {
semant_error(attr) << "attr is self\n";
continue;
}
if (attr_set.count(attr->get_name())) {
semant_error(attr) << "attr is redined\n";
continue;
}
attr_set.insert(attr->get_name());
objectEnv.addid(attr->get_name(), new Symbol(attr->get_type()));
}
}上述代码即涉及到了一部分有关于check的检查操作,比如说name是否重定义(用set去重),或者是否为self.之后在将其加入到当前作用域中.
至于关于method中对于环境表的处理.对于每个method进行处理时,都需要enterscope,结束处理时则是exitscope.其中的formal则调用addid.相关的代码实现如下:
for (auto method : curr_methods) {
// 进入该method的scope之中
objectEnv.enterscope();
......
for (int i = curr_formals->first(); curr_formals->more(i) == TRUE; i = curr_formals->next(i)) {
......
// 将这个identifier加入到scope中
objectEnv.addid(curr_formal->get_name(), new Symbol(formal_type));
}
......
objectEnv.exitscope();
}以上代码省略了一些涉及到method及其formal的检查代码,只看和环境表相关的部分.
4. 对各种类型表达式的递归检查
关于这部分我认为共同点是都需要继续递归检查,然后基于递归的结果进行错误判断.大致可以分为两类,第一类比较简单不需要借助环境表.第二类则相对比较复杂,需要借助环境表来获取有关与临时变量的一些信息.
除了检查语义错误,不能忘记对当前的这个语法单元设置type,其实这些都对应了ast上的节点,因此我们可以说语义分析有对ast树中的节点类型信息进行重新调整的作用,并返回.这一部分的实现好在cool-manmal中有很详细的形式化表示,因此很多表达式边看手册就不难写出来.
其中最简单的莫过于几个常量的,如下:
Symbol int_const_class::check_type() {
type = Int;
return type;
}
Symbol bool_const_class::check_type() {
type = Bool;
return type;
}
Symbol string_const_class::check_type() {
type = Str;
return type;
}手册上的形式化描述也是简简单单,直接设置type就好了.还有几个二元operator的也比较简单,首先需要对其中涉及的表达式(比如e1和e2)进行递归地check,获取其返回值之后,再结合手册中所提到的合法条件进行判断就好了.比如说mul_class:
Symbol mul_class::check_type() {
if (e1->check_type()!= Int || e2->check_type() != Int) {
classtable->semant_error(this) << "the e1 or e2 is not Int type in a mul_class\n";
}
type = Int;
return type;
}需要分别对e1和e2进行check_type然后判断两者是否同时都为Int类型,最后设置type并返回.下面为手册中定义的语义规则:
像leq_class,divide_class,sub_class等大概也是类似的逻辑.关于block_class这种更是简单粗暴,直接对其中的body遍历对其中每一个都调用check_type,然后将type设置为最后一个表达式的类型即可,最终返回.其实现如下:
Symbol block_class::check_type() {
for (int i = body->first(); body->more(i) == TRUE; i = body->next(i)) {
type = body->nth(i)->check_type();
}
return type;
}此外,还有一些可能会涉及到SELF_TYPE的情况,我最初对于这种情况的处理,是将SELF_TYPE转化成实际的class
type,但实际上不应该这么做,直接设置成SELF_TYPE就好了.比如说new__class这种情况:
Symbol new__class::check_type() {
Symbol tp_name = type_name;
if (tp_name == SELF_TYPE) {
type = SELF_TYPE;
return type;
}
if (classtable->get_class_byname(tp_name) == nullptr) {
classtable->semant_error(this) << "The Object type not declare\n";
type = Object;
} else {
type = tp_name;
}
return type;
}之后关于dispatch和static_dispatch的实现是比较复杂的,其中需要处理的部分挺多.首先需要对其中的expr,进行check_type并且获取其类型,也就是调用某个method的对象的类型.之后根据返回的类型,从classtable中查找该method是否存在(需要考虑继承体系的情况).之后将其中参数中的表达式逐个求出,并且根据所获取的method的信息,比对formal的类型是否合法,最后设置type并返回.其中的具体实现如下:
Symbol dispatch_class::check_type() {
Class_ curr_class = classtable->get_curr_class();
Symbol expr_type = expr->check_type();
Symbol expr_type_not_self = (expr_type == SELF_TYPE)
? dynamic_cast<class__class*>(classtable->get_curr_class())->get_name() : expr_type;
if (classtable->get_class_byname(expr_type_not_self) == nullptr) { // 根本找不到这个type
classtable->semant_error(this) << "the type of expr " << expr_type_not_self << " is not defined\n";
type = Object;
return type;
}
// 判断method是否存在
method_class *method = classtable->get_method(classtable->get_class_byname(expr_type_not_self), name);
if (method == nullptr) { // 如果这个method不存在的话
classtable->semant_error(this) << "the method " << name << " is not exsit\n";
type = Object;
return type;
}
Formals method_formals = method->get_formals();
formal_class *curr_formal;
for (int i = actual->first(); actual->more(i) == TRUE; i = actual->next(i)) {
Expression expr = actual->nth(i);
Symbol curr_expr_type = expr->check_type();
curr_formal = dynamic_cast<formal_class*> (method_formals->nth(i));
Symbol formal_type = curr_formal->get_type();
if (!type_less_or_equal(curr_expr_type, formal_type)) {
classtable->semant_error(this) << "the formal is " << formal_type <<" but the type " << curr_expr_type << " is error in method "
<< method->get_name() << '\n';
}
}
Symbol return_type = method->get_returntype();
type = (return_type == SELF_TYPE) ? expr_type : return_type;
return type;
}至于static与之类似.
还有一些需要涉及到环境表操作的类型检查.比如说assign_class, typcase_class,branch_class等等.比如说assign_class这其中涉及到对某个变量(也许是attr,也许是local变量,也许是函数中的参数),其中实现如下:
Symbol assign_class::check_type() {
Symbol *id_type = objectEnv.lookup(name); // 这个变量是之前已经声明过的变量
Symbol expr_type = expr->check_type();
type = expr_type;
if (id_type == nullptr) {
classtable->semant_error(this)
<< name <<" the name of object is not defined\n";
return type;
}
if (!type_less_or_equal(expr_type, *id_type)) {
classtable->semant_error(this)
<< "the type of expr: " << expr_type << "not <= the type of id: " << *id_type << "\n";
type = Object;
}
return type;
}对于所需要赋值的变量名,需要从环境表中检索出来其类型,然后对expr进行check_type,进而比对类型是否合法.像let_class这种还会涉及到新作用域的创建,以及临时变量的声明(可以包含init).其实现如下:
Symbol let_class::check_type() {
Symbol e1_type = init->check_type();
Symbol decl_type = type_decl;
if (identifier == self) {
classtable->semant_error(this) << "the identifier can not be self in let \n";
type = Object;
return type;
}
decl_type = (decl_type == SELF_TYPE) ?
dynamic_cast<class__class*>(classtable->get_curr_class())->get_name() : decl_type;
if (classtable->get_class_byname(decl_type) == nullptr) { // 不存在这个类型的type_decl
classtable->semant_error(this) << "the decl type " << type_decl << " is not defined\n";
type = Object;
return type;
}
if (e1_type != No_type && !type_less_or_equal(e1_type, decl_type)) {
classtable->semant_error(this) << "the init type not <= decl type\n";
type = Object;
return type;
}
objectEnv.enterscope();
objectEnv.addid(identifier, new Symbol(type_decl));
Symbol e2_type = body->check_type();
objectEnv.exitscope();
type = e2_type;
return type;
}在这里由于let表达式要进入一个新的作用域,因此调用objectEnv.enterscope()创建新的作用域,然后将该变量的声明加入,之后再对let中的body进行检查,在body->check_type()中很有可能会涉及到对于刚刚加入的变量.之后处理完毕后,弹出当前作用域,设置类型并返回.
这里只分析几个比较典型的,其他的就不再一一说明了.
5. 其他问题
有一个比较重要的部分,就是比较一个class A和B,是否符合A <= B的关系,可以表示A为B的子孙类(包括和B同类型的情况),这在手册中的形式化表达式中经常可见.其实现如下:
static bool type_less_or_equal(Symbol class1, Symbol class2) {
if (class1 == class2) {
return true;
}
if (class1 != SELF_TYPE && class2 == SELF_TYPE) {
return false;
}
class1 = (class1 == SELF_TYPE) ?
dynamic_cast<class__class*>(classtable->get_curr_class())->get_name() : class1;
class__class *class_class1 = dynamic_cast<class__class*> (classtable->get_class_byname(class1));
class__class *class_class2 = dynamic_cast<class__class*> (classtable->get_class_byname(class2));
if (class_class1 == nullptr || class_class2 == nullptr) {
return false;
}
Symbol type1 = class_class1->get_name();
Symbol type2 = class_class2->get_name();
auto chain = classtable->get_class_chain(classtable->get_class_byname(class1));
for (auto chain_class : chain) {
class__class *chain__class_class = dynamic_cast<class__class*> (chain_class);
if (chain__class_class->get_name() == type2) {
return true;
}
}
return false;
}我在这里采用了一个简单粗暴的办法,就是获取class1的继承链,然后遍历(继承链是从Object一直到自身的顺序排列的),如果中途有等于class2的类型的,也就说明class2要么和class1相等,要么是class1中继承链上的某个祖先.如果找不到,就返回false,不符合该特点.
除此之外,我在说一说我的代码所存在的问题,我认为我的代码还有许多可以优化的地方,比如说关于继承链的获取需要在语义分析阶段调用多次,这样每次都需要遍历带来额外开销,这完全就是冗余的,可以设置一个map将每个class的继承链保存到其中.