Генерация случайных последовательностей, соответствующих заданному регулярному выражению - PullRequest
Новая
       4

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

4 голосов
/ 06 декабря 2010

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

Ответы [ 5 ]

3 голосов
/ 06 декабря 2010

С чисто теоретической точки зрения регулярные выражения эквивалентны рациональным языкам, которые строятся на следующей основе:

  • {} (язык без слов) является рациональным.
  • {a} (язык с одной буквой из одного слова) рационально.
  • Если L и M являются двумя рациональными языками, то их объединение (слова либо в L, либо в M) рационально.
  • Если L и M являются двумя рациональными языками, то их объединение LM (слова, построенные путем добавления слова из L к слову из M) также рационально.
  • Если L является рациональным языком, то L* (слова, образованные путем объединения любого количества слов из языка L) также рационально.

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

  • make({}) = ""
  • make({a}) = "a"
  • make(A|B) = flip-coin ? make(A) : make(B)
  • make(AB) = make(A) + make(B)
  • make(A*) = flip-coin ? "" : make(A) + make(A*)
1 голос
/ 29 января 2015
1 голос
/ 21 октября 2012

В .NET вы также можете посмотреть на проект Тариф .Он делает именно то, что вы описываете.

Вот как его использовать: 

var xeger = new Xeger(pattern);
var match = xeger.Generate();

Regex.IsMatch(match, pattern);
// Prints -> true

Поскольку вы упомянули модульное тестирование, вы можете также рассмотреть возможность использования Автофиксирование который, как только вы украсите Свойство (или Поле) с атрибутом [RegularExpression] , ему будет присвоено значение, соответствующее регулярному выражению.

1 голос
/ 06 декабря 2010

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

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

Конечно, я понятия не имею, насколько выполнимым является этот метод в коде или существуют ли такие библиотеки.

http://lara.epfl.ch/dokuwiki/equivalence_of_finite_state_machine_and_regular_expression_languages

0 голосов
/ 13 июня 2011

Хотя не .NET, но может быть интересно. Нашел эту реализацию в Haskell . Автор утверждает, что он более мощный, чем CPAN Genex .

...