真不巧，这个学期看起来又是一套自编新实验。虽然下面这段话有待商榷，但为了分，总不能不做吧。
不自己经历一次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.