用于将字符集转换为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

看看像 Google RE2 和 TRE 这样的正则表达式库在做什么。