前言

本章为语义分析的实验，通过编写c++代码来完成对语义的检测

How to start

在开始之前，需要先看下PA4里面的一些代码，这些代码在前面的语法分析其实已经用到了

主要为：cool-tree.h cool-tree.handcode.h semant.h semant.cc，再加上symboltabe的使用：

symtab_example.cc include/PA4/symtab.h

其实在学习学校课程的时候，一开始我看目录的时候就在想，语法分析和语义分析的区别是？

其实很简单，例如在自然语言中，“我吃鸡肉”这个句子，从语法和语义上来讲都是正确的，主谓宾

但反过来，“鸡肉吃我”，语法上也是对的，主谓宾正确，但语义上有问题

放在编程语言中，比如重复定义一个类，从语法上来说没毛病，但语义上看，类可能不能重复定义

所以理解起来其实不难，从字面上看就可以，语法分析检查语言的格式但并不关心具体的含义

一些步骤

语义分析需要的一些步骤，大致如下：

  • 分析类的语义
    • 创建类表，用于记录各个类
    • 安装基本类Object，Str，Int，Bool，Io
    • 安装各个用户定义的类并检查SELF_TYPE，重复定义和继承(不能从Int，Str，Bool继承)
    • 检查各个类的继承关系，检查所继承的父类是否定义
    • 检查类继承是否成环，如A→B,B→C,C→A
    • 检查Main类是否存在，Main类中是否有main方法
  • 类内
    • 记录各个类中的方法method和成员
  • 方法
    • 检测方法的重复定义
    • 方法的继承
    • …………..
  • 成员
    • 成员名
    • 类型未定义
  • 表达式

代码

测试：

image.png

ClassTable

ClassTable:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class ClassTable;
typedef ClassTable *ClassTableP;
typedef std::map<Symbol, Class_>Symbol_Table;
typedef std::vector<method_class*>Method_List;
typedef std::map<Class_, Method_List>Method_Table;
typedef std::map<Symbol, bool>Symbol_Map;
// This is a structure that may be used to contain the semantic
// information such as the inheritance graph.  You may use it or not as
// you like: it is only here to provide a container for the supplied
// methods.

class ClassTable {
private:
  int semant_errors;
  void install_basic_classes();
  void install_classes(Classes classes);
  void check_inheritance();
  ostream& error_stream;

public:
  Method_Table methodtable;
  Symbol_Table symboltable;
  ClassTable(Classes);
  int errors() { return semant_errors; }
  ostream& semant_error();
  ostream& semant_error(Class_ c);
  ostream& semant_error(Symbol filename, tree_node *t);
  ostream& internal_error(int lineno);
  void check_main();
  void install_methods();
  void check_methods();
  std::vector<Class_> getInheritanceChain(Class_ c);
  std::vector<Class_> getInheritanceChain(Symbol name);
  method_class* get_Method(Class_ c, Symbol name);
};

symboltable用于存储类和类名，methodtable用于存储类和其对应的方法

基本类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
void ClassTable::install_basic_classes() {

    Symbol filename = stringtable.add_string("<basic class>");

    // 
    // The Object class has no parent class. Its methods are
    //        abort() : Object    aborts the program
    //        type_name() : Str   returns a string representation of class name
    //        copy() : SELF_TYPE  returns a copy of the object
    //
    // There is no need for method bodies in the basic classes---these
    // are already built in to the runtime system.

    Class_ Object_class =
	class_(Object, 
	       No_class,
	       append_Features(
			       append_Features(
					       single_Features(method(cool_abort, nil_Formals(), Object, no_expr())),
					       single_Features(method(type_name, nil_Formals(), Str, no_expr()))),
			       single_Features(method(copy, nil_Formals(), SELF_TYPE, no_expr()))),
	       filename);

    // 
    // The IO class inherits from Object. Its methods are
    //        out_string(Str) : SELF_TYPE       writes a string to the output
    //        out_int(Int) : SELF_TYPE            "    an int    "  "     "
    //        in_string() : Str                 reads a string from the input
    //        in_int() : Int                      "   an int     "  "     "
    //
    Class_ IO_class = 
	class_(IO, 
	       Object,
	       append_Features(
			       append_Features(
					       append_Features(
							       single_Features(method(out_string, single_Formals(formal(arg, Str)),
										      SELF_TYPE, no_expr())),
							       single_Features(method(out_int, single_Formals(formal(arg, Int)),
										      SELF_TYPE, no_expr()))),
					       single_Features(method(in_string, nil_Formals(), Str, no_expr()))),
			       single_Features(method(in_int, nil_Formals(), Int, no_expr()))),
	       filename);  

    //
    // The Int class has no methods and only a single attribute, the
    // "val" for the integer. 
    //
    Class_ Int_class =
	class_(Int, 
	       Object,
	       single_Features(attr(val, prim_slot, no_expr())),
	       filename);

    //
    // Bool also has only the "val" slot.
    //
    Class_ Bool_class =
	class_(Bool, Object, single_Features(attr(val, prim_slot, no_expr())),filename);

    //
    // The class Str has a number of slots and operations:
    //       val                                  the length of the string
    //       str_field                            the string itself
    //       length() : Int                       returns length of the string
    //       concat(arg: Str) : Str               performs string concatenation
    //       substr(arg: Int, arg2: Int): Str     substring selection
    //       
    Class_ Str_class =
	class_(Str, 
	       Object,
	       append_Features(
			       append_Features(
					       append_Features(
							       append_Features(
									       single_Features(attr(val, Int, no_expr())),
									       single_Features(attr(str_field, prim_slot, no_expr()))),
							       single_Features(method(length, nil_Formals(), Int, no_expr()))),
					       single_Features(method(concat, 
								      single_Formals(formal(arg, Str)),
								      Str, 
								      no_expr()))),
			       single_Features(method(substr, 
						      append_Formals(single_Formals(formal(arg, Int)), 
								     single_Formals(formal(arg2, Int))),
						      Str, 
						      no_expr()))),
	       filename);
    
    //install name
    symboltable[Object_class->get_name()] = Object_class;
    symboltable[IO_class->get_name()] = IO_class;
    symboltable[Int_class->get_name()] = Int_class;
    symboltable[Bool_class->get_name()] = Bool_class;
    symboltable[Str_class->get_name()] = Str_class;
}

几个基本类的安装，主要在最后做了修改，记录到name表中

类

