Comment générer des chaînes aléatoires qui correspondent à une expression rationnelle donnée?

Question

Dupliquer:

  

chaîne aléatoire qui correspond à une regexp

Non, ce n'est pas. Je suis à la recherche d'une méthode facile et universelle, que je pouvais mettre en œuvre. C'est beaucoup plus difficile que les mots de passe de façon aléatoire générer.

---

Je veux créer une application qui prend une expression régulière, et montre 10 chaînes générées au hasard qui correspondent à cette expression. Il est censé aider les gens à mieux comprendre leurs expressions régulières, et de décider à savoir si elles sont suffisamment en sécurité à des fins de validation. Est-ce que quelqu'un sait d'une façon facile de le faire?

Une solution évidente serait d'écrire (ou voler) un analyseur de regexp, mais qui semble vraiment sur ma tête.

Je le répète, je suis à la recherche d'un facile et universel façon de le faire.

Modifier approche de la force Brute hors de question. En supposant que les chaînes aléatoires serait juste [a-z0-9]{10} et 1 million d'itérations par seconde, il faudrait 65 ans pour itérer cuvette l'espace de toutes les chaînes 10-char.

Answer 1

Parse votre expression régulière dans un href="http://en.wikipedia.org/wiki/Deterministic_finite_state_machine" DFA , puis parcourir votre DFA au hasard jusqu'à ce que vous vous retrouvez dans un état d'accepter, délivrer en sortie un caractère pour chaque transition. Chaque promenade donnera une nouvelle chaîne qui correspond à l'expression.

Cela ne fonctionne pas pour les expressions « ordinaires » qui ne sont pas vraiment régulière, bien que, comme les expressions avec des références arrières. Cela dépend de ce genre d'expression que vous êtes après.

Answer 2

Jetez un oeil à Perl String :: aléatoire .

Answer 3

Une solution plutôt laid qui peuvent ou peuvent ne pas être pratique consiste à tirer parti d'une option de diagnostic regex existant. Certaines bibliothèques regex ont la possibilité de savoir où l'expression régulière n'a pas réussi à égaler. Dans ce cas, vous peut utiliser ce qui est en effet une forme de force brute, mais en utilisant un caractère à la fois et essayer d'obtenir plus de chaînes (et plus en correspondance) jusqu'à ce que vous avez obtenu un match complet. Ceci est une solution très laid. Cependant, contrairement à une solution standard de force brute, il échec sur une chaîne comme ab également vous dire s'il existe une chaîne ab. * Qui correspondra (sinon, arrêtez-vous et essayer ca. Dans ce cas, essayez une chaîne plus longue). Ceci est probablement pas réalisable avec toutes les bibliothèques regex.

Sur le côté positif, ce genre de solution est probablement assez cool d'un point de vue pédagogique. Dans la pratique, il est probablement similaire en effet à une solution DFA, mais sans l'obligation de penser à dfas.

Notez que vous ne voulez pas utiliser des chaînes aléatoires avec cette technique. Cependant, vous pouvez utiliser des caractères aléatoires pour commencer si vous garder une trace de ce que vous avez testé dans un arbre, donc l'effet est le même.

Answer 4

si vos critères sont seulement que votre méthode est facile et universel, alors il n'y a pas rien de plus facile ou plus universel que la force brutale. :)

for (i = 0; i < 10; ++i) {
    do {
        var str = generateRandomString();
    } while (!myRegex.match(str));
    myListOfGoodStrings.push(str);
}

Bien sûr, cela est une façon très stupide de faire des choses et la plupart du temps a été conçu comme une blague.

Je pense que le mieux serait d'essayer d'écrire votre propre analyseur très basique, enseigner seulement les choses que vous vous attendez à rencontrer (par exemple: la lettre et le nombre varie, en répétant / caractères en option ... ne vous inquiétez pas A propos de look-behinds etc)

Answer 5

Le critère d'universalité est impossible. Compte tenu de l'expression régulière « ^ Pour être, ou ne pas être - c'est la question suivante: $ » , il n'y aura pas dix chaînes aléatoires uniques qui correspondent.

Pour les cas non dégénéré:

lien de Moonshadow à cordes :: Random Perl est la réponse. Un programme Perl qui lit un RegEx de stdin et écrit la sortie de dix invocations de cordes :: aléatoire est trivial à stdout. Compiler soit un exe Windows ou Unix avec Perl2Exe et l'appeler à partir de PHP, Python, ou quel que soit.

Voir aussi générateur de texte aléatoire basé sur regex