Calculer la différence et l’intersection entre deux expressions régulières

 (phylactery.org)
2 points par GN⁺ 2023-09-12 | 1 commentaires | Partager sur WhatsApp
  • Lorsqu’il faut comparer des expressions régulières comme des ensembles de chaînes, antimirov calcule sur un seul écran la relation d’inclusion et l’équivalence de deux expressions α et β, ainsi que leur intersection et leur différence
  • La zone de résultats affiche à la fois les compléments et les relations et permet de vérifier des opérations comme ~α, α < β, α = β, α & β, α ^ β, α - β
  • En saisissant une chaîne distincte s, il est possible de vérifier immédiatement si chaque expression régulière correspond via s ∈ α, s ∈ β
  • La grammaire prend en charge ., la concaténation, l’alternative |, les répétitions *·+·?·{n}·{m,n}, les groupes de caractères, les groupes de caractères niés, les échappements et les échappements Unicode UTF-16
  • Les fonctionnalités qui modifient le comportement comme les ancres, les assertions de largeur nulle, les références arrière, l’extraction de sous-groupes, la recherche ou correspondance partielle, et l’ignorance de la casse ne sont pas prises en charge

Comparaison d’expressions régulières et opérations ensemblistes

  • La zone de saisie reçoit deux expressions régulières, α et β
  • La sortie affiche ensemble les compléments, les relations et les opérations ensemblistes sur les deux expressions régulières
    • ~α, ~β : complément de chaque expression régulière
    • α < β, α = β, α > β : relation d’inclusion et équivalence entre les deux expressions régulières
    • α & β : intersection
    • α ^ β : différence symétrique
    • α - β : différence
  • Si l’on saisit la chaîne s, on peut vérifier si elle appartient à chaque expression régulière sous la forme s ∈ α, s ∈ β
  • La taille de chaque expression régulière et le nombre d’états du DFA sont également affichés
    • Dans l’écran d’exemple, |α| = 1, |β| = 1
    • Dans l’écran d’exemple, dfa(α) et dfa(β) ont chacun 1 état

Syntaxe d’expressions régulières prise en charge

  • Les opérateurs de base couvrent le caractère unique, la concaténation, l’alternative et la répétition
    • . : correspond à n’importe quel caractère unique
    • xy : concaténation qui fait correspondre x puis y
    • x|y : correspond à x ou y
    • x* : répétition zéro fois ou plus
    • (xyz) : groupement
    • () : expression régulière vide correspondant à la chaîne vide
  • Les abréviations courantes de répétition sont également prises en charge
    • x+ : répétition une fois ou plus, équivalente à xx*
    • x? : correspondance optionnelle, équivalente à (x|)
    • x{n} : concatène x n fois
    • x{m,n} : concatène x au moins m fois et au plus n fois
  • Les ensembles de caractères et les échappements peuvent prendre les formes suivantes
    • [a-z0-9] : correspond à un caractère unique du groupe
    • [^a-z0-9] : correspond à un caractère unique absent du groupe
    • \c : échappement du caractère spécial c
    • \u001a : correspond au caractère UTF-16 correspondant
    • Sinon, des caractères comme a, b, c correspondent à eux-mêmes

Fonctionnalités non prises en charge

  • antimirov se concentre sur le traitement des expressions régulières comme objets d’opérations ensemblistes, et exclut donc les fonctionnalités suivantes
    • ancres ^, $
      • toutefois, ^ et $ doivent toujours être échappés
    • assertions de largeur nulle, par exemple (?=...), (?<=...)
    • références arrière, par exemple \1, \2
    • extraction de sous-groupes
    • recherche ou correspondance partielle
    • autres drapeaux modifiant le comportement, comme l’ignorance de la casse
  • Pour plus d’informations, voir non/antimirov

À lire aussi