类的安装与检查

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void ClassTable::install_classes(Classes classes){
    //list<node>
    Symbol curr_name;
    Symbol parent_name;
    for (int i = classes->first();classes->more(i);i = classes->next(i)){
        curr_class = classes->nth(i);
        curr_name = curr_class->get_name();
        parent_name = curr_class->get_parent();
        //check SELF_TYPE
        if (curr_name == SELF_TYPE){
            semant_error(curr_class) << "Redefinition of basic class SELF_TYPE.\\n";
        }else if(symboltable.find(curr_name) != symboltable.end()){
            semant_error(curr_class) << "Class " << curr_name << " was previously defined.\\n";
        }else if(parent_name == Int || parent_name == Str || parent_name == Bool){
            semant_error(curr_class) << "Class " << curr_name << " cannot inherit Class " << parent_name << ".\\n";
        }else{
            symboltable[curr_name] = curr_class;
        }
    }
}

程序是由n个类构成的，因此，program类中有一系列的class_list，即此处的classes

函数完成类的基本安装，所谓安装，就是先将所有类都记录进name表中以便后续处理，同时完成了一些检测，如重复定义等

这里用到的first()，more()和next()，是classes列表一些方法，同样的在其他地方也多次使用，可见tree.h中的定义和实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <class Elem> class list_node : public tree_node {
public:
    tree_node *copy()            { return copy_list(); }
    Elem nth(int n);
    //
    // The next three define a simple iterator.
    //
    int first()      { return 0; }
    int next(int n)  { return n + 1; }
    int more(int n)  { return (n < len()); }

    virtual list_node<Elem> *copy_list() = 0;
    virtual ~list_node() { }
    virtual int len() = 0;
    virtual Elem nth_length(int n, int &len) = 0;

    static list_node<Elem> *nil();
    static list_node<Elem> *single(Elem);
    static list_node<Elem> *append(list_node<Elem> *l1,list_node<Elem> *l2);
};

继承检查

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//check the inheritance of classes
void ClassTable::check_inheritance(){
    Symbol curr_name; 
    Symbol parent_name;
    std::set<Symbol> tmp_set;
    Symbol first_symbol;
    for (Symbol_Table::iterator it = symboltable.begin();it != symboltable.end();it++){
        curr_name = it->first;
        curr_class = it->second;
        parent_name = curr_class->get_parent();

        //check if parent defined
        if (curr_name != Object && parent_name != Object){
            if (symboltable.find(parent_name) == symboltable.end()){
                semant_error(curr_class) << "Class " << curr_name << " inherits from an undefined class " << parent_name << ".\\n";
                continue;
            }
            //check cycle
            first_symbol = curr_name;
            while(curr_name != Object){
                parent_name = curr_class->get_parent();
                // semant_error(curr_class) << "Class " << curr_name << " loglog.\\n";
                if(tmp_set.find(curr_name) != tmp_set.end()){
                    semant_error(symboltable[first_symbol]) << "Class " << first_symbol  
                                    << ", or an ancestor of " << first_symbol << ", is involved in an inheritance cycle.\\n";
                    break;
                }else{
                    tmp_set.insert(curr_name);
                    curr_name = parent_name;
                    curr_class = symboltable[curr_name];
                }
            }
            tmp_set.clear();
            
        }
    }
}

检查父类未定义，类继承成环的问题

方法

Main和main

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void ClassTable::check_main(){
    //check Main
    if (symboltable.find(Main) == symboltable.end()){
        semant_error() << "Class Main is not defined.\\n";
        return;
    }

    //check main() method
    Features feature_list = symboltable[Main]->get_features();
    bool find_flag = false;
    bool para_flag = false;
    method_class* curr_method;

    for (int i = feature_list->first();feature_list->more(i);i = feature_list->next(i)){
        if(feature_list->nth(i)->is_method() && static_cast<method_class*>(feature_list->nth(i))->get_name() == main_meth){
            find_flag = true;
            curr_method = static_cast<method_class*>(feature_list->nth(i));
            Formals formals = curr_method->get_formals();
            if ((formals->len()) >= 1){
                para_flag = true;
            }
        }
    }
    
    if(!find_flag){
        semant_error(symboltable[Main]) << "No 'main' method in class Main.\\n";
        return;
    }
    //检测main参数
    if(para_flag){
        semant_error(symboltable[Main]->get_filename(), curr_method) << "'main' method in class Main should have no arguments.\\n";
    }
}

安装与检查

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
void ClassTable::install_methods(){
    Symbol curr_nmae;
    Features features;
    Method_List methodlist;
    method_class* tmp_method;
    attr_class* tmp_attr;
    for (Symbol_Table::iterator it = symboltable.begin();it != symboltable.end();it++){
        curr_class = it->second;
        //install every method
        features = curr_class->get_features();
        for (int i = features->first();features->more(i);i = features->next(i)){
            if(features->nth(i)->is_method()){
                //method
                tmp_method = static_cast<method_class*>(features->nth(i));
                bool find_flag = false;
                for (Method_List::iterator itv = methodlist.begin();itv != methodlist.end();itv++){
                    if ((*itv)->get_name() == tmp_method->get_name()){
                        find_flag = true;
                    }
                }
                if (find_flag){
                    semant_error(curr_class->get_filename(), tmp_method) << "Method " 
                                                                << tmp_method->get_name() << " is multiply defined.\\n";
                }
                else{
                    methodlist.push_back(tmp_method);
                }
            }else{
                tmp_attr = static_cast<attr_class*>(features->nth(i));
                if (tmp_attr->get_name() == self){
                    semant_error(curr_class->get_filename(), tmp_attr) << "'self' cannot be the name of an attribute.\\n";
                    return;
                }
            }   
        }
        methodtable[curr_class] = methodlist;
        methodlist.clear();
    }
}

对每一个类的各个方法进行记录，检查重复定义，成员名等问题

