Мне интересно, как найти набор всех совпадений для данного регулярного выражения с конечным числом совпадений.
Например:
Все эти примеры можно предположить, что они начинаются с ^ и заканчиваются на $
`hello?` -> (hell, hello) `[1-9][0-9]{0,3}` -> (1,2,3 ..., 9998, 9999) `My (cat|dog) is awesome!` -> (My cat is awesome!, My dog is awesome!) `1{1,10}` -> (1,11, ..., 111111111, 1111111111) `1*` -> //error `1+` -> //error `(1|11){2}` -> (1,11,111,1111) //notice how it doesn't repeat any of the possibilities
Мне также было бы интересно, есть ли способ получить счет уникальных решений для регулярного выражения или если есть способ определить, имеет ли регулярное выражение конечные решения.
Было бы неплохо, если бы алгоритм мог анализировать любое регулярное выражение, но достаточно мощный подмножество регулярного выражения.
Меня интересует решение PHP для этой проблемы, но другие языки также будут в порядке.
РЕДАКТИРОВАТЬ:
Я узнал в своем классе Formal Theory о DFA, который можно использовать для реализации регулярных выражений (и других регулярных языков). Если бы я мог преобразовать регулярное выражение в DFA, решение кажется мне довольно прямым, но это преобразование кажется мне довольно сложным.
EDIT 2:
Спасибо за все предложения, см. Мой пост о публичном проекте github, над которым я работаю, чтобы «ответить» на этот вопрос.
Преобразование из регулярного выражения в DFA довольно просто. Однако проблема, с которой вы столкнетесь, заключается в том, что генерируемый DFA может содержать циклы (например, для * или + ), что сделает невозможным полное расширение. Кроме того, {n,n} не может быть явно отображено в DFA, поскольку DFA не имеет «памяти», сколько раз оно зацикливается.
Какое решение этой проблемы будет сводиться к созданию функции, которая токенизирует и анализирует регулярное выражение, а затем возвращает массив всех возможных совпадений. Использование рекурсии здесь поможет вам.
Начальная точка в псевдокоде может выглядеть так:
to GenerateSolutionsFor(regex): solutions = [""] for token in TokenizeRegex(regex): if token.isConstantString: for sol in solutions: sol.append(token.string) else if token.isLeftParen: subregex = get content until matching right paren subsols = GenerateSolutionsFor(subregex) for sol in solutions: for subsol in subsols: sol.append(subsol) else if token.isVerticalBar: solutions.add(GenerateSolutionsFor(rest of the regex)) else if token.isLeftBrace: ...
Мне интересно, как найти набор всех совпадений для данного регулярного выражения с конечным числом совпадений.
Поскольку вы рассматриваете только регулярные выражения, обозначающие конечные языки, вы фактически рассматриваете подмножество регулярных выражений над алфавитом. В частности, вы не имеете дело с регулярными выражениями, построенными с использованием оператора звезды Клейна. Это предполагает простой рекурсивный алгоритм построения множества строк, обозначенных регулярными выражениями без звезды Клейна над алфавитом Σ.
LANG(a) = {a} for all a ∈ Σ LANG(x ∪ y) = LANG(x) ∪ LANG(y) LANG(xy) = {vw : v ∈ LANG(x) ∧ w ∈ LANG(y)}
Рассмотрим регулярное выражение, такое как a(b ∪ c)d . Это как раз пример вашего кота и собаки. Выполнение алгоритма будет правильно определять язык, обозначаемый регулярным выражением:
LANG(a((b ∪ c)d)) = {xy : x ∈ LANG(a) ∧ y ∈ LANG((b ∪ c)d)} = {xy : x ∈ {a} ∧ y ∈ {vw : v ∈ LANG(b ∪ c) ∧ w ∈ LANG{d}}} = {ay : y ∈ {vw : v ∈ (LANG(b) ∪ LANG(c)) ∧ w ∈ {d}}} = {ay : y ∈ {vd : v ∈ {b} ∪ {c}} = {ay : y ∈ {vd : v ∈ {b,c}}} = {ay : y ∈ {bd, cd}} = {abd, acd}
Вы также спрашиваете, существует ли алгоритм, определяющий, является ли регулярный язык конечным. Алгоритм состоит в построении детерминированного конечного автомата, принимающего язык, а затем определения того, содержит ли переходный график переход от начального состояния к конечному состоянию, содержащему цикл. Заметим, что подмножество регулярных выражений, построенных без звезды Клейна, обозначает конечные языки. Поскольку объединение и конкатенация конечных множеств конечно, это следует простой индукцией.
Возможно, вы захотите посмотреть на эту библиотеку Regex, которая анализирует синтаксис RegEx (хотя и немного отличается от стандарта perl) и может построить из него DFA: http://www.brics.dk/automaton/
Я начал работать над решением на Github . Он может уже использовать lex большинство примеров и дать решение для конечного регулярного выражения.
В настоящее время он проходит следующие модульные тесты.
<?php class RegexCompiler_Tests_MatchTest extends PHPUnit_Framework_TestCase { function dataProviderForTestSimpleRead() { return array( array( "^ab$", array( "ab" ) ), array( "^(ab)$", array( "ab" ) ), array( "^(ab|ba)$", array( "ab", "ba" ) ), array( "^(ab|(b|c)a)$", array( "ab", "ba", "ca" ) ), array( "^(ab|ba){0,2}$", array( "", "ab", "ba", "abab", "abba", "baab", "baba" ) ), array( "^(ab|ba){1,2}$", array( "ab", "ba", "abab", "abba", "baab", "baba" ) ), array( "^(ab|ba){2}$", array( "abab", "abba", "baab", "baba" ) ), array( "^hello?$", array( "hell", "hello" ) ), array( "^(0|1){3}$", array( "000", "001", "010", "011", "100", "101", "110", "111" ) ), array( "^[1-9][0-9]{0,1}$", array_map( function( $input ) { return (string)$input; }, range( 1, 99 ) ) ), array( '^\n$', array( "\n" ) ), array( '^\r$', array( "\r" ) ), array( '^\t$', array( "\t" ) ), array( '^[\\\\\\]a\\-]$', array( "\\", "]", "a", "-" ) ), //the regex is actually '^[\\\]a\-]$' after PHP string parsing array( '^[\\n-\\r]$', array( chr( 10 ), chr( 11 ), chr( 12 ), chr( 13 ) ) ), ); } /** * @dataProvider dataProviderForTestSimpleRead */ function testSimpleRead( $regex_string, $expected_matches_array ) { $lexer = new RegexCompiler_Lexer(); $actualy_matches_array = $lexer->lex( $regex_string )->getMatches(); sort( $actualy_matches_array ); sort( $expected_matches_array ); $this->assertSame( $expected_matches_array, $actualy_matches_array ); } } ?>
Я хотел бы создать класс MatchIterator который мог бы обрабатывать бесконечные списки, а также тот, который произвольно генерировал совпадения из регулярного выражения. Я также хотел бы изучить создание регулярного выражения из набора совпадений как способ оптимизации поиска или сжатия данных.
Вероятно, это не отвечает на все ваши вопросы / потребности, но, возможно, это хорошая отправная точка. Я искал решение для автоматического генерации данных, которое соответствует регулярному выражению некоторое время назад, и я нашел этот модуль perl Parse :: RandGen, Parse :: RandGen :: RegExp, который работал довольно впечатляюще хорошо для моих нужд:
http://metacpan.org/pod/Parse::RandGen