Algoritmo eficiente para convertir un conjunto de caracteres en nfa/dfa

Question

Actualmente estoy trabajando en un generador de escáner. El generador ya funciona bien. Pero al usar clases de caracteres, el algoritmo se vuelve muy lento.

El generador de escáner produce un escáner para archivos codificados en UTF8. Debe admitirse el rango completo de caracteres (0x000000 a 0x10ffff).

Si utilizo juegos de caracteres grandes, como cualquier operador '.' o la propiedad Unicode {L}, la nfa (y también la dfa) contiene muchos estados (> 10000). Por lo tanto, la conversión para nfa a dfa y crear el dfa mínimo lleva mucho tiempo (incluso si el dfa mínimo de salida contiene solo unos pocos estados).

Aquí está mi implementación actual de crear un conjunto de caracteres como parte de la 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; 
} 

¿Alguien sabe cómo implementar la función de manera mucho más eficiente para crear solo los estados necesarios?

EDIT:

Para ser más específicos que necesito una función como:

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

una función de ayuda para convertir un personaje (int) para un byte de codificación UTF-8 [] se define como:

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

Answer 1

Mire qué bibliotecas de expresiones regulares como Google RE2 y TRE están haciendo.

Answer 2

Existen varias maneras de manejarlo. Todos se reducen a tratar conjuntos de caracteres a la vez en las estructuras de datos, en lugar de enumerar todo el alfabeto alguna vez. También es la forma de hacer escáneres para Unicode en una cantidad razonable de memoria.

Tiene muchas opciones sobre cómo representar y procesar conjuntos de caracteres. Actualmente estoy trabajando con una solución que mantiene una lista ordenada de las condiciones de contorno y los estados objetivo correspondientes. Puede procesar operaciones en estas listas mucho más rápido de lo que podría hacerlo si tuviera que escanear todo el alfabeto en cada coyuntura. De hecho, es lo suficientemente rápido como para funcionar en Python con una velocidad aceptable.

Answer 3

Tuve el mismo problema con mi generador de escáner, así que se me ocurrió la idea de reemplazar los intervalos por sus identificadores, que se determinan usando el árbol de intervalos. Por ejemplo, un rango de ... en dfa se puede representar como: 97, 98, 99, ..., 122, en su lugar, represento rangos como [97, 122], luego construyo una estructura de árbol de intervalos fuera de ellos, por lo que al final se representan como identificadores que se refieren al árbol de intervalos. Dado el siguiente RE: a ..z +, terminamos con tal de DFA:

0 -> a -> 1 
0 -> b -> 1 
0 -> c -> 1 
0 -> ... -> 1 
0 -> z -> 1 

1 -> a -> 1 
1 -> b -> 1 
1 -> c -> 1 
1 -> ... -> 1 
1 -> z -> 1 
1 -> E -> ACCEPT 

Ahora comprimir intervalos:

0 -> a..z -> 1 

1 -> a..z -> 1 
1 -> E -> ACCEPT 

extraer todos los intervalos de DFA y construimos árbol de intervalo fuera de ellos:

{ 
    "left": null, 
    "middle": { 
     id: 0, 
     interval: [a, z], 
    }, 
    "right": null 
} 

Reemplazar real intervalos a sus identificadores:

0 -> 0 -> 1 
1 -> 0 -> 1 
1 -> E -> ACCEPT 

Answer 4

En esta biblioteca (http://mtimmerm.github.io/dfalex/) lo hago poniendo un rango de caracteres consecutivos en cada transición, en lugar de caracteres individuales. Esto se lleva a cabo a través de todos los pasos de la construcción de NFA, la conversión de NFA-> DFA, la minimización de DFA y la optimización.

Es bastante compacto, pero agrega complejidad de código a cada paso.