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

Question

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

扫描仪生成器为 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;
}

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

编辑:

更具体地说，我需要一个像这样的函数:

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

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

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

Answer 1

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

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