Cálculo de diferencias e intersecciones entre dos expresiones regulares

 (phylactery.org)
2 puntos por GN⁺ 2023-09-12 | 1 comentarios | Compartir por WhatsApp
  • Cuando necesitas comparar expresiones regulares como si fueran conjuntos de cadenas, antimirov calcula en una sola pantalla la inclusión y equivalencia entre dos expresiones α y β, además de su intersección y diferencia
  • El área de resultados muestra el complemento y las relaciones al mismo tiempo, y permite revisar operaciones como ~α, α < β, α = β, α & β, α ^ β, α - β
  • Si ingresas una cadena aparte s, puedes verificar de inmediato si coincide con cada expresión regular mediante s ∈ α, s ∈ β
  • La sintaxis soporta ., concatenación, alternancia |, repetición *·+·?·{n}·{m,n}, grupos de caracteres, grupos de caracteres negados, escapes y escapes Unicode UTF-16
  • No soporta funciones que cambian el comportamiento como anclas, aserciones de longitud cero, retroreferencias, extracción de subgrupos, búsqueda o coincidencia parcial, ni ignorar mayúsculas/minúsculas

Comparación de expresiones regulares y operaciones de conjuntos

  • El área de entrada recibe dos expresiones regulares α y β
  • La salida muestra conjuntamente el complemento y las operaciones relacionales y de conjuntos entre ambas expresiones regulares
    • ~α, ~β: complemento de cada expresión regular
    • α < β, α = β, α > β: relación de inclusión y equivalencia entre las dos expresiones regulares
    • α & β: intersección
    • α ^ β: diferencia simétrica
    • α - β: diferencia
  • Si ingresas la cadena s, puedes comprobar si pertenece a cada expresión regular en la forma s ∈ α, s ∈ β
  • También se muestra el tamaño de cada expresión regular y la cantidad de estados del DFA
    • En la pantalla de ejemplo, |α| = 1, |β| = 1
    • En la pantalla de ejemplo, dfa(α) y dfa(β) tienen 1 estado cada uno

Sintaxis de expresiones regulares compatible

  • Los operadores básicos cubren carácter único, concatenación, alternancia y repetición
    • .: coincide con cualquier carácter único
    • xy: concatenación que coincide con x seguido de y
    • x|y: coincide con x o y
    • x*: repetición de 0 o más veces
    • (xyz): agrupación
    • (): expresión regular vacía que coincide con la cadena vacía
  • También soporta abreviaturas comunes de repetición
    • x+: repetición de 1 o más veces, equivalente a xx*
    • x?: coincidencia opcional, equivalente a (x|)
    • x{n}: concatena x n veces
    • x{m,n}: concatena x entre m y n veces
  • Los conjuntos de caracteres y escapes pueden usarse en las siguientes formas
    • [a-z0-9]: coincide con un carácter único dentro del grupo
    • [^a-z0-9]: coincide con un carácter único que no está en el grupo
    • \c: escape del carácter especial c
    • \u001a: coincide con el carácter UTF-16 correspondiente
    • Además, caracteres como a, b, c coinciden consigo mismos

Funciones no compatibles

  • antimirov se enfoca en tratar las expresiones regulares como objetos de operaciones de conjuntos, por lo que excluye las siguientes funciones
    • Anclas ^, $
      • Aun así, ^ y $ deben escaparse
    • Aserciones de longitud cero, por ejemplo (?=...), (?<=...)
    • Retroreferencias, por ejemplo \1, \2
    • Extracción de subgrupos
    • Búsqueda o coincidencia parcial
    • Otras banderas que cambian el comportamiento, como ignorar mayúsculas/minúsculas
  • Puedes consultar más información en non/antimirov

Lecturas relacionadas

