Algorithme efficace pour la conversion d'un jeu de caractères en nfa/dfa

Question

Je travaille actuellement sur un générateur de scanner. Le générateur fonctionne déjà correctement. Mais lorsque vous utilisez des classes de caractères, l'algorithme devient très lent.

Le générateur de scanner produit un scanner pour les fichiers codés en UTF8. La plage complète de caractères (0x000000 à 0x10ffff) doit être prise en charge.

Si j'utilise de grands jeux de caractères, comme n'importe quel opérateur '.' ou la propriété unicode {L}, le nfa (et aussi le dfa) contient beaucoup d'états (> 10000). Donc, la conversion de nfa en dfa et la création de la dfa minimale prennent beaucoup de temps (même si la sortie minimale dfa ne contient que quelques états).

Voici mon implémentation actuelle de la création d'une partie de jeu de caractères 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; 
} 

Est-ce que quelqu'un sait comment implémenter la fonction beaucoup plus efficacement pour créer uniquement les états nécessaires?

EDIT:

Pour être plus précis, je besoin d'une fonction comme:

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

Une fonction d'aide pour convertir un caractère (int) à un octet UTF8 [] est défini comme:

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

Answer 1

Regardez ce que les bibliothèques d'expressions régulières comme Google RE2 et ERT font.

Answer 2

Il y a un certain nombre de façons de le gérer. Ils se résument tous à traiter des ensembles de caractères à la fois dans les structures de données, au lieu d'énumérer l'ensemble de l'alphabet. C'est aussi comment vous faites des scanners pour Unicode dans une quantité raisonnable de mémoire.

Vous avez plusieurs choix sur la façon de représenter et de traiter des ensembles de caractères. Je travaille actuellement avec une solution qui conserve une liste ordonnée des conditions aux limites et des états cibles correspondants. Vous pouvez traiter les opérations sur ces listes beaucoup plus rapidement que si vous deviez scanner l'alphabet entier à chaque moment. En fait, il est assez rapide pour fonctionner en Python avec une vitesse acceptable.

Answer 3

J'ai eu le même problème avec mon générateur de scanner, donc je suis venu avec l'idée de remplacer des intervalles par leurs ids qui est déterminé en utilisant l'arbre d'intervalle. Par exemple, la plage a..z dans dfa peut être représentée par: 97, 98, 99, ..., 122, je représente plutôt des plages comme [97, 122], puis je construis une structure arborescente d'intervalle, donc à la fin ils sont représentés comme des identifiants qui se réfèrent à l'arbre des intervalles. Étant donné le RE suivant: a ..z +, nous nous retrouvons avec une telle 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 

maintenant compriment intervalles:

0 -> a..z -> 1 

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

Extrait tous les intervalles de votre DFA et de construire l'arbre intervalle d'eux:

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

Remplacer réelle intervalles à leurs identifiants:

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

Answer 4

Dans cette bibliothèque (http://mtimmerm.github.io/dfalex/) je le fais en mettant une gamme de caractères consécutifs sur chaque transition, au lieu de caractères simples. Ceci est effectué à travers toutes les étapes de la construction NFA, de la conversion NFA-> DFA, de la minimisation DFA et de l'optimisation.

Il est assez compact, mais il ajoute de la complexité au code à chaque étape.