Show HN : Expressions régulières transductives pour l’édition de texte

 (github.com/c0stya)
1 points par GN⁺ 2025-02-09 | 1 commentaires | Partager sur WhatsApp
  • TRRE est une extension du langage des expressions régulières qui ajoute l’opérateur : pour exprimer directement des transformations de texte, proposée avec l’outil CLI expérimental trre, proche de grep -E
  • La forme de base est une paire transductive du type a:b, qui transforme un motif d’entrée en motif de sortie ; la suppression s’écrit x:, l’insertion :x, comme une transformation avec la chaîne vide
  • Comme avec les expressions régulières classiques, on peut utiliser les alternatives, la répétition et les transformations de plages de caractères ; des exemples incluent cat:dog, [a:A-z:Z] et un chiffrement de César
  • L’implémentation interne construit un Finite State Transducer (FST), qui manipule des paires entrée-sortie au lieu du FSA des expressions régulières ordinaires, avec une déterminisation expérimentale à la volée
  • Il n’existe pas encore de binaire précompilé ; il faut compiler le projet soi-même, et la stabilisation du DFT, la prise en charge complète d’Unicode, la finalisation des fonctionnalités ERE et une gestion efficace des plages restent dans la TODO list

Le problème que TRRE cherche à résoudre

  • Les expressions régulières classiques sont utiles pour trouver des motifs dans du texte, mais pour l’édition de texte, la logique de traitement des groupes peut devenir complexe car elle agit comme un post-traitement
  • TRRE étend le langage des expressions régulières pour réunir l’appariement de motifs et la modification de texte dans une seule expression
  • La syntaxe centrale est de la forme motif-à-apparier:motif-à-générer, l’exemple le plus simple étant a:b, qui remplace a par b
  • L’outil CLI trre est une implémentation qui illustre ce concept et fonctionne dans un esprit proche de grep -E

Syntaxe de transformation de base

  • Une substitution de chaîne s’écrit comme cat:dog
    • echo 'cat' | ./trre 'cat:dog' affiche dog
    • On peut obtenir le même résultat avec une transformation caractère par caractère comme (c:d)(a:o)(t:g)
  • Cela peut servir, comme sed, à remplacer toutes les occurrences dans une chaîne
    • En appliquant lamb:cat à Mary had a little lamb., on obtient Mary had a little cat.
  • La suppression s’exprime en laissant la partie droite vide, sous la forme chaîne_à_supprimer:
    • (x:)or supprime x dans xor pour produire or
    • a: remplace tous les a par le symbole vide dans le mode scan par défaut, ce qui les supprime
    • On peut utiliser une expression entre crochets comme [aie]: pour supprimer plusieurs caractères
  • L’insertion s’exprime en laissant la partie gauche vide, sous la forme :chaîne_à_insérer
    • (:x)or insère x devant or pour produire xor
    • had a (:little )lamb insère little dans ce contexte

Transformations au-dessus des expressions régulières

  • TRRE prend en charge les alternatives avec |, comme les expressions régulières classiques
    • (c:b)at|(d:h)og transforme cat dog en bat hog
  • Les opérateurs de répétition peuvent aussi s’appliquer aux transformations
    • (cat:dog)* transforme catcatcat en dogdogdog
    • En mode scan par défaut, cat:dog suffit aussi à appliquer la transformation de façon répétée et à produire le même résultat
  • Quand on utilise une répétition dans le motif de gauche, plusieurs entrées peuvent être consommées pour produire une seule sortie
    • (cat)*:dog transforme catcatcat en dog
  • Utiliser * ou + dans le motif de droite peut provoquer une boucle infinie
    • Il faut éviter des expressions comme :a*
    • Si une répétition finie est nécessaire, on peut préciser le nombre d’occurrences avec :(repeat-10-times){10}

