为什么Java正则表达式引擎会在+重复上抛出StringIndexOutOfBoundsException？
我写了一个正则表达式模式来找到Fibonacci数字（没关系，为什么，我刚刚做了）。 它按预期工作得非常好（ 参见ideone.com ）：
String FIBONACCI = "(?x) .{0,2} | (?: (?=(\\2?)) (?=(\\2\\3|^.)) (?=(\\1)) \\2)++ . "; for (int n = 0; n < 1000; n++) { String s = new String(new char[n]); if (s.matches(FIBONACCI)) { System.out.print(n + " "); } } // 0 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 占有重复（即主循环上的++ ）是至关重要的，因为您不希望使用此匹配算法进行回溯。 但是，使重复回溯（即在主“循环”上只是+ ）不会导致不匹配，而是导致运行时exception！ （ 如ideone.com上所示 ）：
Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: -1 at java.lang.String.charAt(String.java:686) at java.lang.Character.codePointAt(Character.java:2335) at java.util.regex.Pattern$CharProperty.match(Pattern.java:3344) at java.util.regex.Pattern$GroupCurly.match0(Pattern.java:3994) at java.util.regex.Pattern$GroupCurly.match0(Pattern.java:3966) at java.util.regex.Pattern$GroupCurly.match(Pattern.java:3916) at java.util.regex.Pattern$Branch.match(Pattern.java:4114) at java.util.regex.Matcher.match(Matcher.java:1127) at java.util.regex.Matcher.matches(Matcher.java:502) at java.util.regex.Pattern.matches(Pattern.java:930) at java.lang.String.matches(String.java:2090)
有人可以解释这里发生了什么吗 这是Java正则表达式引擎中的错误吗？
错误ID 6984178
有很多与StringIndexOutOfBoundsException的引擎相关的错误（ 请参阅：搜索结果 。特别是已报告此内容并在内部接受为错误ID 6984178 （可能需要一段时间才能显示在外部数据库中）。
这是一个更简单的模式，可以重现bug（ 另请参见ideone.com ）：
System.out.println( "abaab".matches("(?x) (?: (?=(a+)) \\1 b )* x") ); // StringIndexOutOfBounds: -1
注意使用*? 或*+只是按预期返回false 。
看起来问题是由于在前瞻中有一个对捕获组的引用而尝试回溯贪婪的重复：超出范围索引是第一个和第二个a+之间的长度差异（例如"aabaaaaab"获得-3 ）。
人们可能不得不调试java.util.regex.Pattern源代码来查明错误的确切性质。
探索斐波那契模式
在Java引擎上，使用贪婪的回溯+
这里有一个更详细的片段，展示了引擎如何在这种模式下获得加速：
String FIBONACCI = "(?x) .{0,2} | (?: (?=(\\2|^)) (?=(\\2\\3|^.)) (?=(\\1)) \\2)+ . "; for (int n = 0; n < 1000; n++) { String s = new String(new char[n]); try { if (s.matches(FIBONACCI)) { System.out.printf("%n%s", n); } } catch (StringIndexOutOfBoundsException e) { String index = e.getMessage().replace("String index out of range: ", ""); System.out.printf(" <%s:%s>", n, index); } }
（略微编辑的）输出（ 如ideone.com上所示 ）：
0 1 2 3 <5:-1> 6 <7:-1> ... <12:-1> <13:-3> 14 <15:-3> ... <33:-3> <34:-8> 35 <36:-8> ... <88:-8> <89:-21> 90 <91:-21> ... <232:-21> <233:-55> 234 <235:-55> ... <609:-55> <610:-144> 611 <612:-144> ...
所以引擎试图以-1，-3，-8，-21，-55，-144等方式访问字符串索引。请注意，这些是其他每个Fibonacci数，但是为负数。 另请注意，除了前几个数字之外，其余的匹配（6,14,35，…）都不是斐波纳契数。
在.NET引擎上，贪婪的回溯+
尽管该模式最初是在考虑占有性量词的必要性的情况下编写的，但实际上回溯重复仍将产生正确的答案（假设引擎不像Java那样错误）。 这是.NET引擎上的C＃实现（ 另请参见ideone.com ）：
Regex r = new Regex( @"(?x) ^.{0,1}$ | ^(?: (?=(\2?)) (?=(\2\3|^.)) (?=(\1)) \2)+ . $ " ); for (int n = 0; n < 1000; n++) { if (r.IsMatch("".PadLeft(n))) { Console.Write("{0} ", n); } } // 0 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987
正如您所看到的，即使使用回溯+ “循环”，输出也是正确的。 事实上，正是因为它是一个回溯循环，特殊情况可以仅限于.{0,1}而不是.{0,2} 。
在Java引擎上，不情愿的回溯+?
这可以按预期在Java中使用。 此外，因为它不情愿，我们也可以将特殊情况限制为.{0,1} （ 另见ideone.com ）：
String FIBONACCI = "(?x) .{0,1} | (?: (?=(\\2|^)) (?=(\\2\\3|^.)) (?=(\\1)) \\2)+? . ";
关于算法
公式
该模式利用斐波纳契数的第二个同一性 ：
这可以通过归纳certificate。
模式
让我们使用这个版本的模式（在Java中工作，锚定时也适用于C＃）：
summation free-space! "loop" ↓ ↓ (?x) .{0,1} | (?: (?=(\2|^)) (?=(\2\3|^.)) (?=(\1)) \2)+? . \____/ \___________________________________/ ↑ ↑ base case inductive case +Fi +1 for n = 0,1 (assertions don't "count" toward sum)! $1 := $2 (or initialized with 0) $2 := $2+$3 (or initialized with 1) $3 := $1 (a temporary variable for the "swap")
基于[$1, $2] := [$2, $2+$1]转换，Fibonacci序列生成很简单。 由于断言是按顺序执行的，因此引入了临时变量（就像单指派“伪代码”版本一样）。