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

Question

Quiero averiguar si alguna vez 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 siguientes son muy diferentes, pero ambos partido xy50:

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

¿Es posible determinar, utilizando un algoritmo de computadora, si dos expresiones regulares pueden tener un tales conflicto? ¿Cómo?

Answer 1

No hay 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 le puede dar un algoritmo aquí, pero aquí hay dos discusiones de un método para generar la intersección sin tener que 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 las 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 expresión regular de la OP es la siguiente con la sintaxis Ragel:

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

y tiene la siguiente máquina de estados:

Mientras la intersección vacía:

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

parece esto:

Así que si falla todo, 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 2

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

Si limitar la cuestión a expresiones puras regulares (no hay referencias hacia atrás, búsqueda hacia delante, de búsqueda hacia atrás, u otras características que permitan el reconocimiento de contexto libre o más complejo idiomas), la pregunta es, al menos, decidible. Los idiomas regulares se cierran bajo la intersección , y hay un algoritmo que toma las dos expresiones regulares como entradas y produce, en un tiempo finito, un DFA que reconoce la intersección.

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

Por desgracia, hay una explosión posiblemente exponencial cuando se convierte la primera NFA a un DFA, por lo que el problema se vuelve rápidamente inviable en la práctica como el tamaño de las expresiones de entrada crece.

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

Answer 3

Sí, creo que esto es solucionable: en lugar de pensar en expresiones regulares como cadenas coincidentes, también puede pensar que están generando cadenas. 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 las expresiones regulares R y T, podríamos intentar hacer coincidir T contra [R]. Eso es [R] coincide con T iff 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 expresión regular normal coincida con intente 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á 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 siguientes estados simultáneamente.

Answer 4

Otro enfoque sería aprovechar el Perl Regexp::Optimizer de 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 Ron Savage's Regexp::Assemble podría ser aún más útil. Permite ensamblar un número arbitrario de expresiones regulares en una única 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-sabores.}