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

Question

Дубликат:

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

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

---

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

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

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

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

Answer 1

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

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

Answer 2

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

Answer 3

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

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

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

Answer 4

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

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

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

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

Answer 5

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

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

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

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