Algoritmo efficiente per convertire un set di caratteri in un nfa/dfa

Question

Attualmente sto lavorando su un generatore di scanner. Il generatore funziona già correttamente. Ma quando si usano classi di caratteri l'algoritmo diventa molto lento.

Il generatore di scanner produce uno scanner per i file codificati UTF8. L'intera gamma di caratteri (da 0x000000 a 0x10ffff) deve essere supportata.

Se utilizzo set di caratteri di grandi dimensioni, come qualsiasi operatore '.' o la proprietà unicode {L}, il nfa (e anche il dfa) contiene molti stati (> 10000). Quindi la conversione di nfa in dfa e creare il minimo dfa richiede molto tempo (anche se l'output minimo dfa contiene solo alcuni stati).

Ecco la mia attuale implementazione della creazione di un set di caratteri parte del 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; 
} 

Qualcuno sa come implementare la funzione in modo molto più efficiente per creare solo gli stati necessari?

EDIT:

Per essere più precisi devo una funzione come:

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

una funzione di supporto per convertire un carattere (int) per un byte UTF8 [] è definito come:

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

Answer 1

Guardate quali librerie di espressioni regolari come Google RE2 e TRE stanno facendo.

Answer 2

Ci sono diversi modi per gestirlo. Si riducono tutti a trattare gruppi di personaggi alla volta nelle strutture dati, invece di enumerare l'intero alfabeto in assoluto. È anche il modo in cui si creano scanner per Unicode in una quantità ragionevole di memoria.

Hai molte scelte su come rappresentare e set di processo di caratteri. Attualmente sto lavorando con una soluzione che mantiene un elenco ordinato di condizioni al contorno e stati obiettivo corrispondenti. Puoi elaborare le operazioni su questi elenchi molto più rapidamente di quanto potresti se dovessi eseguire la scansione dell'intero alfabeto in ogni giuntura. In effetti, è abbastanza veloce da funzionare in Python con una velocità accettabile.

Answer 3

Ho avuto lo stesso problema con il mio generatore di scanner, così mi è venuta in mente l'idea di sostituire intervalli da loro ID, che è determinato mediante albero intervallo. Ad esempio gamma a..z in DFA può essere rappresentato come: 97, 98, 99, ..., 122, invece che rappresentano intervalli esempio [97, 122], quindi costruire struttura ad albero intervallo fuori di essi, così alla fine sono rappresentati come id che si riferiscono all'albero ad intervalli. Dato il seguente RE: a ..z +, si finisce con tale 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 

Ora comprimere intervalli:

0 -> a..z -> 1 

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

estrarre tutti gli intervalli dal vostro DFA e costruiamo albero intervallo di fuori di essi:

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

Sostituire reale intervalli ai loro id:

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

Answer 4

In questa libreria (http://mtimmerm.github.io/dfalex/) lo faccio mettendo un intervallo di caratteri consecutivi su ogni transizione, anziché singoli caratteri. Questo viene eseguito attraverso tutti i passaggi della costruzione di NFA, conversione NFA-> DFA, minimizzazione DFA e ottimizzazione.

È abbastanza compatto, ma aggiunge complessità del codice ad ogni passaggio.