Expresiones regulares generativas

Normalmente en nuestro trabajo utilizamos expresiones regulares en captura o coincide con operaciones.Expresiones regulares generativas

Sin embargo, las expresiones regulares se pueden utilizar, al menos manualmente, para generar sentencias legales que coincidan con la expresión regular. Por supuesto, algunas expresiones regulares pueden coincidir con oraciones infinitamente largas, por ejemplo, la expresión .+.

Tengo un problema que podría resolverse mediante el uso de un algoritmo de generación de oraciones de expresión regular.

En pseudocódigo, que operaría algo como esto:

re = generate("foo(bar|baz)?", max_match = 100); #Don't give me more than 100 results 
assert re == ("foobar", "foobaz", "foo");

Qué algoritmo llevaría a cabo esto por mí?

Fuente

2010-11-17 Paul Nathan

Sé cómo hacer esto fácilmente con una cadena de búsqueda dada y un patrón determinado. ¿Es eso lo suficientemente bueno? Si es así, dímelo y te mostraré. Eres muy inteligente para darle un límite superior, también. Yo puedo hacer eso. Pero hay infinitas cadenas de lo contrario, así que no sé cómo lo harías, aunque tal vez se aplique la "prueba de fuzz" de Bart Miller, en la que genera entradas aleatorias para alimentar programas para ver si eso hace que fallen espectacularmente. – tchrist

@tchrist: Puedo generar basura al azar bastante bien. Me gustaría hacer algo como lo muestra el ejemplo anterior. Mi rummaging muestra que el módulo de Perl String :: Random es muy parecido a Xeger, pero no admite (|). Xeger solo anda por el autómata que describe la expresión regular. Ese parece ser un caso común. Leí que Haskell tiene un módulo de expresiones regulares que genera, estoy cavando en ese cajero automático. –

No se pudo encontrar el módulo de expresiones regulares de haskell. : -/ –

Eche un vistazo a Xeger (Google Code).

El sistema de equipo de Visual Studio parece tener un inverse regex generator, también, pero no parece que el algoritmo sea de código abierto.

Fuente

2010-11-17 20:21:48

Nombre interesante. – Gumbo

@Gumbo HA !!! eso pasó justo a mi lado. – Keng

Hmm. Eso es un generador aleatorio.Me gustaría * algún tipo de confianza en que, para un lenguaje finito que describe la expresión regular, puedo enumerar todas las palabras en el lenguaje (sí, podría generar algún tipo de medida estadística, que * podría * funcionar, pero estoy no lo suficientemente bueno en estadísticas avanzadas para tener confianza en mi intervalo de confianza ...). –

Microsoft tiene una gratis a base de SMT (MSRL-licencia) función "Rex" para esto: http://research.microsoft.com/en-us/downloads/7f1d87be-f6d9-495d-a699-f12599cea030/

En la sección Introducción de la "Rex: Simbólico Explorador de expresiones regulares" de papel:

Traducimos (extendimos) expresiones regulares o expresiones regulares [5] en una representación simbólica de autómatas finitos llamados SFA. En una SFA, los movimientos están etiquetados por fórmulas que representan conjuntos de caracteres en lugar de caracteres individuales. Un SFA A se traduce en un conjunto de axiomas (recursivos) que describen la condición de aceptación para las cadenas aceptadas por A y se basan en la representación de cadenas como listas.

Como el solucionador SMT puede generar todas las soluciones posibles dentro de cierto tamaño, esto puede ser similar a lo que está buscando.

En un frente más estadístico y menos formal, la expresión regular :: módulo de CPAN Genex puede funcionar tan bien: http://search.cpan.org/dist/Regexp-Genex/

Se puede utilizar con algo como esto:

#!/usr/bin/env perl 
use Regexp::Genex ':all'; 
my $hits = 100; 
my $re = qr/[a-z](123|456)/; 
local $Regexp::Genex::DEFAULT_LEN = length $re; 
my %seen; 
while ((time - $^T) < 2) { 
    @seen{strings($re)} =(); 
    $Regexp::Genex::DEFAULT_LEN++; 
} 
print "$_\n" for (sort %seen)[0..$hits-1];

ajustar el tiempo y tamaño de muestra según sea necesario. ¡Espero que esto ayude!

Fuente

2011-05-21 19:30:34 audreyt

Acabo de implementar otra herramienta de "salida todas las soluciones posibles" en https://github.com/audreyt/regex-genex con el solucionador SMT yices2. Puede ser útil también. :-) – audreyt

Expresiones regulares generativas

Respuesta

Cuestiones relacionadas