方法的检查

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
void ClassTable::check_methods(){
    Symbol curr_name;
    std::vector<Class_> chain;
    for (Symbol_Table::iterator it = symboltable.begin();it != symboltable.end();it++){
        if (it->first == Object || it->first == IO || it->first == Int || it->first == Bool || it->first == Str) continue;
        curr_name = it->first;
        curr_class = it->second;
        //获取父类链子
        chain = getInheritanceChain(curr_class);
        chain.push_back(curr_class);

        for (size_t i = 1;i < chain.size();i++){
            //继承父类的成员，将当前类所继承来的成员和数据类型写进符号表
            Class_ ancestor_class = chain[i];
            Features features = ancestor_class->get_features();
            attrtable.enterscope();
            for (int j = features->first();features->more(j);j = features->next(j)){
                if (features->nth(j)->is_attr()){
                    attr_class* curr_attr = static_cast<attr_class*>(features->nth(j));
                    if (i == chain.size()-1 && attrtable.lookup(curr_attr->get_name())){
                        semant_error(curr_class->get_filename(), curr_attr) << "Attribute " << curr_attr->get_name()
                                                                        << " is an attribute of an inherited class.\\n";
                    }
                    attrtable.addid(curr_attr->get_name(),new Symbol(curr_attr->get_type()));
                }
            }
        }
        //对子类和父类中的同名方法进行检查
        Features features = curr_class->get_features();
        for (int i = features->first();features->more(i);i = features->next(i)){
            //每个方法
            if(features->nth(i)->is_method()){
                method_class* curr_method = static_cast<method_class*>(features->nth(i));
                //对该方法进行检查
                curr_method->check_type();
                for (size_t j = 1;j < chain.size();j++){
                    method_class* ancestor_method = get_Method(chain[j], curr_method->get_name());
                    if (ancestor_method){
                        //比较同名方法的类型是否一致
                        if (curr_method->get_type() != ancestor_method->get_type()){
                            semant_error(curr_class->get_filename(), curr_method) << "In redefined method " 
                                                << curr_method->get_name() << ", return type " << curr_method->get_type() 
                                                << " is different from original return type " << ancestor_method->get_type() 
                                                << ".\\n";
                        }
                        //比较同名方法的参数类型是否一致
                        Formals curr_formals = curr_method->get_formals();
                        Formals ancestor_formals = ancestor_method->get_formals();

                        int n1 = curr_formals->first();
                        int n2 = ancestor_formals->first();
                        while(curr_formals->more(n1) && ancestor_formals->more(n2)){
                            if (curr_formals->nth(n1)->get_type() != ancestor_formals->nth(n2)->get_type()){
                                semant_error(curr_class->get_filename(), curr_formals->nth(n1)) << "In redefined method " 
                                        << curr_method->get_name() << ", parameter type " << curr_formals->nth(n1)->get_type()
                                        << " is different from original type " << ancestor_formals->nth(n2)->get_type() << ".\\n";
                            }
                            n1 = curr_formals->next(n1);
                            n2 = ancestor_formals->next(n2);
                            if (curr_formals->more(n1) != ancestor_formals->more(n2)){
                                semant_error(curr_class->get_filename(), curr_method) 
                                        << "Incompatible number of formal parameters in redefined method " 
                                        << curr_method->get_name() << ".\\n";
                            }
                        }
                    }
                }
            }else{//成员
                attr_class* curr_attr = static_cast<attr_class*>(features->nth(i));
                //获取初始化表达式的类型
                Symbol expr_type = curr_attr->get_init()->check_type();
                if (symboltable.find(curr_attr->get_type()) == symboltable.end()){
                    semant_error(curr_class->get_filename(), curr_attr) << "Class " << curr_attr->get_type() 
                                << " of attribute " << curr_attr->get_name() << " is undefined.\\n";
                }else if(classtable->symboltable.find(expr_type) != classtable->symboltable.end() && !conform(expr_type, curr_attr->get_type())){
                    //检查初始化的表达式类型是否存在且是否与定义的类型相等
                    classtable->semant_error(curr_class->get_filename(), curr_attr) << "Inferred type " << expr_type 
                                            << " of initialization of attribute " << curr_attr->get_name() 
                                            << " does not conform to declared type " << curr_attr->get_type() << ".\\n";
                }
            }
        }
        for (size_t k = 1; k < chain.size(); k++){
            attrtable.exitscope();
        }
    }
}

对父子类中的同名方法和同名成员进行检查

对成员的类型定义进行检查

这里用到了另一个重要的数据结构：symtab

符号表，用于检查过程中的记录，检查参数等等，该表为一个可以自己定义的键值对表，定义在symtab.h中

可以通过看symtab_example.cc来学习其使用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <stdlib.h>
#include <stdio.h>
#include <symtab.h>

int main(int argc, char *argv[]) {
  // 
  // Create a mapping from strings to ints
  //

  SymbolTable<char *,int> *map = new SymbolTable<char *, int>();
  char *Fred = "Fred";
  char *Mary = "Mary";
  char *Miguel = "Miguel";

  // enter a scope; required before any symbols can be added
  map->enterscope();
  
  // add a couple of entries mapping name to age.
  // note the second argument must be a pointer to an integer
  map->addid(Fred, new int(22));
  map->addid(Mary, new int(25));

  // add a scope, add more names:
  map->enterscope();
  map->addid(Miguel, new int(35));
  map->addid(Mary, new int(23));

  // check whether Fred is in the current scope; predicate is false
  cout << ((map->probe(Fred) != NULL) ? "Yes\\n" : "No\\n");

  // check whether Mary is in any scope; predicate is true
  cout << ((map->lookup(Mary) != NULL) ? "Yes\\n" : "No\\n");

  // print age of most-closely-nested Mary; note the
  // lookup returns a pointer to an integer.
  cout << *(map->lookup(Mary)) << "\\n";

  // check whether Miguel is in the current scope; predicate is true
  cout << ((map->probe(Miguel) != NULL) ? "Yes\\n" : "No\\n");

  // leave a scope
  map->exitscope();

  // print age of most-closely-nested Mary
  cout << *(map->lookup(Mary)) << "\\n";

  // check whether Fred is in the current scope; predicate is now true
  cout << ((map->probe(Fred) != NULL) ? "Yes\\n" : "No\\n");

  // check whether Miguel is in any scope; predicate is now false
  cout << ((map->lookup(Miguel) != NULL) ? "Yes\\n" : "No\\n");

  return 0;
 
}

测试运行：

1
2
make symtab_example
./symtab_example

得到：

1
2
3
4
5
6
7
8
$ ./symtab_example
No
Yes
23
Yes
25
Yes
No

enterscope用于进入新一层符号表，exitscope退出到上一层

probe在当前符号表寻找相应记录，lookup用于在全局符号表中寻找记录

最后一部分，对各种类型的表达式进行检查

如case表达式，if表达式，while表达式等等，主要的目标就是类型，重复定义，是否未定义，该表达式的返回的数据类型等等

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
#include <stdlib.h>
#include <stdio.h>
#include <stdarg.h>
#include "semant.h"
#include "utilities.h"

extern int semant_debug;
extern char *curr_filename;

typedef SymbolTable<Symbol,Symbol> Attrtable;
Attrtable attrtable;
Class_ curr_class;
static ClassTable *classtable;
//////////////////////////////////////////////////////////////////////
//
// Symbols
//
// For convenience, a large number of symbols are predefined here.
// These symbols include the primitive type and method names, as well
// as fixed names used by the runtime system.
//
//////////////////////////////////////////////////////////////////////
static Symbol 
    arg,
    arg2,
    Bool,
    concat,
    cool_abort,
    copy,
    Int,
    in_int,
    in_string,
    IO,
    length,
    Main,
    main_meth,
    No_class,
    No_type,
    Object,
    out_int,
    out_string,
    prim_slot,
    self,
    SELF_TYPE,
    Str,
    str_field,
    substr,
    type_name,
    val;
//
// Initializing the predefined symbols.
//
static void initialize_constants(void)
{
    arg         = idtable.add_string("arg");
    arg2        = idtable.add_string("arg2");
    Bool        = idtable.add_string("Bool");
    concat      = idtable.add_string("concat");
    cool_abort  = idtable.add_string("abort");
    copy        = idtable.add_string("copy");
    Int         = idtable.add_string("Int");
    in_int      = idtable.add_string("in_int");
    in_string   = idtable.add_string("in_string");
    IO          = idtable.add_string("IO");
    length      = idtable.add_string("length");
    Main        = idtable.add_string("Main");
    main_meth   = idtable.add_string("main");
    //   _no_class is a symbol that can't be the name of any 
    //   user-defined class.
    No_class    = idtable.add_string("_no_class");
    No_type     = idtable.add_string("_no_type");
    Object      = idtable.add_string("Object");
    out_int     = idtable.add_string("out_int");
    out_string  = idtable.add_string("out_string");
    prim_slot   = idtable.add_string("_prim_slot");
    self        = idtable.add_string("self");
    SELF_TYPE   = idtable.add_string("SELF_TYPE");
    Str         = idtable.add_string("String");
    str_field   = idtable.add_string("_str_field");
    substr      = idtable.add_string("substr");
    type_name   = idtable.add_string("type_name");
    val         = idtable.add_string("_val");
}

ostream& ClassTable::semant_error(Class_ c)
{                                                             
    return semant_error(c->get_filename(),c);
}

ostream& ClassTable::semant_error(Symbol filename, tree_node *t)
{
    error_stream << filename << ":" << t->get_line_number() << ": ";
    return semant_error();
}

ostream& ClassTable::semant_error()                  
{                                                 
    semant_errors++;                            
    return error_stream;
}

ostream& ClassTable::internal_error(int lineno) {
    error_stream << "FATAL:" << lineno << ": ";
    return error_stream;
}

ClassTable::ClassTable(Classes classes) : semant_errors(0) , error_stream(cerr) { //init semant_errors and error_stream

    /* Fill this in */
    install_basic_classes();
    install_classes(classes);
    check_inheritance();
    
}

void ClassTable::install_basic_classes() {

    Symbol filename = stringtable.add_string("<basic class>");

    // 
    // The Object class has no parent class. Its methods are
    //        abort() : Object    aborts the program
    //        type_name() : Str   returns a string representation of class name
    //        copy() : SELF_TYPE  returns a copy of the object
    //
    // There is no need for method bodies in the basic classes---these
    // are already built in to the runtime system.

    Class_ Object_class =
	class_(Object, 
	       No_class,
	       append_Features(
			       append_Features(
					       single_Features(method(cool_abort, nil_Formals(), Object, no_expr())),
					       single_Features(method(type_name, nil_Formals(), Str, no_expr()))),
			       single_Features(method(copy, nil_Formals(), SELF_TYPE, no_expr()))),
	       filename);

    // 
    // The IO class inherits from Object. Its methods are
    //        out_string(Str) : SELF_TYPE       writes a string to the output
    //        out_int(Int) : SELF_TYPE            "    an int    "  "     "
    //        in_string() : Str                 reads a string from the input
    //        in_int() : Int                      "   an int     "  "     "
    //
    Class_ IO_class = 
	class_(IO, 
	       Object,
	       append_Features(
			       append_Features(
					       append_Features(
							       single_Features(method(out_string, single_Formals(formal(arg, Str)),
										      SELF_TYPE, no_expr())),
							       single_Features(method(out_int, single_Formals(formal(arg, Int)),
										      SELF_TYPE, no_expr()))),
					       single_Features(method(in_string, nil_Formals(), Str, no_expr()))),
			       single_Features(method(in_int, nil_Formals(), Int, no_expr()))),
	       filename);  

    //
    // The Int class has no methods and only a single attribute, the
    // "val" for the integer. 
    //
    Class_ Int_class =
	class_(Int, 
	       Object,
	       single_Features(attr(val, prim_slot, no_expr())),
	       filename);

    //
    // Bool also has only the "val" slot.
    //
    Class_ Bool_class =
	class_(Bool, Object, single_Features(attr(val, prim_slot, no_expr())),filename);

    //
    // The class Str has a number of slots and operations:
    //       val                                  the length of the string
    //       str_field                            the string itself
    //       length() : Int                       returns length of the string
    //       concat(arg: Str) : Str               performs string concatenation
    //       substr(arg: Int, arg2: Int): Str     substring selection
    //       
    Class_ Str_class =
	class_(Str, 
	       Object,
	       append_Features(
			       append_Features(
					       append_Features(
							       append_Features(
									       single_Features(attr(val, Int, no_expr())),
									       single_Features(attr(str_field, prim_slot, no_expr()))),
							       single_Features(method(length, nil_Formals(), Int, no_expr()))),
					       single_Features(method(concat, 
								      single_Formals(formal(arg, Str)),
								      Str, 
								      no_expr()))),
			       single_Features(method(substr, 
						      append_Formals(single_Formals(formal(arg, Int)), 
								     single_Formals(formal(arg2, Int))),
						      Str, 
						      no_expr()))),
	       filename);
    
    //install name
    symboltable[Object_class->get_name()] = Object_class;
    symboltable[IO_class->get_name()] = IO_class;
    symboltable[Int_class->get_name()] = Int_class;
    symboltable[Bool_class->get_name()] = Bool_class;
    symboltable[Str_class->get_name()] = Str_class;
}

void ClassTable::install_classes(Classes classes){
    //list<node>
    Symbol curr_name;
    Symbol parent_name;
    for (int i = classes->first();classes->more(i);i = classes->next(i)){
        curr_class = classes->nth(i);
        curr_name = curr_class->get_name();
        parent_name = curr_class->get_parent();
        //check SELF_TYPE
        if (curr_name == SELF_TYPE){
            semant_error(curr_class) << "Redefinition of basic class SELF_TYPE.\\n";
        }else if(symboltable.find(curr_name) != symboltable.end()){
            semant_error(curr_class) << "Class " << curr_name << " was previously defined.\\n";
        }else if(parent_name == Int || parent_name == Str || parent_name == Bool){
            semant_error(curr_class) << "Class " << curr_name << " cannot inherit Class " << parent_name << ".\\n";
        }else{
            symboltable[curr_name] = curr_class;
        }
    }
}

