Динамические регулярные выражения

В документации по Perl приводится пример применения динамических регулярных выражений для того, чтобы выяснить, является ли заданная в тексте последовательность чисел последовательностью Фибоначчи. А мы в качестве более сложного примера поставим немного другую задачу: найти в $_ первую наидлиннейшую последовательность 10-ных цифр, которые стоят подряд и возрастают на 1. Например, в строке

$_='0123 1234345678910 ';

искомая наидлиннейшая последовательность такая: 3456789.

Вот сама программа:

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

my ($len,$d,$res)=(0);
$_='0123 1234345678910 ';
no warnings;

/((\d)
   (?{$d=$+})
   (?>
       (??{ ++$d < 10 ? "$d" : "(?!)" })*
   )
 )
 (?{                       	# Эти символы нельзя разделять
  if (length $1 > $len)
   { $len=length $1;
     $res=$1;
   }
 })                        	# Эту скобку нельзя отделять от предыдущей скобки "}"
 (?!)
 /x;
print $res if defined $res;

Вначале переменной $len присваивается 0. В комментариях указана особенность конструкций (?{ и }), в которых фигурную скобку нельзя отделять от соседнего символа даже и при свободном форматировании.

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

Код в этом динамическом регулярном выражении при каждой итерации, обусловленной квантификатором *, увеличивает на единицу переменную $d, и если ее значение меньше десяти, то он возвращает значение этой переменной, а если $d после инкремента принимает значение 10, которое уже не подходит для цифры, то этот код Perl возвращает уже знакомый нам подшаблон (?!), который заставляет квантификатор * сделать шаг назад и остановиться на своем предыдущем состоянии, при котором было совпадение с наибольшей цифрой. После этого совпадения для атомарных скобок управление передается за них и выполняется код Perl, который проверяет, больше ли длина переменной $1 длины переменной $len. Если больше, значит, мы нашли более длинную последовательность цифр, поэтому мы запоминаем ее в переменной $res и обновляем содержимое переменной $len, которая хранит размер найденной длиннейшей последовательности цифр. После этого кода опять стоит подшаблон (?!), который заставляет все регулярное выражение сделать повтор со следующего символа целевого текста.

Директива no warnings нужна, чтобы отменить предупреждение

matches null string many times in regex; …

которое появится, когда динамическое регулярное выражение вернет подшаблон (?!).

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

Здесь опять замечу, что это регулярное это выражение возвращает несовпадение и используется только ради побочного эффекта (установки переменной $res ).

Насколько эффективно работает это регулярное выражение? Вставьте встроенный код

Perl после атомарных скобок, который будет печатать содержимое переменной $1:

/((\d)
   (?{$d=$+})
   (?>
       (??{ ++$d < 10 ? "$d" : "(?!)" })*
   )
 ) (?{print "$1\n"})
 (?{                       # Эти символы нельзя разделять
  if (length $1 > $len)
   { $len=length $1;
     $res=$1;
   }
 })                        # Эту скобку нельзя отделять от предыдущей скобки "}"
 (?!)
 /x;
print $res if defined $res;

В результате на печати получим:

0123
123
23
3
1234
234
34
4
3456789
456789
56789
6789
789
89
9
1
0
3456789

Видим, что вначале регулярное выражение находит длиннейшую последовательность цифр, а потом перестартовывает с каждой следующей цифры этой последовательности благодаря второму подшаблону (?!). Хотелось бы, чтобы вместо этого начальная позиция при итерациях устанавливалась сразу за найденной последовательностью цифр, дабы не делать лишней работы. Но мне кажется, это невозможно, т.к. присвоение внутри регулярного выражения функции pos (pos($_)=…) не дает эффекта.

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

(?(?{$len == 4})\G(?!))

При достижении этого условия встроенный код Perl вернет истину, и на место всей условной конструкции будет подставлен подшаблон

\G(?!)

Он говорит, что с конца предыдущего совпадения (или с начала текста при первой итерации поиска) нет совпадения. На этом все регулярное выражение закончит работу, т.к. итерация его со следующей позиции невозможна из-за привязки к концу предыдущего совпадения. В том месте, где вы установили, что надо поскорее выйти из регулярного выражения, подставьте подшаблон (?!), чтобы произошла итерация всего регулярного выражения. Но помните, что она не произойдет до тех пор, пока слева от текущей позици в шаблоне имеются квантификаторы или конструкции выбора альтернативы с сохраненными состояниями.

