Cadena aleatoria que coincide con una expresión regular

¿Cómo haría para crear una cadena alfanumérica aleatoria que coincida con una determinada expresión regular?

Esto es específicamente para crear contraseñas iniciales que cumplan con los requisitos de contraseña habituales.

Welp, solo reflexionando, pero la pregunta general de generar entradas aleatorias que coincidan con una expresión regular me resulta factible para una definición suficientemente relajada de lo aleatorio y una definición suficientemente ajustada de expresiones regulares. Estoy pensando en la definición formal clásica, que permite solo () | * y caracteres del alfabeto.

Las expresiones regulares se pueden asignar a máquinas formales llamadas autómatas finitos . Tal máquina es un gráfico dirigido con un nodo particular llamado estado final, un nodo llamado estado inicial y una letra del alfabeto en cada borde. El regex acepta una palabra si es posible comenzar en el estado inicial y atravesar un borde etiquetado con cada carácter a través del gráfico y finalizar en el estado final.

Uno podría construir el gráfico, luego comenzar en el estado final y recorrer los bordes al azar hacia atrás, manteniendo un registro de la ruta. En una construcción estándar, cada nodo del gráfico es accesible desde el estado inicial, por lo que no debe preocuparse por cometer errores irrecuperables y tener que retroceder. Si alcanza el estado inicial, deténgase y lea el camino en el futuro. Ese es tu partido para la expresión regular.

Sin embargo, no hay una garantía particular sobre cuándo o si alcanzará el estado inicial. Uno tendría que descubrir en qué sentido las cadenas generadas son “aleatorias”, y en qué sentido está esperando un elemento aleatorio del idioma en primer lugar.

Sin embargo, tal vez ese sea un punto de partida para pensar sobre el problema.

Ahora que lo he escrito, me parece que podría ser más simple resolver repetidamente las opciones para simplificar el patrón de expresiones regulares hasta que se quede con una cadena simple. Encuentre el primer carácter no alfabético en el patrón. Si es un *, repita el elemento anterior algunas veces y elimine el *. Si es un |, elija cuál de los elementos OR para conservar y eliminar el rest. Para un paréntesis izquierdo, haz lo mismo, pero mirando al personaje que sigue el derecho de parear paren. Esto es probablemente más fácil si analiza primero la expresión regular en una representación en árbol, lo que hace que la estructura de agrupamiento de pares sea más fácil de usar.

Para la persona que le preocupa que decidir si una expresión regular realmente concuerda con algo es equivalente al problema de detención: No, los idiomas regulares se comportan bastante bien. Puede decir si dos expresiones regulares describen el mismo conjunto de cadenas aceptadas. Básicamente, crea la máquina de arriba, luego sigue un algoritmo para producir una máquina equivalente mínima canónica. Haga eso para dos expresiones regulares, luego verifique si las máquinas mínimas resultantes son equivalentes, lo cual es sencillo.

String :: Random en Perl generará una cadena aleatoria a partir de un subconjunto de expresiones regulares:

#!/usr/bin/perl use strict; use warnings; use String::Random qw/random_regex/; print random_regex('[A-Za-z]{3}[0-9][AZ]{2}[!@#$%^&*]'), "\n"; 

Si tienes un problema específico, probablemente tengas una expresión regular específica en mente. Tomaría esa expresión regular, resolveré lo que significa en términos humanos simples, y trabajaré desde allí.

Sospecho que es posible crear un generador de concordancia aleatoria general de expresiones regulares, pero es probable que sea mucho más trabajo que solo manejar un caso específico, incluso si ese caso cambia algunas veces al año.

(En realidad, puede que no sea posible generar coincidencias aleatorias en el sentido más general: tengo una vaga memoria de que el problema de “¿coincide alguna cadena con esta expresión regular?” Es el problema de detención disfrazado. Con un lenguaje de expresiones regulares muy reducido puede que tengas más suerte).

Escribí Parsley , que consta de un Lexer y un generador.

  • Lexer es para convertir una cadena regular similar a una expresión en una secuencia de tokens.
  • Generator está utilizando estos tokens para producir una cantidad definida de códigos.
 $generator = new \Gajus\Parsley\Generator(); /** * Generate a set of random codes based on Parsley pattern. * Codes are guaranteed to be unique within the set. * * @param string $pattern Parsley pattern. * @param int $amount Number of codes to generate. * @param int $safeguard Number of additional codes generated in case there are duplicates that need to be replaced. * @return array */ $codes = $generator->generateFromPattern('FOO[AZ]{10}[0-9]{2}', 100); 

El ejemplo anterior generará una matriz que contiene 100 códigos, cada uno con el prefijo “FOO”, seguido de 10 caracteres de “ABCDEFGHKMNOPRSTUVWXYZ23456789” haystack y 2 números del “0123456789” haystack.

Esta biblioteca PHP parece prometedora: ReverseRegex

Al igual que todos estos, solo maneja un subconjunto de expresiones regulares pero puede hacer cosas bastante complejas como los códigos postales del Reino Unido:

 ([A-PR-UWYZ]([0-9]([0-9]|[A-HJKSTUW])?|[A-HK-Y][0-9]([0-9]|[ABEHMNPRVWXY])?) ?[0-9][ABD-HJLNP-UW-Z]{2}|GIR0AA) 

Salidas

 D43WF B6 6SB MP445FR P9 7EX N9 2DH GQ28 4UL NH1 2SL KY2 9LS TE4Y 0AP 

Debería escribir un generador de cadenas que pueda analizar expresiones regulares y generar miembros aleatorios de rangos de caracteres para longitudes aleatorias, etc.

Mucho más fácil sería escribir un generador de contraseñas aleatorias con ciertas reglas (comienza con una letra minúscula, tiene al menos una puntuación, letra mayúscula y número, al menos 6 caracteres, etc.) y luego escribir su expresión regular para que cualquier contraseña creada con dichas reglas son validas

Suponiendo que tienes un requisito de longitud mínima y 3 de 4 * (o similar), me inclinaría a utilizar un generador de contraseñas decente.

Construí un par en el pasado (tanto basado en web como en línea de comandos), y nunca tuve que saltar más de una cadena generada para pasar la regla 3 de 4.

  • 3-de-4: debe tener al menos tres de las siguientes características: minúsculas, mayúsculas, números, símbolos

Es posible (por ejemplo, el módulo de expresiones regulares de Haskell tiene un conjunto de pruebas que genera cadenas automáticamente que deben coincidir con ciertas expresiones regulares).

Sin embargo, para una tarea simple a mano, sería mejor tomar un generador de contraseñas simple y filtrar su salida con su expresión regular.

Use la respuesta aceptada en Generando contraseñas aleatorias hasta que coincida con su expresión regular.

¿Por qué no funciona la regexp al revés? Un simple ejemplo: si tu expresión regular es

 /[a-zA-Z]{6}/ 

entonces sabes que necesitas 6 letras az o AZ, así que grábalas. Esto puede ser más elegante, por supuesto y, dependiendo de sus necesidades, puede terminar escribiendo de forma inversa un analizador de expresiones regulares completo, pero puede dejar de agregar características cuando haya cumplido con sus necesidades.