Fonctionnement des recherches de correspondances
Le moteur de traitement des expressions régulières du .NET Framework est un outil de recherche qui fait appel aux expressions régulières en procédant par rétroaction. Cet outil intègre un moteur classique de type NFA (Nondeterministic Finite Automaton) similaire à celui utilisé par Perl, Python, Emacs et Tcl. C'est ce qui le différencie des moteurs de traitement des expressions régulières pures de type DFA (Deterministic Finite Automaton), plus rapides mais également plus limités, que l'on trouve dans awk, egrep ou lex. C'est également ce qui le différencie des moteurs NFA POSIX, standard, mais qui sont plus lents.
Trois types de moteurs de traitement des expressions régulières
Cette section fournit une vue d'ensemble des avantages et des inconvénients des trois types de moteurs et indique la raison pour laquelle le moteur du .NET Framework implémente un outil classique de recherche NFA.
Les moteurs DFA s'exécutent en mode linéaire parce qu'ils n'exigent aucune rétroaction (et qu'ils ne testent donc jamais deux fois le même caractère). Ils peuvent également garantir la recherche de la chaîne la plus longue possible. Toutefois, comme un moteur DFA prend uniquement en compte un état fini, il ne peut pas rechercher un modèle avec backreferences, et comme il ne construit pas d'expansion explicite, il ne peut pas non plus capturer de sous-expressions.
Les moteurs NFA classiques exécutent des algorithmes « gourmands » de recherche de correspondances rétroactive, testent toutes les expansions possibles d'une expression régulière dans un ordre spécifique et acceptent la première occurrence. Comme un NFA classique procède à une expansion spécifique des expressions régulières pour obtenir une correspondance, il peut capturer des occurrences de sous-expressions et de backreferences. Cependant, étant donné qu'un NFA classique recherche par rétroaction, il peut visiter exactement le même état plusieurs fois si l'état est accessible via différents chemins. Son exécution risque ainsi de se ralentir considérablement. Comme un NFA classique accepte la première correspondance trouvée, il peut également en négliger d'autres (éventuellement plus longues).
Les moteurs NFA POSIX sont similaires aux moteurs NFA classiques, à la différence qu'ils continuent de rechercher rétroactivement jusqu'à ce qu'ils aient trouvé de façon certaine la correspondance la plus longue possible. C'est la raison pour laquelle un moteur NFA POSIX est plus lent qu'un moteur NFA classique et, si vous utilisez un NFA POSIX, il est impossible de préférer la correspondance la plus courte en changeant l'ordre de la recherche rétroactive.
Les moteurs NFA classiques ont la préférence des programmeurs parce qu'ils sont plus expressifs que les moteurs DFA ou NFA POSIX. Même si leur exécution est parfois très lente, il reste possible de les amener à effectuer des recherches en mode linéaire ou polynomial à l'aide de modèles propres à limiter les ambiguïtés et à réduire la rétroaction.
Possibilités du moteur du .NET Framework
En intégrant les avantages d'un moteur NFA classique, le moteur de traitement des expressions régulières du .NET Framework propose un ensemble complet de constructions pour permettre aux programmeurs de diriger le moteur de recherche rétroactive. Ces constructions peuvent servir à rechercher des correspondances plus rapidement ou à indiquer la priorité d'expansions spécifiques par rapport à d'autres.
Autres fonctionnalités :
Quantifieurs « lents » : ??, *?, +?, {n,m}?. Ils indiquent au moteur de recherche rétroactive de rechercher d'abord le nombre minimal de répétitions. Par opposition, les quantifieurs gourmands ordinaires essaient de trouver d'abord le nombre maximal de répétitions.
Préanalyse positive. Elle permet au moteur de recherche rétroactive de retourner au même endroit dans le texte après avoir trouvé la correspondance d'une sous-expression. Cette fonctionnalité est utile pour effectuer une recherche dans le texte en vérifiant plusieurs modèles à partir d'une même position.
Préanalyse négative. Elle ajoute la possibilité de retrouver une expression uniquement si une sous-expression n'a pas de correspondance. Cette fonctionnalité est particulièrement efficace pour élaguer une recherche, étant donné qu'une expression correspondant à un cas à éliminer est souvent beaucoup plus simple qu'une expression correspondant à des cas à inclure. (Par exemple, il est difficile d'écrire une expression pour les mots ne commençant pas par « non »).
Évaluation conditionnelle. Cette fonctionnalité permet au moteur d'effectuer une recherche en utilisant plusieurs modèles supplémentaires, selon les résultats obtenus pour la sous-expression précédente. Elle propose une forme de backreference plus puissante qui permet, par exemple, de retrouver une parenthèse fermante lorsqu'une parenthèse ouvrante a été capturée précédemment dans une sous-expression.
Sous-expressions de recherche non rétroactive (également connues sous le nom de sous-expressions gourmandes). Cette fonctionnalité permet au moteur de recherche non rétroactive de vérifier qu'une sous-expression recherche uniquement la première correspondance trouvée pour cette sous-expression, comme si l'expression s'exécutait indépendamment de l'expression qui la contient. Sans cette construction, les recherches rétroactives à partir de la plus longue expression peuvent modifier le comportement d'une sous-expression.
Recherche de correspondances de droite à gauche. Cette fonctionnalité est utile lorsque la recherche s'effectue de droite à gauche et non de gauche à droite ou dans les cas où il est plus efficace de lancer une recherche en commençant par la partie droite du modèle qu'en commençant par la gauche.
Postanalyse positive et négative. Cette fonctionnalité est comparable à la préanalyse. Comme le moteur des expressions régulières permet une recherche complète des correspondances de droite à gauche, les expressions régulières autorisent des postanalyses illimitées.