Dérivés d'expressions régulières expliqués à l'aide de Pac-Man

Nov 25 2022

Un tutoriel expliquant l'algorithme de correspondance des expressions régulières fonctionnelles

Manger des cerises rouges vous donne la possibilité de manger des fantômes bleus. L'idée que des dérivées puissent être utilisées pour créer un algorithme de correspondance d'expressions régulières est presque aussi ridicule.

images par auteur | fantôme et cerises de Pac-Man

En 1964, Brzozowski a publié le premier article sur les dérivés d'expressions régulières . C'est de loin l'un de mes algorithmes préférés. En utilisant des dérivés d'expressions régulières, nous pouvons implémenter un algorithme pour faire correspondre les expressions régulières. Cet algorithme est très :

Facile
fonctionnel
facilement extensible avec vos propres opérateurs

Dans cet article, je vais vous montrer comment nous pouvons faire correspondre une chaîne avec une expression régulière en utilisant seulement deux fonctions pures et quelques analogies Pac-Man. Si vous préférez, vous pouvez regarder la vidéo suivante au lieu de lire l'article car elle couvre le même sujet :

Récapitulatif des expressions régulières

Tout d'abord, passons en revue rapidement les expressions régulières pour nous assurer que nous sommes sur la même page. L'expression a(a|b)*correspond à une chaîne qui commence par un a, suivi d'un nombre quelconque de a's et b's.

La chaîne abcorrespondra a(a|b)*. Nous l'indiquerons avec un fantôme bleu comestible.
La chaîne aabbbacorrespond également a(a|b)*puisqu'elle commence par un aet est suivie de plusieurs a's et b's.
Ensuite, la chaîne acne correspond pas à a(a|b)*, car la regex ne correspond à aucun cet notre regex ne fait aucune correspondance de sous-chaîne. Nous l'indiquerons en utilisant un fantôme rouge qui poursuit le Pac-Man.
Enfin, la chaîne bane correspond pas non plus a(a|b)*car elle ne commence pas par un a.

Présentation de l'algorithme

Avant d'entrer dans les détails, voyons un aperçu du fonctionnement de cet algorithme. J'ai conçu un jeu étrange de Pac-Man où vous ne pouvez manger les fantômes que si vous mangez les fruits dans une séquence qui correspond à la regex. Notre Pac-Man représente la regex aba*. Il a le chapelet de fruits suivant à manger : une pomme, puis une banane, puis une pomme : aba.

Lorsque nous commençons, le fantôme nous poursuit et l'expression régulière qu'il nous reste à faire correspondre est aba*.
Nous mangeons la première pomme, et l'expression régulière qu'il nous reste maintenant à faire correspondre est ba*. Le fantôme nous poursuit toujours car le fruit que nous avons mangé jusqu'à présent, la pomme, ne correspond pas à la regex.
Ensuite, nous mangeons la banane. La regex qu'il nous reste alors à faire correspondre est a*. Maintenant, le fantôme commence à s'enfuir car, techniquement, abcorrespond déjà à aba*.
Nous pouvons essayer de manger le fantôme ou de manger une autre pomme, auquel cas l'expression régulière qu'il nous reste à faire correspondre est toujours a*. Le fantôme s'enfuit toujours car abacorrespond également à l'expression régulière aba*.

Animation de Pac-Main mangeant une pomme, une banane et une autre pomme

Il y a une autre fonction à l'œuvre ici. La fonction vérifie si le fantôme poursuit le Pac-Man ou si le Pac-Man a déjà trouvé la regex et poursuit le fantôme. Cette fonction s'appelle la fonction nullable ; il vérifie si l'expression régulière restante correspond à la chaîne vide. Il peut le faire car si la regex restante correspond à la chaîne vide, le fruit qu'il a mangé doit déjà avoir été suffisant pour satisfaire la regex.

nullable : correspond à la chaîne vide

not nullable : ne correspond pas à la chaîne vide

Algorithme d'appariement des dérivées

Cela signifie que nous n'avons besoin que de deux fonctions pour écrire l'algorithme d'appariement dérivé :

la fonction dérivée
la fonction nullable

Un en Golang pour les programmeurs impératifs :

et un autre en Haskell pour les programmeurs fonctionnels :

Ces deux fonctions sont équivalentes et simplement écrites dans des styles de programmation différents. Dans le code Haskell, foldlégalement appelé pli gauche ou réduction dans d'autres langages, fait le travail de la boucle for pour vous. De plus, dans Haskell, nous n'avons pas besoin de virgules pour passer des paramètres aux fonctions ; puisque l'application de fonction est l'opération la plus courante dans un langage de programmation fonctionnel, nous utilisons l'espace pour délimiter les paramètres.

Maintenant, approfondissons la façon d'implémenter les fonctions nulles et dérivées.

Digression de l'histoire de l'origine de Pac-Man

