准备把把一些优秀的公开课的lab给刷一遍，已经完成的公开课有：
6.s081 (操作系统)CMU15445（数据库）cs149（并行计算）cs143（编译原理）games101（计算机图形学）6.824（分布式系统）cs144（计算机网络）
后期计划的公开课：
6.858（计算机系统安全）
所有的实验部分的代码见github仓库。
https://github.com/wangdh15
编译器一直是自己想学的内容，之前草草看过龙书的部分内容，这次就着cs143这门课的lab来完整地入门一下编译原理。
课程的lab可以直接从edx上面下载到。整个课程lab分为五个部分：
cool语言实现stack词法分析语法分析语义分析代码生成
第1个lab是熟悉课程需要实现的语言cool。第2,3个lab主要是学习flex和bison两个工具的使用，其中bison对error的处理要想清楚。这两部分没有什么有趣的事情，建议看一遍《flex&bison》这本书，应该没有什么大问题。 后两个lab代码量比较大，且更有意思一点。缺点是课程给的代码框架比较老，编码风格一开始很不适应，不过自己实现的部分只需要调用给的框架的一小部分接口，熟悉了也就没什么大问题了。下面就后两个lab的自己的一些实现细节和代码中有的坑进行说明。
1. LAB4 语义分析
该部分实验的主要任务是对生成的AST进行类型检查。具体的规则manual写的非常清楚了，对着实现一遍即可。其中有几个点：
继承图检测环。该部分我直接使用了拓扑排序的算法。case分支涉及到继承树找若干个节点的最近公共祖先的问题。这部分考虑效率的话，可以先对继承树跑一边dfs，为每个节点分配一个dfs序号（中序遍历序号），然后求n个节点的最近公共祖先问题可以转化为求最小序号和最大序号节点的最近公共祖先的问题（反证一下即可）。然后经典的求两个节点的lca，可以采用树上倍增或者离线+tarjan算法求解即可。具体可google。2. LAB5 代码生成
该部分实验的具体任务是利用打好类型信息的AST，生成可执行的MIPS代码。这部分主要的工作：
阅读给的trap.handle代码，熟悉提供的几个基础类的函数的实现（主要是了解函数调用的规范）。为每个class生成一个protObj，并为每个class生成对应dispatchTab，给每个class分配一个编号。该编号作为各个tab的索引。为每个class分配编号，我还是采用了LAB4中的dfs序，这样有如下的好处：在case语句中，我们需要找到所有分支哪个距离当前表达式的类型最近，如果采用dfs序的话，对于一个节点，其所有子类的编号处于一个范围内，所以可以非常容易判断一个类型是不是另一个类型的子类。其次在生成代码的时候，可以对编号最大的放到判断的最前面，这是因为如果类A是类B的子类，则类B的编号一定比类A的编号大，这样就可以优先匹配到与表达式类型最近的分支。一个class所有的attr的初始化操作放到Class.init函数中实现。对于每个函数，其可以看到的变量有：1. 当前class和父类的所有成员。2. 函数传入的参数。 3. 局部变量所以可以在生成的过程中，利用this指针加偏移量访问类成员，利用fp指针加偏移量访问函数参数和局部变量。为了简单，采用课程的建议使用了stack machine的模式，每个表达式调用前后确保栈的状态不发生变化。函数参数的栈空间的回收在背调函数中进行（与trap.handle中保持一致）提供的代码中有一个坑，就是如果一个节点是no_type的话，对应的指针是nullptr，而不是代码中提供的no_type，这个地方调试了很久才发现。。
剩下的就是按部就班实现各个部分的代码了。调试的时候需要看一下spim如何使用，如何打断点，如何查看各个寄存机状态，内存状态等，这些google手册就行了。
具体实现细节见下面的仓库。每个lab都能够100%通过提供的测试样例。
https://github.com/wangdh15/cs143
gitee把所有项目给我整private了，现在把代码全部搬到了github上。。。
