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

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

Например:

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

`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-решение этой проблемы, но подойдут и другие языки.

РЕДАКТИРОВАТЬ:

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

РЕДАКТИРОВАТЬ 2:

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


php regex algorithm language-agnostic dfa
person Kendall Hopkins    schedule 30.09.2011    source источник
comment
Отличный вопрос. Я полагаю, что что-то, что могло бы сделать это, было бы очень полезно для модульного тестирования.   -  person FtDRbwLXw6    schedule 30.09.2011
comment
@drrcknlsn Это было одной из моих мыслей, я думал использовать его для генерации полного кеша для системы маршрутизации на основе регулярных выражений для MVC.   -  person Kendall Hopkins    schedule 30.09.2011
comment
Вы предполагаете неявные якоря. Легко показать все возможные способы сопоставления заданной строки. Например, для Hello world шаблон /hel+o?/i соответствует Hello, Hell и Hel. Однако это не то же самое, что поколение.   -  person tchrist    schedule 30.09.2011
comment
@tchrist All of these example you can assume they start with ^ and end with $   -  person Kendall Hopkins    schedule 30.09.2011
comment
Это Java, а не PHP, но это поможет вам начать. stackoverflow .com / questions / 22115 / Также обратите внимание на регулярное выражение stackoverflow.com/questions/3165809/   -  person Jim Mischel    schedule 30.09.2011
comment
Что он? language agnostic [т.е. общие решения для каждого языка] или php [решение может и должно использовать инструменты php]. Также: вы предполагаете ascii или unicode? для юникода регулярное выражение ... может быть проблематичным [слишком много возможностей]   -  person amit    schedule 30.09.2011
comment
Я знаю, как сгенерировать все возможности с учетом конкретного / конечного набора входных данных, который я предоставил в своем решении. Если это тебе не поможет, дай мне знать.   -  person tchrist    schedule 01.10.2011

Ответы (5)


arrow_upward
3
arrow_downward

Преобразование регулярного выражения в 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:
            ...
person Community    schedule 30.09.2011
comment
Это в значительной степени то, что я имел в виду, но я не понимаю, как TokenizeRegex будет работать. Мне кажется, это самая сложная часть всей проблемы. - person Kendall Hopkins; 30.09.2011
comment
@KendallHopkins: учитывая контекст ответа, токенизатор - это просто лексер, построенный для каждого из символов регулярного выражения. Если вы не возражаете против использования регулярных выражений в вашем инструменте анализа регулярных выражений, любой инструмент lex должен работать. Это выглядит сложным только в том случае, если вы хотите избежать использования регулярных выражений. В любом случае, можно также использовать то, что используется в реальной реализации. См. Пример stackoverflow.com/questions/265457/regex-grammar. - person ccoakley; 01.10.2011
comment
Правильная реализация TokenizeRegex будет просто разбивать строку на отдельные символы. Объединение диапазонов простых символов, которые можно рассматривать как единое целое, повысит производительность (например, "hell", "o", "?"), но это не критично. - person ; 01.10.2011
comment
@Kendall: ознакомьтесь с Сопоставление регулярных выражений может быть простым и быстрым. В нем объясняется, как преобразовать (гораздо более простой) синтаксис регулярного выражения в NFA, который можно преобразовать в DFA; это отличная статья, и она может помочь вам задуматься над ней. - person Antal Spector-Zabusky; 01.10.2011

arrow_upward
2
arrow_downward

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

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

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}

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

person danportin    schedule 04.10.2011
comment
Хороший ответ, но вы можете пояснить, что вы имеете в виду, проверяя наличие циклов. Конечно, граф DFA, содержащий цикл, необходим для языка, который он принимает как бесконечность, но этого недостаточно. - person Patrick87; 05.10.2011
comment
Ты прав. Я изменил проверку циклов на определение, есть ли переход от начального состояния к конечному состоянию, содержащему цикл. Последнее является достаточным условием, первое - просто необходимым. Спасибо. - person danportin; 05.10.2011

arrow_upward
0
arrow_downward

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

person Mike Sokolov    schedule 05.10.2011

arrow_upward
0
arrow_downward

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

person Kendall Hopkins    schedule 05.10.2011

arrow_upward
0
arrow_downward

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

http://metacpan.org/pod/Parse%3a%3aRandGen

person aurora    schedule 04.10.2011