Regex alla generazione di stringhe

La risposta di kevin è stata un buon inizio per sapere come possiamo gestire le espressioni regolari da un punto di vista teorico, il che aiuterebbe a costruire una libreria java che consenta agli utenti di generare string in base a una determinata regex. Ecco una cosa che ho creato, una libreria java che fornisce molte funzionalità per l'utilizzo della regex per generare String (generazione casuale, generazione di stringhe in base al suo indice, genera tutte le stringhe ..) controllalo qui .

Esempio:

    Generex generex = new Generex("[0-3]([a-c]|[e-g]{1,2})");

    // generate the second String in lexicographical order that match the given Regex.
    String secondString = generex.getMatchedString(2);
    System.out.println(secondString);// it print '0b'

    // Generate all String that matches the given Regex.
    List<String> matchedStrs = generex.getAllMatchedStrings();

    // Using Generex iterator
    Iterator iterator = generex.iterator();
    while (iterator.hasNext()) {
        System.out.print(iterator.next() + " ");
    }
    // it print 0a 0b 0c 0e 0ee 0e 0e 0f 0fe 0f 0f 0g 0ge 0g 0g 1a 1b 1c 1e
    // 1ee 1e 1e 1f 1fe 1f 1f 1g 1ge 1g 1g 2a 2b 2c 2e 2ee 2e 2e 2f 2fe 2f 2f 2g
    // 2ge 2g 2g 3a 3b 3c 3e 3ee 3e 3e 3f 3fe 3f 3f 3g 3ge 3g 3g 1ee

    // Generate random String
    String randomStr = generex.random();
    System.out.println(randomStr);// a random value from the previous String list

Un'espressione regolare viene mappata direttamente su una macchina a stati finiti. Generare stringhe dal FSM è semplice con un algoritmo di backtracking. L'esempio è per l'espressione regolare / aa? B /

(start) 0 -- a --> 1 -- a --> 2 -- b --> 3 (accepting and terminal)
                   |                     ^
                   |---------b ----------|

State   Previous char   Input char    Input string     History
  0        null                           --             []
                            a              a         
  1        null                                        [{a,1}]
                            a              aa          [{a,1},{a,2}]
  2        null
                            b             aab          [{a,1},{a,2},{b,3}]
  3        null
         Accepting state, emit 'aab' as valid input
         Terminal state, backtrack
  2          b                             aa          [{a,1},{a,2}]
         No further valid inputs, backtrack
  1          a                             a           [{a,1}]
                            b              ab
  3        null                                        [{a,1},{b,3}]
         Accepting state, emit 'ab' as valid input
         Terminal state, backtrack
  1          b                             a           [{a,1}]
         No further valid inputs, backtrack
  0          a                             --          []
         No further valid inputs, stack empty, terminate

Da sole, le regex servono allo scopo di rispondere alla domanda: "Dato questo elenco di stringhe come input e questo modello, quale sottoinsieme lo rappresenta?". Non funziona a ritroso, cioè da questa regex, inizia a generare stringhe che lo corrispondono.

Detto questo, dai un'occhiata a questo: link , che dovrebbe fare ciò che vuoi ottenere (con alcune limitazioni come descritto nel link ).

Se la tua espressione regolare è accettata, immagino che l'anwer della tua domanda sia piuttosto semplice, cioè generi l'elenco e prendi l'oggetto all'indice i

Vorrei proporre questa risposta nel caso in cui possa aiutarti in che modo. Nel caso ci siano alcuni dettagli o alcuni piccoli errori, si prega di lasciare un commento. Proverò a correggere.

1. Per prima cosa guardate l'automa a stati finiti minimo FSA della regex
2. Trova la prima stringa corrispondente della FSA. Questo può essere fatto creando una FSA ausiliaria in cui rimuovi tutti i percorsi che portano allo stato di rifiuto, quindi inizia a camminare attraverso l'FSA ausiliario. Ad ogni transizione, scegli il primo carattere dell'alfabeto di input per assicurarti di generare la prima stringa corrispondente.
3. Ora dobbiamo ottenere la seconda stringa di corrispondenza della regex originale, quindi modifichiamo l'FSA ausiliario in modo che nello stato finale (prima dello stato di accettazione), l'ultimo carattere inserito (della prima stringa corrispondente in 2 sopra) non porterebbe allo stato di accettazione Questo può essere fatto rimuovendo un bordo (e uno stato) o modificando il bordo che porta allo stato di accettazione.
4. Genera la prima stringa corrispondente della FSA ausiliaria modificata, questo ti darebbe la seconda stringa di corrispondenza della regex originale
5. Ripeti la modifica dell'FSA ausiliaria fino a raggiungere la stringa di i-esima corrispondenza. Questa sarebbe la i-la stringa corrispondente della regex originale.