Transformations de plages et générateur

  • Une transformation de plage de caractères s’écrit comme [a:A-z:Z]
    • Cela permet de transformer regular expressions en REGULAR EXPRESSIONS
  • Un exemple de chiffrement de César est inclus
    • [a:b-y:zz:a] transforme caesar cipher en dbftbs djqifs
    • [a:zb:a-z:y] permet de revenir à caesar cipher
  • On peut aussi produire plusieurs sorties à partir d’une seule entrée, comme avec un generator
    • Par défaut, la première correspondance possible est utilisée
    • Avec l’option -a, toutes les sorties possibles sont générées
  • Par exemple, appliquer :(0|1){3} à une entrée vide permet de générer toutes les séquences binaires sur 3 bits, de 000 à 111
  • En utilisant :(0|1){,3}? avec -ma, on peut générer des sorties de type sous-ensembles de longueur inférieure ou égale à 3

Spécification du langage et priorité des opérateurs

  • De manière informelle, TRRE est défini comme une paire motif-à-apparier:motif-à-générer
  • Le motif-à-apparier de gauche peut être une chaîne ou une expression régulière
  • Le motif-à-générer de droite est généralement une chaîne, mais peut aussi être une expression régulière
  • L’opérateur : est actuellement traité comme non associatif, et une forme TRRE:TRRE n’est pas autorisée par la grammaire
    • Cette forme aurait un sens naturel comme composition des relations définies par TRRE, mais elle est encore exclue car la complexité pourrait devenir importante
  • La priorité des opérateurs, du plus fort au plus faible, est la suivante
    • caractère d’échappement \
    • expression entre crochets []
    • groupement ()
    • répétition * + ? {m,n}
    • concaténation
    • Transduction :
    • alternative |

Modes et avidité

  • trre prend en charge deux modes
    • Scan Mode : mode par défaut, qui applique les transformations séquentiellement
    • Match Mode : activé avec l’option -m, qui vérifie si toute la chaîne correspond à l’expression
  • L’option -a génère toutes les sorties possibles
  • Le modificateur ? rend les opérateurs *, +, {,} non-greedy
    • <(.:)*> produit <> à partir de <cat><dog>
    • <(.:)*?> produit <><> à partir de la même entrée
  • Des exemples sont aussi donnés pour modifier le contenu à l’intérieur de balises ou de parenthèses
    • <(.*?:cat)> transforme <dog> <mouse> en <cat> <cat>

Implémentation fondée sur les FST et déterminisation

  • TRRE construit en interne un Finite State Transducer (FST)
  • Un FST est proche d’un Finite State Automaton (FSA) utilisé pour les expressions régulières classiques, mais il manipule des paires entrée-sortie au lieu de simples chaînes
  • Les différences essentielles de TRRE sont les suivantes
    • il définit une relation binaire entre deux langages réguliers
    • il utilise des FST plutôt que des FSA pour l’inférence
    • il prend en charge une déterminisation expérimentale à la volée pour améliorer les performances
  • Dans les moteurs d’expressions régulières classiques, la déterminisation consiste à transformer un automate non déterministe en automate déterministe afin de permettre une inférence en temps linéaire par rapport à la longueur de la chaîne d’entrée
  • Une approche similaire est possible avec TRRE, mais tous les transducteurs non déterministes NFT ne peuvent pas être convertis en transducteurs déterministes DFT
    • s’il existe deux cycles « bad » portant la même étiquette d’entrée, la génération d’états peut entrer dans une boucle infinie
    • il existe des méthodes pour détecter ce type de boucle, mais elles sont coûteuses

Performances et état de l’installation

  • La version non déterministe de base est donnée comme légèrement plus lente que sed sur une substitution simple
    • ./trre '(vodka):(VODKA)' : real 0m0.046s
    • sed 's/vodka/VODKA/' : real 0m0.024s
  • Sur des tâches plus complexes, la version déterministe trre_dft est montrée comme plus rapide que sed
    • sed -e 's/\(.*\)/\U\1/' : real 0m0.508s
    • ./trre_dft '[a:A-z:Z]' : real 0m0.131s
  • Aucun binaire précompilé n’est encore fourni
  • L’installation consiste à cloner le dépôt puis à compiler et tester avec make && sh test.sh
  • La TODO list contient encore les éléments suivants
    • une version DFT stable
    • la prise en charge complète d’Unicode
    • la finalisation des fonctionnalités ERE
      • négation ^ dans []
      • classes de caractères
      • symboles d’ancrage $^
    • une gestion efficace des plages