Что будет, если убрать атомарную группировку?

/((\d)
   (?{$d=$+})
   
       (??{ ++$d < 10 ? "$d" : "(?!)" })*
   
 ) (?{print "$1\n"})
 (?{                       # Эти символы нельзя разделять
  if (length $1 > $len)
   { $len=length $1;
     $res=$1;
   }
 })                        # Эту скобку нельзя отделять от предыдущей скобки "}"
 (?!)
 /x;
print $res if defined $res;

Тогда на печать выйдет гораздо больше строк:

0123
012
01
0
123
12
1
23
2
3
1234
123
12
1
234
23
2
34
3
4
3456789
345678
34567
3456
345
34
3
456789
45678
4567
456
45
4
56789
5678
567
56
5
6789
678
67
6
789
78
7
89
8
9
1
0
3456789

Из этой распечатки видно, что после выполнения второго подшаблона (?!) не происходит итерация всего регулярного выражения, как в первом случае, ведь квантификатор * имеет сохраненные состояния. Он начинает отдавать по одной захваченной цифре, пока не отдаст их все. Только после этого происходит рестарт всего регулярного выражения со следующего символа целевого текста.

12.2. Поиск вложенных конструкций

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

Рассмотрим задачу удаления всех комментариев, которые заключены в фигурные скобки, вместе с этими скобками. При этом предположим, что эти комментарии могут иметь произвольную вложенность. Т.е. надо уничтожить все правильно сбалансированные серии фигурных скобок вместе с их содержимым. От строки

$_=" {a{b{c{{d{}m}e}f}}gf{ }f";

после этого должно остаться ' {agff'.

Будем рассуждать от легкого случая к более сложным. Если бы речь шла только о первом уровне вложенности: …{…}…, то мы могли бы создать такой объект регулярного выражения:

my $level0=qr/(?>[^{}]*)/;

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

s/\{$level0}//g;

