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 星号的正则表达式子集表示有限语言。因为有限集的并集和串联是有限的，所以很容易归纳。

于 2011-10-04T19:28:57.290 回答
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 回答
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 回答