Mais avant de faire cela, je ne sais pas si vous vous êtes déjà interrogé sur l'histoire d'origine de Pac-Man. Je soutiens qu'il n'y avait pas de baril de déchets nucléaires dans lequel Pac-Man est tombé, ce qui a permis à Pac-Man d'acquérir le pouvoir de manger des fantômes. La logique est beaucoup plus simple.

Pac-Man est un fruit ! Quand Pac-Man mange d'autres fruits, Pac-Man est un cannibale. Donc, si jamais vous êtes poursuivi par un fantôme, vous devez manger de la chair humaine, et le fantôme devrait, au moins temporairement, commencer à vous fuir. Maintenant, je n'ai pas essayé cela moi-même, mais la logique semble solide.

Cela explique pourquoi les zombies poursuivent toujours les humains. Comme l'a dit un jour David Attenborough :

« Les zombies qui nous poursuivent sont eux-mêmes poursuivis par des fantômes que nous ne pouvons pas voir. Après que les zombies aient mangé une partie de notre chair humaine, vous les verrez montrer l'étrange comportement de mâcher l'air, c'est le zombie qui mange le fantôme qui le poursuivait auparavant.

Opérateurs de base

L'implémentation des fonctions nullables et dérivées nous oblige d'abord à définir les opérateurs de base disponibles dans nos expressions régulières.

Nous pouvons considérer une expression régulière comme décrivant un ensemble de chaînes.

Cela signifie que l'ensemble vide représente un opérateur qui ne correspond à aucune chaîne.
La chaîne vide représente un ensemble singleton d'une seule chaîne qui correspond uniquement à la chaîne vide.
Le caractère représente également un ensemble singleton qui correspond uniquement au caractère unique a.
Nous pouvons ensuite combiner ces expressions régulières de base à l'aide d'opérateurs tels que : or, concatenationet Kleene star, où ret sreprésente les deux expressions d'expression régulière que nous combinons.

Fonction Nullable

Nous pouvons commencer par la fonction nullable. Examinons quelques exemples et déterminons laquelle de ces expressions régulières correspond à la chaîne vide pour avoir un aperçu de la façon dont cette fonction est implémentée.

a*correspond à la chaîne vide car zéro ou plus inclut zéro.
(a*|b)correspond à la chaîne vide puisque le côté gauche du ou correspond à la chaîne vide.
abne correspond pas à la chaîne vide, puisqu'il ne correspond qu'à la chaîneab
ab*ne correspond pas non plus à la chaîne vide, car ab*nécessite une chaîne qui commence par una
(a|b)ne correspond pas à la chaîne vide, car ni le côté gauche ni le côté droit de ne orcorrespondent à la chaîne vide.

exemples nullables

Voici l'implémentation de la fonction nullable. Le côté gauche représente les valeurs transmises à la fonction et le côté droit représente l'implémentation de la fonction dans ce cas. Les fantômes rouges représentent faux et les fantômes bleus représentent vrai :

implémentation de la fonction nullable

L'ensemble vide ne correspond pas à la chaîne vide puisqu'il ne correspond à aucune chaîne.
La chaîne vide correspond à la chaîne vide car elle ne correspond qu'à la chaîne vide.
Le caractère ane correspond pas à la chaîne vide car il ne correspond qu'au caractère a.
Si nous avons une logique or, nous devons vérifier les deux côtés. Si l'un ou l'autre correspond à la chaîne vide, la logique orcorrespond à la chaîne vide.
Pour que les concatenationdeux expressions régulières correspondent à la chaîne vide, elles doivent toutes deux correspondre à la chaîne vide.
Et enfin, si nous avons zero or morede quelque chose, cela inclut zéro, ce qui signifie qu'il correspond toujours à la chaîne vide.

Notre opérateur supérieur est le orthis signifie que nous devons vérifier la nullabilité des côtés gauche et droit : bet a*.
Nous vérifions et voyons que le caractère bsur le côté gauche n'est pas nullable : false.
Ensuite, nous vérifions et voyons que le a*sur le côté droit est nullable : true.
Maintenant, nous sommes revenus falseet truenous pouvons orles obtenir true.

Exercices nullables

Essayez de parcourir l'implémentation et vérifiez si les expressions régulières suivantes acceptent les valeurs NULL. Vous pouvez cliquer dessus pour vérifier votre réponse :

une
un*(b*|∅)
εa
∅*
(∅|b)*(abc|ε)

Avant d'examiner l'implémentation de la fonction, examinons des exemples de dérivée. Ici nous allons prendre la dérivée de quelques expressions régulières, toutes par rapport au caractère a:

L'expression régulière qui reste à trouver après a*avoir mangé une apomme est toujours a*.
La dérivée de ab*par rapport à aest b*, puisque nous avons déjà identifié le préfixe a.
La dérivée de (a|b)bpar rapport à aest b.
La dérivée de b|(a*b)par rapport à aest a*b. La gauche bne correspondait pas, nous pouvions donc la jeter et la aétait consommée par les zero or more a's à droite.
Ensuite, nous avons ab*, celui-ci est un peu délicat. Après qu'il ait mangé la pomme, l'expression régulière qui reste à faire correspondre est b(ab)*. Puisque nous n'avons fait qu'apparier le a, nous nous attendons à en voir au moins un de plus b.

