12

有限数の一致を持つ特定の正規表現へのすべての一致のセットを見つける方法を知りたいです。

例えば：

^これらの例はすべて、次で始まり、次で終わると想定できます$

`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 プロジェクトに関する私の投稿を参照してください。

4

5 に答える 5

3

正規表現から DFA への変換は非常に簡単です。ただし、ここで遭遇する問題は、生成された DFA にループ ( for*や など+) が含まれている可能性があり、完全に展開できなくなることです。さらに、{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:
            ...
于 2011-09-30T19:32:15.780 に答える
2

有限数の一致を持つ特定の正規表現へのすべての一致のセットを見つける方法を知りたいです。

有限言語を示す正規表現のみを検討しているため、実際には、アルファベットに対する正規表現のサブセットを検討しています。特に、Kleene スター演算子を使用して構築された正規表現を扱っていません。これは、アルファベット Σ に Kleene スターを使用せずに、正規表現によって示される文字列のセットを構築するための単純な再帰アルゴリズムを示唆しています。

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}

また、通常の言語が有限であるかどうかを判断するアルゴリズムがあるかどうかも尋ねます。アルゴリズムは、言語を受け入れる決定論的有限オートマトンを構築し、遷移グラフに開始状態からサイクルを含む最終状態へのウォークが含まれているかどうかを判断することから成ります。Kleene star を使用せずに構築された正規表現のサブセットは、有限言語を表すことに注意してください。有限集合の結合と連結は有限であるため、これには簡単な帰納法が続きます。

于 2011-10-04T19:28:57.290 に答える
0

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無限リストを処理できるクラスと、正規表現からランダムに一致を生成するクラスを構築したいと考えています。また、ルックアップの最適化やデータの圧縮の方法として、一致セットから正規表現を構築することも検討したいと思います。

于 2011-10-05T04:45:30.617 に答える
0

これはおそらくあなたのすべての質問/ニーズに答えているわけではありませんが、おそらく良い出発点です. 少し前に正規表現に一致するデータを自動生成するためのソリューションを探していましたが、この perl モジュール Parse::RandGen, Parse::RandGen::RegExp を見つけました。

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

于 2011-10-04T20:17:17.397 に答える
0

この Regex ライブラリを参照してください。これは RegEx 構文を解析し (perl 標準とは少し異なります)、そこから DFA を構築できます: http://www.brics.dk/automaton/

于 2011-10-05T01:04:06.697 に答える