Show HN: Expresiones regulares transductivas para edición de texto

 (github.com/c0stya)
1 puntos por GN⁺ 2025-02-09 | 1 comentarios | Compartir por WhatsApp
  • TRRE es una extensión del lenguaje de expresiones regulares que agrega el operador : para expresar transformaciones de texto directamente, y se ofrece con la herramienta CLI experimental trre, similar a grep -E
  • La forma básica es un par transductivo como a:b, que cambia un patrón de entrada por un patrón de salida; la eliminación se expresa como x: y la inserción como :x, es decir, transformaciones con la cadena vacía
  • Igual que en una expresión regular común, se pueden usar alternativas, repeticiones y transformaciones de rangos de caracteres, con ejemplos como cat:dog, [a:A-z:Z] y un cifrado César
  • La implementación interna construye un Finite State Transducer (FST) que maneja pares entrada-salida en lugar del FSA de una expresión regular normal, y también soporta una determinización experimental on-the-fly
  • Por ahora no hay binarios precompilados y hay que compilarlo manualmente; entre los TODO pendientes están estabilizar DFT, soporte completo de Unicode, completar funciones ERE y procesar rangos de forma eficiente

El problema que TRRE busca resolver

  • Las expresiones regulares comunes son útiles para encontrar patrones en texto, pero en edición de texto la lógica de manejo de grupos puede volverse compleja al funcionar como posprocesamiento
  • TRRE extiende el lenguaje de expresiones regulares para poner el matching de patrones y la modificación de texto dentro de una misma expresión
  • La sintaxis central tiene la forma pattern-to-match:pattern-to-generate, y el ejemplo más simple es a:b, que cambia a por b
  • La herramienta CLI trre es una implementación que demuestra esta idea y funciona con una sensación similar a grep -E

Sintaxis básica de transformación

  • La sustitución de cadenas se escribe como cat:dog
    • echo 'cat' | ./trre 'cat:dog' imprime dog
    • También se puede lograr el mismo resultado con una transformación carácter por carácter como (c:d)(a:o)(t:g)
  • Puede usarse, como sed, para cambiar todas las coincidencias dentro de una cadena
    • Si se aplica lamb:cat a Mary had a little lamb., el resultado es Mary had a little cat.
  • La eliminación se expresa dejando vacía la parte derecha, con la forma string_to_delete:
    • (x:)or elimina x de xor y produce or
    • a: cambia todas las a por el símbolo vacío y las elimina en el scan mode por defecto
    • También se pueden eliminar varios caracteres con corchetes, como en [aie]:
  • La inserción se expresa dejando vacía la parte izquierda, con la forma :string_to_insert
    • (:x)or inserta x antes de or y produce xor
    • had a (:little )lamb inserta little dentro de ese contexto

Transformaciones sobre expresiones regulares

  • TRRE soporta alternativas con |, igual que una expresión regular normal
    • (c:b)at|(d:h)og cambia cat dog por bat hog
  • Los operadores de repetición también pueden aplicarse a transformaciones
    • (cat:dog)* cambia catcatcat por dogdogdog
    • En el scan mode por defecto, cat:dog por sí solo también se aplica repetidamente y logra el mismo resultado
  • Si se usa repetición en el patrón izquierdo, se pueden consumir varias entradas y convertirlas en una sola salida
    • (cat)*:dog cambia catcatcat por dog
  • Si se usan * o + en el patrón derecho, puede producirse un bucle infinito
    • Conviene evitar expresiones como :a*
    • Si hace falta una repetición finita, se puede indicar explícitamente la cantidad, como en :(repeat-10-times){10}

Transformación de rangos y generadores

  • La transformación de rangos de caracteres se escribe como [a:A-z:Z]
    • Puede convertir regular expressions en REGULAR EXPRESSIONS
  • Se incluye un ejemplo de cifrado César
    • [a:b-y:zz:a] cambia caesar cipher por dbftbs djqifs
    • [a:zb:a-z:y] lo revierte de nuevo a caesar cipher
  • También puede actuar como generator, produciendo varias salidas a partir de una sola entrada
    • Por defecto se usa la primera coincidencia posible
    • Con la opción -a genera todas las salidas posibles
  • Por ejemplo, aplicar :(0|1){3} a una entrada vacía genera secuencias binarias de 3 bits desde 000 hasta 111
  • Si se usa :(0|1){,3}? junto con -ma, se generan salidas con forma de subconjuntos de longitud 3 o menor