//check the inheritance of classes
void ClassTable::check_inheritance(){
    Symbol curr_name; 
    Symbol parent_name;
    std::set<Symbol> tmp_set;
    Symbol first_symbol;
    for (Symbol_Table::iterator it = symboltable.begin();it != symboltable.end();it++){
        curr_name = it->first;
        curr_class = it->second;
        parent_name = curr_class->get_parent();

        //check if parent defined
        if (curr_name != Object && parent_name != Object){
            if (symboltable.find(parent_name) == symboltable.end()){
                semant_error(curr_class) << "Class " << curr_name << " inherits from an undefined class " << parent_name << ".\\n";
                continue;
            }
            //check cycle
            first_symbol = curr_name;
            while(curr_name != Object){
                parent_name = curr_class->get_parent();
                // semant_error(curr_class) << "Class " << curr_name << " loglog.\\n";
                if(tmp_set.find(curr_name) != tmp_set.end()){
                    semant_error(symboltable[first_symbol]) << "Class " << first_symbol  
                                    << ", or an ancestor of " << first_symbol << ", is involved in an inheritance cycle.\\n";
                    break;
                }else{
                    tmp_set.insert(curr_name);
                    curr_name = parent_name;
                    curr_class = symboltable[curr_name];
                }
            }
            tmp_set.clear();
            
        }
    }
}

void ClassTable::check_main(){
    //check Main
    if (symboltable.find(Main) == symboltable.end()){
        semant_error() << "Class Main is not defined.\\n";
        return;
    }

    //check main() method
    Features feature_list = symboltable[Main]->get_features();
    bool find_flag = false;
    bool para_flag = false;
    method_class* curr_method;

    for (int i = feature_list->first();feature_list->more(i);i = feature_list->next(i)){
        if(feature_list->nth(i)->is_method() && static_cast<method_class*>(feature_list->nth(i))->get_name() == main_meth){
            find_flag = true;
            curr_method = static_cast<method_class*>(feature_list->nth(i));
            Formals formals = curr_method->get_formals();
            if ((formals->len()) >= 1){
                para_flag = true;
            }
        }
    }
    
    if(!find_flag){
        semant_error(symboltable[Main]) << "No 'main' method in class Main.\\n";
        return;
    }
    //检测main参数
    if(para_flag){
        semant_error(symboltable[Main]->get_filename(), curr_method) << "'main' method in class Main should have no arguments.\\n";
    }

}

void ClassTable::install_methods(){
    Symbol curr_nmae;
    Features features;
    Method_List methodlist;
    method_class* tmp_method;
    attr_class* tmp_attr;
    for (Symbol_Table::iterator it = symboltable.begin();it != symboltable.end();it++){
        curr_class = it->second;
        //install every method
        features = curr_class->get_features();
        for (int i = features->first();features->more(i);i = features->next(i)){
            if(features->nth(i)->is_method()){
                //method
                tmp_method = static_cast<method_class*>(features->nth(i));
                bool find_flag = false;
                for (Method_List::iterator itv = methodlist.begin();itv != methodlist.end();itv++){
                    if ((*itv)->get_name() == tmp_method->get_name()){
                        find_flag = true;
                    }
                }
                if (find_flag){
                    semant_error(curr_class->get_filename(), tmp_method) << "Method " 
                                                                << tmp_method->get_name() << " is multiply defined.\\n";
                }
                else{
                    methodlist.push_back(tmp_method);
                }
            }else{
                tmp_attr = static_cast<attr_class*>(features->nth(i));
                if (tmp_attr->get_name() == self){
                    semant_error(curr_class->get_filename(), tmp_attr) << "'self' cannot be the name of an attribute.\\n";
                    return;
                }
            }   
        }
        methodtable[curr_class] = methodlist;
        methodlist.clear();
    }
}

//to make a chain for inherits
std::vector<Class_> ClassTable::getInheritanceChain(Class_ c){
    std::vector<Class_> chain;
    while(c->get_name() != Object){
        chain.push_back(c);
        if (symboltable.find(c->get_parent()) == symboltable.end()){
            internal_error(__LINE__) << "invalid inheritance chain.\\n";
        }
        else
            c = symboltable[c->get_parent()];
    }
    chain.push_back(symboltable[Object]);
    return chain;
}
std::vector<Class_> ClassTable::getInheritanceChain(Symbol name) {
    if (name == SELF_TYPE)
        name = curr_class->get_name();
    if (symboltable.find(name) == symboltable.end()){
        internal_error(__LINE__) << name << " not found in class table.\\n";
    }
    return getInheritanceChain(symboltable[name]);
}

static Class_ LCA(Symbol name1, Symbol name2) {
    
    std::vector<Class_> chain1 = classtable->getInheritanceChain(name1);
    std::vector<Class_> chain2 = classtable->getInheritanceChain(name2);

    std::reverse(chain1.begin(), chain1.end());
    std::reverse(chain2.begin(), chain2.end());

    size_t i;
    for (i = 1; i < std::min(chain1.size(), chain2.size()); i++)
        if (chain1[i] != chain2[i])
            return chain1[i - 1];

    return chain1[i - 1];
}

//根据类和方法名返回类中的方法
method_class* ClassTable::get_Method(Class_ c, Symbol name){
    Method_List methodlist = methodtable[c];
    for (size_t i = 0;i < methodlist.size();i++){
        if (methodlist[i]->get_name() == name){
            return methodlist[i];
        }
    }
    return NULL;
}

//该函数用于检测变量的类型和表达式返回的是否一致
static bool conform(Symbol name1, Symbol name2){
    if (name1 == SELF_TYPE && name2 == SELF_TYPE)
        return true;
    if (name1 != SELF_TYPE && name2 == SELF_TYPE)
        return false;
    if (name1 == SELF_TYPE)
        name1 = curr_class->get_name();

    if (classtable->symboltable.find(name1) == classtable->symboltable.end()){
        classtable->internal_error(__LINE__) << name1 << " not found in class table.\\n";
        return false;
    }

    if (classtable->symboltable.find(name2) == classtable->symboltable.end()){
        classtable->internal_error(__LINE__) << name2 << " not found in class table.\\n";
        return false;
    }
    
    Class_ c1 = classtable->symboltable[name1];
    Class_ c2 = classtable->symboltable[name2];
    std::vector<Class_> chain = classtable->getInheritanceChain(c1);
    
    //检测是否是同一个类型，即检测是否为同一个类或父子类
    for (size_t i = 0; i < chain.size(); i++)
        if (chain[i] == c2)
            return true;

    return false;
}

