Механизм работы регулярных выражений. Поиск с возвратами

Рассмотрим еще один пример. Пусть мы имеем шаблон

abcd|abc|ab

и строку

ab

Когда механизм поиска обрабатывает конструкцию выбора, он пытается найти совпадение с одной и той же текущей позиции текста, пробуя для нее последовательно эти подшаблоны в порядке их записи (слева направо). Если какой-то подшаблон совпал, то механизм поиска пропускает оставшиеся подшаблоны из конструкции выбора и далее переходит к подшаблону, стоящему за этой конструкцией.

В нашем примере сначала будет попробован подшаблон abcd, эта проба закончится неудачей. Также неудачей закончится проба следующего подшаблона abc. И только последний подшаблон ab совпадет. Если бы после этой конструкции выбора шаблон продолжался и следующий за ней подшаблон не совпал, то в общем случае произошел бы возврат к этой конструкции выбора и в дело пошел бы следующий за ab подшаблон (если бы он существовал). В этом примере ab - последний подшаблон, поэтому в общем случае возврат продолжился бы еще левее, за конструкцию выбора и так далее до самого начала всего шаблона. И только в случае, когда при всевозможных значениях квантификаторов и номеров подшаблонов в конструкциях выбора совпадение не было бы найдено, произошло бы продвижение начальной позиции поиска в тексте на один символ.

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

(ab|abc)\w*

и строка

abc

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

.*|abc

первый подшаблон может совпасть с текущей позиции текста всегда при нулевом значении квантификатора *. До попытки применить вторую альтернативу очередь никогда не дойдет, как будто ее нет вовсе!

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

Такой алгоритм поиска называется недетерминированным конечным автоматом (НКА). Этот алгоритм управляется шаблоном, и программист может указать, какое именно совпадение ему нужно. Существуют другие алгоритмы поиска (детерминированный конечный автомат ДКА или смешанные алгоритмы), но в языке Perl и других языках и библиотеках (PHP, PCRE) применяется НКА, хотя он не самый быстрый среди алгоритмов поиска. Программисту, привыкшему к алгоритму НКА, другой язык программирования, который использует другой алгоритм поиска, может преподнести сюрприз. Я уже не говорю о том, что в других языках некоторые метасимволы могут работать иначе, чем в Perl.

Рассмотрим еще примеры:

$_='abcd';
/(\w+)(\w+)/;
print "$1|$2";

Сначала первая пара скобок захватит всю строку, но во имя нахождения совпадения для всего шаблона пожертвует одним символом для второй скобки. В результате будет напечатано abc|d. Если во второй паре скобок вместо плюса стояла бы звездочка или вопросительный знак, то на их долю вообще не осталось бы символов - все их поглотил бы квантификатор из первой пары скобок, и переменная $2 получила бы пустое значение. Вот она, "жадность" в действии. Каждый "жадный" квантификатор оставляет остальной части шаблона минимум символов, лишь бы нашлось совпадение.

Минимальные квантификаторы действуют наоборот: берут себе минимум символов, а оставляют максимум для нахождения совпадения. Конструкция же выбора не минимальна и не максимальна, она упорядочена по очереди появления в ней альтернативных подшаблонов.

Возьмем шаблон

12?3

и строку

123

Т.к. квантификатор ? жаден, то вначале будет попробован вариант с его максимальным значением, которое равно единице. Но перед этим будет создано сохраненное состояние:

в шаблоне 1.3
в строке 1.23

где точкой обозначена текущая позиция поиска. Подшаблон 2? совпадет с 2, а 3 совпадет с символом 3. Совпадение будет найдено с первой попытки, и сохраненное состояние не вступит в игру, а если бы и вступило, то не привело бы к успеху поиска.

Теперь рассмотрим работу этого шаблона на строке

13

Вначале литерал 1 совпадет с символом 1 в строке. Далее 2? с максимальным значением квантификатора, а это просто 2, не совпадет с символом 3. Но перед этим создается сохраненное состояние:

в шаблоне 1.3
в строке 1.3

При этой локальной неудаче произойдет возврат к последнему сохраненному состоянию, который приведет к совпадению литерала 3 с символом 3, и поиск закончится удачно.

Вы можете распечатывать отладочную информацию и наблюдать процесс возвратов и итераций. Для этого надо вставить внутрь регулярного выражения код Perl, который будет распечатывать текущую позицию в тексте всегда, когда этот код будет попадаться при продвижении текущей позиции по регулярному выражению слева направо. О вставке кода и функции pos, возвращающей текущую позицию поиска, мы поговорим в дальнейших лекциях, а сейчас рассмотрим пример из главы 3, но в свободном форматировании с модификатором x, о котором речь пойдет также в начале этой главы:

#!/usr/bin/perl -w
use strict;
use re 'eval';

$_='abcd';
m!(?{ print "Starting from ".pos($_)."\n" })
  (\w
    (?{ print pos($_)."\n$1\n" })
  )*!x;

Если убрать код Perl, то оператор поиска будет выглядеть так:

m!(\w)*!x;

На печать выведется следующее:

Starting from 0
1
Use of uninitialized value in concatenation (.) or string at (re_eval 2) line 1.

2
a
3
b
4
c

Конструкция

(?{ код Perl })

вставляет код Perl в шаблон. Иногда при вставке кода в регулярное выражение транслятор выдает ошибку

Eval-group not allowed at runtime, use re 'eval' in regex m/…

Чтобы избежать этой ошибки, нужно директивой

use re 'eval';

разрешить вставку кода Perl внутрь шаблонов.

Этот код у нас распечатывает текущую позицию поиска pos в строке $_ (позиция отсчитывается от нуля) и значение переменной $1.

Вначале мы видим строку

Starting from 0

