Regular Expressions
Types de moteur d'expression régulière

NFA

Un moteur NFA (Nondeterministic Finite Automaton) est entraîné par le motif .

Principe

Le motif de regex est analysé dans un arbre.

Le pointeur de la position actuelle est défini sur le début de la chaîne d'entrée et une correspondance est tentée à cette position. Si la correspondance est faisable, la position est incrémentée au prochain caractère de la chaîne et une autre correspondance est tentée à partir de cette position. Ce processus est répété jusqu'à ce qu'une correspondance soit trouvée ou que la fin de la chaîne d'entrée soit atteinte.

Pour chaque tentative de match

L'algorithme fonctionne en effectuant une traversée de l'arbre de configuration pour une position de départ donnée. Au fur et à mesure de sa progression dans l'arborescence, il met à jour la position actuelle en utilisant les caractères correspondants.

Si l'algorithme rencontre un nœud d'arbre qui ne correspond pas à la chaîne d'entrée à la position actuelle, il devra revenir en arrière . Ceci est effectué en revenant au nœud parent dans l'arborescence, en réinitialisant la position d'entrée actuelle à la valeur qu'il avait lors de la saisie du nœud parent et en essayant la branche suivante.

Si l'algorithme parvient à quitter l'arborescence, il signale une correspondance réussie. Sinon, lorsque toutes les possibilités ont été essayées, le match échoue.

Optimisations

Les moteurs Regex appliquent généralement certaines optimisations pour de meilleures performances. Par exemple, s'ils déterminent qu'une correspondance doit commencer par un caractère donné, ils tenteront une correspondance uniquement aux positions de la chaîne d'entrée où ce caractère apparaît.

Exemple

abeacab correspondre a(b|c)a avec la chaîne d'entrée abeacab :

L'arbre de modèle pourrait ressembler à:

CONCATENATION
    EXACT: a
    ALTERNATION
        EXACT: b
        EXACT: c
    EXACT: a

Les processus de correspondance sont les suivants:

a(b|c)a      abeacab
^            ^

a se trouve dans la chaîne d'entrée, consommez-le et passez à l'élément suivant dans l'arbre des modèles: l'alternance. Essayez la première possibilité: un b exact.

a(b|c)a      abeacab
  ^           ^

b se trouve, si l'alternance réussit, consommer et passer à l'élément suivant de la concaténation: une exacte a :

a(b|c)a      abeacab
      ^        ^

a n'est pas trouvé à la position attendue. Retour à l'alternance, réinitialiser la position d'entrée à la valeur qu'il avait à l'entrée de l'alternance pour la première fois, et essayez la deuxième alternative:

a(b|c)a      abeacab
    ^         ^

c n'est pas trouvé à cette position. Retour à la concaténation. Il n'y a pas d'autres possibilités à essayer à ce stade, donc il n'y a pas de correspondance au début de la chaîne.

Tentez une deuxième correspondance à la position de saisie suivante:

a(b|c)a      abeacab
^             ^

a ne correspond pas là. Tentez un autre match à la position suivante:

a(b|c)a      abeacab
^              ^

Pas de chance non plus. Avance à la position suivante.

a(b|c)a      abeacab
^               ^

a match, alors consommez-le et entrez l'alternance:

a(b|c)a      abeacab
  ^              ^

b ne correspond pas. Essayez la deuxième alternative:

a(b|c)a      abeacab
    ^            ^

c correspond, consommez-le et passez à l'élément suivant dans la concaténation:

a(b|c)a      abeacab
      ^           ^

a correspond, et la fin de l'arbre a été atteint. Signaler un match réussi:

a(b|c)a      abeacab
                \_/

DFA

Un moteur DFA (Déterministic Finite Automaton) est piloté par l’entrée .

Principe

L'algorithme analyse la chaîne d'entrée une fois et se souvient de tous les chemins possibles dans l'expression régulière. Par exemple, lorsqu'une alternance est rencontrée dans le motif, deux nouveaux chemins sont créés et tentés indépendamment. Lorsqu'un chemin donné ne correspond pas, il est supprimé des possibilités.

Implications

Le temps de correspondance est limité par la taille de la chaîne en entrée. Il n'y a pas de retour en arrière et le moteur peut trouver plusieurs correspondances simultanément, même des correspondances qui se chevauchent.

Le principal inconvénient de cette méthode est la réduction du nombre de fonctionnalités pouvant être prises en charge par le moteur, par rapport au type de moteur NFA.

Exemple

Match a(b|c)a contre abadaca :

abadaca      a(b|c)a
^            ^        Attempt 1      ==> CONTINUE

abadaca      a(b|c)a
 ^           ^        Attempt 2      ==> FAIL
               ^      Attempt 1.1    ==> CONTINUE
                 ^    Attempt 1.2    ==> FAIL

abadaca      a(b|c)a
  ^          ^        Attempt 3      ==> CONTINUE
                   ^  Attempt 1.1    ==> MATCH

abadaca      a(b|c)a
   ^         ^        Attempt 4      ==> FAIL
               ^      Attempt 3.1    ==> FAIL
                 ^    Attempt 3.2    ==> FAIL

abadaca      a(b|c)a
    ^        ^        Attempt 5      ==> CONTINUE

abadaca      a(b|c)a
     ^       ^        Attempt 6      ==> FAIL
               ^      Attempt 5.1    ==> FAIL
                 ^    Attempt 5.2    ==> CONTINUE

abadaca      a(b|c)a
      ^      ^        Attempt 7      ==> CONTINUE
                   ^  Attempt 5.2    ==> MATCH

abadaca      a(b|c)a
       ^       ^      Attempt 7.1    ==> FAIL
                 ^    Attempt 7.2    ==> FAIL