Especificación del lenguaje y precedencia de operadores

  • De manera informal, TRRE se define como pares pattern-to-match:pattern-to-generate
  • El pattern-to-match de la izquierda puede ser una cadena o una expresión regular
  • El pattern-to-generate de la derecha suele ser una cadena, pero también puede ser una expresión regular
  • El operador : se trata actualmente como no asociativo, por lo que la forma TRRE:TRRE no está permitida gramaticalmente
    • Esa forma tendría el significado natural de componer las relaciones que define TRRE, pero por la complejidad adicional todavía se deja fuera
  • La precedencia de operadores, de mayor a menor, es la siguiente
    • Carácter de escape \
    • Expresiones entre corchetes []
    • Agrupación ()
    • Repetición * + ? {m,n}
    • Concatenación
    • Transducción :
    • Alternativa |

Modos y voracidad

  • trre soporta dos modos
    • Scan Mode: modo por defecto, aplica transformaciones secuencialmente
    • Match Mode: usa la bandera -m y verifica si toda la cadena coincide con la expresión
  • La opción -a genera todas las salidas posibles
  • El modificador ? vuelve non-greedy a los operadores *, + y {,}
    • <(.:)*> sobre <cat><dog> produce <>
    • <(.:)*?> sobre la misma entrada produce <><>
  • También se incluyen ejemplos de cambiar contenido dentro de etiquetas o paréntesis
    • <(.*?:cat)> cambia <dog> <mouse> por <cat> <cat>

Implementación basada en FST y determinización

  • Internamente, TRRE construye un Finite State Transducer (FST)
  • Un FST es similar al Finite State Automaton (FSA) usado en expresiones regulares comunes, pero trabaja con pares entrada-salida en lugar de cadenas simples
  • Las diferencias clave de TRRE son las siguientes
    • Define una relación binaria entre dos lenguajes regulares
    • Usa FST en lugar de FSA para la inferencia
    • Soporta determinización experimental on-the-fly para mejorar el rendimiento
  • En motores de expresiones regulares comunes, la determinización convierte un autómata no determinista en uno determinista para permitir inferencia en tiempo lineal respecto a la longitud de la cadena de entrada
  • En TRRE puede aplicarse una idea parecida, pero no todos los transductores no deterministas NFT pueden convertirse en transductores deterministas DFT
    • Si hay dos ciclos “malos” con la misma etiqueta de entrada, la generación de estados puede caer en un bucle infinito
    • Existen métodos para detectar estos bucles, pero su costo es alto

Rendimiento y estado de instalación

  • Se muestra un ejemplo donde la versión no determinista básica es un poco más lenta que sed en una sustitución simple
    • ./trre '(vodka):(VODKA)': real 0m0.046s
    • sed 's/vodka/VODKA/': real 0m0.024s
  • En tareas más complejas, hay un ejemplo donde la versión determinista trre_dft es más rápida que sed
    • sed -e 's/\(.*\)/\U\1/': real 0m0.508s
    • ./trre_dft '[a:A-z:Z]': real 0m0.131s
  • Todavía no se ofrecen binarios precompilados
  • La instalación consiste en clonar el repositorio y luego compilar y probar con make && sh test.sh
  • Entre los TODO pendientes están los siguientes
    • Una versión DFT estable
    • Soporte completo de Unicode
    • Completar funciones ERE
      • Negación ^ dentro de []
      • Clases de caracteres
      • Símbolos ancla $^
    • Procesamiento eficiente de rangos

Enfoques de referencia

Lecturas relacionadas

