È possibile testare un'espressione regolare per vedere se si riduce a *

Question

Sto sviluppando un'applicazione in cui gli utenti immettono un'espressione regolare come criterio di filtro, tuttavia non voglio che le persone siano (facilmente) in grado di immettere .* (vale a dire qualsiasi cosa). Il problema è che se uso semplicemente if (expression == ".*"), questo potrebbe essere facilmente aggirato inserendo qualcosa come .*.*.

Qualcuno sa di un test che potrebbe prendere un pezzo di regex e vedere se è essenzialmente .* ma in una forma leggermente più elaborata?

I miei pensieri sono:

1. ho potuto vedere se l'espressione è di uno o più ripetizioni di .*, (vale a dire se corrisponde (\.\*)+ (citazioni/fughe potrebbero non essere del tutto esatto, ma si ottiene l'idea). Il problema è che ci possono essere altre forme di crei una partita globale (ad esempio con $ e ^) che sono troppo esaustivo per pensare di anticipo, lasciate lungo test.

2. ho potuto testare alcuni casuale generato stringhe con esso e assumere t Se tutti passano, l'utente ha inserito un modello di corrispondenza globale. Il problema con questo approccio è che potrebbero esserci situazioni in cui l'espressione è sufficientemente stretta e seleziono solo stringhe errate.

Pensieri, qualcuno?

(FYI, l'applicazione è in Java, ma credo che questo è più di una questione algoritmica di una per una determinata lingua.)

Answer 1

ci sono molte, molte possibilità per raggiungere qualcosa di equivalente a .*. per esempio. basta inserire qualsiasi classe di caratteri e la parte del contatore in una classe o in un'alternanza e corrisponderà a qualsiasi cosa.
Quindi, penso che con un'espressione regolare non sia possibile testare un'altra espressione regolare per l'equivalenza a .*.

Questi sono alcuni esempi che potrebbero corrispondere alla stessa di .* (saranno inoltre corrispondere ai caratteri di nuova riga)

/[\s\S]*/ 
/(\w|\W)*/ 
/(a|[^a])*/ 
/(a|b|[^ab])*/ 

quindi immagino che la tua idea 2 sarebbe molto più facile da raggiungere.

Answer 2

Sì, c'è un modo. Si tratta di convertire la regex in una rappresentazione FSM canonica. Vedi http://en.wikipedia.org/wiki/Regular_expression#Deciding_equivalence_of_regular_expressions

È probabile che trovi il codice pubblicato che fa il lavoro per te. In caso contrario, i passaggi dettagliati sono descritti qui: http://swtch.com/~rsc/regexp/regexp1.html

Se sembra troppo lavoro, è possibile utilizzare un test probabilistico rapido e sporco. Appena generato alcune stringhe casuali per vedere se corrispondono alla regex dell'utente. Se corrispondono, hai una buona indicazione che la regex è eccessivamente ampia.

Answer 3

Grazie a tutti,

ho fatto mancare il test per l'ingresso di equivalenza sul wikipedia, che era interessante.

I miei ricordi di DFA (mi sembra di ricordare di dover dimostrare, o almeno dimostrare, in un esame CompSci 2 ° anno che una regex non può testare per palindromi) sono probabilmente meglio riposati al momento!

Ho intenzione di ridurre l'approccio alla generazione di un set di stringhe da testare. Se passano tutti, quindi sono abbastanza fiducioso che il filtro è troppo ampio e deve essere ispezionato manualmente. Nel frattempo, almeno un errore indica che è più probabile che l'espressione sia adatta allo scopo.

Ora per decidere che tipo di corde per generare al fine di eseguire i test ....

Cordiali saluti, Russ.