La dérivée de l'ensemble vide est toujours l'ensemble vide. Il n'y a aucun moyen de récupérer puisque l'ensemble vide ne correspond à rien.
La dérivée de la chaîne vide concernant tout caractère est l'ensemble vide. Il ne s'attendait pas à correspondre à un personnage. Il ne correspondra qu'à la chaîne vide.
La dérivée d'un caractère unique à un caractère similaire (dans ce cas, le apple) est la chaîne vide car après qu'elle se soit trouvée, il ne reste plus que la chaîne vide à correspondre.
La dérivée d'un caractère par rapport à un caractère différent qui n'est pas égal, dans ce cas, l' banana, est l'ensemble vide puisque nous n'avons pas apparié le caractère spécifique.
La dérivée d'une orexpression est la ordes dérivées. Il repousse simplement le problème à ses enfants.
La dérivée de l' concatexpression doit considérer si elle peut sauter la première expression. Il ne peut ignorer la première expression que si la première expression correspond à la chaîne vide et est nullable. Donc, la première chose que nous faisons est de vérifier cela. Pensons au cas où il ne peut pas ignorer la première expression lorsque l'expression rn'est pas nullable. Alors la dérivée est la dérivée de la première expression concatenatedavec la seconde expression s. Si nous pouvons ignorer la première expression régulière, nous devons envisager une alternative qui n'est que la dérivée de la deuxième expression. Nous pouvons alors orles deux alternatives de sauter ret de ne pas sauter ret de retourner cela en conséquence.
Enfin, nous avons l' staropérateur. Il correspond à une expression zéro ou plusieurs fois. Puisqu'on nous passe un caractère, ce n'est pas le cas zéro. Il faut donc considérer le one or morecas. Cela signifie que nous devons prendre la dérivée de l'expression à l'intérieur de staret concatenateà nouveau avec l' zero or moreexpression.

Exemple dérivé 1

Prenons la dérivée de (ab)*par rapport à a.

(ab)*est une zero or moreexpression, nous nous tournons donc vers la zero or morerègle. Nous voyons que cela nécessite de prendre la dérivée de l'expression à l'intérieur du star.

C'est le concatenationde aet b. Nous vérifions donc si le côté gauche est nullable et le caractère an'est pas nullable. Cela signifie que nous ne pouvons pas passer outre. Il faut prendre la dérivée de apar rapport à a. Mais c'est la chaîne vide, donc si nous concatenatela chaîne vide avec le côté droit, qui était b, nous obtenons b.

Maintenant, nous revenons au zero or more, souvenez-vous que nous avons pris la dérivée de abpar rapport à aet avons récupéré a b. Maintenant, nous pouvons concaténer cela avec à (ab)*nouveau et nous obtenons b(ab)*.

Exemple dérivé 2

Prenons la dérivée de (a*ba)par rapport à b.

a*est concaténé avec ba, nous examinons donc la règle de concaténation.
Nous vérifions si le côté gauche a*est nullable, ce qui est le cas. Cela signifie que nous pouvons l'ignorer, ce qui signifie également que nous devons créer une combinaison orde deux dérivées.
Le côté gauche finit par ne pas correspondre, car a*ne correspond pas à b.
Heureusement, nous avons une alternative le ba. La dérivée de bapar rapport à best et a.

J'ai sauté quelques détails ici. Considérez cela comme un exercice pour vérifier mon travail en parcourant vous-même la fonction.

Exercices dérivés

Essayez de parcourir l'implémentation et vérifiez quelles sont les dérivées des expressions régulières suivantes par rapport à b. Vous pouvez cliquer dessus pour vérifier votre réponse :

εb
b*(b|c)
un*(b|c)
bεb
∅*b

J'espère que vous comprenez maintenant pourquoi manger des cerises rouges vous donne la possibilité de manger des fantômes bleus et comment implémenter un matcher d'expression régulière à l'aide de l'algorithme dérivé.

Nous avons couvert l'algorithme de travail de base ici, mais il existe de nombreuses façons de rendre cet algorithme encore meilleur avec de très petites modifications. Nous avons triché et passé sous silence les règles de simplification dans cet article, en les utilisant sans les expliquer, ce qui deviendra particulièrement évident si vous parcourez les exercices. Nous n'avons pas non plus discuté de la façon dont vous pouvez utiliser la mémorisation pour construire paresseusement un automate efficace.

Nous pouvons également facilement étendre l'algorithme pour inclure de nouveaux opérateurs tels que not, interleaveet même prendre en charge les grammaires sans contexte. Je vais discuter de certains de ces sujets dans le prochain article .

En attendant, j'aimerais voir votre implémentation de cet algorithme dans un langage de programmation avec lequel vous êtes le plus à l'aise. Merci de m'envoyer un lien dans les commentaires.