Можем ли мы использовать кванторы внутри выражения lookbehind?

Question

Этот вопрос относится только к Java 7/8.

довольно сложное регулярное выражение, которое использует кванторы запрещены внутри Утверждения касательно предшествующего текста, такие как эта:

(?<=(a|b*)*)bc 

как это приводит к исключению во время выполнения с сообщением вроде:

look-behind group does not have obvious maximum length error 

Я угадывание это потому, что кванторы, такие как * и +, «вообще» не допускаются.

Однако следующая работа делает:

(?<=a*)bc 

Почему это так?

Есть аналогичные сообщения об этой проблеме на SO:

1. Для других языков: ruby, PCRE etc-

2. Некоторые сообщения являются специфическими для Java, но, кажется, не представляют собой конкретные ответы или ссылки, такие как this. В большинстве случаев ответы на эти кванторы просто не могут быть использованы. Кроме того, сайт regular-expressions утверждает то же самое.

3. This post утверждает, что у Java есть ошибки, связанные с реализацией.

Однако пример, который я показал выше, что использует ноль или много квантор * внутри назад 'справедливо для Java 7/8.

Любые ссылки или пояснения будут полезны.

Answer 1

Просмотрев код Pattern и попытавшись его проследить, я убежден, что это всего лишь ошибка. Оба примера должны привести к исключению. Но логика, которая проверяет это, неверна.

Этот код появляется в паре мест:

temp = info.maxLength * cmax + maxL; 
info.maxLength = temp; 
if (temp < maxL) { 
    info.maxValid = false; 
} 

Обратите внимание, что до тех пор, как maxLength и cmax неотрицательны, temp никогда не должно быть меньше, чем maxL, если переполнение не произошло. maxValid в конечном итоге используется кодом lookbehind; если maxValid is false, "look-behind group does not have obvious maximum length error" бросается.

Из того, что я могу сказать, в регулярном выражении, как < префикса>< выражения>{m,n}, в приведенной выше коде, info.maxLength максимальная длина «выражение», cmax является верхней границей квантора, и maxL - максимальная длина «префикса». Когда квантификатор равен * или +, верхняя граница установлена ​​на Integer.MAX_VALUE.(Все переменные здесь int.) Это означает, что будет переполнение , если только info.maxLength не является 1 и maxL является 0. Это именно тот случай с

(?<=a*)bc 

, так как модель с квантором имеет длину 1, и нет ничего перед a* что означает maxL будет 0. Именно поэтому этот случай падает через трещину.

Для любых других значений вычисление будет переполняться, но это не обязательно означает, что temp < maxL будет истинным. Если info.maxLength четное, тогда будет выбрано исключение; но если info.maxLength нечетно, образец будет скомпилирован, если maxL достаточно мал. Это связано с тем, как математика работает; код, который пытается проверить переполнение, является довольно ошибочным. Это означает, что

(?<=a*)bc   // succeeds 
(?<=(ab)*)bc  // throws exception 
(?<=(abc)*)bc  // succeeds 
(?<=(abcd)*)bc // throws exception 
(?<=(abcde)*)bc // succeeds 

также:

(?<=xa*)bc  // throws exception 
(?<=x(abc)*)bc // succeeds 

Примечание: Следует отметить, что в вашем примере регулярное выражение, с просмотром назад бесполезно:

(?<=a*)bc 

просмотра назад, говорит проверить, является ли текущему местоположению предшествует ноль или более символов в письме a. Это всегда верно, тривиально. Таким образом, lookbehind не имеет никакой цели здесь. Точно так же,

(?<=a+)bc 

эквивалентно

(?<=a)bc 

так до тех пор, пока есть один a предшествующий текущее местоположение, это не имеет значения, сколько еще там может быть. То же самое можно сказать и о всех примерах, которые не сгенерирует исключение, для этого, кроме одного:

(?<=x(abc)*)bc // succeeds 

, поскольку здесь сличитель действительно должна идти в обратном направлении ищет abc-х в строке, и убедившись, что последний одному предшествует x. Похоже, что Pattern должен исключать исключение в этом случае, но из-за ошибочной логики проверки переполнения это не так. Поэтому я не уверен, вернет ли он правильный результат, или может ли он произойти сбой или перейти в бесконечный цикл. Однако я не пробовал.

Действительно, код должен непосредственно проверять, равен ли cmaxInteger.MAX_VALUE, вместо того чтобы использовать его в вычислении и надеясь, что код может позже сказать, что результат фиктивный.