Atualmente, estou trabalhando em um gerador de scanner. O gerador já funciona bem. Mas, ao usar classes de caracteres, o algoritmo fica muito lento.

O gerador do scanner produz um scanner para arquivos codificados em UTF8. O intervalo completo de caracteres (0x000000 a 0x10ffff) deve ser suportado.

Se eu usar conjuntos de caracteres grandes, como o operador any '.' ou a propriedade unicode {L}, o nfa (e também o dfa) contém muitos estados (> 10000). Portanto, a conversão de nfa para dfa e cria o mínimo dfa leva muito tempo (mesmo que o dfa mínimo de saída contenha apenas alguns estados).

Aqui está minha implementação atual de criação de um conjunto de caracteres parte do 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;
}

Alguém sabe como implementar a função com muito mais eficiência para criar apenas os estados necessários?

EDITAR:

Para ser mais específico, preciso de uma função como:

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

Uma função auxiliar para converter um caractere (int) em um byte de codificação UTF8 [] é definida como:

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