1 comentarios

 
GN⁺ 2023-09-12
Comentarios de Hacker News

  • Hice una demo web similar que muestra cómo una expresión regular se transforma en parsing → NFA → DFA → DFA mínimo, y luego genera salida hasta LLVM IR/Javascript/WebAssembly
    http://compiler.org/reason-re-nfa/src/index.html

    • Aun así, pasar de un NFA a un DFA explícito no siempre es la mejor opción
      Como referencia, la derivada de Brzozowski también puede ser interesante como enfoque alternativo para hacer matching de expresiones regulares: https://en.wikipedia.org/wiki/Brzozowski_derivative

  • Esta biblioteca puede usarse para construir una jerarquía de clases de strings, y como resultado aprovechar de forma más agresiva los strings tipados
    Por ejemplo, el email y la URL tienen una gramática especial, y su espacio de valores es un subconjunto de todos los strings no vacíos; a su vez, los strings no vacíos son un subconjunto de todos los strings
    Si el sistema de tipos sabe que un string de email es un subtipo de string no vacío, puede considerar válido pasar una dirección de email a una función que requiere un string no vacío
    Esta biblioteca puede usarse para verificar la definición y la jerarquía de esos tipos de string, y la implementación de la jerarquía cambia según el lenguaje, ya sea con subclases, límites de traits, etc.

    • En lenguajes con tipos suma etiquetados, este enfoque se usa bastante. En pseudocódigo estilo Haskell sería algo así
      No se exporta el constructor Address, solo el tipo, y se valida dentro de fromString :: Text -> Maybe Address; si la dirección no es válida, devuelve Nothing
      La validez no se mezcla dentro de los datos, sino que se señala por una vía aparte, y cuando hace falta mostrarla se vuelve a extraer el valor envuelto con toText :: Address -> Text
    • Es mejor no usar una expresión regular para validar direcciones de email
      https://news.ycombinator.com/item?id=31092912
    • Hay pocas cosas tan peculiares como pasar una mañana de fines del verano investigando qué está permitido y qué no en el lado izquierdo del @ en una dirección de email
      La heurística simple de asumir que toda expresión regular que intente representar una “dirección de email válida” está equivocada es bastante segura, pero le quita toda la diversión
    • Tengo curiosidad por saber qué significa “espacio de valores”

  • Las expresiones regulares son un gran ejemplo de cómo una teoría matemática bastante elegante y compleja puede empaquetarse en una interfaz valiosa
    El álgebra lineal me produce una sensación parecida

    • Siempre me sorprende cuánto de las matemáticas puede convertirse en álgebra lineal si se elige el campo adecuado
      Incluso una transformación de Möbius del plano complejo w=(az+b)/(cz+d) puede convertirse en álgebra lineal
    • Normalmente eso significa que la representación se está acercando más a la verdad
      Las buenas interfaces tienen un valor esencial, aunque mucha gente orientada solo a resultados no lo reconozca bien
    • Si mal no recuerdo, en https://store.doverpublications.com/0486485838.html de Conway aparecía la conexión con el álgebra lineal. Solo la hojeé por encima

  • Esta página genial calcula la relación binaria entre pares de expresiones regulares y muestra el DFA como grafo
    Hace una demostración realmente impresionante de operaciones bastante no triviales sobre expresiones regulares

    • Es muy genial, pero tampoco sorprende que, estrictamente hablando, no soporte funciones que hacen que dejen de ser expresiones regulares
      Aun así, pensé que los anchors ^ y $ no iban a ser problema

  • Pegué “regex filter numbers divisible by 3” y la página se quedó completamente congelada: 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])))+$
    Me pregunto si habrá una expresión más corta

    • Esta página web se cuelga con expresiones regulares que generan DFAs con muchos estados
      Por ejemplo (ab+c+)+, (abc){100}, a.*quick brown fox jumps over the lazy dog
    • De todos modos, según la explicación de la página, los anchors no están soportados

  • Quería ver la intersección entre URLs y direcciones de email gramaticalmente válidas, pero incluso ingresando solo la regex de URL de abajo la página tarda demasiado en procesarla
    [\-a-zA-Z0-9@:%._+~#=]{1,256}\.[a-zA-Z0-9()]{1,6}\b([\-a-zA-Z0-9()@:%_+.~#?&//=]*)
    Fuente: https://stackoverflow.com/a/3809435/623763

    • Expresiones como (...){1,256} son muy pesadas, y el código Scala JS termina agotando el tiempo o matando el navegador
      Si lo cambias por (...)+, al menos en mi entorno funciona. Expresiones pequeñas como (...){1,6} probablemente estén bien

  • Al principio me sorprendió y luego me hizo sentido que las expresiones regulares generadas por unión e intersección no sean especialmente compactas
    Por ejemplo, la intersección de "y.+" y ".+z" puede escribirse con una expresión muy simple: "y.*z", y la página también confirma la equivalencia. Pero la herramienta devuelve yz([^z][^z]*z|z)*|y[^z](zz*[^z]|[^z])*zz*
    Debe haber una razón para que salga así, pero producir una expresión regular mínima según criterios como cantidad de caracteres probablemente sea mucho más difícil

    • Una de las razones probablemente sea que ".+z" se vuelve más grande y desordenada después de convertirse en un autómata determinista

  • Hace tiempo usé este concepto para escribir la lógica de validación de una configuración de “IP RegEx filter”
    La meta era permitir que el usuario configurara el filtro de IP con una expresión regular. El equipo de marketing no entendía CIDR, pero sí conocía las expresiones regulares por Google Analytics
    ¿Cómo se puede definir una expresión regular válida? La intersección con la expresión regular de “todas las direcciones IPv4” no debía estar vacía y, al mismo tiempo, tampoco debía ser igual a la expresión regular de “todas las direcciones IPv4”
    Esto evitó muchas quejas de que el filtro no hacía nada, pero no impidió que se ingresaran filtros incorrectos

    • ¿No habría sido posible una solución más simple? En lugar de intentar validar la expresión regular del filtro, se podrían mostrar direcciones IP de ejemplo o permitir que el usuario introdujera un conjunto de direcciones, y luego mostrar cuáles coinciden y cuáles no
      También ayudaría a tratar el problema de los filtros incorrectos

  • Para que fuera más cómodo de usar en móvil, sería bueno desactivar las sugerencias automáticas en el campo de entrada de expresiones regulares
    https://stackoverflow.com/questions/35513968/disable-autocor...

  • Probé la página con 2 expresiones regulares de números divisibles entre 3 similares, y se colgaba incluso si quitaba los ^ y $ de los extremos
    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])))*
    Todo se parsea hasta justo antes del último *, pero en cuanto se agrega ese *, toda la página se congela
    Sin ese *, se obtuvo un validador válido que parsea fragmentos numéricos cuya suma de dígitos es divisible entre 3