为给定的正则表达式创建所有可能匹配的集合

Question

我想知道如何找到一组具有有限数量匹配的给定正则表达式的所有匹配.

例如:

所有这些例子都可以假设他们从一开始就^结束$

`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,那么解决方案对我来说似乎相当直接,但这种转变对我来说似乎相当棘手.

编辑2:

感谢所有建议,请参阅我关于公共github项目的帖子,我正在努力"回答"这个问题.

Answer 1

我已经开始在 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可以处理无限列表的类，以及一个可以从正则表达式随机生成匹配项的类。我还想研究从匹配集构建正则表达式作为优化查找或压缩数据的方法。