Stringa casuale che corrisponde a una regexp

Question

Come faresti per creare una stringa alfanumerica casuale che corrisponda a una determinata espressione regolare?

Questo è specificamente per la creazione di password iniziali che soddisfano i requisiti di password regolari.

Answer 1

Usa la risposta accettata su Generazione di password casuali fino a quando non corrisponde al tuo regexp.

Answer 2

Welp, sto solo riflettendo, ma la domanda generale di generare input casuali che corrispondono a una regex mi sembra fattibile per una definizione sufficientemente rilassata di random e una definizione sufficientemente stretta di regex. Sto pensando alla definizione formale classica, che consente solo () | * e caratteri alfabetici.

Le espressioni regolari possono essere associate a macchine formali chiamate automi finiti . Tale macchina è un grafico diretto con un nodo particolare chiamato stato finale, un nodo chiamato stato iniziale e una lettera dell'alfabeto su ciascun bordo. Il regex accetta una parola se è possibile iniziare dallo stato iniziale e attraversare un bordo etichettato con ciascun carattere attraverso il grafico e terminare allo stato finale.

Si potrebbe costruire il grafico, quindi iniziare allo stato finale e attraversare i bordi casuali all'indietro, tenendo traccia del percorso. In una costruzione standard, ogni nodo nel grafico è raggiungibile dallo stato iniziale, quindi non è necessario preoccuparsi di fare errori irrecuperabili e di dover tornare indietro. Se si raggiunge lo stato iniziale, fermarsi e leggere il percorso andando avanti. Questa è la tua partita per la regex.

Non c'è alcuna garanzia particolare su quando o se raggiungerai lo stato iniziale, comunque. Uno dovrebbe capire in che senso le stringhe generate sono "casuali", e in che senso speri in primo luogo un elemento casuale dalla lingua.

Forse questo è un punto di partenza per pensare al problema, però!

Ora che l'ho scritto, mi sembra che potrebbe essere più semplice risolvere ripetutamente le scelte per semplificare il modello regex fino a quando non ti rimane una semplice stringa. Trova il primo carattere non alfabetico nel modello. Se è un *, replica l'elemento precedente alcune volte e rimuovi il *. Se è un |, scegli quale degli elementi OR avrebbe preservare e rimuovere il resto. Per un paren sinistro, fai lo stesso, ma osserva il personaggio che segue il corrispondente paren destro. Questo è probabilmente più semplice se prima analizzi la regex in una rappresentazione ad albero che semplifica il funzionamento della struttura di raggruppamento dei genitori.

Per la persona che si preoccupava che decidere se una regex corrispondesse effettivamente a qualcosa equivale al problema di fermarsi: no, le lingue normali si comportano abbastanza bene. Puoi dire se due regex descrivono lo stesso set di stringhe accettate. Fondamentalmente fai la macchina sopra, quindi segui un algoritmo per produrre una macchina equivalente canonica minima. Fallo per due regex, quindi controlla se le macchine minime risultanti sono equivalenti, il che è semplice.

Answer 3

String :: Random in Perl genererà una stringa casuale da un sottoinsieme di espressioni regolari:

#!/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

Se hai un problema specifico, probabilmente hai in mente un'espressione regolare specifica. Prenderei quell'espressione regolare, capirei cosa significa in termini umani semplici e lavorerei da lì.

Sospetto che sia possibile creare un generatore di corrispondenze casuali regex generale, ma è probabile che molto sia più lavoro che gestire un caso specifico, anche se quel caso cambia alcune volte all'anno.

(In realtà, potrebbe non essere possibile generare corrispondenze casuali nel senso più generale - ho una vaga memoria che il problema di "ogni stringa corrisponde a questa regex" è il problema di fermare sotto mentite spoglie. -down lingua regex potresti avere più fortuna però.)

Answer 5

Ho scritto Prezzemolo , che consistono in un Lexer e un generatore.

• Lexer serve per convertire una stringa simile a un'espressione regolare in una sequenza di token.
• Il generatore utilizza questi token per produrre un numero definito di codici.

$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'esempio sopra genererà un array contenente 100 codici, ciascuno con il prefisso "FOO", seguito da 10 caratteri da "ABCDEFGHKMNOPRSTUVWXYZ23456789" pagliaio e 2 numeri da "0123456789" pagliaio.

Answer 6

Questa libreria PHP sembra promettente: ReverseRegex

Come tutti questi, gestisce solo un sottoinsieme di espressioni regolari ma può fare cose abbastanza complesse come i codici postali del Regno Unito:

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

Uscite

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

Answer 7

Dovresti scrivere un generatore di stringhe in grado di analizzare espressioni regolari e generare membri casuali di intervalli di caratteri per lunghezze casuali, ecc.

Molto più semplice sarebbe scrivere un generatore di password casuale con determinate regole (inizia con una lettera minuscola, ha almeno una punteggiatura, lettera maiuscola e numero, almeno 6 caratteri, ecc.) e quindi scrivere la tua regex in modo che qualsiasi le password create con tali regole sono valide.

Answer 8

Supponendo che tu abbia sia una lunghezza minima sia un requisito 3-of-4 * (o simile), sarei propenso a usare un generatore di password decente.

Ho creato un paio in passato (sia web-based che riga di comando) e non ho mai dovuto saltare più di una stringa generata per passare la regola 3 di 4.

• 3-of-4: deve avere almeno tre delle seguenti caratteristiche: minuscolo, maiuscolo, numero, simbolo

Answer 9

È possibile (ad esempio, il modulo regexp di Haskell ha una suite di test che genera automaticamente stringhe che dovrebbero corrispondere a determinate regex).

Tuttavia, per una semplice attività a portata di mano potresti essere meglio prendere un semplice generatore di password e filtrarne l'output con regexp.

Answer 10

Perché non lavorare la regexp all'indietro? Un semplice esempio: se regexp è

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

allora sai che hai bisogno di 6 lettere dalla a alla z o dalla a alla z, quindi generale. Questo può diventare più elaborato, ovviamente e, a seconda delle tue esigenze, potresti finire per scrivere in senso inverso un intero parser regexp, ma puoi smettere di aggiungere funzionalità quando hai soddisfatto le tue necessità.