java - 使用正则匹配a^xb^x，其中x为a,b出现的次数

Question

澄清一下，我想知道如何使用正则表达式来匹配:

ab
aabb
aaabbb 
...

我刚刚发现这在 Perl 中有效:

if ($exp =~ /^(a(?1)?b)$/)

要理解这一点，请看一下字符串，就好像它是从外向内生长的，而不是从左向右生长的:

ab
a(ab)b
aa(ab)bb

(?1) 是对外括号组的引用。对于最后一种情况(从外向内)，我们需要 ? 之后，什么都没有留下， ? 表示前面表达式的 0 或 1(因此它基本上充当我们的基本情况)。

我的问题是:Java 中 (?1) 的等价物是什么？

Answer 1

一般而言，正则表达式仅限于正则语言，这意味着由于它们等同于 DFA(离散有限自动机)可接受的语言，因此它们不能计数，因为广义计数需要无限数量的状态来表示无限数量的可能计数值。

由于 discrete != infinte，您无法真正计数，但您可以进行一些有限类型的匹配，例如您的 (a (something) b) 示例。

讨论 DFA 的一些局限性(以及扩展的正则语言/正则表达式) http://www.cs.washington.edu/education/courses/cse599/99sp/admin/Slides/Week2/sld012.htm

一张更好但更冗长的幻灯片，它通过进入 DFA 的(仍然有点高级)细节来扩展限制 http://www.cs.princeton.edu/courses/archive/spr05/cos126/lectures/18.pdf

顺便说一句，由内而外的扩展是一个很酷的 DFA 技巧，它基本上通过使用恰好重建字符串镜像的模式匹配来回避实际的计数需求。它看起来像计数，但一旦你做了更多有趣的事情就会分崩离析，比如要求按顺序匹配(而不是镜像顺序匹配)。