Встроенный код и поиск вложенных конструкций
В те времена, когда в арсенале регулярных выражений еще не было встроенного кода (и динамических регулярных выражений), поиск вложенных конструкций произвольного уровня вложенности был невозможен. Рассмотим вариант проверки, содержит ли текст правильно закрытые конструкции из круглых скобок. Например, строка
2*(3+2*(5-1)-2)+12
содержит конструкцию из правильно закрытых скобок, а строки
( ) ) ( )
и
( ( ) ( )
содержат неправильно сбалансированные круглые скобки.
Для составления такого регулярного выражения надо завести счетчик открывающих скобок, который вначале будет содержать 0, при встрече открывающей скобки будет увеличиваться на 1, а при встрече закрывающей скобки вначале будет проводиться проверка этого счетчика на 0. Если встретилась закрывающая скобка и счетчик содержит 0, то это будет говорить о нарушении баланса скобок. Иначе мы вычтем из содержимого счетчика 1. А в конце текста надо проверить, имеет ли счетчик значение 0, и если нет, то это опять ошибка.
Схема регулярного выражения будет такая:
^ # поиск от начала текста (?> # поиск без возвратов (?: (?> [^()]+ ) # все кроме круглых скобок без возврата | \( # или открывающая круглая скобка | \) # или закрывающая круглая скобка )* # сколько угодно раз ) $ # поиск до конца текста
Вначале счетчик $ctop (count of open parens) содержит 0. При встрече открывающей скобки выполняем код
(?{ ++$ctop })
При встрече закрывающей скобки выполняем условный оператор с кодом Perl в условии:
(?(?{ $ctop }) (?{ --$ctop }) | (?!) )
А если к этому моменту $ctop равен нулю, то подставляем шаблон (?!), который приведет к несовпадению для всего регулярного выражения.
В конец регулярного выражения подставим код
(?(?{ $ctop }) (?!) )
который тоже приведет к несовпадению для всего шаблона, если счетчик $ctop не будет равен нулю.
Теперь вся программа:
$_='( () ) ( ) (()())'; my $ctop=0; if (/ ^ (?> (?: (?> [^()]+ ) | \( (?{ ++$ctop }) | \) (?(?{ $ctop }) (?{ --$ctop }) | (?!) ) )* ) (?(?{ $ctop }) (?!) ) $ /x ) { print 'Match' } else { print 'Not match' }
При этих данных наша программа выводит Match, но если нарушить баланс скобок, то будет выведено Not match.
В этом примере скобки представлялись одним символом, но они могут быть и многосимвольными. Например, мы проверяем правильность вложенности тегов table. В этом случае подшаблон (?> [^()]+ ) нужно заменить на другую конструкцию, т.к. многосимвольные скобки нельзя втиснуть в класс символов. Вместо этого подшаблона используется такая конструкция:
(?> (?: (?! <table|</table ) .)+ )
Эта конструкция проверяет, находится ли в текущей позиции фрагмент <table или </table, и если нет ни того, ни другого фрагмента, то она поглощает один символ с помощью точки.
После этой вставки поменяем ограничители регулярного выражения и добавим модификаторы is, чтобы был поиск без учета регистра и точка соответствовала также символу перевода строки. Получим такую программу:
$_=<<EOF; <Table> <tr><td> <Table> <tr><td> </td></tr> </TABLE> </td></tr> </TABLE> EOF
my $ctop=0; if (m% ^ (?> (?: (?> (?: (?! <table|</table ) .)+ ) | <table (?{ ++$ctop }) | </table (?(?{ $ctop }) (?{ --$ctop }) | (?!) ) )* ) (?(?{ $ctop }) (?!) ) $ %isx ) { print 'Match' } else { print 'Not match' }
С данными в переменной $_ будет напечатано Match.
