编译原理课程设计报告
Lab 2
实验任务 2.1 正规表达式转 NFA 算法及实现
尽管推荐使用中缀表达式转后缀表达式以完成次任务，但是事实上 Thompson 构造法直接递归实现也很自然。
具体来说，我们可以认为我们在处理的一定是一个由单个节点开始，单个节点终止的 NFA。
对于普通字符只需要在当前节点后新增一条对应节点对应边即可。
那么对字符串流的操作（* + 等，以及 ()）都可以看作创建一个新的 NFA，并将该新 NFA 连接到当前状态上。区别在于重复类的只需要创造一个 NFA 并做好相关链接后返回，而括号需要进入新的 NFA 递归新增节点。
特殊的是 |，实践上可以认为移动当前指针到开始节点即可。需要注意的是在收尾的时候需要从每一个分支连接到结束节点。
自此即可自然递归实现，可见于源代码中 src/nfa.rs 的 Nfa::new 函数及其相关函数。
实验任务 2.2 NFA 转 DFA 算法及实现
子集构造算法和 -闭包的求解过程本身已经相当程序化，在实现过程中并无值得注意的细节。
具体来说，
-闭包的实现为了抽象性以存于 src/utils.rs 的 Nodes::empty_closure 中。
而子集构造算法则位于 src/dfa.rs 中 From<&Nfa> trait 对 Dfa 的实现中。
如果注重时间复杂度的话，可以先行求出所有 -闭包并做分类，令 为点数， 为边数。时间复杂度应为 。
本次实验的实践考虑到代码抽象性没有做此优化，复杂度最劣可能为 。即图中每个点的 -闭包 均为全集。
实验任务 2.3 DFA 最⼩化算法及实现
本实验任务的核心是实现 Hopcroft 算法。一般认为 Hopcroft 算法的时间复杂度应为 。但是在具体实现上有很多实现并不能做到这一点，这里给出一个程序化的描述：
- 将点集按照终止结点和非终止节点分成两组。
- 将两组加入队列 。
- 如果队列 已空，终止程序。
- 从队列 中取出一个集合 。
-
遍历现有划分的所有集合：
- 令当前遍历到的集合为
-
遍历字符集，令当前遍历到的字符为 :
- 令 ， 。
- 如果 和 有一个不为空。则将 , 替换划分中 ，将两者中的较小项加入队列。
- 执行 3。
考虑时间复杂度。队列中任意一项，如果被加回队列，长度一定是其原长度的一半。而对于每一次处理，其复杂度是 的。显然，其最多 层，因此总复杂度应为 。
考虑正确性。划分法的正确性是显然的，因此只需确定是没有可能多划，没有可能少划即可证明其正确性。因为算法流程不超出正常的划分法方式，其自然不会多划。对于少划的可能性，不妨考虑反证。
如果存在一个集合 ，其可以被一个字符 分成两部分，分别到 ，那么 两个状态在被分开时一定有一个会被推入队列，因此集合 一定会在处理时被分割，冲突。
故该算法正确。
具体实现中，需要考虑用链表维护划分，除此之外不存在能够在 复杂插入删除的序列数据结构。
Lab 4
chumsky / PEGs
chumsky 作为一个递归下降的，用于解析 PEGs 的库，和本次实验要求的 SysY 文法略有出入（以 BNF 形式给出）。另一个和常见的文法分析器不同的点是，该库是一个「声明式」而非「命令式」的解析器。这会在编写时带来巨大的额外工作量，但是对应的，程序的架构页更加直接。这使得我有机会为更细粒度的文法解析器撰写测试并进行分析，很遗憾的事 SysY 给定的文法相当的不原子化，这是得该库的特性器不仅难以充分发挥，事实上还带来的额外的编写成本。
具体来说，我们可以将文法分为多个层级：
介于递归下降的特性，我们需要对递归做手动处理。
对于 AddExp 等此类的直接递归，由于 PEGs 是有优先级的文法系统，我们可以使用 foldl/foldr 来处理。
对于类似 Exp -> AddExp -> MulExp -> UnaryExp -> Primary 的间接，循环递归。我们需要使用 recursive 块来处理。这里需要注意暴露出的点，比如我在此处选择 AddExp 作为跳出循环的点，因为其他模块中只会使用 Exp 和 AddExp，且 Exp 只会由 AddExp 规约而来，因此属于较好的跳出点。
另一个值得一提的事情是，由于声明式的描述方法，类型名有概率变得非常长，需要使用 Boxed 等方法适时擦除类型，避免类型名过长使得 rustc 甚至电脑崩溃。
测试
Rust 语言自带良好的单元测试功能，况且如果能有对小模块单元测试的能力，就可为后续测试提供巨大的提示。对词法分析的测试是相对容易处理的，但文法分析的测试则应当感谢 chumsky 库，这使得我能够将语法分成多个部分，从而依次分析测试。
改进方向
囿于时间原因，本实验有部分值得一试但尚未来得及完成的功能：
- 对语义分析的测试。事实上我可以很自豪的说本程序在 AST 部分提供了完善的抽象，这位语义分析环节的单元测试留下了充分的空间。
- 语义分析报错的行号。这一部分则是纯粹的 dirty work，在语法分析阶段事实上可以拿到每一个 AST Node 在原串中的对应范围，但是 AST 抽象中均未记录（Number 和 Ident 做了实验性的处理），补全这部分即可有完善的报错。