我们如何将a ^ n b ^ n与Java正则表达式匹配?

2020年11月29日 28点热度 0条评论

This is the second part of a series of educational regex articles. It shows how lookaheads and nested references can be used to match the non-regular languge anbn. Nested references are first introduced in: How does this regex find triangular numbers?

原型(prototype)非
regular languages之一是:

L = { anbn: n > 0 }

这是所有非空字符串的语言,它由一定数量的
a后面跟相等数量的
b组成。这种语言的字符串示例为
ab
aabb
aaabbb

pumping lemma可以表明该语言是非常规的。实际上,它是原型(prototype)
context-free language,可以由
context-free grammar
S → aSb | ab生成。

尽管如此,现代正则表达式实现显然不仅仅可以识别常规语言。也就是说,根据形式语言理论的定义,它们不是“正常的”。 PCRE和Perl支持递归正则表达式,.NET支持平衡组定义。甚至更少的“花式”功能,例如向后引用匹配,表示正则表达式不规则。

但是,这种“基本”功能到底有多强大?例如,我们可以用Java正则表达式识别
L吗?我们能否将环顾四周和嵌套引用结合起来,并提供一种适用于例如
String.matches 匹配
ab
aabb
aaabbb等字符串吗?

引用文献

  • perlfaq6: Can I use Perl regular expressions to match balanced text?
  • MSDN - Regular Expression Language Elements - Balancing Group Definitions
  • pcre.org - PCRE man page
  • regular-expressions.info-LookaroundsGrouping and Backreferences
  • java.util.regex.Pattern
  • 相关问题

  • Does lookaround affect which languages can be matched by regular expressions?
  • .NET Regex Balancing Groups vs PCRE Recursive Patterns
  • 解决方案如下:

    答案是不用说,是的!您当然可以编写Java正则表达式模式来匹配anbn。它使用肯定的前瞻性进行断言,并使用一个嵌套的引用进行“计数”。
    该答案不是立即给出模式,而是将引导读者完成其推导过程。随着解决方案的逐步构建,给出了各种提示。在这方面,希望这个答案将不仅仅包含另一种整洁的正则表达式模式。希望读者还将学习如何“思考正则表达式”,以及如何将各种结构和谐地组合在一起,以便他们将来可以自己衍生出更多模式。
    为简洁起见,用于开发解决方案的语言将是PHP。模式完成后的最终测试将用Java完成。

    步骤1:先行断言
    让我们从一个简单的问题开始:我们要在字符串的开头匹配a+,但前提是它紧跟在b+之后。我们可以使用^来匹配我们的匹配项,并且由于我们只想匹配a+而没有b+,因此可以使用anchor断言(?=…)
    这是带有简单测试工具的模式:

    function testAll($r, $tests) {
       foreach ($tests as $test) {
          $isMatch = preg_match($r, $test, $groups);
          $groupsJoined = join('|', $groups);
          print("$test $isMatch $groupsJoined\n");
       }
    }
     
    $tests = array('aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb');
     
    $r1 = '/^a+(?=b+)/';
    #          └────┘
    #         lookahead
    
    testAll($r1, $tests);
    

    输出为(
    lookahead):

    aaa 0
    aaab 1 aaa
    aaaxb 0
    xaaab 0
    b 0
    abbb 1 a
    

    这正是我们想要的输出:我们匹配
    a+,只要它在字符串的开头,并且仅在它后面紧跟
    b+即可。


    类(class):您可以在环视环境中使用模式进行断言。

    第2步:提前捕获(以及f-e-s a p c c n g模式)

    现在让我们说,即使我们不希望
    b+成为比赛的一部分,我们还是希望将
    as seen on ideone.com归入第1组。此外,由于我们期望使用更复杂的模式,因此我们对
    capture使用
    x修饰符,因此我们可以使我们的正则表达式更具可读性。

    在之前的PHP代码段的基础上,我们现在具有以下模式:

    $r2 = '/ ^ a+ (?= (b+) ) /x';
    #             │   └──┘ │
    #             │     1  │
    #             └────────┘
    #              lookahead
     
    testAll($r2, $tests);
    

    现在的输出是(
    free-spacing):

    aaa 0
    aaab 1 aaa|b
    aaaxb 0
    xaaab 0
    b 0
    abbb 1 a|bbb
    

    请注意,例如
    aaa|b
    join的结果-将每个组用
    '|'捕获的内容。在这种情况下,第0组(即模式匹配的内容)捕获了
    aaa,而第1组捕获了
    b


    类(class):您可以在环顾范围内进行捕获。您可以使用自由间距来增强可读性。

    步骤3:将前瞻重构为“循环”

    在介绍计数机制之前,我们需要对我们的模式进行一次修改。当前,前瞻位于
    +重复“循环”之外。到目前为止,这还不错,因为我们只是想断言
    b+后面有一个
    a+,但是最终我们真正想做的是断言对于在“循环”中匹配的每个
    a,都有一个对应的
    b与之对应。 。

    现在不用担心计数机制,只需按如下所示进行重构即可:

  • 首先将a+重构为(?: a )+(请注意(?:…)是一个非捕获组)
  • 然后在该非捕获组中移动前瞻
  • 注意,现在我们必须“跳过” a*,然后才能“看到” b+,因此请相应地修改模式
  • 因此,我们现在有以下内容:

    $r3 = '/ ^ (?: a (?= a* (b+) ) )+ /x';
    #          │     │      └──┘ │ │
    #          │     │        1  │ │
    #          │     └───────────┘ │
    #          │       lookahead   │
    #          └───────────────────┘
    #           non-capturing group
    

    输出与之前的相同(
    as seen on ideone.com),因此在这方面没有任何变化。重要的是,现在我们在
    +“循环”的每次迭代中都进行断言。使用我们当前的模式,这不是必需的,但是接下来,我们将使用自引用为我们使组1“计数”。


    类(class):您可以在非捕获组中捕获。环顾四周可以重复。

    步骤4:这是我们开始计算的步骤

    这是我们要做的事情:我们将重写第1组,以便:

  • +的第一次迭代结束时,当第一个a匹配时,它应捕获b
  • 在第二个迭代的末尾,当另一个a与之匹配时,它应捕获bb
  • 在第三次迭代结束时,它应该捕获bbb
  • ...
  • 在第n次迭代结束时,第1组应捕获bn
  • 如果没有足够的b捕获到组1中,则声明将失败
  • 因此,第1组现在是
    (b+),将必须重写为类似
    (\1 b)的内容。也就是说,我们尝试将
    b“添加”到上一次迭代中捕获的第1组。

    这里存在一个小问题,因为该模式缺少“基本情况”,即在没有自引用的情况下可以匹配的情况。需要基本情况​​,因为组1开始“未初始化”;它尚未捕获任何内容(甚至不是空字符串),因此自引用尝试将始终失败。

    有很多解决方法,但是现在让我们使自引用匹配
    as seen on ideone.com,即
    \1?。这可能成功也可能不完美,但是让我们看看它能做什么,如果有任何问题,那么我们将在那座桥上过桥。另外,在进行测试时,我们将添加更多测试用例。

    $tests = array(
      'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb'
    );
     
    $r4 = '/ ^ (?: a (?= a* (\1? b) ) )+ /x';
    #          │     │      └─────┘ | │
    #          │     │         1    | │
    #          │     └──────────────┘ │
    #          │         lookahead    │
    #          └──────────────────────┘
    #             non-capturing group
    

    现在的输出是(
    optional):

    aaa 0
    aaab 1 aaa|b        # (*gasp!*)
    aaaxb 0
    xaaab 0
    b 0
    abbb 1 a|b          # yes!
    aabb 1 aa|bb        # YES!!
    aaabbbbb 1 aaa|bbb  # YESS!!!
    aaaaabbb 1 aaaaa|bb # NOOOOOoooooo....
    

    哈!看来我们现在真的很接近解决方案!我们设法通过自我引用使第1组“计数”!但是等等...第二个和最后一个测试用例出了点问题!
    b不够,以某种方式它算错了!我们将在下一步研究为什么会发生这种情况。


    类(class):“初始化”自引用组的一种方法是使自引用匹配为可选。

    步骤4½:了解出了什么问题

    问题在于,由于我们将自引用匹配设为可选,因此当
    b不足时,“计数器”可以“重置”为0。让我们用
    aaaaabbb作为输入来仔细检查模式的每次迭代会发生什么。

     a a a a a b b b
    ↑
    # Initial state: Group 1 is "uninitialized".
               _
     a a a a a b b b
      ↑
      # 1st iteration: Group 1 couldn't match \1 since it was "uninitialized",
      #                  so it matched and captured just b
               ___
     a a a a a b b b
        ↑
        # 2nd iteration: Group 1 matched \1b and captured bb
               _____
     a a a a a b b b
          ↑
          # 3rd iteration: Group 1 matched \1b and captured bbb
               _
     a a a a a b b b
            ↑
            # 4th iteration: Group 1 could still match \1, but not \1b,
            #  (!!!)           so it matched and captured just b
               ___
     a a a a a b b b
              ↑
              # 5th iteration: Group 1 matched \1b and captured bb
              #
              # No more a, + "loop" terminates
    

    哈!在第四次迭代中,我们仍然可以匹配
    \1,但是我们不能匹配
    \1b!由于我们允许使用
    \1?对自引用进行匹配,因此引擎回溯并采用了“不用了,谢谢”选项,然后允许我们仅对
    b进行匹配和捕获!

    但是请注意,除了第一次迭代外,您始终可以只匹配自引用
    \1。当然,这很明显,因为这是我们在上一次迭代中捕获的,并且在我们的设置中,我们始终可以再次对其进行匹配(例如,如果上次捕获
    bbb,我们可以确保仍然存在
    bbb,但是在那里这次可能不是
    bbbb)。


    类(class):提防回溯。正则表达式引擎将尽您所能进行尽可能多的回溯,直到给定的模式匹配为止。这可能会影响性能(即
    as seen on ideone.com)和/或正确性。

    第5步:自救!

    现在,“修复”应该很明显:将可选重复与
    catastrophic backtracking量词结合在一起。也就是说,不要简单地使用
    ?,而应使用
    ?+(请记住,量化为所有格的重复不会后退,即使这种“合作”可能导致整体模式匹配)。

    用非常非正式的术语来说,这是
    ?+
    ?
    ??所说的:

    ?+

    • (optional) "It doesn't have to be there,"
      • (possessive) "but if it is there, you must take it and not let go!"

    ?

    • (optional) "It doesn't have to be there,"
      • (greedy) "but if it is you can take it for now,"
        • (backtracking) "but you may be asked to let it go later!"

    ??

    • (optional) "It doesn't have to be there,"
      • (reluctant) "and even if it is you don't have to take it just yet,"
        • (backtracking) "but you may be asked to take it later!"

    在我们的设置中,
    \1不会在第一时间出现,但是在那之后的任何时间都将永远存在,因此我们总是想匹配它。因此,
    \1?+将完全完成我们想要的工作。

    $r5 = '/ ^ (?: a (?= a* (\1?+ b) ) )+ /x';
    #          │     │      └──────┘ │ │
    #          │     │          1    │ │
    #          │     └───────────────┘ │
    #          │         lookahead     │
    #          └───────────────────────┘
    #             non-capturing group
    

    现在的输出是(
    possessive):

    aaa 0
    aaab 1 a|b          # Yay! Fixed!
    aaaxb 0
    xaaab 0
    b 0
    abbb 1 a|b
    aabb 1 aa|bb
    aaabbbbb 1 aaa|bbb
    aaaaabbb 1 aaa|bbb  # Hurrahh!!!
    

    哎呀!问题解决了!!!现在,我们正按照我们想要的方式正确计数!


    类(class):了解贪婪,勉强和所有格重复之间的区别。可选拥有可能是强大的组合。

    步骤6:画龙点睛

    因此,我们现在所拥有的是一个重复匹配
    a的模式,对于每个匹配的
    a,在组1中都会捕获到一个对应的
    b。当不再有
    +或断言由于存在而断言失败时,
    a终止。没有对应的
    b

    为了完成这项工作,我们只需要在我们的模式
    a后面追加。现在,这是对第1组匹配项的后向引用,后面是行 anchor 的末尾。 anchor 确保字符串中没有多余的
    \1 $;换句话说,实际上我们有abn。

    这是最终确定的模式,其中包含其他测试用例,其中包括一个10,000个字符长的用例:

    $tests = array(
      'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb',
      '', 'ab', 'abb', 'aab', 'aaaabb', 'aaabbb', 'bbbaaa', 'ababab', 'abc',
      str_repeat('a', 5000).str_repeat('b', 5000)
    );
     
    $r6 = '/ ^ (?: a (?= a* (\1?+ b) ) )+ \1 $ /x';
    #          │     │      └──────┘ │ │
    #          │     │          1    │ │
    #          │     └───────────────┘ │
    #          │         lookahead     │
    #          └───────────────────────┘
    #             non-capturing group
    

    它找到4个匹配项:
    b
    ab
    aabb和a5000b5000。它需要
    as seen on ideone.com

    步骤7:Java测试

    因此该模式可在PHP中运行,但最终目标是编写一种可在Java中运行的模式。

    public static void main(String[] args) {
     
            String aNbN = "(?x) (?:  a  (?= a* (\\1?+ b))  )+ \\1";
            String[] tests = {
                    "",      // false
                    "ab",    // true
                    "abb",   // false
                    "aab",   // false
                    "aabb",  // true
                    "abab",  // false
                    "abc",   // false
                    repeat('a', 5000) + repeat('b', 4999), // false
                    repeat('a', 5000) + repeat('b', 5000), // true
                    repeat('a', 5000) + repeat('b', 5001), // false
            };
            for (String test : tests) {
                    System.out.printf("[%s]%n  %s%n%n", test, test.matches(aNbN));
            }
     
    }
     
    static String repeat(char ch, int n) {
            return new String(new char[n]).replace('\0', ch);
    }
    

    该模式按预期方式工作(
    only 0.06s to run on ideone.com)。

    现在我们得出结论...

    需要说的是,前瞻中的
    aaabbb以及实际上的“主
    a*循环”都允许回溯。鼓励读者确认为什么这不是正确性方面的问题,以及为什么同时拥有所有格也行得通(尽管也许将强制性和非强制性所有格量词以相同的方式混合使用可能会导致误解)。

    还应该说,虽然整洁的是有一个匹配abn的正则表达式模式,但这实际上并非总是“最佳”解决方案。更好的解决方案是简单地匹配
    +,然后在托管编程语言中比较第1组和第2组捕获的字符串的长度。

    在PHP中,可能看起来像这样(
    as seen on ideone.com):

    function is_anbn($s) {
       return (preg_match('/^(a+)(b+)$/', $s, $groups)) &&
          (strlen($groups[1]) == strlen($groups[2]));
    }
    

    本文的目的不是要说服读者相信正则表达式几乎可以做任何事情;它显然不能,甚至可以做到,但如果可以导致更简单的解决方案,则至少应考虑对托管语言的部分委派。

    如顶部所述,尽管本文必须为stackoverflow标记为
    ^(a+)(b+)$,但可能不止于此。虽然学习断言,嵌套引用,所有格限定符等当然有值(value),但也许更大的一课是创造性的过程,通过该过程人们可以尝试解决问题,遇到困难时通常需要做出的确定和努力工作各种约束,从各个部分的系统组成,以建立有效的解决方案,等等。

    奖金 Material ! PCRE递归模式!

    由于我们确实提出了PHP,因此需要说PCRE支持递归模式和子例程。因此,以下模式适用于
    [regex](
    as seen in ideone.com):

    $rRecursive = '/ ^ (a (?1)? b) $ /x';
    

    当前,Java的正则表达式不支持递归模式。

    更多的奖励 Material !配套abncn!

    因此,我们已经看到了如何匹配非常规的,但仍然与上下文无关的abn,但是我们还可以匹配甚至不是与上下文无关的abncn吗?

    答案是肯定的!鼓励读者尝试自己解决这个问题,但是下面提供了解决方案(带有
    as seen on ideone.com)。

    preg_match