真不巧，这个学期看起来又是一套自编新实验。虽然下面这段话有待商榷，但为了分，总不能不做吧。

不自己经历一次 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闭包

1. 有入边，有出边：同 Thompson 构造法
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。

单元测试