Perl регулярные выражения: поиск образца максимального размера

Иногда может потребоваться найти то, что задано, но чтобы это найденное было побольше. Для начала разберём такой учебный примерчик: найти оператором m// в тексте первую наидлиннейшую последовательность 10-ных цифр, которые идут подряд и возрастают на 1. Например, если задана строка "23 456745678", то должна отыскаться подстрока 45678.

Если бы меня в детстве спросили: "Какой язык тебе больше нравится?", - я бы не задумываясь ответил: "Коровий с гречневой кашей!" Но сейчас я больше склоняюсь к Перлу: на каком ещё языке можно писать такие небольшие, но очень загадочные программки? И особенно в этом помогают динамические регулярные выражения, которые мы здесь и попробуем применить.

Динамическое регулярное выражение (??{ код Perl }) похоже на вставку кода Perl (?{ код Perl }) и отличается от неё лишним вопросительным знаком. Это код Perl, который каждый раз выполняется и каждый раз результат выполнения рассматривается как подшаблон, который подставляется на место данного динамического регулярного выражения, и каждый раз он компилируется во внутреннее представление. Это замедляет работу Perl регулярного выражения, но зато даёт большие возможности для сложного поиска, когда подшаблон можно создавать "на лету" в зависимости от результатов предыдущего поиска.

Общая идея поиска этой длиннейшей последовательности будет такая: захватываем очередную цифру (\d) и она тут же попадает в переменную $+. Мы её запоминаем: $d=$+ прибавляем к ней 1: ++$d и на лету создаём подшаблон (??{$d}) для очередной цифры. Так мы сможем захватить все цифры, которые возрастают на 1 и идут подряд. Но надо позаботиться, чтобы не выйти за цифру 9, и подумать, какой подшаблон подставить, если очередной символ в тексте уже не будет тем, что нам нужно. При получении из текста цифры 9 и вообще при окончании нужной нам последовательности цифр мы подставим замечательный подшаблон (?!), найденный Дж. Фридлом, автором книги "Регулярные выражения". Он означает "с этого места нет пустого фрагмента". Смысл этого подшаблона в том, что он ничему не соответствует, т.к. пустой фрагмент встречается в тексте всюду. Когда механизм поиска встречает подобный подшаблон, то он понимает, что текущий поиск оказался неудачным, и откатывается назад, если позади есть квантификаторы, "жадность" которых можно менять, а если их нет, то происходит инкрементация начальной позиции поиска. Ну, а если текущая позиция поиска находится в самом конце текста, то оператор поиска просто возвращает ложь.

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

#!/usr/bin/perl -w
use strict;

# Найти в $_ первую наидлиннейшую последовательность 10-ных цифр, которые возрастают на 1
# Автор Сергей Мельников. Сделано для сайта "Perl регулярные выражения, статьи вебмастеру"
# http://www.cronc.com/ru.shtml

my ($len,$d,$res,$p)=(0);
$_='01345';
#no warnings;

/((\d)                                   # Захватываем очередную цифру
   (?{$d=$+})                            # Запоминаем её в $d
    (?>                                  # Ликвидируем откаты назад (backtracking)
       (??{++$d < 10 ? "$d" : "(?!)"})*  # Подставляем нужный подшаблон
    )
 )
 (?{                                     # Эти символы нельзя разделять
#print "$1\n";                           # Отладочный вывод последовательности цифр
  if (length $1 > $len)                  # Эта последовательность длинее предыдущих?
   { $len=length $1;                     # Да, запоминаем её длину
     $res=$1;                            # И её саму
     $p=pos;                             # И смещение в тексте сразу за ней
   }
 })                                      # Эти скобки нельзя разделять
 (?!)                                    # Вынуждаем искать дальше
 /x;

if (defined $res)
 { print "$res pos=".($p-$len)."\n";     # Выводим результат и позицию его начала
 }

Вся текущая возрастающая последовательность собирается у нас в $1, а очередная цифра попадает в $2 и становится также доступной через переменную $+. Разберём, как работает динамическое регулярное выражение. В нём выбирается, какой подшаблон подставить: "$d" (следующая цифра в последовательности), или "(?!)" (текущий поиск завершился неудачей). "$d" подставляется, если в $+ находится цифра меньше 9, иначе подставляется "(?!)", который заставляет текущую позицию поиска в шаблоне выйти за квантификатор *. В Perl допускается ставить квантификатор к конструкциям "заглядывания вперёд" и назад, хотя смысл квантификатора здесь не совсем понятен: на человеческом языке (?!)* означает "с текущей позиции текста нет пустого фрагмента 0 или более раз". Philip Hazel, большой спец по регулярным выражениям и автор библиотеки PCRE (см. его сайт pcre.org), критикует эту вольность Perl и запрещает это в своей библиотеке. В предыдущих версиях Perl во время выполнения программы, когда конструировался подшаблон (?!)*, выдавал предупреждение

 (?!)* matches null string many times in regex; ...

а в версии 5.12, которую я сейчас использую, этого сообщения уже нет, поэтому я закомментировал директиву "no warnings;". Благодаря атомарной группировке (?> шаблон ), не возникает возврата в поиске из-за квантификатора *, и управление передаётся за закрывающую захватывающую скобку для $1 коду Perl, который проверяет длину очередной последовательности цифр, попавшей в $1, и запоминает, если надо, её в $res. Далее управление попадает на подшаблон (?!), что заставляет сделать инкрементацию начальной позиции поиска и искать, начиная со следующей цифры. Иначе мы бы находили не длиннейшую последовательность цифр, а первую попавшуюся.

Теперь давайте раскомментируем оператор print "$1\n"; и посмотрим, что напечатается:

 01
 1
 345
 45
 5
 345 pos=2
 

Видим, что сначала находится последовательность 01, она запоминается в $res, затем благодаря (?!) происходит инкрементация начальной позиции поиска и он возобновляется с цифры 1, но последовательность 1 отвергается кодом Perl, т.к. она короче уже найденной 01. Таким путём захватывается вся возрастающая последовательность цифр, а не её часть. Потом находится последовательность 345 и ещё исследуется её "хвост" 45 и 5, что, в общем, является лишним. Можно ли избавиться от этого "исследования хвостов"? Вряд ли, т.к. текущую позицию поиска в тексте, которая возвращается функцией pos, внутри регулярного выражения поменять не удастся. Эта функция допускает присваивание, но оно имеет эффект только за пределами регулярных выражений. Как ответил Василий Иванович на вопрос Петьки сможет ли он выпить цистерну спирта, "Нет Петька, такое только Ленину под силу".

А теперь для любопытства уберём или закомментируем скобки атомарной группировки (?> и соответствующую ей ) и посмотрим, что выдаст диагностическая печать:

 01
 0
 1
 345
 34
 3
 45
 4
 5
 345 pos=2

Мы видим, что объём лишней выполняемой работы возрос за счёт перебора с возвратами. После того, как в $2 попала цифра 1, динамическое регулярное выражение подставило подшаблон "2", который не нашёл соответствия тексту. Механизм регулярных выражений сказал: "Не беда, у квантификатора * есть сохранённое состояние, я уменьшу его "жадность" до 0 захватываемых символов и откачусь назад, авось что-то и найдётся". Оно действительно находится, но встроенный код Perl отвергает эту находку и происходит инкрементация начальной позиции поиска.

Обратите внимание, что построенный нами оператор m/// всегда возвращает ложь, поэтому его бесполезно вставлять в условие оператора if. Наш оператор m/// используется исключительно для получения побочных результатов (присвоения переменной $res и т.п.)