c++ - solo - ¿Cómo puedes detectar si dos expresiones regulares se superponen en las cadenas que pueden coincidir?
validar correo electronico en asp.net c# (3)
En teoría, el problema que usted describe es imposible.
En la práctica, si tiene un número manejable de expresiones regulares que usan un subconjunto limitado o de sintaxis de expresiones regulares, y / o una selección limitada de cadenas que se pueden usar para compararlas con el contenedor de expresiones regulares, es posible que pueda resolverlo. .
Suponiendo que no esté intentando resolver el caso general abstracto, podría haber algo que pueda hacer para resolver una aplicación práctica. Tal vez si proporcionara una muestra representativa de las expresiones regulares y describiera las cadenas con las que se correspondería, podría crearse una heurística para resolver el problema.
Tengo un contenedor de expresiones regulares. Me gustaría analizarlos para determinar si es posible generar una cadena que coincida con más de 1 de ellos. Aparte de escribir mi propio motor de expresiones regulares con este caso de uso en mente, ¿hay una manera fácil en C ++ o Python para resolver este problema?
No hay manera fácil.
Mientras sus expresiones regulares solo utilicen características estándar (creo que Perl le permite incrustar código arbitrario en la coincidencia), puede producir de cada una un autómata de estado finito no determinista (NFA) que codifique de forma compacta todas las cadenas que el RE coincide.
Dado cualquier par de NFA, es decidible si su intersección está vacía. Si la intersección no está vacía, entonces algunas cadenas coinciden con ambos RE en el par (y viceversa).
La prueba de decidibilidad estándar es determinarlos en DFA s primero, y luego construir un nuevo DFA cuyos estados son pares de los dos estados de DFA, y cuyos estados finales son exactamente aquellos en los que ambos estados del par son definitivos en su DFA original . Alternativamente, si ya ha mostrado cómo calcular el complemento de una NFA, entonces puede (el estilo de ley de DeMorgan) obtener la intersección por complement(union(complement(A),complement(B))) .
Desafortunadamente, NFA -> DFA implica una explosión de tamaño potencialmente exponencial (porque los estados en la DFA son subconjuntos de estados en la NFA). De Wikipedia :
Algunas clases de lenguajes regulares solo pueden ser descritas por autómatas finitos deterministas cuyo tamaño crece exponencialmente en el tamaño de las expresiones regulares equivalentes más cortas. El ejemplo estándar son los idiomas L_k que consisten en todas las cadenas sobre el alfabeto {a, b} cuya quinta-última letra es igual a a.
Por cierto, definitivamente deberías usar OpenFST . Puede crear autómatas como archivos de texto y jugar con operaciones como minimización, intersección, etc. para ver cuán eficientes son para su problema. Ya existe el código abierto regexp-> nfa-> compiladores dfa (recuerdo un módulo de Perl); modifica uno para generar archivos de autómatas OpenFST y jugar.
Afortunadamente, es posible evitar la explosión de un subconjunto de estados e intersectar dos NFA directamente utilizando la misma construcción que para DFA:
si A ->a B (en una NFA, puede pasar del estado A al B dando como resultado la letra ''a'')
y X ->a Y (en la otra NFA)
luego (A,X) ->a (B,Y) en la intersección
(C,Z) es final si C es final en una NFA y Z es final en la otra.
Para iniciar el proceso, comience en el par de estados de inicio para las dos NFA, por ejemplo (A,X) ; este es el estado de inicio de la intersección-NFA. Cada vez que visite un estado por primera vez, genere un arco según la regla anterior para cada par de arcos que salen de los dos estados, y luego visite todos los (nuevos) estados a los que llegan esos arcos. Almacenarías el hecho de que expandiste los arcos de un estado (por ejemplo, en una tabla hash) y terminarás explorando todos los estados accesibles desde el principio.
Si permites las transiciones de épsilon (que no generan una letra), está bien:
si A ->epsilon B en la primera NFA, entonces para cada estado (A,Y) que alcance, agregue el arco (A,Y) ->epsilon (B,Y) y similar para épsilones en la NFA de la segunda posición.
Las transiciones de Epsilon son útiles (pero no necesarias) para tomar la unión de dos NFA cuando se traduce una expresión regular a una NFA; siempre que tenga alternancia regexp1|regexp2|regexp3 , tome la unión: una NFA cuyo estado de inicio tiene una transición de épsilon a cada una de las NFA que representan las expresiones regulares en la alternancia.
Decidir el vacío para un NFA es fácil: si alguna vez alcanza un estado final al hacer una búsqueda en profundidad desde el estado inicial, no está vacío.
Esta intersección NFA es similar a la composición del transductor de estado finito (un transductor es un NFA que emite pares de símbolos, que se concatenan por pares para coincidir con una cadena de entrada y salida, o para transformar una entrada dada en una salida).
Este inversor de expresiones regulares (escrito mediante pyparsing) funciona con un subconjunto limitado de sintaxis de re (no * o + permitido, por ejemplo); puede invertir dos re en dos conjuntos y luego buscar una intersección de conjuntos.