[Coursera] Compilers Design (Unit #3)

previously:
PA-2    http://www.1point3acres.com/bbs/thread-41727-1-1.html
PA-1    http://www.1point3acres.com/bbs/thread-40902-1-1.html

Programming Assignment 3

In this assignment, you will use the abstract syntax trees (AST) built by the parser to check that a program conforms to the Cool specification.
Your static semantic component should reject erroneous programs; for correct programs, it must gather certain information for use by the code
generator. The output of the semantic analyzer will be an annotated AST for use by the code generator.

At a high level, your semantic checker will have to perform the following major tasks:
    1. Look at all classes and build an inheritance graph.
    2. Check that the graph is well-formed.
    3. For each class
        (a) Traverse the AST, gathering all visible declarations in a symbol table.
        (b) Check each expression for type correctness.
        (c) Annotate the AST with types.

programming assignment 3

之前没看到这个帖子，我应该回复到这里的

心得主要是
＊ Read the f***ing manual, read, read it. If you don't understand most of it, you will risk having to start all over again half way.
＊ AST要遍历（至少）两遍，第一遍收集所有method与attribute的信息，也就是M与C这两个类型环境的信息，第二遍使用M、C、O的信息将AST里的类型域填上。（或可称disambiguate）
＊ 第一遍遍历AST时，不需深入到任何Expression。
＊ 第二遍遍历AST时，使用后序遍历（因为AST是多叉树，所以应该只有前序遍历与后序遍历），其原因是处理某个结点时，需要已经知道此结点的所有子结点的信息，故后序遍历。
＊ 这个作业的框架搭得比较好，就算写很烂的Code乱写一气（像我一开始写的时候没想清楚M表里应该存放class__class*还是Symbol；这个应该早先先想好的）也可以改，不会重写太多Code。
＊ 所有的Code都可以只写在semant.cc这一个文件里。＊ 当遇到Segmentation Fault，想找出问题所在，但是却发现mysemant是一个bash脚本没法直接用gdb包裹起来运行？可以这样子Debug：

1. $ mkfifo foo
   
2. $ ./lexer XXX.cl | ./parser XXX.cl > foo
   
3. $ gdb ./semant

复制代码

（最后一行有小于号，显示不出来）具体说明在这里找到的：http://stackoverflow.com/questions/1456253/gdb-debugging-with-pipe
简单来说，foo是一个管道，> 与 < 是输入／输出重定向…

了个去。。。没想到这次作业居然比前两次合起来还要难的多。。累计50+h hours hard work，终于完成。。这应该是完全自己做过的最大的项目了。

理解任务大约要花60%以上的时间，数据结构的设计20%，最后剩下20%实现+调试。
最终也没有使用debugger，因为不知到怎么用= =|

Shuang7 发表于 2013-4-24 22:38
了个去。。。没想到这次作业居然比前两次合起来还要难的多。。累计50+h hours hard work，终于完成。。这应 ...

你好，对于coursera上的compiler的语义分析部分我已经做了一个多星期了，可不可以把你的代码发给我参考下？

cheryl 发表于 2013-4-30 14:55
你好，对于coursera上的compiler的语义分析部分我已经做了一个多星期了，可不可以把你的代码发给我参考下 ...

额。。按照Honor Code的说法是不应该share的，不过其实你可以google到其他同学传到github上的解决方案。。（我查到了两个，一个哥们只完成了7分左右的内容，涉及类的检测，另外一个完成了58分左右，整体思路上可以参考借鉴不少，至少可以帮忙上手，后者其实结构设计得不太好，各种dynamic_cast，你可以在此基础上好好设计下~）
给你几条建议——1.好好看懂cool-tree.h，好好看dump那个文件，了解遍历AST的办法。
2.不要着急用测试，一步步来，先把class的继承关系搞清楚（审查图中回环时要用到一个算法，不过没有相应的测试点），把基本的attribute及method重复定义什么的解决了，可以得到10分左右。
3.理论上typechecking在sematic analysis之后，但是其实两者应该是可以一起做。肯定就是AST后序遍历的那个算法了，如果对函数重载、虚函数等概念不熟练的话需要好好整理下，不然实现起来很麻烦。不用期待一步到位，自顶向下先打出一条路来，再慢慢拓宽，比如我就先实现了Attribute的typecheck，过程中就要实现expression，先把加减乘除那些简单的搞定了再去搞new, object那些expression。我之后回过头来处理method（过程中处理formal），因为它显然比attribute复杂。再之后，各种dispatch，然后let，最后self_type。
有其他问题私下联系吧。

Shuang7 发表于 2013-4-30 22:22
额。。按照Honor Code的说法是不应该share的，不过其实你可以google到其他同学传到github上的解决方案。。 ...

我的思路是把OMC封装起来，构造两个vector来建立继承图，，然后一步步检查，但是不知到中间除了什么问题，就是搞不定……

cheryl 发表于 2013-5-2 19:54
我的思路是把OMC封装起来，构造两个vector来建立继承图，，然后一步步检查，但是不知到中间除了什么问题， ...

“不知道出了什么问题”
图的存储结构就那么几种，两个vector来构建不知道你说的是神马，莫非是前向图？
用哪种存储结构其实不本质，如果封装的好的话。不过对于这次作业来说，还是推荐邻接矩阵或邻接表。。其它的略复杂。

Shuang7 发表于 2013-4-30 22:22
额。。按照Honor Code的说法是不应该share的，不过其实你可以google到其他同学传到github上的解决方案。 ...

你说的回环检测是用两个指针，龟兔赛跑吗？ 哈哈哈。

Shuang7 发表于 2013-5-3 14:46
“不知道出了什么问题”
图的存储结构就那么几种，两个vector来构建不知道你说的是神马，莫非 ...

邻接矩阵怎么弄？好像比较麻烦。如果用map<Symbol,Symbol>来存边。是非常简单的。