将字符集转换为 nfa/dfa 的高效算法

我目前正在研究扫描仪生成器。 发电机已经工作正常。但是当使用字符类时，算法会变得非常慢。

扫描仪生成器生成 UTF8 编码文件的扫描仪。应支持完整范围的字符（0x000000 到 0x10ffff）。

如果我使用大字符集，例如任何运算符“.”或 unicode 属性 {L}，nfa（以及 dfa）包含许多状态（> 10000）。因此，nfa 到 dfa 的转换并创建最小 dfa 需要很长时间（即使输出最小 dfa 仅包含几个状态）。

这是我当前创建 nfa 字符集部分的实现。

void CreateNfaPart(int startStateIndex, int endStateIndex, Set<int> characters)
{
transitions[startStateIndex] = CreateEmptyTransitionsArray();
foreach (int character in characters) {
    // get the utf8 encoded bytes for the character
    byte[] encoded = EncodingHelper.EncodeCharacter(character);
    int tStartStateIndex = startStateIndex;
    for (int i = 0; i < encoded.Length - 1; i++) {
        int tEndStateIndex = transitions[tStartStateIndex][encoded[i]];
        if (tEndStateIndex == -1) {
           tEndStateIndex = CreateState();
               transitions[tEndStateIndex] = CreateEmptyTransitionsArray();
        }                   
        transitions[tStartStateIndex][encoded[i]] = tEndStateIndex;
        tStartStateIndex = tEndStateIndex;
    }
    transitions[tStartStateIndex][encoded[encoded.Length - 1]] = endStateIndex;
}

有谁知道如何更有效地实现该功能以仅创建必要的状态？

EDIT:

更具体地说，我需要一个类似的函数：

List<Set<byte>[]> Convert(Set<int> characters)
{
     ???????
}

将字符 (int) 转换为 UTF8 编码 byte[] 的辅助函数定义为：

byte[] EncodeCharacter(int character)
{ ... }

有多种方法可以处理它。它们都归结为在数据结构中一次处理字符集，而不是枚举整个字母表。这也是在合理的内存量中制作 Unicode 扫描仪的方法。

关于如何表示和处理字符集，您有多种选择。我目前正在研究一种解决方案，该解决方案保留边界条件和相应目标状态的有序列表。如果您必须在每个时刻扫描整个字母表，那么您可以更快地处理这些列表上的操作。事实上，它的速度足够快，可以以可接受的速度在 Python 中运行。