Accueil  / Semaine 5 / La mécanique du traitement des expressions

La mécanique du traitement des expressions

Aller plus loin...

Nous voulons non seulement pouvoir utiliser les expressions régulières, mais aussi pouvoir comprendre comment les moteurs d’expressions régulières fonctionnent.

Automates finis déterministes et non déterministes

Comment écririez-vous un programme en Java qui, étant donné l’expression régulière « ([abc][0-9])*z », doit trouver dans un texte les motifs correspondants ? Sans plus de connaissances, vous écririez peut-être un programme Java très complexe rempli de clauses conditionnelles (« if »).

Pour vous faire une meilleure idée sur la question, je vous invite maintenant à lire le quatrième chapitre de Maîtrise des expressions régulières (2e édition, par Jeffrey E.F. Friedl). Ce chapitre porte sur le fonctionnement des expressions régulières ou, en d’autres termes, sur la manière d’implémenter un moteur pour traiter des expressions régulières.

L’auteur utilise abondamment les acronymes NFA et DFA qui correspondent respectivement aux automates finis non déterministes et aux automates finis déterministes. Un automate fini est tout simplement une machine qui peut passer d’un seul état fini à plusieurs. Par exemple, mon poste de télévision peut être fermé ou ouvert, et s’il est ouvert, il peut être ouvert à l’une des 4 chaînes publiques. Face à un nouvel élément d’information (comme une émission en provenance d’une télécommande), l’automate peut soit demeurer dans son état actuel, soit migrer vers un autre état (comme changer de chaîne). Un automate déterministe sait toujours dans quel état il se trouve. Un automate non déterministe, par contre, peut se trouver dans plusieurs états en même temps (dans un ensemble d’états) [1]. Pour comprendre les automates non déterministes, imaginez que vous avez une télécommande avec les fonctions suivantes : ouvrir le poste de télévision soit à la première chaîne ou soit à la seconde chaîne, changer pour la première chaîne, changer pour la seconde chaîne. Au début, l’appareil sera dans un état incertain, mais il pourra passer à un état déterminé (première ou seconde chaîne) plus tard. On peut imaginer qu’une fois que le téléviseur reçoit l’ordre de la commande de changer pour la première chaîne, il peut en déduire qu’il était à la seconde chaîne initialement. On peut donc dire que l’automate non déterministe se permet de « voyager dans le temps ». Évidemment, on ne met pas de tels téléviseurs sur le marché !

Dans le contexte des expressions régulières, les deux types d’automates représentent deux stratégies. Dans le cas des automates déterministes, à partir d’une position donnée, on lit les caractères un à un, passant chaque fois d’un état à un autre, caractérisant ainsi le motif que l’on est en train de reconnaître. Dans le cas de l’approche par automates non déterministes, on se permettra de traiter plusieurs cas en parallèle à partir d’un même point de départ, revisitant peut-être à plusieurs reprises le même caractère. Ainsi, l’approche non déterministe est plus lourde et complexe et peut même ne jamais se terminer en pratique (prendre un temps très long). Cependant, parce que l’approche déterministe lit les caractères un à un sans retour en arrière possible lorsqu’elle tente de reconnaître un motif partant d’un point donné, elle tend à mener à des moteurs plus limités en pratique. Par exemple, le moteur déterministe ne traitera pas l’expression régulière « (.)\1 » parce que le symbole « \1 » implique un retour en arrière, une mémoire du passé.

La plupart des moteurs d’expressions régulières sont non déterministes (incluant Java). Contrairement à ce qui se passe avec les moteurs déterministes, il est donc très important d’écrire ses expressions régulières avec soin pour éviter des temps de calculs prohibitifs.

Des problèmes de temps de calcul surviennent généralement quand un motif ne peut être trouvé et que le moteur non déterministe tente, par tous les moyens, d’explorer toutes les possibilités, en vain. Par exemple, étant donné l’expression régulière « (a*ba*)* » et la (longue) chaîne
« ababaabababaababaaababababababbaaaaabababababababababbabababababc »,
il est évident pour un humain que la chaîne n’est pas un motif reconnu par l’expression régulière parce qu’elle se termine par la lettre c qui n’est pas autorisée par l’expression régulière. Cependant, un moteur non déterministe explorera toutes les possibilités de reconnaissance du motif et revisitera sans cesse les mêmes caractères. Notons que si on élimine la dernière lettre de la longue chaîne, la reconnaissance du motif se fait en quelques millièmes de secondes. La solution à ce problème particulier est d’utiliser l’expression régulière avec notation atomique « (?>a*ba*)* » ou encore « (a*ba*)*+ » : le temps de calcul est alors, à nouveau, très court .

Conclusion

Décider si une expression régulière peut être trouvée constitue un problème NP-difficile, c’est-à-dire qu’il est très improbable que le problème ait une solution en temps polynomial (O(n^p) pour un entier p). En d’autres termes, il est possible qu’étant donné une expression régulière, il faille un temps très, très grand pour chercher un motif. Ce type de difficulté peut même représenter un problème de sécurité ; imaginons un instant que vous appliquiez des expressions régulières à des données saisies dans un formulaire sur le web : un pirate informatique (cracker) pourrait alors saisir certaines données dans le but de paralyser votre serveur, ce qui donnerait lieu à une attaque par déni de service (Denial Of Service ou DOS en anglais).

Référence : Notation grand-O


[1Il se trouve que tous les automates non déterministes peuvent être réécrits comme des automates déterministes, mais possiblement beaucoup plus complexes (avec un très grand nombre d’états).