//针对方法的检查函数，检查函数名，参数，返回值
void method_class::check_type(){
    attrtable.enterscope();

    formal_class* curr_formal;
    for (int i = formals->first();formals->more(i);i = formals->next(i)){
        curr_formal = static_cast<formal_class*>(formals->nth(i));
        //参数名不能为self
        if (curr_formal->get_name() == self){
            classtable->semant_error(curr_class->get_filename(), curr_formal) << "'self' cannot be the name of a formal parameter\\n"; 
        }else if (curr_formal->get_type() == SELF_TYPE){
            classtable->semant_error(curr_class->get_filename(), curr_formal) << "Formal parameter " << curr_formal->get_name() 
                                                << "cannot have type SELF_TYPE.\\n";
            return;
        }else if(attrtable.probe(curr_formal->get_name())){
            classtable->semant_error(curr_class->get_filename(), curr_formal) << "Formal parameter " << curr_formal->get_name()
                                                                            << " is multiply defined.\\n";
        }else if(classtable->symboltable.find(curr_formal->get_type()) == classtable->symboltable.end()){
            classtable->semant_error(curr_class->get_filename(), curr_formal) << "Class " << curr_formal->get_type() << " of formal parameter " 
                                                << curr_formal->get_name() << " is undefined.\\n";
        }else{
            attrtable.addid(curr_formal->get_name(), new Symbol(curr_formal->get_type()));
        }
    }
    
    Symbol expr_type = expr->check_type();
    
    if (return_type != SELF_TYPE && classtable->symboltable.find(return_type) == classtable->symboltable.end()){
        classtable->semant_error(curr_class->get_filename(), this) << "Undefined return type " << return_type 
                                                                << " in method " << name << ".\\n";
    }
    else if (!conform(expr_type, return_type))
        classtable->semant_error(curr_class->get_filename(), this) << "Inferred return type " << expr_type << " of method " 
                                                    << name << " does not conform to declared return type " << return_type << ".\\n";

    attrtable.exitscope();
}

//针对各类表达式的check
Symbol assign_class::check_type(){
    //赋值表达式的返回值应为赋值语句的返回值
    Symbol r_type = expr->check_type();

    //验证所赋值的变量是否定义
    if (!(attrtable.lookup(name))){
        classtable->semant_error(curr_class->get_filename(), this) << "Assignment to undeclared variable " << name << ".\\n";
        type = r_type;
        return r_type;
    }

    //比较所赋值的变量的类型和表达式返回的数据类型是否一致
    Symbol l_type = *attrtable.lookup(name);
    if(!conform(r_type, l_type)){
        classtable->semant_error(curr_class->get_filename(),this) << "Type " << r_type 
                                        << " of assigned expression does not conform to declared type " << l_type 
                                        << " of identifier " << name << ".\\n";
    }

    type = r_type;
    return r_type;
}

Symbol static_dispatch_class::check_type(){
    bool error = false;
    Symbol expr_type = expr->check_type();

    if (type_name != SELF_TYPE && classtable->symboltable.find(type_name) ==  classtable->symboltable.end()) {
        classtable->semant_error(curr_class->get_filename(), this) << "Static dispatch to undefined class " << type_name << ".\\n";
        type = Object;
        return type;
    }

    if (expr_type != SELF_TYPE && classtable->symboltable.find(expr_type) == classtable->symboltable.end()) {
        type = Object;
        return type;
    }

    if (!conform(expr_type, type_name)) {
        error = true;
        classtable->semant_error(curr_class->get_filename(), this) << "Expression type " << expr_type 
                                << " does not conform to declared static dispatch type " << type_name << ".\\n";
    }
    
    method_class* method = 0;
    std::vector<Class_> chain = classtable->getInheritanceChain(type_name);
    for (size_t i = 0; i < chain.size(); i++) {
        Method_List methods = classtable->methodtable[chain[i]];
        for (size_t i = 0; i < methods.size(); i++)
            if (methods[i]->get_name() == name) {
                method = methods[i];
                break;
            }
    }

    if (method == 0) {
        error = true;
        classtable->semant_error(curr_class->get_filename(), this) << "Static dispatch to undefined method " << name << ".\\n";
    } else {
        Formals formals = method->get_formals();
        int k1 = actual->first(), k2 = formals->first();
        while (actual->more(k1) && formals->more(k2)) {
            Symbol actual_type = actual->nth(k1)->check_type();
            Symbol formal_type = formals->nth(k2)->get_type();
            if (!conform(actual_type, formal_type)) {
                error = true;
                classtable->semant_error(curr_class->get_filename(), this) << "In call of method " << name << ", type " 
                                    << actual_type << " of parameter " << formals->nth(k2)->get_name() 
                                    << " does not conform to declared type " << formal_type << ".\\n";
            }
            k1 = actual->next(k1);
            k2 = formals->next(k2);
            if (actual->more(k1) != formals->more(k2)) {
                error = true;
                classtable->semant_error(curr_class->get_filename(), this) << "Method " << name 
                                                        << " called with wrong number of arguments.\\n";
            }
        }
    }

    if (error) {
        type = Object;
    } else {
        type = method->get_type();
        if (type == SELF_TYPE)
            type = this->type_name;
    }

    return type;
}

Symbol dispatch_class::check_type(){
    bool error = false;
    Symbol expr_type = expr->check_type();

    if (expr_type != SELF_TYPE && classtable->symboltable.find(expr_type) == classtable->symboltable.end()) {
        classtable->semant_error(curr_class->get_filename(), this) << "Dispatch on undefined class " << expr_type << ".\\n";
        type = Object;
        return type;
    }

    method_class* method = 0;
    std::vector<Class_> chain = classtable->getInheritanceChain(expr_type);
    for (size_t i = 0; i < chain.size(); i++) {
        Method_List methods = classtable->methodtable[chain[i]];
        for (size_t i = 0; i < methods.size(); i++)
            if (methods[i]->get_name() == name) {
                method = methods[i];
                break;
            }
    }

    if (method == 0) {
        error = true;
        classtable->semant_error(curr_class->get_filename(), this) << "Dispatch to undefined method " << name << ".\\n";
    } else {
        Formals formals = method->get_formals();
        int k1 = actual->first(), k2 = formals->first();
        while (actual->more(k1) && formals->more(k2)) {
            Symbol actual_type = actual->nth(k1)->check_type();
            Symbol formal_type = formals->nth(k2)->get_type();
            if (!conform(actual_type, formal_type)) {
                error = true;
                classtable->semant_error(curr_class->get_filename(), this) << "In call of method " << name << ", type " 
                                                << actual_type << " of parameter " << formals->nth(k2)->get_name()
                                                << " does not conform to declared type " << formal_type << ".\\n";
            }
            k1 = actual->next(k1);
            k2 = formals->next(k2);
            if (actual->more(k1) xor formals->more(k2)) {
                error = true;
                classtable->semant_error(curr_class->get_filename(), this) << "Method " << name 
                                                << " called with wrong number of arguments.\\n";
            }
        }
    }

    if (error) {
        type = Object;
    } else {
        type = method->get_type();
        if (type == SELF_TYPE)
            type = expr_type;
    }

    return type;
}

