Почему/\ w +:/и/\ S +:/обрабатывают обратное отслеживание по-разному?

Я проанализировал эти два регулярных выражения, используя regex101. Я думаю, что обратный путь /\S+:/ прав. Но я не понимаю этой разницы. Я не прав?

regex101.com

Ответы

Ответ 1

Хотя это кажется специфичным для реализации (RegexBuddy не показывает этого поведения), его можно объяснить следующим образом:

\w не может соответствовать :, но \S может. Таким образом, \S+: нужно проверить больше вариантов входной строки, прежде чем убедиться, что get не может ее сопоставить.

Более оптимизированные двигатели регулярных выражений быстрее исключают невозможные совпадения (например, когда регулярное выражение содержит буквенный символ, отсутствующий в текущей части совпадения), но, видимо, движок, который использует regex101, не делает этого.

Ответ 2

Это pcre оптимизация auto-possessification.

Из http://pcre.org/pcre.txt:

Оптимизация "автоматическое обладание" PCRE обычно применяется к символ повторяется в конце рисунка (а также внутри). Для Например, шаблон "a\d+" скомпилирован, как если бы он был "a\d++", потому что нет смысла даже рассматривать возможность отступления в повторяющиеся цифры.

и

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

Так как : не включен в \w, ваш шаблон интерпретируется как \w++: (второй + предотвращает обратное слежение, видеть притяжательный кванторы). Дополнительные состояния обратного отслеживания исключаются из-за отсутствия другого состояния, в котором он мог бы совпадать.

С другой стороны, : включен в \S, поэтому эта оптимизация не применяется для второго случая.

PCRETEST

Вы можете увидеть разницу, используя pcretest (там версия Windows вы можете скачать здесь).

Образец /\w+:/ занимает 11 шагов и выводит:

/\w+:/
--->get accept:
 +0 ^               \w+
 +3 ^  ^            :
 +0  ^              \w+
 +3  ^ ^            :
 +0   ^             \w+
 +3   ^^            :
 +0    ^            \w+
 +0     ^           \w+
 +3     ^     ^     :
 +4     ^      ^    .*
 +6     ^      ^    
 0: accept:

Однако, если мы используем контрольный глагол (*NO_AUTO_POSSESS), который отключает эту оптимизацию, шаблон /(*NO_AUTO_POSSESS)\w+:/ принимает 14 шагов и выводит:

/(*NO_AUTO_POSSESS)\w+:/
--->get accept:
+18 ^               \w+
+21 ^  ^            :
+21 ^ ^             :
+21 ^^              :
+18  ^              \w+
+21  ^ ^            :
+21  ^^             :
+18   ^             \w+
+21   ^^            :
+18    ^            \w+
+18     ^           \w+
+21     ^     ^     :
+22     ^      ^    .*
+24     ^      ^    
 0: accept:

- на 1 шаг меньше \S+, как и ожидалось, потому что \w+ не соответствует :.

К сожалению regex101 не поддерживает этот глагол.

Обновление: regex101 теперь поддерживает этот глагол, здесь ссылка на 3 случая для сравнения:

regex101 отладчик:

regex101.com debugger