Comment générer au hasard des chaînes qui correspondent à une expression régulière?

Double:

Chaîne de caractères aléatoires qui correspond à une expression régulière

Non, il n'est pas. Je suis à la recherche d'un moyen facile et universelle de la méthode, celle que j'ai pu le mettre en œuvre. C'est beaucoup plus difficile que génère aléatoirement des mots de passe.

Je veux créer une application qui prend une expression régulière, et montre 10 généré de façon aléatoire chaînes qui correspondent à l'expression. Il est censé aider les gens à mieux comprendre leurs expressions régulières, et de décider à savoir si elles sont suffisamment sécurisé pour des fins de validation. Quelqu'un sait-il d'un moyen facile de le faire?

Une solution évidente serait d'écrire (ou voler) une regexp parser, mais qui semble vraiment au dessus de ma tête.

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

Edit: approche par force Brute est 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 la traversée de l'espace de tous les 10 caractères les chaînes de caractères.

  • Je ne pense pas qu'il va y avoir un moyen facile de le faire... peut-être le mechanical turk? 🙂
  • Avez-vous un particulier regex dans l'esprit, ou êtes-vous après une solution générale pour toutes les regex variante? Parce que vous n'allez pas en trouver un qui fonctionne pour Perl ainsi que .NET, sauf si vous vous limitez à vraiment des expressions régulières sans aucune extension.
  • Eh bien, je voudrais une solution générale pour une seule variante, notamment celui que j'utilise, les Expressions Régulières de Perl implémentation en PHP.
  • En général, le problème est #P-dur. researchgate.net/publication/...
  • Voir aussi étant Donné une expression régulière, comment pourrais-je générer toutes les chaînes qui correspondent à elle?
