简单DAG生成算法的一个性质

核心提示： 就可以得到名为dag.png的图片，跟本文顶上的第二张图是一样的，简单DAG生成算法的一个性质(5)， Expression及其派生类是用来表示解析源码后得到的AST或DAG的节点，注意Expression类上的Add和Id这两个静态工厂方法中关于检查节点是否已经存在，这想法是错的，还是乖

就可以得到名为dag.png的图片，跟本文顶上的第二张图是一样的。

Expression及其派生类是用来表示解析源码后得到的AST或DAG的节点。注意Expression类上的Add和Id这两个静态工厂方法中关于检查节点是否已经存在，并尽量返回已有节点的做法：这就是前面提到的简单DAG生成算法在上面这大堆代码里的实现。检测节点的相等性的代码主要是在BinaryExpression和IdExpression里实现的。

Cache本来我是想用HashSet的，不过.NET标准库里的HashSet在这里不好用：虽然很容易知道容器里是否已存在相同的节点，却没办法把那个节点迅速拿出来；要是最终还是得线性遍历的话，那还不如用线性容器。所以最后还是用了List。

Scanner和Parser分别最低限度的实现了词法分析器和递归下降语法分析器。只允许单字符变量名也就是为了方便Scanner的实现。不过这部分其实用ANTLR来生成更方便，也一样可以接上后面的程序运行。

DotGenerator用于根据AST或DAG生成DOT图，实现得有点乱。主要是原本为了保证生成的DOT代码中节点的顺序，而采用了广度优先的遍历顺序；可是后来用于强制指定顺序的代码反而带来了一些问题，所以注释掉了（第308行到第314行）。这样一来用两个Queue来记录着前一行与当前行的节点就不一定有必要了。不过懒得改，就这样吧……

编辑：嗯不行……前面的代码不改还是有问题。本来我是觉得DAG因为没有环所以只要记住“上一层”的节点就足以判断前面是否已经见过该节点，但熬夜写代码看来质量果然是不高啊，这想法是错的。还是乖乖的用一个HashSet来记着前面见到过的节点然后用深度优先遍历算了，免得麻烦。修改后的DotGenerator类如下：