Approches de référence

À lire aussi

1 commentaires

 
GN⁺ 2025-02-09
Avis de Hacker News

  • Je suis curieux de voir où ce projet va aller. Cela dit, la priorité des opérateurs semble peu naturelle, et d’autres personnes dans ce fil semblent avoir eu la même impression
    On s’attend naturellement à ce que cat:dog soit équivalent à (cat):(dog), et non à ca(t:d)og

    • C’est une idée intéressante à bien des égards
      Le fait que cat:dog soit interprété comme ca(t:d)og plutôt que (cat):(dog) m’a aussi dérouté, mais en repensant au fait que nous utilisons tous les expressions régulières un peu de travers, ça s’explique. Les expressions régulières ne devraient “à l’origine” pas être vues comme des matchers, mais comme des générateurs de chaînes ; ainsi, cat|dog peut formellement être vu comme une expansion vers un ensemble du type {catog,cadog}
      Pour la correspondance, il suffit ensuite de faire du matching de sous-chaînes de cet ensemble de chaînes dans un texte plus grand. Le problème, c’est que la plupart des moteurs d’expressions régulières réels ne fonctionnent pas ainsi et ont toutes sortes de comportements étranges pour coller aux attentes ou pour des raisons d’efficacité
      Si l’on teste plusieurs outils d’expressions régulières, on obtient des variantes comme (cat)|(dog) ou (cat)|(dog)|(ca[td]og). Donc, d’un point de vue plus formel, il me semble correct que cat:dog produise ca(t:d)og plutôt que (cat):(dog). Mais après des décennies à détourner les expressions régulières en outils de matching conformes aux attentes des utilisateurs, tout le monde met désormais entre parenthèses l’expression qu’il veut remplacer
      Cette proposition est intéressante et bien conçue, mais elle donne finalement l’impression de ramener les expressions régulières à leur modèle de générateur d’origine. Le problème relève davantage des outils que de la syntaxe
      J’ai travaillé autrefois sur des sujets proches, et si vous n’avez jamais pensé aux expressions régulières comme à des générateurs d’ensembles de chaînes, vous pouvez vous amuser avec ceci : https://onlinestringtools.com/generate-string-from-regex
      Cela dit, le comportement de ces outils de génération est lui aussi très spécifique. Les outils que j’utilisais proposaient plusieurs façons de contraindre le générateur, par exemple en imposant des limites aux fermetures
    • Merci pour le retour ; je réfléchis aussi à la priorité, donc cela pourrait changer
      La repousser après la concaténation peut créer d’autres problèmes. Par exemple, avec un : non associatif, cat:dog:mouse devrait peut-être être illégal, mais je ne suis pas sûr de la façon de le traiter
      Dans la version actuelle, on insère epsilon, c’est-à-dire la chaîne vide. Par exemple, pour supprimer un caractère sur deux, on peut techniquement exécuter ..:, qui est .(.:eps)
      Le résultat de echo 'abcde' | ./trre '..:' est 'ace'
      En fait, l’association de : pourrait aussi avoir le sens d’une composition de relations régulières, mais j’ai considéré que c’était trop complexe pour l’instant
    • Les transformations de plages sont similaires. Au lieu de [a:A-z:Z], [a-z:A-Z] serait préférable, et j’aimerais proposer une forme comme [a-y:b-z;z:a] au lieu de [a:b-y:zz:a]

  • Si les transducteurs à états finis et les outils associés vous intéressent, XFST (Xerox Finite-State Transducer) vaut le coup d’œil. Il est utilisé depuis plus de 20 ans dans des applications de linguistique computationnelle
    Un chercheur finlandais de PARC était venu dans un cours à l’UT pour montrer comment traiter la morphologie du finnois avec des FST, et même vu de l’extérieur, c’était assez impressionnant

    • J’allais aussi le mentionner. Lien vers l’article de Kaplan : https://aclanthology.org/J94-3001.pdf
      Il décrit les travaux réalisés chez PARC
    • http://hfst.github.io/ est la version open source moderne de XFST. Elle englobe foma et OpenFst, et devrait pouvoir faire à peu près tout ce que fait trre, et davantage
    • Pynini pourrait aussi vous intéresser. C’est un wrapper Python pour OpenFst, avec beaucoup de fonctionnalités ajoutées pour faciliter l’utilisation
      OpenFst est vraiment une excellente bibliothèque pour les transducteurs. Les tutoriels d’utilisation de Pynini réalisés sous forme de devoirs par Johns Hopkins et d’autres sont également corrects
      [1] https://www.openfst.org/twiki/bin/view/GRM/Pynini
      [2] https://www.openfst.org/

  • Si vous cherchez une alternative aux expressions régulières standard, en particulier si la logique de groupes vous semble difficile ou si vous voulez des expressions maintenables, Rosie Pattern Language pourrait convenir
    https://gitlab.com/rosie-pattern-language/rosie/-/blob/maste...
    https://rosie-lang.org/about/

  • Génial. Vers 1997, j’ai écrit mon mémoire de Diplom en informatique sur les transducteurs à états finis, et c’était beaucoup moins trivial que je ne l’imaginais
    Le sujet consistait à implémenter la composition et les DFA lorsque c’était possible, y compris des transducteurs composés. C’était une “algèbre des transducteurs à états finis”, avec la morphologie comme cas d’usage. Le sujet était largement sous-estimé, si bien que j’ai dû m’arrêter à mi-chemin. Donc respect
    Concernant la syntaxe, je me demande si vous voulez vraiment que : se lie plus fortement que la concaténation ab

    • Au début des années 2000, j’ai utilisé OpenFST en bio-informatique. C’était amusant à manipuler, mais au final pas utile pour ce que je faisais
      C’est agréable de voir que le projet continue 20 ans plus tard : https://www.openfst.org/twiki/bin/view/FST/WebHome
    • Faire dépendre l’obtention du diplôme, en pratique, de sa capacité à “malmener suffisamment fort les expressions régulières”, c’est un choix incroyablement audacieux
    • Exact. Les transducteurs sont un sujet très ancien. Pour une raison quelconque, ils n’ont pas été aussi fortement associés à un langage particulier que les expressions régulières
      Je ne suis pas encore sûr que : doive se lier plus fortement que la concaténation. J’ai regardé une centaine d’exemples et trouvé que l’approche actuelle, c’est-à-dire : avec une priorité inférieure à ., était plus naturelle ; mais dans le code, il suffit littéralement de changer un seul nombre pour le modifier. C’est pour cela que je l’ai posté ici, j’ai vraiment besoin de retours concrets

  • Dès qu’on veut faire une forme de substitution structurelle, cette approche ne semble plus suffisante. Par exemple, on peut vouloir faire quelque chose comme s/"([^"]*)"/'$1'/
    En plus, si l’on pouvait remplacer, parmi les [^"], ceux qui correspondent à ['] par \', ce serait encore plus utile
    Plus généralement, comme une expression régulière définit en pratique un arbre de parsing sur le résultat de la correspondance, il serait utile de pouvoir effectuer des transformations plus générales sur cet arbre

    • Si j’ai bien compris, l’expression ttre suivante fait ce que tu veux :
      ":'(':(\\')|[^"'])*":'
    • Si j’ai bien compris, tu veux modifier le contenu à l’intérieur des blocs "..." et remplacer les guillemets par des apostrophes '
      C’est possible avec cette expression :
      echo '"hello world" "hello again!"' | ./trre "\":'.+?:-\":'"
      Le résultat est '-' '-'
      Autrement dit, l’expression ".+?:-" remplace le texte à l’intérieur de "" par le symbole -, tout en changeant aussi les guillemets autour. Le point d’interrogation indique le mode non glouton

  • Tout le projet semble reposer sur l’affirmation selon laquelle « les expressions régulières sont un excellent outil pour trouver des motifs dans du texte, mais elles m’ont toujours paru peu naturelles pour l’édition de texte », mais il n’y a aucun exemple
    Je ne comprends pas pourquoi les expressions régulières seraient peu naturelles pour l’édition. Je ne sais pas non plus ce que signifie « édition » ici, ni pourquoi les gens auraient des difficultés avec les groupes
    Il y a beaucoup d’exemples de syntaxe dans ce projet, mais je ne vois pas en quoi c’est mieux que les expressions régulières classiques. Quelques exemples du type « voici la version avec une expression régulière de base, voici ma version, et voilà pourquoi c’est plus simple » aideraient à comprendre le projet

    • À mon avis, les expressions régulières ont généralement un côté on les écrit une fois et on n’y retouche plus. Construire un prototype qui regarde au-delà de ça est une bonne manière d’explorer un meilleur avenir pour ce domaine
    • Remarque pertinente. L’exemple le plus clair, c’est quand il faut remplacer uniquement dans un contexte
      Par exemple, pour remplacer uniquement les y situés entre x et z par Y, en Python on ferait à peu près ceci :
      pattern = r'(x)y(z)'
      replacement = r'\1Y\2'
      result = re.sub(pattern, replacement, text)
      J’aimerais remplacer cela par le motif xy:Yz :
      result = re.trre('xy:Yz', text)
      Si x et z sont des motifs plus complexes, voire des expressions régulières eux-mêmes, cette approche peut être plus pratique
    • Il est plus juste de dire que les expressions régulières seules ne fournissent pas de fonction d’édition. Il y a des groupes, mais pour les recomposer il faut utiliser un autre langage, comme sed
    • Il est question de substitution. Avec la syntaxe de l’auteur, il est plus facile d’exprimer — littéralement de taper — une substitution
      Beau projet

  • Le code C est vraiment agréable à lire. Très bon travail, je suis en train de le parcourir
    Juste un petit commentaire : le lien vers theory.pdf dans le README est cassé. Le PDF se trouve dans le répertoire docs/, il suffit donc d’ajouter docs/ à l’URL

    • Merci pour le retour et pour avoir signalé la coquille. C’est corrigé. En fait, mes compétences en C sont assez rouillées, donc je suis un peu inquiet

  • Il est indiqué qu’il faut éviter d’utiliser * ou + dans la partie droite, car cela peut provoquer une boucle infinie ; pourquoi ne pas simplement l’interdire ?
    Je comprends que cela complique la spécification de la syntaxe, mais je ne vois pas de bonne raison de le conserver

    • Remarque pertinente, et je suis d’accord. Pour l’instant, il vaudrait mieux le désactiver
      La raison initiale était que je voulais implémenter une opération intéressante de composition de transducteurs. On peut effectuer des opérations simples sur une chaîne et composer des trre comme des filtres, mais je ne l’ai pas encore terminé. Donc oui, la remarque est pertinente

  • Exploration intéressante, mais il manque des exemples montrant pourquoi c’est réellement mieux. Bien sûr, c’est peut-être parce que je suis habitué aux expressions régulières depuis trop longtemps
    Par exemple, je ne vois pas en quoi (cat):(dog) en trre est meilleur que s/cat/dog, ni ce que (x:)or apporte par rapport à s/xor/or. Presque tous les exemples se traduisent assez facilement, dans ma tête, par des expressions régulières relativement simples
    S’il y a un avantage clé, j’imagine qu’il se situe du côté de la logique des groupes, donc les exemples gagneraient à se concentrer là-dessus. Il me semblerait préférable d’expliquer d’abord pourquoi c’est un meilleur choix, avant même de présenter la syntaxe de base
    L’exemple du chiffre de César donne vraiment envie d’une fonctionnalité « appliquer ceci en sens inverse ». C’est une demande fréquente dans beaucoup de substitutions de texte, et c’est particulièrement évident dans cet exemple. Le cerveau de programmeur crie immédiatement : « pourquoi devrais-je exprimer deux fois la même logique ? »
    Je ne sais pas encore si c’est utile, mais explorer des alternatives au statu quo établi depuis longtemps est une excellente chose. En général, ce genre de tentative a aussi de bonnes chances de ne pas aboutir, mais l’exploration elle-même est plaisante à voir

  • La spécification semble assez lacunaire. Le tout premier exemple est déjà bizarre :
    $ echo 'cat' | trre 'c:da:ot:g'
    dog
    Je ne comprends pas ce qui se passe ici. La grammaire est donnée comme ceci :
    TRRE <- TRRE* TRRE|TRRE TRRE.TRRE
    TRRE <- REGEX REGEX:REGEX
    Quel est l’arbre d’analyse ici ? Pourquoi c ne devient-il pas da ? Ou bien pourquoi c n’est-il pas supprimé et da transformé en ot ?
    L’idée d’avoir une sémantique de recherche/remplacement plus intuitive qu’un opérateur de groupement est bonne. À l’époque de MS-DOS, on pouvait faire des choses comme ren .log .txt et ça marchait ; avec une mentalité bash moderne, ça n’a aucun sens, mais l’intention était très claire au premier coup d’œil.

    • C’est un problème de priorité des opérateurs et de tokenisation. Dans ce langage, les tokens sont des caractères uniques, et il y a un opérateur invisible entre les caractères.
      Si on appelle explicitement cet opérateur ~, l’exemple ressemble à ceci :
      $ echo 'cat' | trre 'c:d~a:o~t:g'
      dog
      Avec des parenthèses superflues, cela donne :
      $ echo 'cat' | trre '(c:d)~(a:o)~(t:g)'
      dog
    • La grammaire est insuffisamment spécifiée. La grammaire complète est plus complexe. Je pense que la version actuelle devrait être retirée de la documentation ; pour l’instant, elle prête vraiment à confusion.
      La raison pour laquelle c ne devient pas da tient entièrement aux priorités. En voyant cette discussion, j’ai l’impression d’avoir choisi de mauvaises priorités, et que cela crée de la confusion.
      Le tableau des priorités actuel est le suivant :
      | 1 | caractère d’échappement | \ |
      | 2 | expression entre crochets | [] |
      | 3 | groupement | () |
      | 4 | répétition ERE d’un seul caractère | * + ? {m,n} |
      | 5 | transformation | : |
      | 6 | concaténation | . (implicite) |
      | 8 | alternative | | |
      Donc : se lie plus fortement que ., c’est-à-dire que la concaténation implicite.
    • Oui, la spécification est insuffisante. L’exemple de suppression montre que la chaîne vide peut aussi être une REGEX. Dans ce cas, on peut en fait considérer qu’il y a autant de regex de chaîne vide que l’on veut à n’importe quelle position, ce qui donne une infinité d’analyses possibles.
      Si, à la place, on exige que l’expression régulière ne soit pas vide, l’exemple de suppression casse, mais l’ambiguïté se reporte sur la concaténation. Autrement dit, il devient ambigu de savoir si c’est (((c:d)(a:o))(t:g)) ou ((c:d)((a:o)(d:g))). Si l’on suppose une associativité, cette différence ne devrait pas avoir d’importance.
    • D’après le comportement, ça ressemble à c:d, a: c’est-à-dire rien, puis ot:g.
      Mais en relisant, c’est clairement confus, et sur le plan théorique la remarque est juste. Après avoir lu le dépôt, j’en suis moi aussi venu à penser que c devrait être transformé en da, mais je n’en suis pas certain.