1 commentaires

 
GN⁺ 2023-09-12
Commentaires sur Hacker News

  • J’ai créé une démo web similaire qui montre le processus par lequel une expression régulière est transformée de parsing → NFA → DFA → DFA minimal, puis qui génère du LLVM IR/Javascript/WebAssembly à partir du DFA minimal
    http://compiler.org/reason-re-nfa/src/index.html

    • Cela dit, passer d’un NFA à un DFA explicite n’est pas toujours le meilleur choix
      À titre de référence, les dérivées de Brzozowski, utilisables comme approche alternative pour le matching d’expressions régulières, peuvent aussi être intéressantes : https://en.wikipedia.org/wiki/Brzozowski_derivative

  • Cette bibliothèque peut servir à créer une hiérarchie de classes de chaînes, ce qui permet ensuite d’exploiter plus activement les chaînes typées
    Par exemple, les e-mails et les URL ont une syntaxe particulière ; leur espace de valeurs est un sous-ensemble de toutes les chaînes non vides, et les chaînes non vides sont un sous-ensemble de toutes les chaînes
    Si le système de types sait qu’une chaîne e-mail est un sous-type d’une chaîne non vide, il peut juger valide le passage d’une adresse e-mail à une fonction qui exige une chaîne non vide
    Cette bibliothèque peut être utilisée pour vérifier la définition et la hiérarchie de tels types de chaînes, et l’implémentation de la hiérarchie varie selon les langages : sous-classage, bornes de traits, etc.

    • Dans les langages dotés de types somme étiquetés, on utilise souvent ce genre d’approche. En pseudo-code façon Haskell, cela ressemble à peu près à ceci
      On n’exporte pas le constructeur Address, seulement le type, et on valide dans fromString :: Text -> Maybe Address, en renvoyant Nothing si l’adresse est invalide
      Il ne faut pas mélanger la validité aux données ; il vaut mieux la signaler par un autre chemin, puis, lorsqu’il faut produire une sortie, récupérer la valeur encapsulée avec toText :: Address -> Text
    • Mieux vaut éviter d’utiliser une expression régulière pour valider les adresses e-mail
      https://news.ycombinator.com/item?id=31092912
    • Il y a peu de choses aussi étranges que de creuser, un matin de fin d’été, ce qui est autorisé ou non comme adresse e-mail à gauche du @
      L’heuristique simple selon laquelle toute expression régulière qui tente de représenter une « adresse e-mail valide » est fausse est assez sûre, mais elle gâche tout le plaisir
    • Je me demande ce que signifie « espace de valeurs »

  • Les expressions régulières sont un bon exemple de théorie mathématique assez élégante et complexe encapsulée dans une interface utile
    L’algèbre linéaire me donne une impression similaire

    • Je suis toujours étonné de voir à quel point une grande partie des mathématiques peut se transformer en algèbre linéaire dès qu’on dispose du corps approprié
      Même les transformations de Möbius du plan complexe, w=(az+b)/(cz+d), peuvent être converties en algèbre linéaire
    • En général, dans ce genre de cas, cela signifie que la représentation se rapproche de la vérité
      Une bonne interface a une valeur intrinsèque, ce que beaucoup de personnes très orientées résultat ont du mal à reconnaître
    • Si ma mémoire est bonne, le lien avec l’algèbre linéaire apparaissait dans le livre de Conway https://store.doverpublications.com/0486485838.html. Je ne l’ai parcouru qu’en diagonale

  • Cette excellente page calcule des relations binaires entre paires d’expressions régulières et affiche les DFA sous forme de graphes
    Elle montre de façon vraiment impressionnante des opérations assez non triviales effectuées sur des expressions régulières

    • C’est très chouette, mais il n’est pas surprenant, à strictement parler, qu’elle ne prenne pas en charge les fonctionnalités qui font que ce ne sont plus vraiment des expressions régulières
      Je pensais tout de même que les ancres ^ et $ ne poseraient pas de problème

  • J’ai collé “regex filter numbers divisible by 3”, et la page s’est complètement bloquée : https://stackoverflow.com/q/10992279/41948
    ^(?:[0369]+|[147](?:[0369]*[147][0369]*[258])*(?:[0369]*[258]|[0369]*[147][0369]*[147])|[258](?:[0369]*[258][0369]*[147])*(?:[0369]*[147]|[0369]*[258][0369]*[258]))+$
    ^([0369]|[147][0369]*[258]|(([258]|[147][0369]*[147])([0369]|[258][0369]*[147])*([147]|[258][0369]\*[258])))+$
    Je me demande s’il existe une expression plus courte

    • Cette page web se bloque sur les expressions régulières qui produisent des DFA avec beaucoup d’états
      Par exemple (ab+c+)+, (abc){100}, a.*quick brown fox jumps over the lazy dog
    • De toute façon, la description de la page indique que les ancres ne sont pas prises en charge

  • Je voulais voir l’intersection entre des URL et des adresses e-mail syntaxiquement valides, mais rien qu’en saisissant l’expression régulière d’URL ci-dessous, la page met trop longtemps à traiter
    [\-a-zA-Z0-9@:%._+~#=]{1,256}\.[a-zA-Z0-9()]{1,6}\b([\-a-zA-Z0-9()@:%_+.~#?&//=]*)
    Source : https://stackoverflow.com/a/3809435/623763

    • Les expressions comme (...){1,256} sont très lourdes, et le code Scala JS finit par expirer ou par tuer le navigateur
      Si on remplace cela par (...)+, ça fonctionne au moins chez moi. Les petites expressions comme (...){1,6} devraient aller

  • J’ai d’abord été surpris que les expressions régulières produites par l’union et l’intersection ne soient pas particulièrement concises, puis je l’ai vite compris
    Par exemple, l’intersection de "y.+" et ".+z" peut s’écrire sous la forme très simple "y.*z", et la page confirme leur équivalence. Mais l’outil produit yz([^z][^z]*z|z)*|y[^z](zz*[^z]|[^z])*zz*
    Il y a sans doute une raison à ce résultat, mais produire une expression régulière minimale selon un critère comme le nombre de caractères est probablement bien plus difficile

    • L’une des raisons est probablement que ".+z" devient plus grand et plus sale après conversion en automate déterministe

  • J’ai déjà utilisé ce concept par le passé pour écrire la logique de validation d’un paramètre « IP RegEx filter »
    L’objectif était de permettre aux utilisateurs de configurer un filtre IP avec une expression régulière. L’équipe marketing ne comprenait pas le CIDR, mais connaissait les expressions régulières à cause de Google Analytics
    Comment définir une expression régulière valide ? Son intersection avec l’expression régulière de « toutes les adresses IPv4 » devait être non vide, tout en n’étant pas identique à cette expression régulière de « toutes les adresses IPv4 »
    Cela a évité beaucoup de plaintes selon lesquelles le filtre ne faisait rien, mais n’a pas empêché la saisie de filtres erronés

    • N’aurait-il pas été possible d’avoir une solution plus simple ? Plutôt que d’essayer de valider l’expression régulière du filtre, on pourrait afficher des adresses IP d’exemple, ou laisser l’utilisateur saisir un ensemble d’adresses, puis montrer quelles adresses correspondent et lesquelles ne correspondent pas
      Cela aide aussi à traiter le problème des filtres erronés

  • Pour améliorer l’usage sur mobile, il vaudrait mieux désactiver les suggestions automatiques du champ de saisie de l’expression régulière
    https://stackoverflow.com/questions/35513968/disable-autocor...

  • J’ai testé la page avec deux expressions régulières pour les nombres divisibles par 3 similaires, et elle s’est figée même en retirant les ^ et $ aux deux extrémités
    Regex 1 : ([0369]|([258]|[147][0369]*[147])([0369]|([147][0369]*[258]|[258][0369]*[147]))*([147]|[258][0369]*[258])|([147]|[258][0369]*[258])([0369]|([147][0369]*[258]|[258][0369]*[147]))*([258]|[147][0369]*[147]))*
    Regex 2 : ([0369]|[258][0369]*[147]|(([147]|[258][0369]*[258])([0369]|[147][0369]*[258])*([258]|[147][0369]*[147])))*
    Tout est analysé jusqu’à juste avant le dernier *, mais dès qu’on ajoute ce *, toute la page se fige
    Sans le *, cela produisait un validateur fonctionnel qui analysait des morceaux de nombres dont la somme des chiffres est divisible par 3