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

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

12 голосов
/ 30 сентября 2011

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

Например:

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

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

EDIT:

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

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

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

Ответы [ 5 ]

3 голосов
/ 30 сентября 2011

Преобразование из регулярного выражения в DFA довольно простое.Однако проблема, с которой вы столкнетесь, заключается в том, что сгенерированный DFA может содержать циклы (например, для * или +), которые делают невозможным полное расширение.Кроме того, {n,n} нельзя точно представить в DFA, поскольку DFA не имеет «памяти» о том, сколько раз он был зациклен.

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

Начальная точка в псевдокоде может выглядеть следующим образом: 

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:
            ...
2 голосов
/ 04 октября 2011

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

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

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}

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

0 голосов
/ 05 октября 2011

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

0 голосов
/ 05 октября 2011

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

0 голосов
/ 05 октября 2011

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

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

...