真不巧，这个学期看起来又是一套自编新实验。虽然下面这段话有待商榷，但为了分，总不能不做吧。
不自己经历一次 TINY 语言的编译器构造过程，就等于没学这门课。经历过了，而且走通了，你就从现在的 1/100, 飞跃到了 1/3000，甚至 1/10000。毕业后，你就拿着这个名片去华为，去阿里，去腾讯，去百度找工作，或者去北大，清华，上海交大，北航这些学校读研，绝对没问题。这个名片要比现在所谓的竞赛获奖的含金量大得多，别人相信得多。为什么？因为招聘官或者老师都是过来人，都知道编译技术是最难学的知识，没几个人真正学懂。现在你真正学懂了，别人刮目相看。
杨某人《编译技术课程试验指导书（2022 版）》
代码已上传至 GitHub，为防止篇幅过长，没有内置所有代码，可以对比阅读。
文章并未完成，而且 不知道什么时候会施工完成 应该弃坑了，不过代码写完了。
从 “最简 DFA 构造法” 说起
构造 DFA 的方法算是本实验的前置知识，而杨某人自创的 “最简 DFA 构造法“并不是龙书提到的 Thompson 构造法。而要理解最简构造法，需要先理解” 原生构造法“。
原生构造法的核心思想是将正则表达式拆成多个基本运算，再将这些基本运算逐步组合成 NFA。
比如正则表达式 $r \to a^+b^+$，可以拆分为 $r_1 \to a$、$r_2 \to b$、$r_3 \to r_1^+$、$r_4 \to r_2^+$、$r_5 \to r_3r_4$ 这五个正则表达式。然后将其各自转化为 NFA。
在绘制 $r_3$ 对应的 NFA 时，将 $r_1$ 代入，并将整个 NFA 看作是一个状态 / 一个转换，下同。最后组合到 $r_5$ 即可得到 $r$ 的 NFA。
而杨某人认为，一些空转换的作用仅仅是防止过度的反向转换。根据不同的出入边状况，自然构造法中的空转换可以省掉，以在防止倒灌（指顺着回边返回太远）的同时得到更简单的 NFA。
连接
当 $s$ 有出边，$t$ 有入边时，在 $s$ 结束状态和 $t$ 开始状态处加入一个空转换。
否则，与 Thompson 构造法一致，$N(s)$ 的结束状态和 $N(t)$ 的开始状态重合。
Kleene 闭包
-
有入边，有出边：同 Thompson 构造法
-
有入边，无出边：可以省掉后面的空转换
-
无入边，有出边：可以省掉前面的空转换
-
无入边，无出边：不需要空转换
1
2
3
4
当 $s^*$ 的 NFA 只含一个开始、一个接受状态，且无出入边时，可以缩成一个状态。
0 或 1 个 $s?$
就是把 Kleene 闭包的顶上那一个空转换去掉，阻止继续接受即可。
并 $s|t$
当 $s$ 和 $t$ 都没有入边和出边时，转换如图所示。
如果 $s$ 或 $t$ 中任何一个有出入边，则先对其进行改造：
-
有入边，无出边：在前面加空转换
-
无入边，有出边：在后面加空转换
-
有入边，有出边：在两边各加一个空转换
1
2
3
另外还有带 category 属性的接受状态，需要在后面加一个空状态作为新的接受状态，以防止合并时 category 属性丢失。
数据结构
杨某人定义的一堆对象，在 Go 里当然不能继续用了。还好实验一没有继承多态类型推断之类的（实验二就有了），不然工作量又要暴涨。
字符集
字符集和字符集表
一个” 字符集 “代表的其实是一个字符集段，对于同一个字符集，可能会在 CharsetTable 内有多个 Charset 项，通过 SegmentID 相区分。
本实验的代码中，会保证每个字符集中，段不重合且按字符序递增。
正则表达式
操作数类型
Go 的枚举确实有点太弱了，没办法。定义一个新类型，不过这个也算不上限制，可以随便赋值。
词素类型
可以定义一个 String() 方法，以打印其名字。
图（NFA、DFA）
这个就没啥好说的了……
方法
字符集
生成一个字符集
输入两个字符，输出一个 index ID。
字符与字符的并运算
分两种情况，相等（返回一段）或不相等（返回两段）。也可以合并。
字符与字符集的并运算
题意要求，返回的必须是新字符集，其实这也为我们降低了难度，毕竟不用考虑插入段的复杂性。那就可以先将旧的字符集拷贝一份。
第一轮遍历，寻找可以包含的原字符集段，如有，就不用再合了。
第二轮遍历，寻找挨着边界的原字符集段，也就是 fromChar-1 或者 toChar+1，直接边界 +-1 即可，不需要新段。
之后第三轮遍历，找到合适的位置，插入新段，然后将后面段的 SegmentID+1。
单元测试
This content is licensed under a Creative Commons Attribution-ShareAlike 4.0 International license.