//针对if分支
Symbol cond_class::check_type(){
    //cond(Expression pred, Expression then_exp, Expression else_exp)
    
    if (pred->check_type() != Bool){
        classtable->semant_error(curr_class->get_filename(), this) << "Predicate of 'if' does not have type Bool.\\n";
    }

    Symbol then_type = then_exp->check_type();
    Symbol else_type = else_exp->check_type();
    // cout << "xxxxx" << "\\n";
    // 

    if (then_type == SELF_TYPE && else_type == SELF_TYPE){
        type = SELF_TYPE;
    }else{
        //选择辈分大的类作为返回类型
        type = LCA(then_type, else_type)->get_name();
    }

    
    return type;
    
}

//循环
Symbol loop_class::check_type(){
    //loop(Expression pred, Expression body)
    if (pred->check_type() != Bool){
        classtable->semant_error(curr_class->get_filename(), this) << "Loop condition does not have type Bool.\\n";
    }
    body->check_type();
    type = Object;
    return type;
}

//case语句
Symbol typcase_class::check_type(){
    //typcase(Expression expr, Cases cases)
    Symbol expr_type = expr->check_type();
    std::set<Symbol> branch_type_decls;

    for (int i = cases->first(); cases->more(i); i = cases->next(i)) {
        branch_class* branch = static_cast<branch_class*>(cases->nth(i));
        if (branch_type_decls.find(branch->get_type()) != branch_type_decls.end())
            //此处为重复定义分支
           classtable->semant_error(curr_class->get_filename(), branch) << "Duplicate branch " << branch->get_type() 
                                                                                                << " in case statement.\\n";
        else
            branch_type_decls.insert(branch->get_type());
        //检查每个分支的类型
        Symbol branch_type = branch->check_type();
        if (i == cases->first())
            type = branch_type;
        else if (type != SELF_TYPE || branch_type != SELF_TYPE)
            //这里是选择辈分比较大的那个类返回
            type = LCA(type, branch_type)->get_name();
    }

    return type;
}

//case中的分支
Symbol branch_class::check_type(){
    //branch(Symbol name, Symbol type_decl, Expression expr)
    attrtable.enterscope();
    //将该参数保存到符号表
    attrtable.addid(name, new Symbol(type_decl));
    //开始检测
    type = expr->check_type();
    attrtable.exitscope();
    return type;
}

//块语句,expr_list,多个expr
Symbol block_class::check_type(){
    //block(Expressions body)
    //整个块的返回类型由最后一个表达式决定
    for (int i = body->first(); body->more(i); i = body->next(i))
        type = body->nth(i)->check_type();
    return type;
}

//let语句
Symbol let_class::check_type(){
    //let : OBJECTID ':' TYPEID ASSIGN expr IN expr
    //let(Symbol identifier, Symbol type_decl, Expression init, Expression body)
    attrtable.enterscope();
    if (identifier == self){
        classtable->semant_error(curr_class->get_filename(), this) << "'self' cannot be bound in a 'let' expression.\\n";
    }
    attrtable.addid(identifier, new Symbol(type_decl));

    //检测赋值表达式的类型和let定义的数据类型是否一致
    Symbol init_type = init->check_type();
    if (classtable->symboltable.find(type_decl) == classtable->symboltable.end() && type_decl != SELF_TYPE)
        classtable->semant_error(curr_class->get_filename(), this) << "Class " << type_decl << " of let-bound identifier " 
                                                                                        << identifier << " is undefined.\\n";
    else if (init_type != No_type && !conform(init_type, type_decl))
        classtable->semant_error(curr_class->get_filename(), this) << "Inferred type " << init_type << " of initialization of " 
                                                            << identifier << " does not conform to identifier's declared type " 
                                                            << type_decl << ".\\n";

    type = body->check_type();
    attrtable.exitscope();
    return type;
}

//检查加减乘除两端是否都为Int
Symbol plus_class::check_type(){
    //plus(Expression e1, Expression e2)
    Symbol l_type = e1->check_type();
    Symbol r_type = e2->check_type();
    if (l_type != Int || r_type != Int){
        classtable->semant_error(curr_class->get_filename(), this) << "non-Int arguments: " << l_type << " * " << r_type << "\\n";
    }
    type = Int;
    return type;
}

Symbol sub_class::check_type(){
    //sub(Expression e1, Expression e2)
    Symbol l_type = e1->check_type();
    Symbol r_type = e2->check_type();
    if (l_type != Int || r_type != Int){
        classtable->semant_error(curr_class->get_filename(), this) << "non-Int arguments: " << l_type << " + " << r_type << "\\n";
    }
    type = Int;
    return type;
}

Symbol mul_class::check_type(){
    //mul(Expression e1, Expression e2)
    Symbol l_type = e1->check_type();
    Symbol r_type = e2->check_type();
    if (l_type != Int || r_type != Int){
        classtable->semant_error(curr_class->get_filename(), this) << "non-Int arguments: " << l_type << " * " << r_type << "\\n";
    }
    type = Int;
    return type;
}

Symbol divide_class::check_type(){
    //divide(Expression e1, Expression e2)
    Symbol l_type = e1->check_type();
    Symbol r_type = e2->check_type();
    if (l_type != Int || r_type != Int){
        classtable->semant_error(curr_class->get_filename(), this) << "non-Int arguments: " << l_type << " * " << r_type << "\\n";
    }
    type = Int;
    return type;
}
//取反表达式，检测Int
Symbol neg_class::check_type(){
    //neg(Expression e1)
    type = e1->check_type();
    if (type != Int){
        classtable->semant_error(curr_class->get_filename(), this) << "Argument of '~' has type " << type << " instead of Int.\\n";
    }
    type = Int;
    return type;
}

//小于
Symbol lt_class::check_type(){
    //lt(Expression e1, Expression e2)
    Symbol l_type = e1->check_type();
    Symbol r_type = e2->check_type();
    if (l_type != Int || r_type != Int){
        classtable->semant_error(curr_class->get_filename(), this) << "non-Int arguments: " << l_type << " < " << r_type << "\\n";
    }
    type = Bool;
    return type;
}

//等于
Symbol eq_class::check_type(){
    //eq(Expression e1, Expression e2)
    Symbol l_type = e1->check_type();
    Symbol r_type = e2->check_type();
    if ((l_type == Int || l_type == Bool || l_type == Str || r_type == Int || r_type == Bool || r_type == Str) && l_type != r_type){
        classtable->semant_error(curr_class->get_filename(), this) << "Illegal comparison with a basic type.\\n";
    }
    type = Bool;
    return type;
}

