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

• TRRE : expressions régulières de transduction

• Résumé

  • Une extension des expressions régulières pour l’édition de texte et les outils en ligne de commande similaires à grep.
  • Il s’agit d’un prototype, ne pas l’utiliser en production.

• Introduction

  • Les expressions régulières sont des outils utiles pour rechercher des motifs dans le texte.
  • Elles semblent peu naturelles pour l’édition de texte, d’où cette proposition d’extension.
  • Cela s’appelle expressions régulières de transduction ou trre.
  • Le symbole : est utilisé pour définir une transformation.
  • a:b est la forme la plus simple, qui remplace a par b.
  • Un outil en ligne de commande appelé trre a été créé pour démontrer le concept.

• Exemples

  • Bases

    • Remplacer cat par dog :

      $ echo 'cat' | trre 'c:da:ot:g'
      dog
      

    • Remplacer toutes les occurrences d’une chaîne, comme avec sed :

      $ echo 'Mary had a little lamb.' | trre '(lamb):(cat)'
      Mary had a little cat.
      

    • Suppression :

      $ echo 'xor' | trre '(x:)or'
      or
      

    • Insertion :

      $ echo 'or' | trre '(:x)or'
      xor
      

  • Expressions régulières via transduction

    • Utilisation de l’alternance :

      $ echo 'cat dog' | trre 'c:bat|d:hog'
      bat hog
      

    • Utilisation de l’étoile pour répéter la transformation :

      $ echo 'catcatcat' | trre '((cat):(dog))*'
      dogdogdog
      

  • Transduction de plages

    • Transduction de plages de caractères :

      $ echo "regular expressions" | trre "[a:A-z:Z]"
      REGULAR EXPRESSIONS
      

  • Générateurs

    • trre peut produire plusieurs chaînes de sortie pour une seule entrée.
    • Séquence binaire :

      $ echo '' | trre -ma ':(0|1){3}'
      000  001  010  011  100  101  110  111
      

• Spécification du langage

  • trre est défini comme une paire motif-de-correspondance:motif-de-génération.
  • Le motif-de-correspondance peut être une chaîne ou une expression régulière.
  • Le motif-de-génération est généralement une chaîne, mais peut aussi être une regex.

• Pourquoi cela fonctionne

  • trre construit un automate spécial appelé transducteur à états finis (FST).
  • Les FST traitent des paires entrée-sortie.

• Choix de conception et questions ouvertes

  • Plusieurs décisions sont nécessaires concernant l’associativité de :, la priorité, l’epsilon implicite, etc.

• Modes et avidité

  • trre prend en charge deux modes :
    • Mode scan (par défaut) : applique les transformations séquentiellement.
    • Mode match : vérifie la chaîne complète par rapport à l’expression.

• Déterminisation

  • Le processus de conversion d’un automate non déterministe en automate déterministe est important.

• Performances

  • La version NFT (non déterministe) est légèrement plus lente que sed.
  • Pour des tâches complexes, trre_dft (la version déterministe) peut être plus performante que sed.

• TODO

  • Compléter l’ensemble de fonctionnalités ERE, prise en charge complète d’Unicode, gestion efficace des plages, etc.

• Références

  • Inspiré par les articles de Russ Cox et les travaux de Cyril Allauzen et Mehryar Mohri.

[GN⁺]

Commentaires Hacker News

• Cool, j’ai hâte de voir l’évolution de ce projet

  • J’ai l’impression que la priorité des opérateurs n’est pas naturelle
  • Il est étrange que cat:dog soit interprété comme ca(t:d)og plutôt que (cat):(dog)

• Recommande XFST (Xerox Finite-State Transducer)

  • C’est un outil utilisé en linguistique informatique depuis plus de 20 ans
  • A entendu parler de cas où les FST sont utilisés pour l’analyse morphologique du finnois

• Recommande Rosie Pattern Language comme alternative aux expressions régulières standard

  • Cela peut constituer une alternative plus maintenable pour les personnes qui ont du mal avec la logique des groupes
  • Liens associés : GitLab, site officiel de Rosie

• Partage son expérience d’avoir écrit un article sur les transducteurs à états finis en 1997

  • Le sujet portait sur l’analyse morphologique et c’était un sujet sous-estimé
  • Demande s’il est correct, pour la syntaxe, de faire en sorte que : se lie plus fortement que ab

• Trouve cela insuffisant pour effectuer des substitutions structurées

  • Puisque l’expression régulière définit un arbre syntaxique sur la partie appariée du texte, il serait utile de pouvoir effectuer des transformations générales de cet arbre

• Met en doute l’affirmation selon laquelle les expressions régulières seraient peu naturelles pour l’édition de texte

  • L’objectif du projet repose sur cette affirmation, mais aucun exemple n’est donné
  • Ne comprend pas pourquoi certaines personnes ont du mal à utiliser les groupes
  • Il faudrait des exemples expliquant pourquoi la grammaire de ce projet est meilleure que les expressions régulières

• Complimente la grande propreté du code C

  • Le lien theory.pdf dans le README est erroné et doit être corrigé

• S’interroge sur le conseil de ne pas utiliser * ni +

  • Cela rendrait la grammaire plus complexe, mais il vaudrait peut-être mieux les autoriser

• Trouve le premier exemple étrange

  • Le résultat de echo 'cat' | trre 'c:da:ot:g' est bizarre
  • Il est difficile de comprendre comment l’arbre syntaxique est construit
  • Trouve que la méthode de recherche/remplacement de l’époque MS-DOS était plus intuitive

• Se demande si les exemples sont bien des sorties réelles du programme

  • Il comprend peut-être mal la syntaxe, mais les exemples semblent erronés
  • Le résultat de echo 'cat dog' | trre 'c:bat|d:hog' paraît étrange