Создать набор всех возможных совпадений для заданного регулярного выражения

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

Например:

Во всех этих примерах вы можете предположить, что они начинаются с ^ и заканчиваются на $

`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

Мне также было бы интересно, если бы был способ получения count уникальных решений для регулярного выражения или если есть способ определить, имеет ли регулярное выражение конечные решения.

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

Меня интересует решение PHP для этой проблемы, но другие языки также будут в порядке.

EDIT:

Я узнал в своем классе Formal Theory о DFA, который можно использовать для реализации регулярных выражений (и других регулярных языков). Если бы я мог преобразовать регулярное выражение в DFA, то решение кажется мне довольно прямым, но это преобразование кажется мне довольно сложным.

ИЗМЕНИТЬ 2:

Спасибо за все предложения, см. мой пост о публичном проекте github. Я работаю над тем, чтобы "ответить" на этот вопрос.

Ответ 1

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

В настоящее время он проходит следующие модульные тесты.

<?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, который мог бы обрабатывать бесконечные списки, а также тот, который произвольно генерировал совпадения из регулярного выражения. Я также хотел бы изучить создание регулярного выражения из набора совпадений как способ оптимизации поиска или сжатия данных.

Ответ 2

Преобразование из регулярного выражения в 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:
            ...

Ответ 3

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

Поскольку вы рассматриваете только регулярные выражения, обозначающие конечные языки, вы на самом деле рассматриваете подмножество регулярных выражений над алфавитом. В частности, вы не имеете дело с регулярными выражениями, построенными с использованием оператора звезды Клейна. Это предполагает простой рекурсивный алгоритм построения множества строк, обозначенных регулярными выражениями без звезды Клейна над алфавитом Σ.

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}

Вы также спрашиваете, существует ли алгоритм, определяющий, является ли регулярный язык конечным. Алгоритм состоит в построении детерминированного конечного автомата, принимающего язык, а затем определения того, содержит ли переходный график переход от начального состояния к конечному состоянию, содержащему цикл. Заметим, что подмножество регулярных выражений, построенных без звезды Клейна, обозначает конечные языки. Поскольку объединение и конкатенация конечных множеств конечно, это следует легкой индукцией.

Ответ 4

Это, вероятно, не отвечает на все ваши вопросы/потребности, но, возможно, это хорошая отправная точка. Я искал решение для автоматического генерации данных, которое соответствует регулярному выражению некоторое время назад, и я нашел этот модуль perl Parse:: RandGen, Parse:: RandGen:: RegExp, который работал довольно впечатляюще хорошо для моих нужд:

http://metacpan.org/pod/Parse::RandGen

Ответ 5

Возможно, вы захотите посмотреть на эту библиотеку Regex, которая анализирует синтаксис RegEx (хотя и немного отличается от стандарта perl) и может построить из него DFA: http://www.brics.dk/automaton/