代码之家 › 专栏 › 技术社区 › polygenelubricants

为什么Java正则表达式引擎在+重复时抛出StringIndexOutfoundsException?

nested-reference fibonacci regex java

16

polygenelubricants · 技术社区 · 14 年前

我已经编写了一个regex模式来查找fibonacci数(这不重要,我只是做了)。它的工作和预期的一样出色( see on 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

一个 possessive 重复(即 ++ 在主“循环”)上是至关重要的,因为您不希望使用此匹配算法进行回溯。但是,使重复可追溯(即 + 在主“循环”)中不会导致不匹配,而是运行时异常!!!( as seen on 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正则表达式引擎中的错误吗?

1 回复 | 直到 14 年前

1

11

randers 9 年前

错误ID 6984178

有许多与引擎抛掷有关的错误 StringIndexOutOfBoundsException ( see: search results 是的。特别是这一个已经被报告和内部接受为 Bug ID 6984178 (这可能需要一段时间才能显示在外部数据库中)。

这里有一个更简单的模式来复制这个bug( see also on ideone.com ):

System.out.println(
   "abaab".matches("(?x) (?: (?=(a+)) \\1 b )* x")
); // StringIndexOutOfBounds: -1

注意使用 *? 或 *+ 简单的回报 false 如预期。

看起来这个问题是由于当前面有一个捕获组的引用时,试图回溯贪婪的重复而触发的:越界索引是第一个和第二个之间的长度差 a+ (例如 "aabaaaaab" 得到 -3 )中。

可能需要调试 java.util.regex.Pattern source code 以确定错误的确切性质。

探索斐波那契模式

基于贪婪回溯的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);
    }
}

(稍微编辑过的)输出是( as seen on 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等处的字符串索引。请注意,这些都是其他斐波那契数,但都是负数。还要注意,除了前几个数字之外,其余的匹配项(6、14、35,…)是不是斐波那契数。

在.NET引擎上,带有贪婪回溯 `+`

虽然模式最初是在考虑所有格量词的必要性的情况下编写的,但事实上,回溯重复仍然会给出正确的答案(假设引擎不像java那样有缺陷)。下面是在.NET引擎上的C实现( see also on 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} ( see also on ideone.com )以下内容:

String FIBONACCI = 
        "(?x) .{0,1} | (?: (?=(\\2|^)) (?=(\\2\\3|^.)) (?=(\\1)) \\2)+? . ";

关于算法

公式

模式利用了 Second Identity of Fibonacci Numbers 以下内容:

alt text

这可以通过归纳法来证明。

模式

让我们使用这个版本的模式(它在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")

fibonacci序列的生成是直接的,基于 [$1, $2] := [$2, $2+$1] 过渡。由于断言是按顺序执行的,所以引入了一个临时变量(就像单个赋值的“伪代码”版本一样)。