Напоминаю, что символ } не обязательно маскировать, т.к. он в отличие от символа { не является метасимволом регулярного выражения.

Эта программа корректно бы удаляла комментарии первого уровня вложенности. От строки a{b}c осталось бы ac. Но если бы мы задали этой программе строку

a{b{c}d}e

то в результате получили бы остаток

a{bd}e

Удаляются только скобки с фрагментами, которые не содержат этих скобок. Мы могли бы повторять подстановку, пока оператор s/…/…/ возвращает ненулевой результат, но нам нужен общий метод для любого уровня вложенности. С этой целью расширим наш объект регулярного выражения. Он должен совпадать не только с текстом без скобок, но и с текстом без скобок, который ограничен этими фигурными скобками. Это мы сделаем с помощью конструкции альтернативного шаблона:

my $level1=qr/(?>[^{}]|\{$level0})*/;

Здесь мы воспользовались тем, что у нас уже есть регулярное выражение, которое соответствует фрагменту текста без фигурных скобок, это объект $level0. Чтобы фрагменты текста без скобок поглощались быстрее, можно поставить квантификатор +:

my $level1=qr/(?>[^{}]+|\{$level0})*/;

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

my $level1=qr/(?>(?>[^{}]+)|\{$level0})*/;

Программа

$_='a{b{c}d}e';
my $level0=qr/(?>[^{}]*)/;
my $level1=qr/(?>(?>[^{}]+)|\{$level0})*/;
s/\{$level1}//g;
print $_;

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

ae

Но если ей дать текст со скобками третьего уровня вложенности, то она оставляет скобки первого уровня вложенности:

$_='a{b{c{d}}e}f';
my $level0=qr/(?>[^{}]*)/;
my $level1=qr/(?>(?>[^{}]+)|\{$level0})*/;
s/\{$level1}//g;
print $_;

Выводится

a{be}f

Мы могли бы по аналогии создать объект $level3 и т.д., но динамические регулярные выражения позволяют сразу создать объект $levelN для произвольного уровня вложенности:

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

$_=" {a{b{c{{d{}m}e}f}}gf{ }f";
my $levelN;
$levelN=qr
/(?>
    (?>[^{}]+)|		   # все кроме фигурных скобок
         \{(??{$levelN})}  # или текст, соответств. всему шаблону, ограниченный скобками
  )*			   # сколько угодно раз
/x;
s/\{$levelN}//g;
print $_;

В результате получаем

{agff

Это верный результат.

Как видим, объект $levelN строится рекурсивно, используя себя в качестве своего компонента. Поэтому переменную $levelN лучше объявить заранее, чтобы не было сообщения об использовании неинициализированной переменной.

В процессе работы регулярное выражение подставит $levelN столько раз, сколько раз встретит открывающую фигурную скобку.

Мы могли бы перенести внешние фигурные скобки внутрь нашего объекта $levelN, тогда в операторе подстановки не нужно было бы их выписывать:

$_=" {a{b{c{{d{}m}e}f}}gf{ }f";
my $levelN;
$levelN=qr
/\{				# открывающая фигурная скобка
 (?>
    (?>[^{}]+)|			# все кроме фигурных скобок
         (??{$levelN})		# или текст, соответствующий всему шаблону
  )*				# сколько угодно раз
 }				# и закрывающая фигурная скобка
/x;
s/$levelN//g;
print $_;

Во второй альтернативе также нужно убрать фигурные скобки, т.к. в $levelN они уже присутствуют. На печати результат тот же:

{agff

Рассмотрим теперь случай, когда "скобки" представляют собой многосимвольные конструкции, например, теги <table и </table>. Раньше мы уже рассматривали такие "скобки" и выработали технический прием с заменой класса символов на негативную опережающую проверку.

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

$_=<<EOD;
aa<table>
 <tr>
ff<table>
  <tr>
 </table>
 <tr>
</table>bb
ssssssss
<table>
</table>
EOD

my $levelN;
$levelN=qr
"(?>
      (?:(?!</?table).)+|         # все символы до фрагмента </?table
      <table[^>]*>(??{$levelN})</table>	# или вся следующая таблица
 )*         # сколько угодно раз
"isx;

my @tables=m"<table[^>]*>$levelN</table>"gi;
print join "\n--\n",@tables if @tables;

Конструкция (?!</?table).)+ с помощью точки будет брать символы до встречи с фрагментом, соответствующим шаблону </?table. На печать выходит

<table>
 <tr>
ff<table>
  <tr>
 </table>
 <tr>
</table>
--
<table>
</table>

Я не стал перегружать это регулярное выражение атомарными скобками, вы можете сделать это самостоятельно.

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

$_='abc';
print "$1 $2" if /(a)(??{"(b)"})(c)/;

В результате напечатается

a c

Если бы мы попытались распечатать "$1 $2 $3", то на печать вышло бы то же самое и еще предупреждение об использовании неинициализированной переменной (это $3 ).

Если бы мы вставляли значение переменной, которое содержит текст (b), то результат был бы тем же:

$_='abc';
my $a='(b)';
print "$1 $2" if /(a)(??{$a})(c)/;

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

$_='abc';
my $a=qr'(b)';
print "$1 $2" if /(a)(??{$a})(c)/;

Но как только мы попытаемся внутри всего регулярного выражения использовать одно динамическое регулярное выражение, содержащее захватывающие скобки, то Windows покажет окно с сообщением, что в Perl обнаружена ошибка и это приложение будет закрыто, при этом извиняясь за неудобство. Perl успевает вывести сообщение, что совпадение закончилось успешно. Эта ошибка возникает не только в Perl под Windows.

Вот эти фрагменты кода вызывают ошибку Perl:

$_='abc';
my $a='(b)';
/(??{$a})/;

$_='abc';
print 'Found' if /(??{"(b)"})/;

$_='abc';
my $a=qr'(b)';
print 'Found' if /(??{"$a"})/;

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

$_='abc';
my $a=qr'(b)';
print 'Found' if /(??{$a})/;

В остальных случаях Perl аварийно завершается. При использовании незахватывающих скобок:

$_='abc';
my $a='(?:b)';
/(??{$a})/;

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