Она говорит о старте очередной итерации поиска. Эта итерация в нашем примере единственная. Далее происходит сопоставление \w и символа a, а затем - печать текущей позиции поиска (2) и значения переменной $1. Но т.к. эта печать происходит еще до закрытия захватывающей скобки, когда переменная $1 еще не появилась, то возникает предупреждающее сообщение об использовании неопределенной переменной. Конечно, его можно было бы избежать, если написать

print "$1\n" if defined $1;

Но я не стал излишне загромождать код.

Затем скобки захватывают символ a, и переменная $1 приобретает значение $1='a', а квантификатор * заставляет вернуться за закрывающую скобку и повторить поиск, начиная от \w. Теперь \w соответствует символу b, а распечатывается текущая позиция 2 и текущее значение $1, которое равно a. Затем повторяется тот же самый цикл, который печатает очередные текущие позиции и захваченные символы. После того, как подшаблон \w совпадает с d, печатается последняя позиция этой строки 4 и текущее значение $1, которое равно c. Значение d не вышло на печать, т.к. печать происходит до закрытия захватывающей скобки. А если бы мы вставили печать после нее или следующим оператором за оператором поиска, то увидели бы и значение d.

С помощью такого диагностического вывода можно отследить, как выполняется поиск. Иногда вывод показывает слишком большое число итераций и/или возвратов, которые надо оптимизировать.

2.3. Атомарная группировка

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

\s*=\s*

Представим, что вокруг знака равенства стояли бы пробелы и впоследствии ссылка не была бы найдена. Тогда произошел бы возврат и квантификатор \s* отдал бы один пробел для продолжения поиска. Но мы-то знаем, что это не повлияет на нахождение ссылки, так зачем проделывать ненужную работу? Для уничтожения сохраненных состояний подшаблон \s* надо заключить в специальную скобочную конструкцию:

(?>\s*)

Эти скобки не являются захватывающими. При выходе за закрывающую скобку все сохраненные состояния, созданные внутри этих скобок, будут уничтожены. В данном примере это, вообще говоря, приведет к более быстрому приходу к отрицательному результату поиска. Слова "вообще говоря" означают, что на уничтожение сохраненных состояний тоже требуется время, поэтому выигрыш (или даже проигрыш) во времени определяется каждым конкретным случаем.

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

<a(?>\s+)
(?>[^>]*)
и т.д.

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

Рассмотрим такие примеры:

(?>\w*)c

и строку

abc

Как вы уже догадались, совпадения не будет найдено. Квантификатор * захватит все три символа, а после выхода за скобки сохраненные состояния будут уничтожены, поэтому этот квантификатор ни за что не отдаст захваченное. Будут перепробованы итерации со второго, третьего символа и с конца строки, но все будет безрезультатно. Без атомарной группировки совпадение было бы найдено при первой итерации с начала строки.

А что будет в случае минимального квантификатора? Возьмем шаблон

(?>\w*?)c

и строку

abc

Совпадение будет найдено, но только при третьей итерации. \w* захватит 0 символов, а литерал c совпадет с символом c. Если в "жадном" режиме квантификатор внутри атомарной группировки захватывает все и не отдает, то в минимальном режиме он берет минимум возможного и ничего больше.

Если бы мы вынесли квантификатор за пределы атомарной группировки:

(?>\w)*c
(?>\w)*?c

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

Вот более практический и сложный пример: пусть нам надо округлять числа типа

23.34000012
23.345000023
34.4000025
456.00

так, чтобы после десятичной точки оставалось минимум два знака, а третий знак чтобы присутствовал, только если он не равен нулю. В приведенном примере должно получиться так:

23.34
23.345
34.40
456.00

Округление мы будем делать оператором s/…/…/. Поставим еще условие, что он не должен ничего менять, если число уже имеет правильный вид. Тогда получалась бы замена цифр самих на себя.

Вначале нас интересует десятичная точка: \., затем - две обязательных цифры: \d\d. За ними может идти цифра от 1 до 9, а может и не идти: [1-9]?. Все это мы возьмем в захватывающие скобки, чтобы этим заменить все от точки до конца числа. А после еще могут идти цифры: \d*, они будут удалены. Оператор получается такой:

s/(\.\d\d[1-9]?)\d*/$1/;

Но этот оператор делает замену, к примеру, в числе 23.345, меняя найденное на себя, т.е. выполняя ненужную работу. Вот пример кода:

$_='23.345';
print s/(\.\d\d[1-9]?)\d*/$1/."\n";
print $_;

Он выведет

1
23.345

Напомню, что оператор s возвращает число успешно сделанных замен. Вот, как это происходит: подшаблон

(\.\d\d[1-9]?)

совпадает с

.345

Далее цифр нет, поэтому \d* совпадает с пустой подстрокой, и т.к. совпадение найдено, то замена срабатывает. А она должна срабатывать только, если после .345 есть цифра. Давайте для этого попробуем заменить \d* на \d+ и посмотрим, что получится. А получается результат

1
23.34

Третья цифра обрезается. Это происходит потому, что теперь \d+ совпасть не с чем. Но ведь у регулярного выражения в запасе есть сохраненное состояние в подшаблоне [1-9]?. Происходит возврат внутрь скобок к этому подшаблону, и для него пробуется состояние, когда квантификатор равен нулю. В этом случае скобки совпадают с .34, а \d+ совпадает с третьей цифрой 5, поэтому пятерка из результата удаляется. Нам нужно, чтобы при совпадении подшаблона [1-9]? с третьей цифрой это совпадение не отменялось. Но для этого надо удалить данное сохраненное состояние, т.е. заключить подшаблон [1-9]? в атомарные скобки:

s/(\.\d\d(?>[1-9]?))\d+/$1/;

Теперь пример работает правильно.