Stanford Compiler PA4
课程主页：
https://www.edx.org/course/compilers
课程视频：
https://www.bilibili.com/video/BV1NE411376V?p=20&t=6
参考资料：
https://github.com/dychen/compilers/tree/master/PA4
https://github.com/yifanyang96/Compiler/tree/master/PA4
https://github.com/skyzluo/CS143-Compilers-Stanford
https://github.com/afterthat97/cool-compiler
这次回顾作业4——语义分析，这次作业难度很大，主要参考了第一份资料。
由于作业5的难度更大，所以暂时搁置课程的学习，待以后有机会再完成剩余部分的内容。
准备工作
文件介绍
$\text{cool-tree.h}$
抽象语法树节点的定义，添加了类Env，对应类型环境：
为了捕获有关标识符类型的信息，我们使用类型环境（type environment）。 该环境由三部分组成：方法环境$M$，对象环境$O$和表达式在其中出现的当前类的名称$C$。
$\text{semant.h}$
- 添加了ClassTable，包含继承图以及符合和类对应的关系，对应类型环境中的$M, O$
$\text{semant.cc}$
- 具体实现
具体流程
程序的整体流程如下：
- 扫描类，构造继承图，判断继承图是否合法。
- 检查语义条件。
分析
步骤1
分析classes
程序的开始为如下语句：
/* ClassTable constructor may do some semantic analysis */
ClassTable *classtable = new ClassTable(classes);经过分析后不难得到如下继承关系：
class class__class : public Class__class
class Class__class : public tree_node
typedef Class__class *Class_;
typedef list_node<Class_> Classes_class;
typedef Classes_class *Classes;
template <class Elem> class list_node : public tree_node所以classes为指向类列表的指针。
再回顾前一次作业中语法分析的内容：
%union {
Boolean boolean;
Symbol symbol;
Program program;
Class_ class_;
Classes classes;
Feature feature;
Features features;
Formal formal;
Formals formals;
Case case_;
Cases cases;
Expression expression;
Expressions expressions;
char *error_msg;
}
Program ast_root; /* the result of the parse */
Classes parse_results; /* for use in semantic analysis */
%type <program> program
%type <classes> class_list
%type <class_> class
program
: class_list
{ @$ = @1;
ast_root = program($1); };
/* [[class;]]+ */
class_list不难看出这里的classes即对应class_list。
继承关系的注意事项
根据cool-manual 8.4, 8.5以及https://doraemonzzz.com/2021/04/15/2021-4-15-Stanford-Compiler-Week-5-Cool-Type-Checking/可得
- 继承或重定义Bool是错误的。
- 继承或重定义String是错误的。
- 不能从self_type继承。
错误处理
错误处理需要使用semant_error，其定义如下：
// semant_error is an overloaded function for reporting errors
// during semantic analysis. There are three versions:
//
// ostream& ClassTable::semant_error()
//
// ostream& ClassTable::semant_error(Class_ c)
// print line number and filename for `c'
//
// ostream& ClassTable::semant_error(Symbol filename, tree_node *t)
// print a line number and filename特殊的类Object
在Cool中，Object是所有类的基类，所以没有父类；在semant.cc中，定义其父类为No_class，这也是判断节点是否为根节点的依据，Object_class的定义如下：
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);核心代码
核心代码如下，其中继承图检验包含在步骤2中：
ClassTable *classtable = new ClassTable(classes);
ClassTable::ClassTable(Classes classes) : semant_errors(0) , error_stream(cerr) {
/* Fill this in */
install_basic_classes();
for (int i = classes->first(); classes->more(i); i = classes->next(i)){
add_to_class_table(classes->nth(i));
}
}
void ClassTable::add_to_class_table(Class_ c){
Symbol name = c->get_name();
Symbol parent = c->get_parent();
Features features = c->get_features();
Symbol filename = c->get_filename();
if ((parent == Bool) || (parent == Str) || (parent == SELF_TYPE)){
// 不能从bool, string, self_type继承
semant_error(c) << name << "Can't inherent from " << parent << "!" << endl;
}else if (name == SELF_TYPE){
// 不能定义self_type
semant_error(c) << "Can't define SELF_TYPE!" << endl;
}else if ((class_table.find(name) != class_table.end()) ||
(inhert_graph.find(name) != inhert_graph.end())){
// 不能重复定义
semant_error(c) << "Can't be defined multiple times!" << endl;
}else{
class_table[name] = c;
inhert_graph[name] = parent;
}
}步骤2
核心代码
核心代码如下，其中feature表示method或者attr：
// second pass
if ((!classtable->errors()) && (classtable->is_valid())){
Env env(classtable);
for (int i = classes->first(); classes->more(i); i = classes->next(i)){
env.om->enterscope();
env.cur_class = classes->nth(i);
classes->nth(i)->init(env);
classes->nth(i)->type_check(env);
env.om->exitscope();
}
}
// class__class, 初始化, 递归处理, 先设置父节点
void class__class::init(Env env){
if (name != Object){
// 先设置父节点
env.ct->get_class(parent)->init(env);
}
// 设置feature
for (int i = features->first(); features->more(i); i = features->next(i)){
features->nth(i)->add_to_env(env);
}
}
// class__class
Class_ class__class::type_check(Env env){
for (int i = features->first(); features->more(i); i = features->next(i)){
features->nth(i)->type_check(env);
}
return this;
}
/**
* 1. 进入新的作用域
* 2. 添加当前类到环境
* 3. 遍历变量
* 4. 判断方法是是否继承正确
* 5. 判断实际返回类型
* 1. 如果返回类型是SELF_TYPE, 实际返回类型也为SELF_TYPE
* 2. 返回类型存在
* 3. 实际返回类型是声明类型的子类
**/
Feature method_class::type_check(Env env){
}
/**
* 1. 进入新的作用域
* 2. 添加当前类到环境
* 3. 计算init,
* 1. 判断不是self
* 2. 如果返回类型为SELF_TYPE, 则返回类型为当前类
* 3. 判断其返回类型是否为type_decl子类
**/
Feature attr_class::type_check(Env env){
}后续是每种class对应的type_check，其中每个class对应抽象语法树节点，以下是详细信息。
类对应的接口
这部分可以对照如下资料查看：
method
class method_class : public Feature_class {
protected:
Symbol name;
Formals formals;
Symbol return_type;
Expression expr;
}类型检查规则：
attr
class attr_class : public Feature_class {
protected:
Symbol name;
Symbol type_decl;
Expression init;
}类型检查规则：
formal
class formal_class : public Formal_class {
protected:
Symbol name;
Symbol type_decl;
}branch_class
class branch_class : public Case_class {
protected:
Symbol name;
Symbol type_decl;
Expression expr;
}assign
class assign_class : public Expression_class {
protected:
Symbol name;
Expression expr;
}static_dispatch_class
class static_dispatch_class : public Expression_class {
protected:
Expression expr;
Symbol type_name;
Symbol name;
Expressions actual;
}类型检查规则：
dispatch
class dispatch_class : public Expression_class {
protected:
Expression expr;
Symbol name;
Expressions actual;
}类型检查规则：
cond
class cond_class : public Expression_class {
protected:
Expression pred;
Expression then_exp;
Expression else_exp;
}类型检查规则：
loop
class loop_class : public Expression_class {
protected:
Expression pred;
Expression body;
}类型检查规则：
case
class typcase_class : public Expression_class {
protected:
Expression expr;
Cases cases;
}类型检查规则：
block class
class block_class : public Expression_class {
protected:
Expressions body;
}let
class let_class : public Expression_class {
protected:
Symbol identifier;
Symbol type_decl;
Expression init;
Expression body;
}类型检查规则：
其中$\mathrm{x}$不能是$\mathrm{self}$, $\mathrm{T_0}$可以$\text{self_type}$。
加减乘除的类型检查规则：
plus
class plus_class : public Expression_class {
protected:
Expression e1;
Expression e2;
}sub
class sub_class : public Expression_class {
protected:
Expression e1;
Expression e2;
}mul
class mul_class : public Expression_class {
protected:
Expression e1;
Expression e2;
}divide
class divide_class : public Expression_class {
protected:
Expression e1;
Expression e2;
}neg
class neg_class : public Expression_class {
protected:
Expression e1;
}类型检查规则：
lt
class lt_class : public Expression_class {
protected:
Expression e1;
Expression e2;
}类型检查规则：
eq
class eq_class : public Expression_class {
protected:
Expression e1;
Expression e2;
}类型检查规则：
注意事项：
可以自由比较任何类型，但Int，String和Bool除外，这些类只能与相同类型的对象进行比较。
comp_class
class comp_class : public Expression_class {
protected:
Expression e1;
}类型检查规则：
int
class int_const_class : public Expression_class {
protected:
Symbol token;
}bool
class bool_const_class : public Expression_class {
protected:
Boolean val;
}string
class string_const_class : public Expression_class {
protected:
Symbol token;
}new
class new__class : public Expression_class {
protected:
Symbol type_name;
}类型检查规则：
isvoid
class isvoid_class : public Expression_class {
protected:
Expression e1;
}类型检查规则：
no_expr
class no_expr_class : public Expression_class {
}object
class object_class : public Expression_class {
protected:
Symbol name;
}补充信息
树程序包中的类回顾：
// 类
Class_ class_(Symbol name, Symbol parent, Features features, Symbol filename)
{
return new class__class(name, parent, features, filename);
}
// 方法
Feature method(Symbol name, Formals formals, Symbol return_type, Expression expr)
{
return new method_class(name, formals, return_type, expr);
}
// 属性
Feature attr(Symbol name, Symbol type_decl, Expression init)
{
return new attr_class(name, type_decl, init);
}
// 参数: 名称, 类型
Formal formal(Symbol name, Symbol type_decl)
{
return new formal_class(name, type_decl);
}完整代码
cool-tree.h
#ifndef COOL_TREE_H
#define COOL_TREE_H
//////////////////////////////////////////////////////////
//
// file: cool-tree.h
//
// This file defines classes for each phylum and constructor
//
//////////////////////////////////////////////////////////
#include "tree.h"
#include "cool-tree.handcode.h"
#include <symtab.h>
// add begin
class ClassTable;
// 环境信息, 对应类型环境中的(O, M, C)
class Env {
public:
// 符号表, 对应O, M
SymbolTable<Symbol, Symbol> *om;
// 类表, 补充信息
ClassTable *ct;
// 环境的当前类, 对应C
Class_ cur_class;
Env() {
om = new SymbolTable<Symbol, Symbol>();
ct = NULL;
cur_class = NULL;
}
Env(ClassTable *ct) {
om = new SymbolTable<Symbol, Symbol>();
this->ct = ct;
cur_class = NULL;
}
};
// add end
// define the class for phylum
// define simple phylum - Program
typedef class Program_class *Program;
class Program_class : public tree_node {
public:
tree_node *copy() { return copy_Program(); }
virtual Program copy_Program() = 0;
#ifdef Program_EXTRAS
Program_EXTRAS
#endif
};
// define simple phylum - Class_
typedef class Class__class *Class_;
class Class__class : public tree_node {
public:
tree_node *copy() { return copy_Class_(); }
virtual Class_ copy_Class_() = 0;
// add begin
virtual Symbol get_name() = 0;
virtual Symbol get_parent() = 0;
virtual Features get_features() = 0;
virtual void init(Env env) = 0;
virtual Class_ type_check(Env env) = 0;
virtual bool has_method(Symbol name) = 0;
virtual Feature get_method(Symbol name) = 0;
// add end
#ifdef Class__EXTRAS
Class__EXTRAS
#endif
};
// define simple phylum - Feature
typedef class Feature_class *Feature;
class Feature_class : public tree_node {
public:
tree_node *copy() { return copy_Feature(); }
virtual Feature copy_Feature() = 0;
// add begin
virtual void add_to_env(Env env) = 0;
virtual Feature type_check(Env env) = 0;
virtual bool is_method() = 0;
virtual Symbol get_name() = 0;
virtual Formals get_formals() = 0;
virtual Symbol get_return_type() = 0;
virtual Expression get_expr() = 0;
virtual Symbol get_type_decl() = 0;
virtual Expression get_init() = 0;
// add end
#ifdef Feature_EXTRAS
Feature_EXTRAS
#endif
};
// define simple phylum - Formal
typedef class Formal_class *Formal;
class Formal_class : public tree_node {
public:
tree_node *copy() { return copy_Formal(); }
virtual Formal copy_Formal() = 0;
// add begin
virtual Formal type_check(Env env) = 0;
virtual Symbol get_name() = 0;
virtual Symbol get_type() = 0;
// add end
#ifdef Formal_EXTRAS
Formal_EXTRAS
#endif
};
// define simple phylum - Expression
typedef class Expression_class *Expression;
class Expression_class : public tree_node {
public:
tree_node *copy() { return copy_Expression(); }
virtual Expression copy_Expression() = 0;
// add begin
virtual Expression type_check(Env env) = 0;
// add end
#ifdef Expression_EXTRAS
Expression_EXTRAS
#endif
};
// define simple phylum - Case
typedef class Case_class *Case;
class Case_class : public tree_node {
public:
tree_node *copy() { return copy_Case(); }
virtual Case copy_Case() = 0;
// add begin
virtual Symbol type_check(Env env) = 0;
virtual Symbol get_type() = 0;
// add end
#ifdef Case_EXTRAS
Case_EXTRAS
#endif
};
// define the class for phylum - LIST
// define list phlyum - Classes
typedef list_node<Class_> Classes_class;
typedef Classes_class *Classes;
// define list phlyum - Features
typedef list_node<Feature> Features_class;
typedef Features_class *Features;
// define list phlyum - Formals
typedef list_node<Formal> Formals_class;
typedef Formals_class *Formals;
// define list phlyum - Expressions
typedef list_node<Expression> Expressions_class;
typedef Expressions_class *Expressions;
// define list phlyum - Cases
typedef list_node<Case> Cases_class;
typedef Cases_class *Cases;
// define the class for constructors
// define constructor - program
class program_class : public Program_class {
protected:
Classes classes;
public:
program_class(Classes a1) {
classes = a1;
}
Program copy_Program();
void dump(ostream& stream, int n);
#ifdef Program_SHARED_EXTRAS
Program_SHARED_EXTRAS
#endif
#ifdef program_EXTRAS
program_EXTRAS
#endif
};
// define constructor - class_
class class__class : public Class__class {
protected:
Symbol name;
Symbol parent;
Features features;
Symbol filename;
public:
class__class(Symbol a1, Symbol a2, Features a3, Symbol a4) {
name = a1;
parent = a2;
features = a3;
filename = a4;
}
Class_ copy_Class_();
void dump(ostream& stream, int n);
//add
Symbol get_name() { return name; };
Symbol get_parent() { return parent; };
Features get_features() { return features; };
//Symbol get_filename() { return filename; };
void init(Env env);
Class_ type_check(Env env);
bool has_method(Symbol name);
Feature get_method(Symbol name);
#ifdef Class__SHARED_EXTRAS
Class__SHARED_EXTRAS
#endif
#ifdef class__EXTRAS
class__EXTRAS
#endif
};
// define constructor - method
class method_class : public Feature_class {
protected:
Symbol name;
Formals formals;
Symbol return_type;
Expression expr;
public:
method_class(Symbol a1, Formals a2, Symbol a3, Expression a4) {
name = a1;
formals = a2;
return_type = a3;
expr = a4;
}
Feature copy_Feature();
void dump(ostream& stream, int n);
// add begin
void add_to_env(Env env);
Feature type_check(Env env);
bool is_method() { return true; };
Symbol get_name() { return name; };
Formals get_formals() { return formals; };
Symbol get_return_type() { return return_type; };
Expression get_expr() { return expr; };
Symbol get_type_decl() { return NULL; };
Expression get_init() { return NULL; };
// add end
#ifdef Feature_SHARED_EXTRAS
Feature_SHARED_EXTRAS
#endif
#ifdef method_EXTRAS
method_EXTRAS
#endif
};
// define constructor - attr
class attr_class : public Feature_class {
protected:
Symbol name;
Symbol type_decl;
Expression init;
public:
attr_class(Symbol a1, Symbol a2, Expression a3) {
name = a1;
type_decl = a2;
init = a3;
}
Feature copy_Feature();
void dump(ostream& stream, int n);
// add begin
void add_to_env(Env env);
Feature type_check(Env env);
bool is_method() { return false; };
Symbol get_name() { return name; };
Formals get_formals() { return NULL; };
Symbol get_return_type() { return NULL; };
Expression get_expr() { return NULL; };
Symbol get_type_decl() { return type_decl; };
Expression get_init() { return init; };
// add end
#ifdef Feature_SHARED_EXTRAS
Feature_SHARED_EXTRAS
#endif
#ifdef attr_EXTRAS
attr_EXTRAS
#endif
};
// define constructor - formal
class formal_class : public Formal_class {
protected:
Symbol name;
Symbol type_decl;
public:
formal_class(Symbol a1, Symbol a2) {
name = a1;
type_decl = a2;
}
Formal copy_Formal();
void dump(ostream& stream, int n);
// add begin
Formal type_check(Env env);
Symbol get_name() { return name; };
Symbol get_type() { return type_decl; };
// add end
#ifdef Formal_SHARED_EXTRAS
Formal_SHARED_EXTRAS
#endif
#ifdef formal_EXTRAS
formal_EXTRAS
#endif
};
// define constructor - branch
class branch_class : public Case_class {
protected:
Symbol name;
Symbol type_decl;
Expression expr;
public:
branch_class(Symbol a1, Symbol a2, Expression a3) {
name = a1;
type_decl = a2;
expr = a3;
}
Case copy_Case();
void dump(ostream& stream, int n);
// add begin
Symbol type_check(Env env);
Symbol get_type() { return type_decl; };
// add end
#ifdef Case_SHARED_EXTRAS
Case_SHARED_EXTRAS
#endif
#ifdef branch_EXTRAS
branch_EXTRAS
#endif
};
// define constructor - assign
class assign_class : public Expression_class {
protected:
Symbol name;
Expression expr;
public:
assign_class(Symbol a1, Expression a2) {
name = a1;
expr = a2;
}
Expression copy_Expression();
void dump(ostream& stream, int n);
// add begin
Expression type_check(Env env);
// add end
#ifdef Expression_SHARED_EXTRAS
Expression_SHARED_EXTRAS
#endif
#ifdef assign_EXTRAS
assign_EXTRAS
#endif
};
// define constructor - static_dispatch
class static_dispatch_class : public Expression_class {
protected:
Expression expr;
Symbol type_name;
Symbol name;
Expressions actual;
public:
static_dispatch_class(Expression a1, Symbol a2, Symbol a3, Expressions a4) {
expr = a1;
type_name = a2;
name = a3;
actual = a4;
}
Expression copy_Expression();
void dump(ostream& stream, int n);
// add begin
Expression type_check(Env env);
// add end
#ifdef Expression_SHARED_EXTRAS
Expression_SHARED_EXTRAS
#endif
#ifdef static_dispatch_EXTRAS
static_dispatch_EXTRAS
#endif
};
// define constructor - dispatch
class dispatch_class : public Expression_class {
protected:
Expression expr;
Symbol name;
Expressions actual;
public:
dispatch_class(Expression a1, Symbol a2, Expressions a3) {
expr = a1;
name = a2;
actual = a3;
}
Expression copy_Expression();
void dump(ostream& stream, int n);
// add begin
Expression type_check(Env env);
// add end
#ifdef Expression_SHARED_EXTRAS
Expression_SHARED_EXTRAS
#endif
#ifdef dispatch_EXTRAS
dispatch_EXTRAS
#endif
};
// define constructor - cond
class cond_class : public Expression_class {
protected:
Expression pred;
Expression then_exp;
Expression else_exp;
public:
cond_class(Expression a1, Expression a2, Expression a3) {
pred = a1;
then_exp = a2;
else_exp = a3;
}
Expression copy_Expression();
void dump(ostream& stream, int n);
// add begin
Expression type_check(Env env);
// add end
#ifdef Expression_SHARED_EXTRAS
Expression_SHARED_EXTRAS
#endif
#ifdef cond_EXTRAS
cond_EXTRAS
#endif
};
// define constructor - loop
class loop_class : public Expression_class {
protected:
Expression pred;
Expression body;
public:
loop_class(Expression a1, Expression a2) {
pred = a1;
body = a2;
}
Expression copy_Expression();
void dump(ostream& stream, int n);
// add begin
Expression type_check(Env env);
// add end
#ifdef Expression_SHARED_EXTRAS
Expression_SHARED_EXTRAS
#endif
#ifdef loop_EXTRAS
loop_EXTRAS
#endif
};
// define constructor - typcase
class typcase_class : public Expression_class {
protected:
Expression expr;
Cases cases;
public:
typcase_class(Expression a1, Cases a2) {
expr = a1;
cases = a2;
}
Expression copy_Expression();
void dump(ostream& stream, int n);
// add begin
Expression type_check(Env env);
// add end
#ifdef Expression_SHARED_EXTRAS
Expression_SHARED_EXTRAS
#endif
#ifdef typcase_EXTRAS
typcase_EXTRAS
#endif
};
// define constructor - block
class block_class : public Expression_class {
protected:
Expressions body;
public:
block_class(Expressions a1) {
body = a1;
}
Expression copy_Expression();
void dump(ostream& stream, int n);
// add begin
Expression type_check(Env env);
// add end
#ifdef Expression_SHARED_EXTRAS
Expression_SHARED_EXTRAS
#endif
#ifdef block_EXTRAS
block_EXTRAS
#endif
};
// define constructor - let
class let_class : public Expression_class {
protected:
Symbol identifier;
Symbol type_decl;
Expression init;
Expression body;
public:
let_class(Symbol a1, Symbol a2, Expression a3, Expression a4) {
identifier = a1;
type_decl = a2;
init = a3;
body = a4;
}
Expression copy_Expression();
void dump(ostream& stream, int n);
// add
Expression type_check(Env env);
#ifdef Expression_SHARED_EXTRAS
Expression_SHARED_EXTRAS
#endif
#ifdef let_EXTRAS
let_EXTRAS
#endif
};
// define constructor - plus
class plus_class : public Expression_class {
protected:
Expression e1;
Expression e2;
public:
plus_class(Expression a1, Expression a2) {
e1 = a1;
e2 = a2;
}
Expression copy_Expression();
void dump(ostream& stream, int n);
// add begin
Expression type_check(Env env);
// add end
#ifdef Expression_SHARED_EXTRAS
Expression_SHARED_EXTRAS
#endif
#ifdef plus_EXTRAS
plus_EXTRAS
#endif
};
// define constructor - sub
class sub_class : public Expression_class {
protected:
Expression e1;
Expression e2;
public:
sub_class(Expression a1, Expression a2) {
e1 = a1;
e2 = a2;
}
Expression copy_Expression();
void dump(ostream& stream, int n);
// add begin
Expression type_check(Env env);
// add end
#ifdef Expression_SHARED_EXTRAS
Expression_SHARED_EXTRAS
#endif
#ifdef sub_EXTRAS
sub_EXTRAS
#endif
};
// define constructor - mul
class mul_class : public Expression_class {
protected:
Expression e1;
Expression e2;
public:
mul_class(Expression a1, Expression a2) {
e1 = a1;
e2 = a2;
}
Expression copy_Expression();
void dump(ostream& stream, int n);
// add begin
Expression type_check(Env env);
// add end
#ifdef Expression_SHARED_EXTRAS
Expression_SHARED_EXTRAS
#endif
#ifdef mul_EXTRAS
mul_EXTRAS
#endif
};
// define constructor - divide
class divide_class : public Expression_class {
protected:
Expression e1;
Expression e2;
public:
divide_class(Expression a1, Expression a2) {
e1 = a1;
e2 = a2;
}
Expression copy_Expression();
void dump(ostream& stream, int n);
// add begin
Expression type_check(Env env);
// add end
#ifdef Expression_SHARED_EXTRAS
Expression_SHARED_EXTRAS
#endif
#ifdef divide_EXTRAS
divide_EXTRAS
#endif
};
// define constructor - neg
class neg_class : public Expression_class {
protected:
Expression e1;
public:
neg_class(Expression a1) {
e1 = a1;
}
Expression copy_Expression();
void dump(ostream& stream, int n);
// add begin
Expression type_check(Env env);
// add end
#ifdef Expression_SHARED_EXTRAS
Expression_SHARED_EXTRAS
#endif
#ifdef neg_EXTRAS
neg_EXTRAS
#endif
};
// define constructor - lt
class lt_class : public Expression_class {
protected:
Expression e1;
Expression e2;
public:
lt_class(Expression a1, Expression a2) {
e1 = a1;
e2 = a2;
}
Expression copy_Expression();
void dump(ostream& stream, int n);
// add begin
Expression type_check(Env env);
// add end
#ifdef Expression_SHARED_EXTRAS
Expression_SHARED_EXTRAS
#endif
#ifdef lt_EXTRAS
lt_EXTRAS
#endif
};
// define constructor - eq
class eq_class : public Expression_class {
protected:
Expression e1;
Expression e2;
public:
eq_class(Expression a1, Expression a2) {
e1 = a1;
e2 = a2;
}
Expression copy_Expression();
void dump(ostream& stream, int n);
// add begin
Expression type_check(Env env);
// add end
#ifdef Expression_SHARED_EXTRAS
Expression_SHARED_EXTRAS
#endif
#ifdef eq_EXTRAS
eq_EXTRAS
#endif
};
// define constructor - leq
class leq_class : public Expression_class {
protected:
Expression e1;
Expression e2;
public:
leq_class(Expression a1, Expression a2) {
e1 = a1;
e2 = a2;
}
Expression copy_Expression();
void dump(ostream& stream, int n);
// add begin
Expression type_check(Env env);
// add end
#ifdef Expression_SHARED_EXTRAS
Expression_SHARED_EXTRAS
#endif
#ifdef leq_EXTRAS
leq_EXTRAS
#endif
};
// define constructor - comp
class comp_class : public Expression_class {
protected:
Expression e1;
public:
comp_class(Expression a1) {
e1 = a1;
}
Expression copy_Expression();
void dump(ostream& stream, int n);
// add begin
Expression type_check(Env env);
// add end
#ifdef Expression_SHARED_EXTRAS
Expression_SHARED_EXTRAS
#endif
#ifdef comp_EXTRAS
comp_EXTRAS
#endif
};
// define constructor - int_const
class int_const_class : public Expression_class {
protected:
Symbol token;
public:
int_const_class(Symbol a1) {
token = a1;
}
Expression copy_Expression();
void dump(ostream& stream, int n);
// add begin
Expression type_check(Env env);
// add end
#ifdef Expression_SHARED_EXTRAS
Expression_SHARED_EXTRAS
#endif
#ifdef int_const_EXTRAS
int_const_EXTRAS
#endif
};
// define constructor - bool_const
class bool_const_class : public Expression_class {
protected:
Boolean val;
public:
bool_const_class(Boolean a1) {
val = a1;
}
Expression copy_Expression();
void dump(ostream& stream, int n);
// add begin
Expression type_check(Env env);
// add end
#ifdef Expression_SHARED_EXTRAS
Expression_SHARED_EXTRAS
#endif
#ifdef bool_const_EXTRAS
bool_const_EXTRAS
#endif
};
// define constructor - string_const
class string_const_class : public Expression_class {
protected:
Symbol token;
public:
string_const_class(Symbol a1) {
token = a1;
}
Expression copy_Expression();
void dump(ostream& stream, int n);
// add begin
Expression type_check(Env env);
// add end
#ifdef Expression_SHARED_EXTRAS
Expression_SHARED_EXTRAS
#endif
#ifdef string_const_EXTRAS
string_const_EXTRAS
#endif
};
// define constructor - new_
class new__class : public Expression_class {
protected:
Symbol type_name;
public:
new__class(Symbol a1) {
type_name = a1;
}
Expression copy_Expression();
void dump(ostream& stream, int n);
// add begin
Expression type_check(Env env);
// add end
#ifdef Expression_SHARED_EXTRAS
Expression_SHARED_EXTRAS
#endif
#ifdef new__EXTRAS
new__EXTRAS
#endif
};
// define constructor - isvoid
class isvoid_class : public Expression_class {
protected:
Expression e1;
public:
isvoid_class(Expression a1) {
e1 = a1;
}
Expression copy_Expression();
void dump(ostream& stream, int n);
// add begin
Expression type_check(Env env);
// add end
#ifdef Expression_SHARED_EXTRAS
Expression_SHARED_EXTRAS
#endif
#ifdef isvoid_EXTRAS
isvoid_EXTRAS
#endif
};
// define constructor - no_expr
class no_expr_class : public Expression_class {
protected:
public:
no_expr_class() {
}
Expression copy_Expression();
void dump(ostream& stream, int n);
// add begin
Expression type_check(Env env);
// add end
#ifdef Expression_SHARED_EXTRAS
Expression_SHARED_EXTRAS
#endif
#ifdef no_expr_EXTRAS
no_expr_EXTRAS
#endif
};
// define constructor - object
class object_class : public Expression_class {
protected:
Symbol name;
public:
object_class(Symbol a1) {
name = a1;
}
Expression copy_Expression();
void dump(ostream& stream, int n);
// add begin
Expression type_check(Env env);
// add end
#ifdef Expression_SHARED_EXTRAS
Expression_SHARED_EXTRAS
#endif
#ifdef object_EXTRAS
object_EXTRAS
#endif
};
// define the prototypes of the interface
Classes nil_Classes();
Classes single_Classes(Class_);
Classes append_Classes(Classes, Classes);
Features nil_Features();
Features single_Features(Feature);
Features append_Features(Features, Features);
Formals nil_Formals();
Formals single_Formals(Formal);
Formals append_Formals(Formals, Formals);
Expressions nil_Expressions();
Expressions single_Expressions(Expression);
Expressions append_Expressions(Expressions, Expressions);
Cases nil_Cases();
Cases single_Cases(Case);
Cases append_Cases(Cases, Cases);
Program program(Classes);
Class_ class_(Symbol, Symbol, Features, Symbol);
Feature method(Symbol, Formals, Symbol, Expression);
Feature attr(Symbol, Symbol, Expression);
Formal formal(Symbol, Symbol);
Case branch(Symbol, Symbol, Expression);
Expression assign(Symbol, Expression);
Expression static_dispatch(Expression, Symbol, Symbol, Expressions);
Expression dispatch(Expression, Symbol, Expressions);
Expression cond(Expression, Expression, Expression);
Expression loop(Expression, Expression);
Expression typcase(Expression, Cases);
Expression block(Expressions);
Expression let(Symbol, Symbol, Expression, Expression);
Expression plus(Expression, Expression);
Expression sub(Expression, Expression);
Expression mul(Expression, Expression);
Expression divide(Expression, Expression);
Expression neg(Expression);
Expression lt(Expression, Expression);
Expression eq(Expression, Expression);
Expression leq(Expression, Expression);
Expression comp(Expression);
Expression int_const(Symbol);
Expression bool_const(Boolean);
Expression string_const(Symbol);
Expression new_(Symbol);
Expression isvoid(Expression);
Expression no_expr();
Expression object(Symbol);
#endifsemant.h
#ifndef SEMANT_H_
#define SEMANT_H_
#include <assert.h>
#include <iostream>
#include <unordered_map>
#include <vector>
#include "cool-tree.h"
#include "stringtab.h"
#include "symtab.h"
#include "list.h"
#define TRUE 1
#define FALSE 0
class ClassTable;
typedef ClassTable *ClassTableP;
// 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();
ostream& error_stream;
// add begin
// 符号和类对应的关系
std::unordered_map<Symbol, Class_> class_table;
// 继承图
std::unordered_map<Symbol, Symbol> inhert_graph;
// add end
public:
ClassTable(Classes);
int errors() { return semant_errors; }
ostream& semant_error();
ostream& semant_error(Class_ c);
ostream& semant_error(Symbol filename, tree_node *t);
// add begin
void add_to_class_table(Class_ c);
bool is_valid();
Class_ get_class(Symbol s);
Symbol get_parent(Symbol child, Symbol name);
bool check_method(Symbol s1, Symbol s2, Symbol name);
bool is_class_exit(Symbol s);
bool is_sub_class(Symbol s1, Symbol s2);
Symbol lub(Symbol s1, Symbol s2);
Symbol get_parents(Symbol s, std::vector<Symbol> &v);
Formals get_formals(Symbol name, Symbol method);
Symbol get_return_type(Symbol name, Symbol method);
bool check(Formals formals, std::vector<Symbol> return_type);
// add end
};
#endifsemant.cc
#include <stdlib.h>
#include <stdio.h>
#include <stdarg.h>
#include <stack>
#include <unordered_set>
#include <vector>
#include "semant.h"
#include "utilities.h"
extern int semant_debug;
extern char *curr_filename;
//////////////////////////////////////////////////////////////////////
//
// 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");
}
// change
ClassTable::ClassTable(Classes classes) : semant_errors(0) , error_stream(cerr) {
/* Fill this in */
install_basic_classes();
for (int i = classes->first(); classes->more(i); i = classes->next(i)){
add_to_class_table(classes->nth(i));
}
}
void ClassTable::install_basic_classes() {
// The tree package uses these globals to annotate the classes built below.
// curr_lineno = 0;
Symbol filename = stringtable.add_string("<basic class>");
// The following demonstrates how to create dummy parse trees to
// refer to basic Cool classes. There's no need for method
// bodies -- these are already built into the runtime system.
// IMPORTANT: The results of the following expressions are
// stored in local variables. You will want to do something
// with those variables at the end of this method to make this
// code meaningful.
//
// 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);
// add
add_to_class_table(Object_class);
add_to_class_table(IO_class);
add_to_class_table(Int_class);
add_to_class_table(Bool_class);
add_to_class_table(Str_class);
}
////////////////////////////////////////////////////////////////////
//
// semant_error is an overloaded function for reporting errors
// during semantic analysis. There are three versions:
//
// ostream& ClassTable::semant_error()
//
// ostream& ClassTable::semant_error(Class_ c)
// print line number and filename for `c'
//
// ostream& ClassTable::semant_error(Symbol filename, tree_node *t)
// print a line number and filename
//
///////////////////////////////////////////////////////////////////
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;
}
// start
// add class to classtable
void ClassTable::add_to_class_table(Class_ c){
Symbol name = c->get_name();
Symbol parent = c->get_parent();
Features features = c->get_features();
Symbol filename = c->get_filename();
if ((parent == Bool) || (parent == Str) || (parent == SELF_TYPE)){
// 不能从bool, string, self_type继承
semant_error(c) << name << "Can't inherent from " << parent << "!" << endl;
}else if (name == SELF_TYPE){
// 不能定义self_type
semant_error(c) << "Can't define SELF_TYPE!" << endl;
}else if ((class_table.find(name) != class_table.end()) ||
(inhert_graph.find(name) != inhert_graph.end())){
// 不能重复定义
semant_error(c) << "Can't be defined multiple times!" << endl;
}else{
class_table[name] = c;
inhert_graph[name] = parent;
}
}
/**
* 判断定义是否合理：
* 1. 不含环。
* 2. 判断是否包含Main。
* 3. 判断父类是否都已定义。
**/
bool ClassTable::is_valid(){
bool cycle_flag = true;
bool main_flag = false;
bool define_flag = true;
for (auto it = inhert_graph.begin(); it != inhert_graph.end(); it++){
Symbol child = it->first;
Symbol parent = it->second;
// 判断是否包含main
if (child == Main){
main_flag = true;
}
// Object的parent为No_class, 该条件判断是否为根
while (parent != No_class){
// 环
if (parent == child){
semant_error(class_table[child]) << "Has cycle!" << endl;
return false;
}
// 不存在父节点
if (!inhert_graph.count(parent)){
semant_error(class_table[child]) << "Doesn't contain parent!" << endl;
return false;
}
parent = inhert_graph[parent];
}
}
if (main_flag){
return true;
}else{
semant_error() << "Class Main is not defined." << endl;
return false;
}
}
// 获得s对应的类
Class_ ClassTable::get_class(Symbol s){
return class_table[s];
}
// 找到有方法name的父类
Symbol ClassTable::get_parent(Symbol child, Symbol name){
Symbol parent = inhert_graph[child];
// 保证
while (parent != No_class){
// test 4
Class_ parent_class = class_table[parent];
if (parent_class->get_method(name)){
return parent_class->get_name();
}
parent = inhert_graph[parent];
}
return NULL;
};
// 判断s1和s2的方法name是否相同
bool ClassTable::check_method(Symbol s1, Symbol s2, Symbol name){
Class_ c1 = class_table[s1];
Class_ c2 = class_table[s2];
Feature f1 = c1->get_method(name);
Feature f2 = c2->get_method(name);
Formals fo1 = f1->get_formals();
Formals fo2 = f2->get_formals();
Symbol rt1 = f1->get_return_type();
Symbol rt2 = f2->get_return_type();
// 返回类型
if (rt1 != rt2){
return false;
}
// 判断输入参数类型
int i = fo1->first();
int j = fo2->first();
while ((fo1->more(i)) && (fo2->more(j))) {
if (fo1->nth(i)->get_type() != fo2->nth(j)->get_type()){
return false;
}
i = fo1->next(i);
j = fo2->next(j);
}
if (fo1->more(i) || fo2->more(j)){
return false;
}
return true;
}
// 判断类是否存在
bool ClassTable::is_class_exit(Symbol s){
return inhert_graph.count(s);
}
// 判断s1是否是s2的子类
bool ClassTable::is_sub_class(Symbol s1, Symbol s2){
if (s2 == Object){
return true;
}
// 判断s1是否为空
while (s1 != NULL){
if (s1 == s2){
return true;
}
s1 = inhert_graph[s1];
}
return false;
}
// 获得所有父节点
Symbol ClassTable::get_parents(Symbol s, std::vector<Symbol> &v){
while (s != No_class){
v.push_back(s);
s = inhert_graph[s];
}
}
// 层数最低的公共祖先
Symbol ClassTable::lub(Symbol s1, Symbol s2){
Symbol res = Object;
std::vector<Symbol> v1;
std::vector<Symbol> v2;
get_parents(s1, v1);
get_parents(s2, v2);
int n1 = v1.size();
int n2 = v2.size();
int i = n1 - 1;
int j = n2 - 1;
while ((i >= 0) && (j >= 0) && (v1[i] == v2[j])){
res = v1[i];
i--;
j--;
}
return res;
}
// 找到类名为name, 方法名为method的formals
Formals ClassTable::get_formals(Symbol name, Symbol method){
Symbol c = name;
while (c != No_class){
// 获得类
Class_ c_class = class_table[c];
// 判断是否有方法
if (c_class->get_method(method)){
Formals f = c_class->get_method(method)->get_formals();
if (f != NULL){
return f;
}
}
c = inhert_graph[c];
}
return NULL;
}
// 找到类名为name, 方法名为method的return_type
Symbol ClassTable::get_return_type(Symbol name, Symbol method){
Symbol c = name;
while (c != No_class){
// 获得类
Class_ c_class = class_table[c];
// 判断是否有方法
if (c_class->get_method(method)){
Symbol f = c_class->get_method(method)->get_return_type();
if (f != NULL){
return f;
}
}
c = inhert_graph[c];
}
return NULL;
}
// 判断par_types中元素是否为formals中对应元素的子类
bool ClassTable::check(Formals formals, std::vector<Symbol> par_types){
int i = formals->first();
int j = 0;
int n = par_types.size();
while (formals->more(i) && (j < n)){
if (!is_sub_class(par_types[j], formals->nth(i)->get_type())){
return false;
}
j++;
i = formals->next(i);
}
if ((j < n) || (formals->more(i))){
return false;
}
return true;
}
// class__class, 初始化, 递归处理, 先设置父节点
void class__class::init(Env env){
if (name != Object){
// 先设置父节点
env.ct->get_class(parent)->init(env);
}
// 设置feature
for (int i = features->first(); features->more(i); i = features->next(i)){
features->nth(i)->add_to_env(env);
}
}
// not use
bool class__class::has_method(Symbol name) {
for (int i = features->first(); features->more(i); i = features->next(i)){
if ((features->nth(i)->is_method()) && (features->nth(i)->get_name() == name)){
return true;
}
}
return false;
}
// 获得方法
Feature class__class::get_method(Symbol name) {
for (int i = features->first(); features->more(i); i = features->next(i)){
if ((features->nth(i)->is_method()) && (features->nth(i)->get_name() == name)){
return features->nth(i);
}
}
return NULL;
}
// method_class
void method_class::add_to_env(Env env){
}
// attr_class
void attr_class::add_to_env(Env env){
if (env.om->probe(name) == NULL){
// 如果scope中属性未定义, 则直接定义
env.om->addid(name, &type_decl);
}else{
// 如果scope中属性已定义, 则报错
env.ct->semant_error(env.cur_class) << "Can't be defined multiple times!" << endl;
}
}
/** type_check **/
// class__class
Class_ class__class::type_check(Env env){
for (int i = features->first(); features->more(i); i = features->next(i)){
features->nth(i)->type_check(env);
}
return this;
}
/**
* 1. 进入新的作用域
* 2. 添加当前类到环境
* 3. 遍历变量
* 4. 判断方法是是否继承正确
* 5. 判断实际返回类型
* 1. 如果返回类型是SELF_TYPE, 实际返回类型也为SELF_TYPE
* 2. 返回类型存在
* 3. 实际返回类型是声明类型的子类
**/
Feature method_class::type_check(Env env){
// step1
env.om->enterscope();
// step2
Symbol cur_class = env.cur_class->get_name();
env.om->addid(self, &cur_class);
// step3
for (int i = formals->first(); formals->more(i); i = formals->next(i)){
formals->nth(i)->type_check(env);
}
// step4
// 首先获得包含当前method的父类, 然后查看是否和父类method匹配
// 获得包含method的父类
Symbol parent_class = env.ct->get_parent(cur_class, name);
if (parent_class != NULL){
// 判断方法是否继承正确
if(!env.ct->check_method(cur_class, parent_class, name)){
env.ct->semant_error(env.cur_class) << "Method " << name << "inherent wrong!" << endl;
}
}
// step5
Symbol true_return_type = expr->type_check(env)->type;
if (return_type == SELF_TYPE){
// 5.1
if (true_return_type != SELF_TYPE){
env.ct->semant_error(env.cur_class) << "True return type should be SELF_TYPE!" << endl;
}
}else if (!env.ct->is_class_exit(return_type)){
// 5.2
env.ct->semant_error(env.cur_class) << "Return type doesn't exist!" << endl;
}else{
// 5.3
if (true_return_type == SELF_TYPE){
true_return_type = env.cur_class->get_name();
}
if (!env.ct->is_sub_class(true_return_type, return_type)){
env.ct->semant_error(env.cur_class->get_filename(), this) << "True return type isn't subclass of return type!" << endl;
}
}
// step1
env.om->exitscope();
return this;
}
/**
* 1. 进入新的作用域
* 2. 添加当前类到环境
* 3. 计算init,
* 1. 判断不是self
* 2. 如果返回类型为SELF_TYPE, 则返回类型为当前类
* 3. 判断其返回类型是否为type_decl子类
**/
Feature attr_class::type_check(Env env){
// step1
env.om->enterscope();
// step2
Symbol cur_class = env.cur_class->get_name();
env.om->addid(self, &cur_class);
// step3
Symbol true_return_type = init->type_check(env)->type;
// 3.1
if (name == self){
env.ct->semant_error(env.cur_class->get_filename(), this) << "Attr shouldn't be self!" << endl;
}
// 3.2
// SELF_TYPE的类型为自身
if (true_return_type == SELF_TYPE){
true_return_type = env.cur_class->get_name();
}
// 3.3
// 判断是否为type_decl的子类, 排除No_type
if (true_return_type != No_type){
if (!(env.ct->is_sub_class(true_return_type, type_decl))){
env.ct->semant_error(env.cur_class) << "True attr type isn't subcalss of type_decl!" << endl;
}
}
// step1
env.om->exitscope();
return this;
}
/**
* 1. 判断参数是否存在
* 2. 判断类型是否为SELF_TYPE
* 3. 添加到om中
**/
Formal formal_class::type_check(Env env){
if (env.om->probe(name)){
env.ct->semant_error(env.cur_class) << "Name already exist!" << endl;
}else if (type_decl == SELF_TYPE){
env.ct->semant_error(env.cur_class) << "Type shouldn't be SELF_TYPE!" << endl;
}else{
env.om->addid(name, &type_decl);
}
return this;
}
/**
* branch
* ID : TYPE => expr
* name : type_decl => expr
**/
Symbol branch_class::type_check(Env env){
if (env.om->probe(name)){
env.ct->semant_error(env.cur_class) << "Name already exist!" << endl;
return Object;
}
env.om->addid(name, &type_decl);
return expr->type_check(env)->type;
}
/**
* assign
* OBJECTID ASSIGN expr
* name = expr
**/
Expression assign_class::type_check(Env env){
Symbol expect_type = *env.om->lookup(name);
Symbol true_type = expr->type_check(env)->type;
if (env.ct->is_sub_class(true_type, expect_type)){
type = true_type;
}else{
env.ct->semant_error(env.cur_class) << "Assign error!" << endl;
type = Object;
}
return this;
}
/**
* static_dispatch
* expr@TYPEID.OBJECTID(actual)
* expr@name.name(actual)
**/
Expression static_dispatch_class::type_check(Env env){
// step1
Symbol t0 = expr->type_check(env)->type;
if (env.ct->is_sub_class(t0, type_name)){
// 当前类型
Symbol cur_class = t0;
if (t0 == SELF_TYPE){
cur_class = env.cur_class->get_name();
}
// step2
// 获得参数的类型
std::vector<Symbol> par_types;
for (int i = actual->first(); actual->more(i); i = actual->next(i)){
Symbol t = actual->nth(i)->type_check(env)->type;
if (t == SELF_TYPE){
t = env.cur_class->get_name();
}
par_types.push_back(t);
}
// 获得参数列表
Formals formals = env.ct->get_formals(cur_class, name);
Symbol return_type = env.ct->get_return_type(cur_class, name);
// 方法定义有误
if ((formals == NULL) || (return_type == NULL)){
env.ct->semant_error(env.cur_class) << "Method define wrong!" << endl;
type = Object;
return this;
}
// step4
if (!env.ct->check(formals, par_types)){
env.ct->semant_error(env.cur_class) << "Par type define wrong!" << endl;
type = Object;
return this;
}
// 更新type
if (return_type == SELF_TYPE){
type = t0;
}else{
type = return_type;
}
return this;
}else{
env.ct->semant_error(env.cur_class) << "Wrong class!" << endl;
type = Object;
return this;
}
}
/**
* dispatch
* expr.name(actual)
* 1. eval expr, 判断是否存在
* 2. eval actual, 获得参数类型
* 3. 判断方法是否定义有误
* 4. 判断actual的类型是否匹配
**/
Expression dispatch_class::type_check(Env env){
// step1
Symbol t0 = expr->type_check(env)->type;
// 当前类型
Symbol cur_class = t0;
if (t0 == SELF_TYPE){
cur_class = env.cur_class->get_name();
}
// step2
// 获得参数的类型
std::vector<Symbol> par_types;
for (int i = actual->first(); actual->more(i); i = actual->next(i)){
Symbol t = actual->nth(i)->type_check(env)->type;
if (t == SELF_TYPE){
t = env.cur_class->get_name();
}
par_types.push_back(t);
}
// 获得参数列表
Formals formals = env.ct->get_formals(cur_class, name);
Symbol return_type = env.ct->get_return_type(cur_class, name);
// 方法定义有误
if ((formals == NULL) || (return_type == NULL)){
env.ct->semant_error(env.cur_class) << "Method define wrong!" << endl;
type = Object;
return this;
}
// step4
if (!env.ct->check(formals, par_types)){
env.ct->semant_error(env.cur_class) << "Par type define wrong!" << endl;
type = Object;
return this;
}
// 更新type
if (return_type == SELF_TYPE){
type = t0;
}else{
type = return_type;
}
return this;
}
/**
* cond
* IF expr THEN expr ELSE expr FI
* if pred then then_exp else else_exp fi
**/
Expression cond_class::type_check(Env env){
Symbol t0 = pred->type_check(env)->type;
Symbol t1 = then_exp->type_check(env)->type;
Symbol t2 = else_exp->type_check(env)->type;
if (t1 == SELF_TYPE){
t1 = env.cur_class->get_name();
}
if (t2 == SELF_TYPE){
t2 = env.cur_class->get_name();
}
if (t0 != Bool){
env.ct->semant_error(env.cur_class) << "Pre type should be bool!" << endl;
type = Object;
}else{
type = env.ct->lub(t1, t2);
}
return this;
}
/**
* loop
* while expr loop expr pool
* while pred loop body pool
**/
Expression loop_class::type_check(Env env){
Symbol pred_type = pred->type_check(env)->type;
Symbol body_type = body->type_check(env)->type;
type = Object;
if (pred_type != Bool){
env.ct->semant_error(env.cur_class) << "Pre type should be bool!" << endl;
}
return this;
}
/**
* case
* case expr of [[ID : TYPE => expr; ]]+ esac
* case expr of cases esac
**/
Expression typcase_class::type_check(Env env){
Symbol expr_type = expr->type_check(env)->type;
// case不能相同
for (int i = cases->first(); cases->more(i); i = cases->next(i)){
for (int j = cases->first(); cases->more(j); j = cases->next(j)){
if ((i != j) && (cases->nth(i)->get_type() == cases->nth(j)->get_type())){
env.ct->semant_error(env.cur_class) << "Case should be different!" << endl;
type = Object;
return this;
}
}
}
// lub
int i = cases->first();
Symbol s = cases->nth(i)->type_check(env);
for (; cases->more(i); i = cases->next(i)){
env.om->enterscope();
Symbol s1 = cases->nth(i)->type_check(env);
s = env.ct->lub(s, s1);
env.om->exitscope();
}
type = s;
return this;
}
/**
* block class
* [[expr;]]+
* body
**/
Expression block_class::type_check(Env env){
Symbol s = NULL;
for (int i = body->first(); body->more(i); i = body->next(i)){
s = body->nth(i)->type_check(env)->type;
}
type = s;
return this;
}
/**
* let
* let ID : TYPE [ <- expr ] [[; ID : TYPE [ <- expr ]]]* in expr
* let identifier : type_decl <- init in body
**/
Expression let_class::type_check(Env env){
if (identifier == self){
env.ct->semant_error(env.cur_class) << "Self can't be used in let!" << endl;
type = Object;
}else{
Symbol expect_type = type_decl;
Symbol true_type = init->type_check(env)->type;
// no init
if (true_type == No_type){
env.om->enterscope();
env.om->addid(identifier, &expect_type);
Symbol s = body->type_check(env)->type;
type = s;
env.om->exitscope();
}else{
// 检查返回类型
if (!env.ct->is_sub_class(true_type, expect_type)){
env.ct->semant_error(env.cur_class) << "True return type isn't subcalss of return type!" << endl;
type = Object;
}else{
env.om->enterscope();
env.om->addid(identifier, &expect_type);
Symbol s = body->type_check(env)->get_type();
type = s;
env.om->exitscope();
}
}
return this;
}
}
// 这部分类规则比较简单, 略过注释
Expression plus_class::type_check(Env env){
Symbol s1 = e1->type_check(env)->type;
Symbol s2 = e2->type_check(env)->type;
if ((s1 == Int) && (s2 == Int)){
type = Int;
}else{
env.ct->semant_error(env.cur_class) << "Type should both be int!" << endl;
type = Object;
}
return this;
}
Expression sub_class::type_check(Env env){
Symbol s1 = e1->type_check(env)->type;
Symbol s2 = e2->type_check(env)->type;
if ((s1 == Int) && (s2 == Int)){
type = Int;
}else{
env.ct->semant_error(env.cur_class) << "Type should both be int!" << endl;
type = Object;
}
return this;
}
Expression mul_class::type_check(Env env){
Symbol s1 = e1->type_check(env)->type;
Symbol s2 = e2->type_check(env)->type;
if ((s1 == Int) && (s2 == Int)){
type = Int;
}else{
env.ct->semant_error(env.cur_class) << "Type should both be int!" << endl;
type = Object;
}
return this;
}
Expression divide_class::type_check(Env env){
Symbol s1 = e1->type_check(env)->type;
Symbol s2 = e2->type_check(env)->type;
if ((s1 == Int) && (s2 == Int)){
type = Int;
}else{
env.ct->semant_error(env.cur_class) << "Type should both be int!" << endl;
type = Object;
}
return this;
}
Expression neg_class::type_check(Env env){
Symbol s1 = e1->type_check(env)->type;
if (s1 == Int){
type = Int;
}else{
env.ct->semant_error(env.cur_class) << "Type should be int!" << " " << s1 << endl;
type = Object;
}
return this;
}
Expression lt_class::type_check(Env env){
Symbol s1 = e1->type_check(env)->type;
Symbol s2 = e2->type_check(env)->type;
if ((s1 == Int) && (s2 == Int)){
type = Bool;
}else{
env.ct->semant_error(env.cur_class) << "Type should both be int!" << endl;
type = Object;
}
return this;
}
Expression eq_class::type_check(Env env){
Symbol s1 = e1->type_check(env)->type;
Symbol s2 = e2->type_check(env)->type;
if ((s1 == Int && s2 != Int) || (s1 != Int && s2 == Int) ||
(s1 == Str && s2 != Str) || (s1 != Str && s2 == Str) ||
(s1 == Bool && s2 != Bool) || (s1 != Bool && s2 == Bool)){
env.ct->semant_error(env.cur_class) << "Can't compare " << s1 << " = " << s2 << endl;
type = Object;
}else{
type = Bool;
}
return this;
}
Expression leq_class::type_check(Env env){
Symbol s1 = e1->type_check(env)->type;
Symbol s2 = e2->type_check(env)->type;
if (((s1 == Int) && (s2 == Int)) ||
((s1 == Str) && (s2 == Str)) ||
((s1 == Bool) && (s2 == Bool))){
type = Bool;
}else{
env.ct->semant_error(env.cur_class) << "Wrong type!" << endl;
type = Object;
}
return this;
}
Expression comp_class::type_check(Env env){
Symbol s1 = e1->type_check(env)->type;
if (s1 == Bool){
type = Bool;
}else{
env.ct->semant_error(env.cur_class) << "Type should be bool!" << endl;
type = Object;
}
return this;
}
Expression int_const_class::type_check(Env env){
type = Int;
return this;
}
Expression bool_const_class::type_check(Env env){
type = Bool;
return this;
}
Expression string_const_class::type_check(Env env){
type = Str;
return this;
}
/**
* new
* new TYPE
* type_name
**/
Expression new__class::type_check(Env env){
Symbol s = type_name;
if (s == SELF_TYPE){
type = s;
}else if (env.ct->is_class_exit(s)){
type = s;
}else{
env.ct->semant_error(env.cur_class) << "Doesn't have class!" << endl;
type = Object;
}
return this;
}
/**
* isvoid
* isvoid expr
* isvoid e1
**/
Expression isvoid_class::type_check(Env env){
Symbol s = e1->type_check(env)->type;
if (!env.ct->is_class_exit(s)){
env.ct->semant_error(env.cur_class) << "Doesn't have class!" << endl;
type = Object;
}
type = Bool;
return this;
}
/**
* no_expr
* type = No_type
**/
Expression no_expr_class::type_check(Env env){
type = No_type;
return this;
}
/**
* object(实例化一个类)
* OBJECTID
* name
**/
Expression object_class::type_check(Env env){
// 重要
if (name == self){
type = SELF_TYPE;
}else if (env.om->lookup(name) != NULL){
type = *(env.om->lookup(name));
}else{
env.ct->semant_error(env.cur_class) << "Doesn't have class!" << endl;
type = Object;
}
return this;
}
/* This is the entry point to the semantic checker.
Your checker should do the following two things:
1) Check that the program is semantically correct
2) Decorate the abstract syntax tree with type information
by setting the `type' field in each Expression node.
(see `tree.h')
You are free to first do 1), make sure you catch all semantic
errors. Part 2) can be done in a second stage, when you want
to build mycoolc.
*/
void program_class::semant()
{
initialize_constants();
/* ClassTable constructor may do some semantic analysis */
// Classes : classes
// first pass
ClassTable *classtable = new ClassTable(classes);
/* some semantic analysis code may go here */
// second pass
if ((!classtable->errors()) && (classtable->is_valid())){
Env env(classtable);
for (int i = classes->first(); classes->more(i); i = classes->next(i)){
env.om->enterscope();
env.cur_class = classes->nth(i);
classes->nth(i)->init(env);
classes->nth(i)->type_check(env);
env.om->exitscope();
}
}
if (classtable->errors()) {
cerr << "Compilation halted due to static semantic errors." << endl;
exit(1);
}
}测试
下载测试脚本：
wget https://courses.edx.org/assets/courseware/v1/2aa4dec0c84ec3a8d91e0c1d8814452b/asset-v1:StanfordOnline+SOE.YCSCS1+1T2020+type@asset+block/pa3-grading.pl在PA4目录下运行如下命令：
make clean && make semant && perl pa3-grading.pl结果：
You got a score of 74 out of 74本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Doraemonzzz！
相关推荐
评论
ValineLivere