Crea un programa que ingresa una expresión regular y emite cadenas que satisfacen esa expresión regular

Question

Creo que el título resume con precisión mi pregunta, pero solo para elaborar un poco.

En lugar de usar una expresión regular para verificar las propiedades de las cadenas existentes, me gustaría utilizar la expresión regular como una forma de generar cadenas que tienen ciertas propiedades.

Nota: La función no tiene que generar cada cadena que satisface la expresión regular (causa que sería un número infinito de cadena para una gran cantidad de expresiones regulares). Solo una muestra de las muchas cadenas válidas es suficiente.

¿Qué tan factible es algo como esto? Si la solución es demasiado complicada/grande, estoy contento con una discusión/esquema general. Además, estoy interesado en cualquier programa o biblioteca existente (.NET) que haga esto.

Answer 1

Bueno, una expresión regular es convertible a DFA que se puede considerar como un gráfico. Para generar una cadena con este gráfico de DFA, encontrará una ruta desde un estado de inicio hasta uno final. Tendría que pensar en cómo desea manejar los ciclos (¿Tal vez recorrer cada ciclo al menos una vez para obtener una muestra? N veces?), Pero no veo por qué no funcionaría.

Answer 2

La forma más fácil de implementar, pero definitivamente la mayoría del enfoque intensivo de tiempo de CPU sería simplemente la fuerza bruta. Configure una tabla de caracteres con los caracteres que su cadena debe contener y luego simplemente genere secuencias secuencialmente y haga una Regex.IsMatch en ellas.

Answer 3

Yo, personalmente, creo que este es el santo grial de reg-ex. Si pudieras implementar esto, incluso solo 3/4 trabajando, no tengo dudas de que serías rico en unos 5 minutos.

Bromas aparte, no estoy seguro de que lo que realmente está persiguiendo es factible. Reg-Ex es un lenguaje muy abierto y flexible que le da a la computadora suficiente información de muestra para encontrar de manera precisa y precisa lo que necesita, probablemente no sea factible.

Si se demuestra que estoy equivocado, le deseo felicitaciones a ese desarrollador.

Para ver esto desde una perspectiva diferente, esto es casi (no del todo) como dar salida a una computadora y, basándose en eso, escribir un programa para usted. Esto está un poco pasado de la raya, pero de alguna manera ilustra mi punto.

Answer 4

Esto se puede hacer por traversing the DFA (incluye pseudocódigo) o bien a pie de árbol sintaxis abstracta de la expresión regular directa o convertirse al NFA en primer lugar, según lo explicado por Doug McIlroy: paper y Haskell code. (Encuentra que el enfoque de NFA es más rápido, pero no lo comparó con el DFA.)

Todos estos funcionan en expresiones regulares sin referencias retrospectivas, es decir, expresiones regulares 'reales' en lugar de Perl regular expresiones. Para manejar las características adicionales de Perl sería más fácil agregar un postfiltro.

Agregado:code for this en Python, por Peter Norvig y yo.

Answer 5

Este utility on UtilityMill invertirá algunos regexens simples. Se basa en this example from the pyparsing wiki.Los casos de prueba para este programa son:

[A-EA] 
[A-D]* 
[A-D]{3} 
X[A-C]{3}Y 
X[A-C]{3}\(
X\d 
foobar\d\d 
foobar{2} 
foobar{2,9} 
fooba[rz]{2} 
(foobar){2} 
([01]\d)|(2[0-5]) 
([01]\d\d)|(2[0-4]\d)|(25[0-5]) 
[A-C]{1,2} 
[A-C]{0,3} 
[A-C]\s[A-C]\s[A-C] 
[A-C]\s?[A-C][A-C] 
[A-C]\s([A-C][A-C]) 
[A-C]\s([A-C][A-C])? 
[A-C]{2}\d{2} 
@|TH[12] 
@(@|TH[12])? 
@(@|TH[12]|AL[12]|SP[123]|TB(1[0-9]?|20?|[3-9]))? 
@(@|TH[12]|AL[12]|SP[123]|TB(1[0-9]?|20?|[3-9])|OH(1[0-9]?|2[0-9]?|30?|[4-9]))? 
(([ECMP]|HA|AK)[SD]|HS)T 
[A-CV]{2} 
A[cglmrstu]|B[aehikr]?|C[adeflmorsu]?|D[bsy]|E[rsu]|F[emr]?|G[ade]|H[efgos]?|I[nr]?|Kr?|L[airu]|M[dgnot]|N[abdeiop]?|Os?|P[abdmortu]?|R[abefghnu]|S[bcegimnr]?|T[abcehilm]|Uu[bhopqst]|U|V|W|Xe|Yb?|Z[nr] 
(a|b)|(x|y) 
(a|b) (x|y) 

Answer 6

Dado que es trivialmente posible escribir una expresión regular que coincide sin condiciones posibles, y creo que también es posible escribir una expresión regular para los que el cálculo requiere una cadena coincidente una búsqueda exhaustiva de posibles cadenas de todas las longitudes, es probable que necesite un límite superior al solicitar una respuesta.