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

• TRRE: expresiones regulares de transducción

• Resumen

  • Es una extensión de las expresiones regulares para la edición de texto y herramientas de línea de comandos similares a grep.
  • Es un prototipo, así que no debe usarse en entornos reales.

• Introducción

  • Las expresiones regulares son una herramienta útil para buscar patrones en texto.
  • Como no parecían naturales para la edición de texto, se propone una extensión.
  • Se llaman expresiones regulares de transducción o trre.
  • Se usa el símbolo : para definir transformaciones.
  • a:b es la forma más simple: sustituye a por b.
  • Se creó una herramienta de línea de comandos llamada trre para demostrar el concepto.

• Ejemplos

  • Básico

    • Cambiar cat por dog:

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

    • Reemplazar todas las coincidencias de una cadena, como en sed:

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

    • Eliminación:

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

    • Inserción:

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

  • Expresiones regulares mediante transducción

    • Uso de alternancia:

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

    • Usar estrella para repetir transformaciones:

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

  • Transformación de rangos

    • Transformación de rangos de caracteres:

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

  • Generador

    • trre puede generar varias cadenas de salida para una sola entrada.
    • Secuencia binaria:

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

• Especificación del lenguaje

  • trre se define como un par patrón-de-coincidencia:patrón-de-generación.
  • patrón-de-coincidencia puede ser una cadena o una expresión regular.
  • patrón-de-generación normalmente es una cadena, pero también puede ser una regex.

• Por qué funciona

  • trre construye un autómata especial llamado transductor finito de estados (FST).
  • Un FST procesa pares de entrada-salida.

• Decisiones de diseño y preguntas abiertas

  • Hay que tomar varias decisiones sobre la asociatividad de :, la precedencia, el épsilon implícito, etc.

• Modos y avidez

  • trre admite dos modos:
    • Modo de escaneo (predeterminado): aplica las transformaciones de manera secuencial.
    • Modo de coincidencia: verifica la cadena completa contra la expresión.

• Determinización

  • Es importante el proceso de convertir un autómata no determinista en uno determinista.

• Rendimiento

  • La versión NFT (no determinista) es un poco más lenta que sed.
  • En tareas complejas, trre_dft (la versión determinista) puede rendir mejor que sed.

• TODO

  • Completar el conjunto de funciones ERE, soporte completo de Unicode, manejo eficiente de rangos y más.

• Referencias

  • Está inspirado en artículos de Russ Cox y en artículos académicos de Cyril Allauzen y Mehryar Mohri.

[GN⁺]

Comentarios de Hacker News

• Qué bueno, espero con interés la evolución de este proyecto

  • Siento que la precedencia de operadores no es natural
  • Es extraño que cat:dog se interprete como ca(t:d)og en lugar de (cat):(dog)

• Recomienda XFST (Xerox Finite-State Transducer)

  • Es una herramienta usada en lingüística computacional desde hace más de 20 años
  • Menciona haber oído de casos donde se usan FST para análisis morfológico del finés

• Recomienda Rosie Pattern Language como alternativa a las expresiones regulares estándar

  • Puede ser una alternativa mantenible para quienes tienen dificultades con la lógica de grupos
  • Comparte enlaces relacionados: GitLab, sitio oficial de Rosie

• Comparte la experiencia de haber escrito un artículo sobre transductores de estado finito en 1997

  • El tema era el análisis morfológico y era un tema subestimado
  • Pregunta si realmente tiene sentido configurar la sintaxis para que : tenga una unión más fuerte que ab

• Siente que no es suficiente para realizar sustituciones estructurales

  • Como la expresión regular define un árbol sintáctico para la parte coincidente del texto, sería útil poder realizar transformaciones generales del árbol

• Pone en duda la afirmación de que las expresiones regulares son antinaturales para editar texto

  • El propósito del proyecto depende de esa afirmación, pero no hay ejemplos
  • No entiende por qué a algunas personas les cuesta usar grupos
  • Hace falta un ejemplo que explique por qué la gramática de este proyecto sería mejor que las expresiones regulares

• Elogia que el código en C está muy limpio

  • El enlace theory.pdf del README está mal y necesita corrección

• Cuestiona el consejo de no usar * ni +

  • Aunque complicaría más la gramática, sería mejor permitirlos

• Siente que el primer ejemplo es extraño

  • El resultado de echo 'cat' | trre 'c:da:ot:g' es raro
  • Es difícil entender cómo se construye el árbol sintáctico
  • Le parece que la forma de buscar/sustituir de la época de MS-DOS era más intuitiva

• Se pregunta si los ejemplos son realmente la salida del programa

  • Puede que no entienda bien la sintaxis, pero los ejemplos parecen estar mal
  • El resultado de echo 'cat dog' | trre 'c:bat|d:hog' es extraño