1 comentarios

 
GN⁺ 2025-02-09
Comentarios de Hacker News

  • Me intriga ver hacia dónde va este proyecto. Dicho eso, la precedencia de operadores se siente poco natural, y parece que otras personas en este hilo sintieron algo parecido
    Uno esperaría naturalmente que cat:dog fuera equivalente a (cat):(dog), no a ca(t:d)og

    • Es una idea interesante en muchos sentidos
      A mí también me confundió que cat:dog se interprete como ca(t:d)og y no como (cat):(dog), pero lo entendí al recordar que todos estamos usando un poco mal las expresiones regulares. Las regex “en realidad” deberían verse como generadores de cadenas, no como matchers, así que cat|dog puede expandirse formalmente como un conjunto tipo {catog,cadog}
      En matching, basta con hacer una búsqueda de subcadenas de ese conjunto de cadenas dentro de un texto más grande. El problema es que la mayoría de los motores de regex reales no funcionan así, sino que hacen varias cosas raras para ajustarse a las expectativas o por eficiencia
      Si pruebas varias herramientas de regex, aparecen variantes como (cat)|(dog) o (cat)|(dog)|(ca[td]og). Por eso, desde una perspectiva más formal, me parece correcto que cat:dog produzca ca(t:d)og y no (cat):(dog). Pero tras décadas de abusar de las regex como herramientas de matching ajustadas a las expectativas del usuario, ahora todos ponemos paréntesis alrededor de la expresión que queremos reemplazar
      Esta propuesta es interesante y está bien diseñada, pero al final se siente como un intento de devolver las regex a su modelo generador original. El problema está más del lado de las herramientas que de la gramática
      Hace tiempo trabajé en algo cercano a este ámbito; si nunca pensaste en las regex como generadores de conjuntos de cadenas, puedes jugar con esto aquí: https://onlinestringtools.com/generate-string-from-regex
      Dicho eso, el comportamiento de estas herramientas de generación también es muy específico. Las herramientas que yo usaba tenían varias formas de limitar el generador especificando restricciones sobre clausuras y cosas similares
    • Gracias por el feedback; la precedencia es algo que yo también estoy evaluando, así que podría cambiarla
      Posponerlo hasta después de la concatenación puede traer otros problemas. Por ejemplo, con un : no asociativo, quizá cat:dog:mouse debería ser ilegal, y no estoy seguro de cómo tratarlo
      En la versión actual se inserta épsilon, es decir, la cadena vacía. Por ejemplo, para eliminar saltando de a un carácter, técnicamente puedes ejecutar ..:, que es .(.:eps)
      El resultado de echo 'abcde' | ./trre '..:' es 'ace'
      De hecho, la asociación de : también podría tener el significado de composición de relaciones regulares, pero por ahora me pareció demasiado complejo
    • Las transformaciones de rangos son parecidas. En vez de [a:A-z:Z], sería mejor [a-z:A-Z], y propondría algo como [a-y:b-z;z:a] en lugar de [a:b-y:zz:a]

  • Si te interesan los transductores de estado finito y herramientas relacionadas, vale la pena ver XFST (Xerox Finite-State Transducer). Se ha usado durante más de 20 años en aplicaciones de lingüística computacional
    Un investigador finlandés de PARC vino a una clase en UT y mostró cómo procesar la morfología del finés con FST; incluso visto desde fuera, era algo bastante impresionante

    • Yo también iba a mencionar esto. Enlace al paper de Kaplan: https://aclanthology.org/J94-3001.pdf
      Explica el trabajo que se hizo en PARC
    • http://hfst.github.io/ es la versión open source moderna de XFST. Abarca foma y OpenFst, y probablemente puede hacer casi todo lo que hace trre, y más
    • También podría interesarte Pynini. Es un wrapper de Python para OpenFst con muchas funciones añadidas para facilitar su uso
      OpenFst es una biblioteca realmente excelente para transductores. También son buenos los tutoriales con casos de uso de Pynini que hicieron en Johns Hopkins y otros lugares en forma de tareas
      [1] https://www.openfst.org/twiki/bin/view/GRM/Pynini
      [2] https://www.openfst.org/

  • Si estás buscando una alternativa a las expresiones regulares estándar, especialmente si la lógica de grupos te resulta difícil o quieres expresiones mantenibles, Rosie Pattern Language podría ser lo adecuado
    https://gitlab.com/rosie-pattern-language/rosie/-/blob/maste...
    https://rosie-lang.org/about/

  • Genial. Hacia 1997 escribí mi tesis de Diplom en informática sobre transductores de estado finito, y resultó ser bastante menos trivial de lo que esperaba
    La tarea era implementar composición y DFA cuando fuera posible, incluidos transductores compuestos. Era “álgebra de transductores de estado finito” y el caso de uso era la morfología. El tema estaba muy subestimado, así que tuve que cerrarlo más o menos a la mitad. Así que, mis respetos
    Sobre la gramática, me pregunto si de verdad quieres que : se asocie con más fuerza que la concatenación ab

    • A principios de los 2000 usé OpenFST en bioinformática. Era divertido para experimentar, pero al final no resultó útil para el trabajo que estaba haciendo
      Es bueno ver que, 20 años después, el proyecto sigue activo: https://www.openfst.org/twiki/bin/view/FST/WebHome
    • Apostar la graduación, en la práctica, a “si puedes manejar expresiones regulares con suficiente intensidad” es una elección tremendamente audaz
    • Así es. Los transductores son un tema muy antiguo. Por alguna razón no quedaron tan fuertemente vinculados a lenguajes específicos como las expresiones regulares
      Todavía no estoy seguro de si : debería asociarse con más fuerza que la concatenación. Después de ver unos 100 ejemplos, me pareció más natural el enfoque actual, es decir, que : tenga menor precedencia que ., pero en el código literalmente se puede cambiar modificando un solo número. Por eso lo publiqué aquí: necesito feedback real

  • En cuanto se quiere hacer algún tipo de sustitución estructural, este enfoque no parece suficiente. Por ejemplo, a veces uno quiere hacer algo como s/"([^"]*)"/'$1'/
    Además, si se pudiera cambiar lo que coincide con ['] dentro de [^"] por \', se vería más útil
    En términos más generales, como una expresión regular básicamente define un árbol de parseo sobre el resultado de la coincidencia, sería útil poder realizar transformaciones más generales sobre ese árbol

    • Si entendí bien, la siguiente expresión ttre hace lo que se busca:
      ":'(':(\\')|[^"'])*":'
    • Si entendí bien, lo que se quiere es cambiar el contenido dentro de un bloque "..." y cambiar las comillas por comillas simples '
      Se puede hacer con esta expresión:
      echo '"hello world" "hello again!"' | ./trre "\":'.+?:-\":'"
      El resultado es '-' '-'
      Es decir, con la expresión ".+?:-" se sustituye el texto dentro de "" por el símbolo - y, al mismo tiempo, se cambian las comillas que lo rodean. El signo de interrogación indica modo no codicioso

  • Parece que todo el proyecto depende de la afirmación “las expresiones regulares son una gran herramienta para encontrar patrones en texto, pero siempre me parecieron poco naturales para editar texto”, pero no hay ni un solo ejemplo
    No entiendo por qué las expresiones regulares serían poco naturales para editar. Tampoco sé qué significa editar aquí, ni por qué la gente tendría problemas con los grupos
    Hay muchos ejemplos de la sintaxis de este proyecto, pero no veo por qué sería mejor que las expresiones regulares normales. Creo que podría entender el proyecto si hubiera algunos ejemplos del tipo “la versión con regex básica es esta, mi versión es esta, y por eso resulta más fácil”

    • Creo que las expresiones regulares suelen tener un carácter de se escriben una vez y no se vuelven a tocar. Crear un prototipo que mire más allá de eso es una buena forma de explorar un futuro mejor para este campo
    • Es una observación válida. El ejemplo más claro es cuando se necesita cambiar solo dentro de un contexto
      Por ejemplo, para cambiar solo la y que está entre x y z por Y, en Python se haría más o menos así:
      pattern = r'(x)y(z)'
      replacement = r'\1Y\2'
      result = re.sub(pattern, replacement, text)
      Yo quisiera reemplazar eso por el patrón xy:Yz:
      result = re.trre('xy:Yz', text)
      Si x y z son patrones más complejos o expresiones regulares en sí mismas, este enfoque podría ser más cómodo
    • Es correcto decir que las expresiones regulares por sí solas no ofrecen funcionalidad de edición. Tienen grupos, pero para combinar esos grupos hay que usar otro lenguaje, como sed
    • Se trata de sustituciones. Con la sintaxis del autor, expresar sustituciones —literalmente, escribirlas— es más fácil
      Buen proyecto

  • El código en C es un verdadero gusto de leer. Muy bueno, lo estoy leyendo ahora
    Solo un comentario breve: el enlace a theory.pdf en el README está roto. El PDF está en el directorio docs/, así que basta con incluir docs/ en la URL

    • Gracias por el feedback y por señalar el typo. Ya lo corregí. La verdad es que mis habilidades en C están bastante oxidadas, así que me da algo de inseguridad

  • Se dice que hay que evitar usar * o + en la parte derecha porque puede causar un bucle infinito, pero ¿no se podría simplemente prohibirlos?
    Entiendo que la especificación de la gramática se volvería más difícil, pero no parece haber una buena razón para mantenerlos

    • Es una observación válida y estoy de acuerdo. Por ahora sería mejor desactivarlos
      La razón original era que quería implementar una operación interesante llamada composición de transductores. Se pueden hacer operaciones simples sobre cadenas y componer trre como filtros, pero todavía no lo terminé. Así que sí, es una observación válida

  • Es una exploración interesante, pero faltan ejemplos de por qué en la práctica es mejor. Claro que también puede ser que yo lleve demasiado tiempo acostumbrado a las expresiones regulares
    Por ejemplo, no veo por qué (cat):(dog) en trre sería mejor que s/cat/dog, ni qué ventaja tiene (x:)or sobre s/xor/or. Casi todos los ejemplos se me traducen mentalmente a expresiones regulares relativamente fáciles
    Si hay una ventaja central, sospecho que está en la lógica de grupos, así que sería bueno enfocar los ejemplos en eso. Parece mejor explicar primero por qué es una mejor opción, incluso antes de explicar la sintaxis básica
    El ejemplo del cifrado César parece pedir a gritos una función de “aplicar esto en sentido inverso”. Es una petición común en muchas sustituciones de texto, y en este ejemplo resulta especialmente clara. La mente de un programador grita de inmediato: “¿por qué tengo que expresar la misma lógica dos veces?”
    Todavía no sé si será útil, pero es excelente explorar alternativas a un statu quo muy asentado. Por lo general, esos intentos también tienen muchas probabilidades de no prosperar, pero aun así la exploración en sí da gusto verla

  • La especificación parece bastante incompleta. El primer ejemplo ya es raro:
    $ echo 'cat' | trre 'c:da:ot:g'
    dog
    No sé qué está pasando aquí. La gramática está así:
    TRRE <- TRRE* TRRE|TRRE TRRE.TRRE
    TRRE <- REGEX REGEX:REGEX
    ¿Cuál es el árbol de parseo aquí? ¿Por qué c no se convierte en da? O ¿por qué no se elimina c y da se convierte en ot?
    La idea de tener una semántica de búsqueda/reemplazo más intuitiva que un operador de agrupación está buena. En la época de MS-DOS podías hacer algo como ren .log .txt y funcionaba; desde la mentalidad moderna tipo bash no tiene sentido, pero a simple vista la intención era clarísima.

    • Esto es un problema de precedencia de operadores y tokenización. En este lenguaje los tokens son caracteres individuales, y entre caracteres hay un operador invisible.
      Si llamamos explícitamente a ese operador ~, el ejemplo se ve así:
      $ echo 'cat' | trre 'c:d~a:o~t:g'
      dog
      Si agregamos paréntesis innecesarios, queda así:
      $ echo 'cat' | trre '(c:d)~(a:o)~(t:g)'
      dog
    • La gramática está poco especificada. La gramática completa es más compleja. Creo que habría que quitar la versión actual de la documentación; por ahora en realidad solo genera confusión.
      Lo de por qué c no se convierte en da se debe totalmente a la precedencia. Viendo esta discusión, parece que elegí una precedencia equivocada, y eso causa confusión.
      La tabla de precedencia actual es la siguiente:
      | 1 | carácter de escape | \ |
      | 2 | expresión con corchetes | [] |
      | 3 | agrupación | () |
      | 4 | repetición ERE de un solo carácter | * + ? {m,n} |
      | 5 | transformación | : |
      | 6 | concatenación | . (implícita) |
      | 8 | selección | | |
      Así que : se asocia con más fuerza que ., es decir, que la concatenación implícita.
    • Sí, la especificación está incompleta. El ejemplo de eliminación muestra que la cadena vacía también puede ser un REGEX. Entonces, en la práctica, se puede considerar que en cualquier posición hay tantas regex de cadena vacía como se quiera, así que hay infinitos parseos.
      Si en cambio se exige que la expresión regular no esté vacía, el ejemplo de eliminación se rompe, pero la ambigüedad pasa al lado de la concatenación. Es decir, queda ambiguo si es (((c:d)(a:o))(t:g)) o ((c:d)((a:o)(d:g))). Si se asume asociatividad, esta diferencia probablemente no importe.
    • Por cómo se siente el comportamiento, parece c:d, a: o sea nada, y ot:g.
      Pero al releerlo, definitivamente es confuso, y en teoría la observación es válida. Después de leer el repositorio, yo también terminé creyendo que c debería convertirse en da, aunque no estoy seguro.