编译原理Semantic Analysis & Type Che

刚做完的一个Project， 做个笔记。。。

整个Project基本上主要就是对Cool的程序做一个Type check，看看有没有声明类型和实际类型不符合。然后判断一要该继承的class是不是已经定义好了。 父类里的函数，如果子类也有的话 是不是变量数量 &类型一样。有没有dead-lock cycle的继承 等等等。。。

通过这个project发现编译原理也许是和算法结合最好的地方。所有的语句都是先被处理成了AST tree 然后拿来 type check的。 比如说判断一个有没有cycle 继承的话 就是directed graph里判断DFS 判断cycle。 以及Lowest common Ancestor 也可以用来判断 声明类型和 实际类型之间的关系。

原来不是非常懂Inference Rule 的意义， 做的时候发现一个expr的type设定 如果已知这个Expr属于加法类型了。分别对e1, e2 typecheck一下看看是否他们recursively 算出来的结果是Int类别。是的话，就可以设定这个expr的结果为Int类型。

一般Type check似乎都是需要many passes. 我们这里先用了一个Pass 把每个class 以及其所对应的变量，function 集合起来。<class, function>  <class, variable>

做了一点点优化这里： 每处理到一个class，就看看他父类里有没有和自己一样的function 以及 argument是不是一样多，类型一致。

这里判断继承关系存不存在loop.

这边是Symbol Table的定义：

Symbol Table其实就是一个Stack， 里面放的东西是一层一层的Scope。Top element是当前scope的信息。比如说哪个变量 在这个 scope里的Type是啥。我们进入一个scope的时候要enter scope，出来的时候，要pop掉scope from stack.

这里是Symbol Table的应用。

我们这里把当前scope里的 formal parameter 全部扔进SymbolTable的Top scope里, overwrite 其他scope对这样变量名的一些定义。

[....怎么感觉我好像没怎么用到SymbolTable的scope呀。。。。尴尬]

比较重要的：

Dispatch:

就是一个Object调用一个method. 例如 e.f(e1,e2,...,en) 返回的应该是Tn+1.

代码版：

Type-check

确认这个Object class 或者parent class里有这个method！

formals 是formal arguments. Actual是实际传入参数。判断是不是数量一样并且类型一样。【可以是subType】

static_dispatch: