Я написал шаблон регулярного выражения, чтобы найти числа Фибоначчи (неважно, почему, я только что сделал). Он отлично работает, как ожидалось (см. на ideone.com):

A possessive повторение (т.е. ++ в основном "цикле" ) имеет решающее значение, потому что вы не хотите возвращаться с этот алгоритм сопоставления. Тем не менее, при повторном выполнении повторения (т.е. Просто + в основном "цикле" ) результаты не совпадают с несоответствиями, а скорее исключение во время выполнения!!! (как видно на ideone.com):

Может кто-нибудь объяснить, что здесь произошло? Является ли это ошибкой в ядре Java regex engine?

Ответы

Ответ 1

Идентификатор ошибки 6984178

Есть много ошибок, связанных с броском двигателя StringIndexOutOfBoundsException (см.: результаты поиска. Это, в частности, было сообщено и внутренне принято как Идентификатор ошибки 6984178 (это может занять некоторое время, чтобы это отображалось во внешней базе данных).

Здесь гораздо более простой шаблон, воспроизводящий ошибку (см. также на ideone.com):

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

Обратите внимание, что использование *? или *+ просто возвращает false, как ожидалось.

Похоже, что проблема вызвана попыткой отступить от жадного повторения, когда есть ссылка на группу захвата внутри lookahead: индекс вне границ - это разница в длине между первой и второй 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 и т.д. Обратите внимание, что это все остальные числа Фибоначчи, но отрицательные. Заметим также, что за пределами первых нескольких номеров остальные матчи (6, 14, 35,...) НЕ являются номерами Фибоначчи.

На движке .NET с жадным обратным следом `+`

В то время как шаблон был первоначально написан с необходимостью для обладателя квантификатора, на самом деле повторение обратного следа все равно даст правильный ответ (предполагая, что движок не глючит, как Java). Здесь реализация С# на движке .NET(см. Также на 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

Как вы можете видеть, результат корректный, даже при обратном цикле + "loop". Фактически, именно потому, что он является циклом обратного отслеживания, специальный случай может быть ограничен только .{0,1} вместо .{0,2}.

На движке Java с неохотным возвратом `+?`

Это работает на Java, как и ожидалось. Кроме того, поскольку он неохотно, мы можем также ограничить специальный случай просто .{0,1} (см. Также на ideone.com):

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

Об алгоритме

Формула

В шаблоне используется Вторая идентификация чисел Фибоначчи:

Это можно доказать индукцией.

Образец

Позвольте использовать эту версию шаблона (который работает в Java и когда он привязан, также работает на С#):

                                                     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]. Поскольку утверждения выполняются последовательно, вводится временная переменная (так же, как версия псевдокода с одним присваиванием).

Почему Java regex engine бросает StringIndexOutOfBoundsException на + повторение?