regex - probar - expresiones regulares para nombres

Regex: determina si dos expresiones regulares pueden coincidir para la misma entrada.

Question

Quiero averiguar si podría haber conflictos entre dos expresiones regulares conocidas, para permitir al usuario construir una lista de expresiones regulares mutuamente excluyentes.

Por ejemplo, sabemos que las expresiones regulares a continuación son bastante diferentes, pero ambas coinciden con xy50 :

''^xy1/d''
''[^/d]/d2$''

¿Es posible determinar, usando un algoritmo computacional, si dos expresiones regulares pueden tener tal conflicto ? ¿Cómo?

Answer 1

El problema se puede replantear como "¿los idiomas descritos por dos o más expresiones regulares tienen una intersección no vacía"?

Si limita la pregunta a expresiones regulares puras (sin referencias, búsqueda anticipada, búsqueda por detrás u otras características que permitan el reconocimiento de lenguajes sin contexto o más complejos), la pregunta es al menos decidible. Los lenguajes regulares se cierran bajo intersección, y hay un algoritmo que toma las dos expresiones regulares como entradas y produce, en tiempo finito, un DFA que reconoce la intersección.

Cada expresión regular se puede convertir en un autómata finito no determinista, y luego en un autómata finito determinista. Un par de DFA se puede convertir a un DFA que reconoce la intersección. Si hay una ruta desde el estado de inicio hasta cualquier estado de aceptación de ese DFA final, la intersección no está vacía (un "conflicto", usando su terminología).

Desafortunadamente, hay una explosión posiblemente-exponencial al convertir el NFA inicial a un DFA, por lo que el problema rápidamente se vuelve inviable en la práctica a medida que crece el tamaño de las expresiones de entrada.

Y si se permiten extensiones a expresiones regulares puras, todas las apuestas están desactivadas; dichos idiomas ya no se cierran bajo intersección, por lo que esta construcción no funcionará.

Answer 2

No hay ningún problema de detención involucrado aquí. Todo lo que necesita es calcular si la intersección de ^xy1/d y [^/d]/d2$ no está vacía.

No puedo darte un algoritmo aquí, pero aquí hay dos discusiones sobre un método para generar la intersección sin recurrir a la construcción de un DFA:

• http://sulzmann.blogspot.com/2008/11/playing-with-regular-expressions.html
• http://www.groupsrv.com/computers/about507565.html

Y luego está RAGEL

• http://www.complang.org/ragel/

que también puede calcular la intersección de expresiones regulares.

ACTUALIZACIÓN: Acabo de probar Ragel con la expresión regular de OP. Ragel puede generar un archivo "punto" para graphviz a partir de la máquina de estado resultante, que es excelente. La intersección de la expresión regular del OP se ve así en la sintaxis de Ragel:

(''xy1'' digit any*) & (any* ^digit digit ''2'') 

y tiene la siguiente máquina de estado:

Mientras que la intersección vacía:

(''xy1'' digit any*) & (''q'' any* ^digit digit ''2'')

Se ve como esto:

Entonces, si todo lo demás falla , entonces aún puede hacer que Ragel calcule la intersección y verifique si genera la máquina de estado vacía, comparando el archivo "punto" generado.

Answer 3

Otro enfoque sería aprovechar Perl Regexp::Optimizer Dan Kogai en su lugar.

  use Regexp::Optimizer;
  my $o  = Regexp::Optimizer->new->optimize(qr/foobar|fooxar|foozap/);
  # $re is now qr/foo(?:[bx]ar|zap)/

Primero, optimice y luego descarte todos los patrones redundantes.

Tal vez Regexp::Assemble Ron Savage podría ser aún más útil. Permite ensamblar un número arbitrario de expresiones regulares en una sola expresión regular que coincida con todo lo que las RE individuales coinciden. * O una combinación de ambas.

_{* Sin embargo, debe tener en cuenta algunas diferencias entre Perl y Java u otros PCRE-flavors.}

Answer 4

Sí, creo que esto es solucionable: en lugar de pensar en expresiones regulares como cadenas coincidentes, también puede considerarlas como cadenas generadoras. Es decir, todas las cadenas con las que coincidirían.

Deje [R] ser el conjunto de cadenas generadas por la expresión regular R. Luego dadas a las expresiones regulares R y T, podríamos intentar hacer coincidir T contra [R]. Eso es [R] coincide con T si hay una cadena en [R] que coincide con T.

Debería ser posible desarrollar esto en un algoritmo donde [R] se construye perezosamente según sea necesario: donde la coincidencia de expresiones regulares normales intentaría hacer coincidir el siguiente carácter de una cadena de entrada y luego avanzar al siguiente carácter en la cadena, el algoritmo modificado verificaría si el FSM correspondiente a la expresión regular de entrada puede generar un carácter coincidente en su estado actual y luego avanza a ''todos los estados siguientes'' simultáneamente.