Использование вертикальной табы(\v), жадных(Greedy) и супержадных выражений

#регулярные_выражения

Что такое вертикальная таба \v?
Чем супержадный метод отличается от жадного?
Аналогично для нежадного.

Не надо меня отсылать к гуглу (или lmgfy). Если хочется послать, пошлите лучше на
"natribu" или на конкретный сайт с описанием проблемы для трехлетних кодеров.
Ибо в наиболее популярных ресурсах я прочел, но ничего не понял. Особенно с табой.    

Ответы

Ответ 1

Пример входных данных:

123 123


Цель: найти совпадение между угловыми скобками (неважно, какими, суть в том, чтобы
посмотреть на разницу в поведении).

Используем нежадный (ленивый, lazy) квантификатор: 
В этом случае движок регулярных выражений будет в буквальном смысле стараться "отделаться
побыстрее". Как будет происходить поиск: 


нашли 
символ a - черт, придется возвращаться назад, опять подбираем под .*, но уже начиная с a
a подходит под .* - и хватит, подбираем под >
символ t - черт... - 


и так далее, с постоянным откатами назад. 
Результат: 

Используем жадный (greedy) квантификатор: 
Движок будет пытаться подобрать побольше символов под каждый квантификатор и производить
откаты только если совпадение не найдено:


нашли 123 123 - все, нечего больше
добавить, идем дальше
подбираем под > - а текста-то уже нету. Придется откатываться назад - переходим на
символ назад и подбираем >
след. символ > - подходит под >. Текст закончился, паттерн закончился


Результат: 123 123

Используем супержадный (ревнивый, possessive) квантификатор: 
Откаты не будут производиться вообще:


нашли 123 123 - все, нечего еще добавить,
идем дальше
подбираем под > - а текста-то уже нету. Пофиг, пути назад нет


совпадений нет.

А на счет вертикальной табуляции - так это же просто управляющий символ, такой же
как \n или \t. К регулярным выражениям прямого отношения не имеет. Раньше использовался
в принтерах - деталей точных не знаю, но олдфаги помнят. Таким образом, \v просто ищет
наличие этого символа в строке.

UPD. (комментарий к @knes и @Valeriy Karchov)

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

Здесь приводится хоть и искусственный, но показательный пример: применяем паттерн
(x+x+)+y к строке вида xxxxxxxxxxy. Если y в конце есть, то ОК, произойдет только один
откат (когда будет искаться совпадение для второго x+) и дело сделано. Но вот если
y в конце нет, то движок будет натужно перебирать все возможные комбинации. Так, у
меня на машине этот поиск (Java) в строке из 19-ти x занял 2 секунды. С другой стороны,
очевидно же, что если какой-либо участок был проматчен с (x+x+)+, то y там точно нет.
Это означает, что мы может установить сверхжадный квантификатор: (x+x+)++y - так как
мы точно знаем, что откат не приведет к нахождению y.

Таким образом, сверхжадные квантификаторы можно использовать в случаях, когда выражение
под квантификатором не может заглотнуть символы, которые предполагалось вытащить следующим
за квантификатором выражением. В ситуациях с неподходящими входными данными это позволит
быстрее определить, что совпадения нет. Так, некоторые движки регулярных выражений
даже определяют ситуации типа [^x]+x и подставляют туда сверхжадный квантификатор.