Случайная строка, которая соответствует регулярному выражению
Нет, это не так. Я ищу простой и универсальный метод, который я мог бы реализовать. Это намного сложнее, чем случайное создание паролей.
Я хочу создать приложение, которое принимает регулярное выражение, и показывает 10 случайно сгенерированных строк, которые соответствуют этому выражению. Он должен помочь людям лучше понять их регулярные выражения и решить, если они достаточно безопасны для целей проверки. Кто-нибудь знает, как легко это сделать?
Одним из очевидных решений было бы написать (или украсть) парсер regexp, но это действительно кажется мне над головой.
Повторяю, я ищу способ простой и универсальный.
Изменить: Не может быть и речи об использовании грубой силы. Предполагая, что случайные строки будут только [a-z0-9]{10} и 1 миллион итераций в секунду, потребовалось бы 65 лет для итерации через пространство всех 10 - char.
Разделите свое регулярное выражение на DFA, затем произвольно перемещайте свой DFA, пока не закончите в принимающем состоянии, выводя символ для каждого перехода, Каждая прогулка даст новую строку, которая соответствует выражению.
Это не работает для "обычных" выражений, которые на самом деле не являются регулярными, например выражения с обратными ссылками. Это зависит от того, какое выражение вы хотите.
Взгляните на Perl String:: Random.
Одним довольно уродливым решением, которое может быть или не быть практичным, является использование существующей опции диагностики регулярных выражений. Некоторые библиотеки регулярных выражений имеют возможность определять, где регулярное выражение не совпало. В этом случае вы можете использовать то, что на самом деле является формой грубой силы, но использовать по одному персонажу за раз и пытаться получить более длинные строки (и последующие сопоставления), пока не получите полное соответствие. Это очень уродливое решение. Однако, в отличие от стандартного решения грубой силы, его сбой на строке, такой как ab, также скажет вам, существует ли строка ab. *, Которая будет соответствовать (если нет, остановится и попробуйте ac. Если да, попробуйте более длинную строку). Вероятно, это невозможно для всех библиотек регулярных выражений.
С яркой стороны такое решение, вероятно, довольно круто с точки зрения обучения. На практике это, вероятно, похоже на решение dfa, но без требования думать о dfas.
Обратите внимание, что вы не захотите использовать случайные строки с помощью этой техники. Тем не менее, вы можете использовать случайные символы для начала, если вы отслеживаете, что вы тестировали в дереве, поэтому эффект тот же.
если ваши единственные критерии в том, что ваш метод прост и универсален, тогда нет ничего проще или универсальнее, чем грубая сила.:)
for (i = 0; i < 10; ++i) {
do {
var str = generateRandomString();
} while (!myRegex.match(str));
myListOfGoodStrings.push(str);
}
Конечно, это очень глупый способ делать что-то, и в основном это означало как шутка.
Я думаю, что лучше всего попытаться написать свой собственный очень простой парсер, обучая его только тем вещам, с которыми вы собираетесь столкнуться (например: буквы и числа, повторяющиеся/необязательные символы... не беспокойтесь о взглядах и т.д.)
Критерий универсальности невозможен. Учитывая регулярное выражение "^ Чтобы быть или не быть - вот вопрос: $" , не будет десяти уникальных случайных строки, которые соответствуют.
Для невырожденных случаев:
ссылка moonshadow на Perl String:: Random - это ответ. Программа Perl, которая читает RegEx из stdin и записывает вывод из десяти вызовов String:: Random в stdout, тривиальна. Скомпилируйте его либо в Windows, либо в Unix exe с Perl2exe и вызовите его из PHP, Python и т.д.
Также см. генератор случайного текста на основе регулярного выражения