//小于等于
Symbol leq_class::check_type(){
    //leq(Expression e1, Expression e2)
    Symbol l_type = e1->check_type();
    Symbol r_type = e2->check_type();
    if (l_type != Int || r_type != Int){
        classtable->semant_error(curr_class->get_filename(), this) << "non-Int arguments: " << l_type << " <= " << r_type << "\\n";
    }
    type = Bool;
    return type;
}

//not
Symbol comp_class::check_type(){
    //comp(Expression e1)
    type = e1->check_type();
    if (type != Bool){
        classtable->semant_error(curr_class->get_filename(), this) << "Argument of 'not' has type " 
                                                                        << type << " instead of Bool.\\n";
    }
    type = Bool;
    return type;
}

//常量
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;
}

//new class_name
Symbol new__class::check_type(){
    //new_(Symbol type_name)
    //检查new的这个类是否存在
    if(type_name != SELF_TYPE && classtable->symboltable.find(type_name) == classtable->symboltable.end()){
        classtable->semant_error(curr_class->get_filename(), this) << "'new' used with undefined class " << type_name << ".\\n";
        type_name = Object;
    }

    type = type_name;
    return type;
}

//为空表达式
Symbol isvoid_class::check_type(){
    //isvoid(Expression e1)
    e1->check_type();
    type = Bool;
    return type;
}

Symbol no_expr_class::check_type(){
    type = No_type;
    return type;
}

//类
Symbol object_class::check_type(){
    //object(Symbol name)
    if (name == self){
        type = SELF_TYPE;
    }else if(attrtable.lookup(name)){
        //检查该是否定义
        type = *attrtable.lookup(name); 
    }else{
        classtable->semant_error(curr_class->get_filename(), this) << "Undeclared identifier " << name << ".\\n";
        type = Object;
    }
    return type;
}

void ClassTable::check_methods(){
    Symbol curr_name;
    std::vector<Class_> chain;
    for (Symbol_Table::iterator it = symboltable.begin();it != symboltable.end();it++){
        if (it->first == Object || it->first == IO || it->first == Int || it->first == Bool || it->first == Str) continue;
        curr_name = it->first;
        curr_class = it->second;
        //获取父类链子
        chain = getInheritanceChain(curr_class);
        chain.push_back(curr_class);

        for (size_t i = 1;i < chain.size();i++){
            //继承父类的成员，将当前类所继承来的成员和数据类型写进符号表
            Class_ ancestor_class = chain[i];
            Features features = ancestor_class->get_features();
            attrtable.enterscope();
            for (int j = features->first();features->more(j);j = features->next(j)){
                if (features->nth(j)->is_attr()){
                    attr_class* curr_attr = static_cast<attr_class*>(features->nth(j));
                    if (i == chain.size()-1 && attrtable.lookup(curr_attr->get_name())){
                        semant_error(curr_class->get_filename(), curr_attr) << "Attribute " << curr_attr->get_name()
                                                                        << " is an attribute of an inherited class.\\n";
                    }
                    attrtable.addid(curr_attr->get_name(),new Symbol(curr_attr->get_type()));
                }
            }
        }
        //对子类和父类中的同名方法进行检查
        Features features = curr_class->get_features();
        for (int i = features->first();features->more(i);i = features->next(i)){
            //每个方法
            if(features->nth(i)->is_method()){
                method_class* curr_method = static_cast<method_class*>(features->nth(i));
                //对该方法进行检查
                curr_method->check_type();
                for (size_t j = 1;j < chain.size();j++){
                    method_class* ancestor_method = get_Method(chain[j], curr_method->get_name());
                    if (ancestor_method){
                        //比较同名方法的类型是否一致
                        if (curr_method->get_type() != ancestor_method->get_type()){
                            semant_error(curr_class->get_filename(), curr_method) << "In redefined method " 
                                                << curr_method->get_name() << ", return type " << curr_method->get_type() 
                                                << " is different from original return type " << ancestor_method->get_type() 
                                                << ".\\n";
                        }
                        //比较同名方法的参数类型是否一致
                        Formals curr_formals = curr_method->get_formals();
                        Formals ancestor_formals = ancestor_method->get_formals();

                        int n1 = curr_formals->first();
                        int n2 = ancestor_formals->first();
                        while(curr_formals->more(n1) && ancestor_formals->more(n2)){
                            if (curr_formals->nth(n1)->get_type() != ancestor_formals->nth(n2)->get_type()){
                                semant_error(curr_class->get_filename(), curr_formals->nth(n1)) << "In redefined method " 
                                        << curr_method->get_name() << ", parameter type " << curr_formals->nth(n1)->get_type()
                                        << " is different from original type " << ancestor_formals->nth(n2)->get_type() << ".\\n";
                            }
                            n1 = curr_formals->next(n1);
                            n2 = ancestor_formals->next(n2);
                            if (curr_formals->more(n1) != ancestor_formals->more(n2)){
                                semant_error(curr_class->get_filename(), curr_method) 
                                        << "Incompatible number of formal parameters in redefined method " 
                                        << curr_method->get_name() << ".\\n";
                            }
                        }
                    }
                }
            }else{//成员
                attr_class* curr_attr = static_cast<attr_class*>(features->nth(i));
                //获取初始化表达式的类型
                Symbol expr_type = curr_attr->get_init()->check_type();
                if (symboltable.find(curr_attr->get_type()) == symboltable.end()){
                    semant_error(curr_class->get_filename(), curr_attr) << "Class " << curr_attr->get_type() 
                                << " of attribute " << curr_attr->get_name() << " is undefined.\\n";
                }else if(classtable->symboltable.find(expr_type) != classtable->symboltable.end() && !conform(expr_type, curr_attr->get_type())){
                    //检查初始化的表达式类型是否存在且是否与定义的类型相等
                    classtable->semant_error(curr_class->get_filename(), curr_attr) << "Inferred type " << expr_type 
                                            << " of initialization of attribute " << curr_attr->get_name() 
                                            << " does not conform to declared type " << curr_attr->get_type() << ".\\n";
                }
            }
        }
        for (size_t k = 1; k < chain.size(); k++){
            attrtable.exitscope();
        }
    }
}

void program_class::semant()
{
    initialize_constants();

    /* ClassTable constructor may do some semantic analysis */
    classtable = new ClassTable(classes);

    /* some semantic analysis code may go here */

    if (classtable->errors()) {
        cerr << "Compilation halted due to static semantic errors." << endl;
        exit(1);
    }
    
    classtable->check_main();
    
    classtable->install_methods();
    
    classtable->check_methods();
    
    if (classtable->errors()) {
        cerr << "Compilation halted due to static semantic errors." << endl;
        exit(1);
    }
}

参考

https://github.com/afterthat97/cool-compiler

https://github.com/skyzluo/CS143-Compilers-Stanford/

https://github.com/dychen/compilers/