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

Question

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

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

Answer 1

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

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

Можно построить график, затем начать с конечного состояния и пересекать случайные ребра назад, отслеживая путь. В стандартной конструкции каждый узел в графе доступен из начального состояния, поэтому вам не нужно беспокоиться о том, что вы можете исправить ошибку и откатиться назад. Если вы достигнете начального состояния, остановитесь и прочитайте путь, идущий вперед. Это ваш матч для регулярного выражения.

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

Может быть, это отправная точка для размышления о проблеме, хотя!

Теперь, когда я это написал, мне кажется, что было бы проще неоднократно разрешать варианты, чтобы упростить шаблон регулярных выражений, пока у вас не останется простая строка. Найдите первый не алфавитный символ в шаблоне. Если это *, скопируйте предыдущий элемент несколько раз и удалите *. Если это |, выберите, какой из элементов OR будет сохранен, а остальные удалите. Для левой пары сделайте то же самое, но посмотрите на персонажа, следующего за соответствующей правой пареной. Это, вероятно, будет проще, если вы сначала проанализируете регулярное выражение в древовидном представлении, с которым будет легче работать со структурой группировки пар.

Для человека, который беспокоился, что решение о том, действительно ли регулярное выражение соответствует чему-либо, равносильно проблеме остановки: нет, обычные языки ведут себя довольно хорошо. Вы можете сказать, описывают ли любые два регулярных выражения один и тот же набор принятых строк. Вы в основном делаете машину выше, затем следуете алгоритму, чтобы произвести канонический минимальный эквивалент машины. Сделайте это для двух регулярных выражений, затем проверьте, эквивалентны ли получающиеся минимальные машины, что просто.

Answer 2

String :: Random в Perl сгенерирует случайную строку из подмножества регулярных выражений:

#!/usr/bin/perl

use strict;
use warnings;

use String::Random qw/random_regex/;

print random_regex('[A-Za-z]{3}[0-9][A-Z]{2}[!@#$%^&*]'), "\n";

Answer 3

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

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

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

Answer 4

Я написал Петрушка , которая состоит из лексера и генератора.

• Lexer предназначен для преобразования строки, подобной регулярному выражению, в последовательность токенов.
• Генератор использует эти токены для получения определенного количества кодов.

$generator = new \Gajus\Parsley\Generator();

/**
 * Generate a set of random codes based on Parsley pattern.
 * Codes are guaranteed to be unique within the set.
 *
 * @param string $pattern Parsley pattern.
 * @param int $amount Number of codes to generate.
 * @param int $safeguard Number of additional codes generated in case there are duplicates that need to be replaced.
 * @return array
 */
$codes = $generator->generateFromPattern('FOO[A-Z]{10}[0-9]{2}', 100);

В приведенном выше примере будет создан массив, содержащий 100 кодов, каждый из которых имеет префикс "FOO", за которым следуют 10 символов из стога сена "ABCDEFGHKMNOPRSTUVWXYZ23456789" и 2 числа из стога "0123456789".

Answer 5

Эта PHP-библиотека выглядит многообещающе: ReverseRegex

Как и все эти, он обрабатывает только подмножество регулярных выражений, но может выполнять довольно сложные вещи, такие как почтовые индексы Великобритании:

([A-PR-UWYZ]([0-9]([0-9]|[A-HJKSTUW])?|[A-HK-Y][0-9]([0-9]|[ABEHMNPRVWXY])?) ?[0-9][ABD-HJLNP-UW-Z]{2}|GIR0AA)

Выходы

D43WF
B6 6SB
MP445FR
P9 7EX
N9 2DH
GQ28 4UL
NH1 2SL
KY2 9LS
TE4Y 0AP

Answer 6

Вам нужно написать генератор строк, который может анализировать регулярные выражения и генерировать случайные члены диапазонов символов для случайных длин и т. Д.

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

Answer 7

Почему бы не использовать регулярное выражение в обратном порядке? Простой пример: если ваше регулярное выражение равно

/[a-zA-Z]{6}/

тогда вы знаете, что вам нужно 6 букв a-z или A-Z, так что сгенерируйте их. Конечно, это может стать интереснее, и, в зависимости от ваших потребностей, вы можете закончить переписывание всего синтаксического анализатора регулярных выражений, но вы можете прекратить добавлять функции, когда выполнили свои потребности.

Answer 8

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

Answer 9

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

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

Answer 10

Если у вас есть требования как минимальной длины, так и 3-х-4 * (или аналогичных), я просто склонен использовать приличный генератор паролей.

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

• 3-из-4: должен иметь как минимум три из следующих характеристик: строчные, прописные, цифры, символы