Chaîne aléatoire qui correspond à une expression rationnelle

Question

Comment feriez-vous pour créer une chaîne alphanumérique aléatoire qui corresponde à une certaine expression régulière?

Ceci est spécifiquement destiné à la création de mots de passe initiaux répondant aux exigences de mot de passe habituelles.

Answer 1

Utilisez la réponse acceptée sur Génération de mots de passe aléatoires jusqu'à ce qu'ils correspondent à votre expression rationnelle.

Answer 2

Welp, juste en train de méditer, mais la question générale de générer des entrées aléatoires qui correspondent à une regex me semble faisable pour une définition suffisamment assouplie de random et une définition suffisamment étroite pour regex. Je pense à la définition formelle classique, qui autorise uniquement les caractères () | * et les caractères alphabétiques.

Les expressions régulières peuvent être mappées vers des machines formelles appelées automates finis . Une telle machine est un graphe dirigé avec un nœud particulier appelé état final, un nœud appelé état initial et une lettre de l'alphabet sur chaque bord. Un mot est accepté par l'expression rationnelle s'il est possible de commencer à l'état initial, de traverser une arête étiquetée avec chaque caractère dans le graphique et de se terminer à l'état final.

On pourrait construire le graphique, puis commencer à l'état final et parcourir les arêtes aléatoires en arrière, en gardant une trace du chemin. Dans une construction standard, chaque nœud du graphique est accessible à partir de l'état initial. Vous n'avez donc pas à vous soucier de faire des erreurs irrécupérables et de devoir revenir en arrière. Si vous atteignez l'état initial, arrêtez-vous et lisez le chemin à suivre. C'est votre match pour la regex.

Cependant, il n’ya aucune garantie particulière quant au moment où vous atteindrez l’état initial ou si vous atteindrez cet état initial. Il faudrait déterminer dans quel sens les chaînes générées sont "aléatoires" et dans quel sens vous souhaitez un élément aléatoire de la langue.

Peut-être que c'est un point de départ pour réfléchir au problème, cependant!

Maintenant que je l'ai écrit, il me semble qu'il serait peut-être plus simple de résoudre plusieurs fois les choix pour simplifier le motif des expressions rationnelles jusqu'à ce qu'il ne reste qu'une simple chaîne. Recherchez le premier caractère non alphabétique du motif. S'il s'agit d'un *, répliquez l'élément précédent un certain nombre de fois et supprimez le *. S'il s'agit d'un |, choisissez lequel des éléments OR'd conserver et supprimez le reste. Pour un paren gauche, faites la même chose, mais en regardant le personnage qui suit le paren droit correspondant. C’est probablement plus facile si vous analysez l’expression rationnelle dans une représentation arborescente qui facilite la gestion de la structure de regroupement des paren.

Pour la personne qui craignait que le fait de décider si une expression rationnelle correspond réellement à quelque chose équivaut au problème de halte: non, les langues ordinaires se comportent assez bien. Vous pouvez savoir si deux expressions rationnelles décrivent le même ensemble de chaînes acceptées. Généralement, vous créez la machine ci-dessus, puis suivez un algorithme pour produire une machine équivalente canonique minimale. Faites cela pour deux expressions rationnelles, puis vérifiez si les machines minimales résultantes sont équivalentes, ce qui est simple.

Answer 3

String :: Aléatoire dans Perl générera une chaîne aléatoire d'un sous-ensemble d'expressions régulières:

#!/usr/bin/perl

use strict;
use warnings;

use String::Random qw/random_regex/;

print random_regex('[A-Za-z]{3}[0-9][A-Z]{2}[!@#$%^&*]'), "\n";

Answer 4

Si vous rencontrez un problème spécifique, vous avez probablement une expression régulière spécifique en tête. Je prendrais cette expression régulière, trouverais ce que cela signifiait en termes humains simples et travaillerais à partir de là.

Je soupçonne qu'il est possible de créer un générateur de correspondance aléatoire regex général, mais cela demandera probablement beaucoup plus de travail que de traiter un cas spécifique, même si ce cas change quelques fois par an.

(En fait, il peut ne pas être possible de générer des correspondances aléatoires au sens le plus général - j’ai un vague souvenir que le problème de "toute chaîne de caractères correspond-il à cette expression régulière" est-il le problème d’arrêt dissimulé? langue regex vous avez peut-être plus de chance.)

Answer 5

J'ai écrit Persil , composé d'un Lexer et d'un générateur.

• Lexer permet de convertir une chaîne de type expression régulière en une séquence de jetons.
• Generator utilise ces jetons pour produire un nombre défini de codes.

$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[A-Z]{10}[0-9]{2}', 100);

L'exemple ci-dessus générera un tableau contenant 100 codes, chacun précédé de "FOO", suivi de 10 caractères de "ABCDEFGHKMNOPRSTUVWXYZ23456789". botte de foin et 2 chiffres de " 0123456789 " meule de foin.

Answer 6

Cette bibliothèque PHP semble prometteuse: ReverseRegex

Comme tous ceux-ci, il ne gère qu'un sous-ensemble d'expressions régulières, mais il peut effectuer des tâches assez complexes comme les codes postaux britanniques:

([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)

Sorties

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

Answer 7

Vous devez écrire un générateur de chaîne capable d'analyser des expressions régulières et de générer des membres aléatoires de plages de caractères pour des longueurs aléatoires, etc.

Il serait beaucoup plus facile d'écrire un générateur de mot de passe aléatoire avec certaines règles (commence par une lettre minuscule, a au moins une ponctuation, une majuscule et un chiffre, au moins 6 caractères, etc.), puis écrivez votre expression rationnelle de manière à ce que Les mots de passe créés avec ces règles sont valides.

Answer 8

En supposant que vous ayez à la fois une longueur minimale et une exigence de 3 sur 4 * (ou similaire), je serais simplement enclin à utiliser un générateur de mot de passe décent.

J'en ai déjà construit un couple (à la fois sur le Web et en ligne de commande) et je n'ai jamais eu à ignorer plus d'une chaîne générée pour passer la règle des 3 sur 4.

• 3 sur 4: doit avoir au moins trois des caractéristiques suivantes: minuscule, majuscule, nombre, symbole

Answer 9

C'est possible (par exemple, le module Haskell regexp dispose d'une suite de tests qui génère automatiquement des chaînes qui doivent correspondre à certaines expressions rationnelles).

Toutefois, pour une tâche simple, il vaudrait peut-être mieux prendre un simple générateur de mot de passe et filtrer sa sortie avec votre expression rationnelle.

Answer 10

Pourquoi ne pas utiliser l'expression rationnelle à l'envers? Un exemple simple: si votre expression rationnelle est

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

alors vous savez que vous avez besoin de 6 lettres a-z ou A-Z, alors générez-les. Bien sûr, cela peut devenir plus sophistiqué et, selon vos besoins, vous pouvez finir par écrire en sens inverse un analyseur d’expression rationnelle complet, mais vous pouvez arrêter d’ajouter des fonctionnalités lorsque vous avez satisfait à vos besoins.