16

フィボナッチ数を見つけるための正規表現パターンを作成しました (理由は関係ありませんが、作成しただけです)。期待どおりに素晴らしく動作します ( 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

このマッチング アルゴリズムで後戻りをしたくないため、所有格の繰り返し (つまり、メインの「ループ」) は非常に重要です。++ただし、繰り返しをバックトラック可能にする (つまり+、メインの「ループ」のみ) と、不一致ではなく、実行時例外が発生します!!! ( 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 正規表現エンジンのバグですか?

4

1 に答える 1

11

バグ ID 6984178

エンジンのスローに関連する多くのバグがありますStringIndexOutOfBoundsException(検索結果 を参照してください。特にこれは、バグ ID 6984178として報告され、内部で受け入れられています(外部データベースに表示されるまでに時間がかかる場合があります)。

バグを再現するもっと単純なパターンを次に示します ( ideone.com も参照)。

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

*?orを使用すると、*+単に期待どおりに返されることに注意してくださいfalse。

この問題は、先読み内のキャプチャ グループへの参照がある場合に貪欲な繰り返しをバックトラックしようとする試みによって引き起こされるようです: 境界外インデックスは、最初と 2 番目の間の長さの差ですa+(例: "aabaaaaab"gets -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 などの文字列インデックスにアクセスしようとします。これらは 1 つおきのフィボナッチ数ですが、負であることに注意してください。また、最初のいくつかの数字を超えて、残りの一致 (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)+? . ";

アルゴリズムについて

式

このパターンは、フィボナッチ数の 2 番目の恒等式を利用します。

代替テキスト

これは帰納法で証明できます。

パターン

このバージョンのパターンを使用してみましょう (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]フィボナッチ数列の生成は、遷移に基づいて簡単です。アサーションは順次実行されるため、一時変数が導入されます (単一代入の「疑似コード」バージョンと同様)。

于 2010-09-13T09:56:26.147 に答える