logo标签列表

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

phpregexalgorithmlanguage-agnosticdfa
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项目的帖子，我正在努力“回答”这个问题。

@drrcknlsn 那是我其中一个想法，我在考虑使用它来为基于正则表达式的路由系统生成完整的缓存，以用于MVC。 - Kendall Hopkins
你正在假设隐式锚点。展示所有匹配给定字符串的可能方式很容易。例如，给定“Hello world”，模式/hel+o?/i匹配Hello、Hell和Hel。但这并不等同于生成。 - tchrist
1
这是Java而不是PHP，但它可以让你入门。https://dev59.com/BHVD5IYBdhLWcg3wTZ1m 还可以看一下http://stackoverflow.com/questions/3165809/regular-expression-to-generate-a-string - Jim Mischel
1
是哪一个？语言无关 [即通用解决方案，适用于所有编程语言]还是php[解决方案可以并且应该使用php工具]。另外：你假设使用ascii还是unicode？对于unicode，正则表达式“...”可能会有问题[太多可能性]。 - amit
我知道如何根据我在解决方案中提供的具体/有限输入集生成所有可能性。如果这对你完全没有帮助，请告诉我。 - tchrist
显示剩余2条评论
5个回答
3
正则表达式转化为DFA相当直观。然而，你会遇到一个问题，那就是生成的DFA可能包含循环（例如对于 * 或 + ），这将使它无法完全展开。此外，在DFA中无法清晰地表示 {n,n} ，因为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:
            ...
1
这基本上是我所想的，但我不明白TokenizeRegex如何工作。对我来说，这似乎是整个问题中最难的部分。 - Kendall Hopkins
1
@KendallHopkins：鉴于答案的背景，分词器只是为每个正则表达式符号构建的词法分析器。只要您不介意在正则表达式分析工具中使用正则表达式，任何词法分析工具都应该可以工作。只有当您想避免使用正则表达式时，它看起来才会困难。无论如何，最好使用实际实现使用的内容。请参见https://dev59.com/IXVC5IYBdhLWcg3wihmv作为示例。 - ccoakley
TokenizeRegex的一个有效实现只需将字符串拆分为其各个字符。将可以作为一个单位处理的普通字符范围组合在一起将提高性能（例如 "hell", "o", "?"），但这并非关键。 - user149341
@Kendall: 看看"正则表达式匹配可以简单快速"。它解释了如何将（更简单的）正则表达式语法转换为NFA，然后可以将其转换为DFA; 这是一篇很棒的文章，可能有助于思考。 - Antal Spector-Zabusky
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星号的正则表达式子集表示有限语言。由于有限集合的并集和连接仍然是有限的，这可以通过简单的归纳得出。
1
不错的回答，但您可能需要澄清一下“检查循环”的含义。当然，包含循环的DFA的图形对于其接受的语言是无限的是必要的，但这并不足够。 - Patrick87
你说得对。我把“检查循环”改成了“确定是否存在从起始状态到包含循环的终止状态的路径”。后者是充分条件，前者仅是必要条件。谢谢。 - emi
0
我已经开始在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

这可能不能回答你所有的问题/需求，但或许它是一个不错的起点。我曾经在寻找一种自动生成符合正则表达式数据的解决方案，后来我发现了这个 Perl 模块 Parse::RandGen、Parse::RandGen::RegExp，对我的需求来说效果相当不错：

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

0

你可能想看看这个正则表达式库，它解析了一个正则表达式语法（尽管与Perl标准有些不同），并可以从中构建DFA：http://www.brics.dk/automaton/

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接