Как создать случайные строки, которые соответствуют заданному регулярному выражению?

Duplicate:

Случайная строка, которая соответствует регулярному выражению

Нет, это не так. Я ищу простой и универсальный метод, который я мог бы реализовать. Это намного сложнее, чем случайное создание паролей.

Я хочу создать приложение, которое принимает регулярное выражение, и показывает 10 случайно сгенерированных строк, которые соответствуют этому выражению. Он должен помочь людям лучше понять их регулярные выражения и решить, если они достаточно безопасны для целей проверки. Кто-нибудь знает, как легко это сделать?

Одним из очевидных решений было бы написать (или украсть) парсер regexp, но это действительно кажется мне над головой.

Повторяю, я ищу способ простой и универсальный.

Изменить: Не может быть и речи об использовании грубой силы. Предполагая, что случайные строки будут только [a-z0-9]{10} и 1 миллион итераций в секунду, потребовалось бы 65 лет для итерации через пространство всех 10 - char.

Ответ 1

Разделите свое регулярное выражение на DFA, затем произвольно перемещайте свой DFA, пока не закончите в принимающем состоянии, выводя символ для каждого перехода, Каждая прогулка даст новую строку, которая соответствует выражению.

Это не работает для "обычных" выражений, которые на самом деле не являются регулярными, например выражения с обратными ссылками. Это зависит от того, какое выражение вы хотите.

Ответ 2

Взгляните на Perl String:: Random.

Ответ 3

Одним довольно уродливым решением, которое может быть или не быть практичным, является использование существующей опции диагностики регулярных выражений. Некоторые библиотеки регулярных выражений имеют возможность определять, где регулярное выражение не совпало. В этом случае вы можете использовать то, что на самом деле является формой грубой силы, но использовать по одному персонажу за раз и пытаться получить более длинные строки (и последующие сопоставления), пока не получите полное соответствие. Это очень уродливое решение. Однако, в отличие от стандартного решения грубой силы, его сбой на строке, такой как ab, также скажет вам, существует ли строка ab. *, Которая будет соответствовать (если нет, остановится и попробуйте ac. Если да, попробуйте более длинную строку). Вероятно, это невозможно для всех библиотек регулярных выражений.

С яркой стороны такое решение, вероятно, довольно круто с точки зрения обучения. На практике это, вероятно, похоже на решение dfa, но без требования думать о dfas.

Обратите внимание, что вы не захотите использовать случайные строки с помощью этой техники. Тем не менее, вы можете использовать случайные символы для начала, если вы отслеживаете, что вы тестировали в дереве, поэтому эффект тот же.

Ответ 4

если ваши единственные критерии в том, что ваш метод прост и универсален, тогда нет ничего проще или универсальнее, чем грубая сила.:)

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

Конечно, это очень глупый способ делать что-то, и в основном это означало как шутка.

Я думаю, что лучше всего попытаться написать свой собственный очень простой парсер, обучая его только тем вещам, с которыми вы собираетесь столкнуться (например: буквы и числа, повторяющиеся/необязательные символы... не беспокойтесь о взглядах и т.д.)

Ответ 5

Критерий универсальности невозможен. Учитывая регулярное выражение "^ Чтобы быть или не быть - вот вопрос: $" , не будет десяти уникальных случайных строки, которые соответствуют.

Для невырожденных случаев:

ссылка moonshadow на Perl String:: Random - это ответ. Программа Perl, которая читает RegEx из stdin и записывает вывод из десяти вызовов String:: Random в stdout, тривиальна. Скомпилируйте его либо в Windows, либо в Unix exe с Perl2exe и вызовите его из PHP, Python и т.д.

Также см. генератор случайного текста на основе регулярного выражения