InformationsquelleAutor Michał Tatarynowicz | 2009-04-14
  1. 24

    Analyser votre expression régulière dans une DFA, puis traverser votre DFA au hasard jusqu'à ce que vous vous retrouvez dans un état acceptant, la sortie d'un personnage pour chaque transition. Chaque promenade se donner une nouvelle chaîne qui correspond à l'expression.

    Cela ne fonctionne pas "régulière" des expressions qui ne sont pas très réguliers, tels que les expressions avec des références arrières. Ça dépend de quel genre d'expression que vous êtes après.

    • Me ramène à la Théorie de Calcul. jusqu'vote!
    • E: automate fini Déterministe
    • E: Automates Finis Déterministes: en.wikipedia.org/wiki/Deterministic_finite_state_machine Fondamentalement, c'est la mise en œuvre d'une expression régulière. Lorsque vous compilez une regex, un DFA est le résultat.
    • E., automates finis déterministes?
    • compte tenu de l'arbitraire d'un regexp la résultante de l'ifd peut être très grande, donc parcourir simplement dfa au hasard peuvent se retrouver dans une boucle...
    • Ce n'est pas facile du tout 🙂
    • Si vous vous retrouvez dans une non-acceptation de la branche de la TFD à partir de laquelle aucun des transitions fin en acceptant les états, alors vous aurez à recommencer. Évidemment, si une telle branche, il devra être coupé de l'ensemble des etats en quelque sorte. Il devrait être assez simple à utiliser des algorithmes de graphes pour les trouver.
    • C'est la façon dont les expressions régulières de travail. Même si vous trouvez une bibliothèque qui le fait pour vous, c'est probablement la façon dont il fonctionne. C'est exactement ce dont vous avez besoin: de parcourir la structure de la regex représente, mais à l'inverse, la production d'un string plutôt que de consommer un.
    • absolument, j'ai été seulement mettre en garde à propos de ce problème. Votre réponse est L'Universelle :)))
    • Voir aussi: chaînes de markov
    • Notez qu'il est également possible de retrouver dans un valide, boucle infinie. Un exemple classique serait à la recherche d'un match pour l' .* . Il va commencer par la génération d'un, puis de aa, puis aaa, etc. Évidemment, vous aurez envie d'essayer de générer le plus court des chaînes d'abord pour éviter ce genre de chose.
    • c'est pourquoi je suggère d'arrêter une fois que vous atteignez un état acceptant, et de tailler les branches qui ne peuvent pas arriver à accepter les états.
    • Mon idée serait de simplement traiter .* comme un nombre aléatoire de caractères aléatoires. Il devrait y avoir certaines limites bien sûr (comme * générer à plus de 1000 caractères.)
    • ou vous pouvez générer un NFA au lieu d'un DFA, avec (x) probabilité de répéter à chaque * nœud, et (1-x) probabilité de continuation par la regex.

    InformationsquelleAutor Welbog
  2. 6

    Prendre un coup d'oeil à Perl String::Aléatoire.

    • Je ne pense pas que vous savez quelque chose de similaire pour PHP?
    • Écrire en Perl, le compiler avec certains Perl-à-exécutable de l'outil, puis de l'appeler à partir de PHP.
    • Le Perl2Exe page d'accueil: indigostar.com/perl2exe.htm
    • Excellente idée, tlholaday, merci 🙂
    • L'internet est une série de tubes.
    • Ouais, je pense que c'est juste plus facile à déployer si vous utilisez une seule langue 🙂
    • Perl String::Random prend uniquement en charge un petit sous-ensemble de regexp, donc je vais avoir à chercher quelque chose de mieux.
    • Essayez de cette bibliothèque PHP. Semble à l'appui de plus de regex formats String::Random.
    • Et un autre PHP lib

    InformationsquelleAutor moonshadow
  3. 0

    Plutôt laid solution qui peut ou peut ne pas être pratique est de tirer parti de l'existant regex option diagnostics. Certains regex bibliothèques ont la capacité de comprendre d'où l'expression régulière n'ont pas pu égaler. Dans ce cas, vous pourrait utiliser ce qui est en effet une forme de force brute, mais en utilisant les caractères un à un et essayer d'obtenir plus de temps (et de loin-matching) des chaînes jusqu'à ce que vous avez obtenu un plein match. C'est une très laid solution. Cependant, contrairement à une norme de la force brute de la solution, il l'échec sur la chaîne ab sera aussi vous dire qu'il existe une chaîne ab.* qui va correspondre (si non, arrêtez-vous et essayez ac. Si oui, essayez une plus longue chaîne). Ce n'est probablement pas faisable avec tous les regex bibliothèques.

    Sur le côté positif, ce type de solution est probablement assez cool à partir d'un point de vue enseignement. Dans la pratique, c'est probablement des effets semblables à un dfa solution, mais sans la nécessité de penser à propos de dfas.

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

    • Idée intéressante, je vais vérifier.
    InformationsquelleAutor Brian
  4. -1

    si votre seul critère est que votre méthode est simple et universel, alors il n'y a rien de plus facile ni de plus universel que la force brute. 🙂

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

    De sûr, c'est un très stupide façon de faire les choses et surtout a été conçu comme une blague.

    Je pense que votre meilleur pari serait d'essayer d'écrire votre propre très de base de l'analyseur, l'enseignement, il juste les choses que vous vous attendez à rencontrer (par exemple: la lettre et le nombre de plages, en répétant d'option et/ou des personnages... ne vous inquiétez pas à propos de look-derrières etc)

    • Je veux un algorithme qui va terminer l'exécution avant la fin des temps. Je veux courir en dessous de 1 seconde, c'est certain.
    • eh bien, vous devriez être plus précis :p de toute façon, j'ai abordé la question avec cela à l'esprit, dans la deuxième partie de ma réponse.
    • L'écriture de mon propre analyseur est exactement le genre de chose que je veux éviter ici 🙂
    InformationsquelleAutor nickf
  5. -2

    L'universalité critère est impossible. Compte tenu de l'expression régulière "^Pour être ou ne pas être, telle est la question:$", il n'y aura pas dix aléatoire unique chaînes qui correspondent.

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

    moonshadow lien en Perl String::le Hasard est la réponse. Un programme en Perl qui lit un RegEx partir de l'entrée standard et écrit la sortie de dix invocations de String::Aléatoire à la sortie standard (stdout) est trivial. Compiler pour Windows ou Unix exe avec Perl2exe et à l'appeler à partir de PHP, Python, ou quoi que ce soit.

    Voir aussi Générateur de Texte aléatoire basé sur les regex

    • L'exemple que vous avez donné n'est certainement pas un cas dégénéré pour moi, mais plutôt, très facile. Le premier caractère ne correspond qu'à "T", la deuxième correspond seulement à "o", et ainsi de suite. Si toutes les versions sont les mêmes, ainsi soit-il.
    • Donc les chaînes aléatoires n'ont pas besoin d'être unique?
    InformationsquelleAutor Thomas L Holaday