Регулярные выражения для "продвинутых новичков"


Прислал: Сергей Колесниченко [ 29.06.2004 @ 13:01 ]
Раздел:: [ Веб-технологии ]


Использование позиционных проверок

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

Сначала немного отвлечемся. Как вы опишите что-то неприметное, либо что вообще трудно описать? Думаю, что надо описать что-то приметное, либо то, что легко описать, а потом указать, где находится искомое "что-то неприметное" относительно описанного "приметного".

Пример:
Мой директор спрашивает, как найти такой-то банк в Киеве. Я знаю, что объяснить местоположение банка голландсокму директору, используя транслитерированные русские названия, невозможно! Но я программист и объясняю, что нужный банк находится на центральной площади. В тоже время площадь описываю словами, что с одной стороны стоит женщина на огромной колонне, а с другой стороны Мак Дональдс. Даже некиевляне догадались, что я имею в виду Площадь Независимости.

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

Каждый раз при помощи регулярных выражений происходит поиск совпадений. Поиск проводится по строке, в строке ищется подстрока. Теперь научимся задавать условие, что должно совпасть перед подстрокой и после нее. Условие совпадения, которое идет перед подстрокой, называют ретроспективной проверкой, условие совпадения, которое идет после подстроки, называется опережающей проверкой. Можно объяснить также, что ретроспективная проверка совпадает слева, опережающая - справа.

Позитивные и негативные проверки

Хорошо, если можно описать, что следует перед искомой подстрокой, а что после. А что если нужно описать, что НЕ идет перед либо после искомой подстроки? Для этого опережающую и ретроспективную проверку делят еще каждую на две:

  • Опрежающая позитивная, опережающая негативная проверки.
  • Ретроспективная позитивная, ретроспективная негативная проверка.

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

Ретроспективная проверка

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

Ретроспективная негативная проверка описывается подобной последовательностью символов: (?<!) Посмотрите, что знак равно сменился на восклицательный знак и проверка сразу поменяла "полярность" т.е. из позитивной превратилась в негативную. Логика простая если вспомнить, что для проверки условия "неравно", отрицания равно, во многих языках программирования используется последовательность символов: !=

Опережающая проверка

Если вы поняли описание ретроспективной проверки, то понять суть опережающей проверки вам будет несложно. Для описания позитивной опережающей проверки используется последовательность символов: (?=) все как и раньше, скобки указывают что символы группируются для какого-то действия, вопросительный знак указывает на то, что следующим символом будет символ, который описывает, какое именно действие будет выполнено над группой символов, либо как будет трактоваться данная группа символов. Символ '=', который идет после вопросительного знака, указывает, что выражение в скобках - опережающая проверка, проверка того, что должно совпасть справа от искомой подстроки.

Для описания негативной опережающей проверки используется последовательность символов:
(?!) тоже самое, только знак равно заменили отрицанием - восклицательным знаком.

Пример №1

Часто возникает проблема по парсингу интересующих программиста данных из HTML, который не всегда хорошего качества, все было бы терпимо, если бы еще не вставки на javascript'е, вот пример такого текста:

<TD>20.02<BR>05:30
<TD class=l>Товар 1<BR>Товар 2
<TD><B>35</B>
<TD><A href="//ссылка/" id=sfsd32dfs
onclick="return m(this)">26.92</A><BR><A href="//ссылка/"
id=r3_3143svsfd onclick="return m(this)">27.05</A>
<TD><B>270.5</B>
</TR>
те цифры, которые написаны через точку, являются ценами. Задача состоит в том, чтобы собрать все цены, которые находятся между тегами <a>... </a>

Видим, что помимо цен между заданными тегами, есть такие, которые идут сразу после тега <TD>, а также стоят между тегами <B>...</B>. Ясно, что описать достаточно точно содержимое атрибутов тега <A> представляется задачей не самой легкой, поэтому надо ее упростить! Любой тег имеет закрывающий знак '>', наша задача описать, что этот знак идет перед ценой, но так как перед ценой может стоять тег <B> и тег <TD>, но эти цены нам не нужны. Каким образом мы узнаем, что цена стоит между тегами <A>...</A>? По тегу, который идет после цены, если это не тег </B>, то это будет либо тег </A> либо <BR>, а так же по тегу перед ценой если этот тег <TD>.

Путем таких размышлений мы пришли к выводу, что должно стоять справа, а что должно стоять слева искомой строки, которая описывается как цифры, разделенные точкой:
\d*\.\d*
То, что должно совпасть слева, мы описали как символ '>', записываем:
(?<=>) - выглядит немного странно, но совпадение слева записывается вот так (?<=), а внтури него после ?<= идет символ '>'
То, что должно совпасть справа описывается
(?=)
внутри мы пишем </A>
Теперь опишем, что не должно стоять перед ценой:
(?<!<TD>) перед ценой не должен стоять тег <TD>, это и есть негативная ретроспективная проверка.
При помощи негативной опережающей проверки опишем, что не должно стоять справа цены:
(?!<\/B>) справа от цены не должен стоять тег </B>

результирующее регулярное выражение, которое описывает все приведенные условия выглядит вот так:

preg_match_all("/(?<!<TD>)(?<=>)\d*\.\d*(?!<\/B>)(?=<\/A>)/", $string, $matches);
print_r($matches); 

После рассмотрения первого примера стоит сделать замечания и пояснения по поводу использования позиционных проверок.
1. Написанные друг за другом проверки применяются независимо друг от друга в одной точке, не меняя ее. Естественно, что совпадение будет найдено, если все проверки совпадут. В нашем примере это были точки перед и после цены. С точки зрения логики применения проверок нет никакой разницы, будет ли стоять проверка на тег <TD> перед проверкой на знак '>'. Правда, с точки зрения оптимизации первой позиционной проверкой должна идти та, которая имеет наибольшую вероятность несовпадения.
2. Совпавшие значения ретроспективных проверок не сохраняются. Т.е. если в нашем примере совпадает опережающая проверка, которая указывает, что после цены идет тег </A>, то сам тег </A>, который заключен в конструкцию (?=) не будет запоминаться в специальных перменных /1,/2 и т.д. Сделано это из-за того, что позиционная проверка совпадает не со строкой, а с местом в строке (она описывает место, где произошло совпадение, а не символы, которые совпали).
3. Нужно указать что PCRE не позволяет делать проверки на совпадение текста произвольной длинны. То есть нельзя делать, например, такую проверку:
/(?<=\d+)

Механизм поиска совпадения в ретроспективной проверке реализован так, что при поиске механизму должна подаваться строка фиксированной длины, для того, чтобы в случае несовпадения, механизм мог вернуться назад на фиксированое количество символов и продолжить поиск совпадений в других позиционных проверках. Думаю, что сразу это понять сложно, но представьте себе как происходит поиск совпадения в части (?<!<TD>)(?<=>) вышеописанного регулярного выражения. Берется строка, в которой происходит поиск, отсчитывается от начала столько символов, сколько символов будет в совпадении позиционной проверки, в нашем варианте это 4:
<, T, D, >
с этого места происходит "заглядывание назад" (ретроспективные проверки на английском языке звучит как lookbhind assertions), т.е. все предыдущие 4 символа проверяются на совпадение со строкой <TD>, если механизм не нашел совпадения, то ему надо вернуться на 4 символа назад, выполнить тоже самое с проверкой (?<=>), т.е. отсчитать один символ, "заглянуть" назад, попробовать найти проверку предыдущего символа с символом '>'. Представьте себе, что условие совпадения состоит из строки нефиксированной длинны:
(?<!<TD>?) подобная запись должна означать, что перед ценой, не должен стоять тег <TD> в количестве максимимум один экземпляр (либо вообще не стоять). Вот и получается, что после того, как механизм отсчитает 4 символа от начала, он проверит на совпадение с <TD>, но в условии указано, что тега может и не быть вообще, тогда возникает вопрос, на сколько знаков верунться назад, чтобы проверить на совпадение другие проверки. На 4 или вообще не возвращаться? Сразу возникает вопрос, а зачем идти вперед, чтобы потом "заглянуть" назад? Делается это для того, чтобы в случае совпадения всех проверок сразу же начать проверку тех символов, которые идут после позиционных проверок.

Пример №2

Как-то мне нужно было получить все изображения, которые использовались на сайте. Что для этого надо сделать? Правильно, надо в браузере нажать на "Сохранить как", указать куда сохранить страницу. Появится файл с исходным кодом страницы и папка с изображениями. Но вы никогда не сохраните в эту папку изображения, которые прописаны в стилях объектов по крайней мере в эксплорере:
style="background-image:url(/editor/em/Unlink.gif);"

Для проведения вышеописанной операции надо:
1. попросить хозяина хоста использовать контент, размещенный на его сайте.
2. найти в тексте все строки, подобные приведенной выше, и выделить в них относительный путь к файлу
3. сформировать файл в котором будут выводиться изображения при помощи <img src=полный_путь_к_изображению>

Делаем:
В переменную $content получаем исходный код страницы. А дальше используя регулярные выражения ищем относительные пути, которые прописаны в стилях. Каждый раз, когда я описываю, как я реализовал пример, я сначала тщательно описываю, что ищем, и тщательно описываю, в каком контексте происходит поиск. Проанализировав исходный код страницы стало понятно, что кроме как в описании стилей относительные пути к изображениям нигде не используются. Слева от относительного пути идет последовательность символов: url(
Справа от относительного пути стоит закрывающаяся круглая скобка.
Между этими последовательностями символов могут быть буквы латинского алфавита, цифры и слеши, а также точка перед расширением файла.

Начнем с простого. Символы латинсокого алфавита, цифры, точка и слеш описываются символьным классом:
[a-z.\/]
их может быть сколько угодно, на самом деле больше 3 (имя файла, минимум один символ, точка, расширение, минимум один символ), но в данном случае, зная контекст, это некритично, поэтому указываем квантификатор *
[a-z.\/]*
Слева должны идти 'url(' и мы это описываем при помощи позитивной ретроспективной проверки:
(?<=url()
Но обратите внимание на то, что скобка в регулярных выражениях является спецсимволом группировки, поэтому чтобы она стала символом, надо перед ней поставить другой спецсимвол - слеш.
(?<=url\()
Справа от относительного пути должна стоять закрывающаяся круглая скобка. Это условие описывается при помощи позитивной опережающей проверки:
(?=\))
Как видите, перед одной из скобок стоит слеш, что означает, что она интепретируется не как спецсимвол, а как литерал. Ниже приведен полный код на PHP, который выполняет все действия, кроме вопроса о разрешении использовать контент:

preg_match_all("/(?<=url\()[a-z.\/]*(?=\))/i", $content, $matches);
foreach($matches[0] as $item)
{
echo "<img src = //www.a???s.ru".$item.">
";
} 

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

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

Описание проблемы поставленной на форуме было таким:
Есть некая страница, созданная в результате работы шаблонизатора, в ней присутствуют элементы типа <input type=checkbox>, авторизированный пользователь работает с этой страницей и отмечает какие-то чекбоксы <input type=checkbox checked>, после отправки формы на сервер страницы снова генерируются шаблонизатором и программист делает так, что эта страница сохраняются в кеше, причем уже с отмеченными чекбоксами.
Задача программиста:
Ему надо по результатам отправленной формы запомнить выделенные чекбоксы и при последующем обращении этого пользователя к этой странице выводить его выбор с уже отмеченными элементами.

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

Его аргументация:
Так быстрее работает чем обработка первоначального шаблона.

Попробую привести свои аргументы против:
Смысл кешировать, если потом данные из кеша надо менять при помощи регулярных выражений? Кеш как раз и нужен для того, чтобы лишний раз не гонять ресурсоемкие процессы, такие как например обработка ВСЕГО текста регулярными выражениями... по нескольку раз.

Представим себе текст, в котором n символов, а также регулярное выражение, в котором
а. есть три условия выбора part1|part2|part3|
б. каждая из частей parti состоит из символьных классов, а также заданных последовательностей литералов.
в. максимальная длинна совпадения регулярного выражения равна m символов.
г. программист использовал функцию preg_replace, мы знаем принцип работы механизма регулярных выражений, а значит можем повторить его работу.

Приведу эти шаги одновременно с аргументами против подхода, который хотел применить программист, которые из них вытекают:
1. берем символ из текста с индексом 1 пытаемся применить регулярное выражение к тексту, который начинается с этого символа. Перебираем каждый символ от начального и сравниваем его с шаблоном (подходит ли).
2. следуя каждой инструкции выбора в регулярном выражении мы можем совершить максимум три выбора и перебрать m последующих символов для КАЖДОГО i-го символа текста.
3. несложно посчитать, какое количество символов будет перебрано впустую, если совпадение не будет найдено.
4. закешированный документ уже является результатом работы регулярного выражения (многие шаблонизаторы работают на регулярных выражениях) таким образом просто напросто дополнительно вызывается механизм регулярных выражений, чтобы отпарсить сырой документ-полуфабрикат, вместо того, чтобы сразу его сделать готовым за один проход.
5. если сравнить регулярные выражения, на которых работают шаблонизаторы и регулярное выражение, которое получится у нашего программиста, то сразу будет видно, что первые проще! По этой причине совпадения будут находиться быстрее.
6. Часто работа регулярных выражений в шаблонизаторе будет происходить с маленькими участками текста (не секрет, что страницы могут собираються из маленьких кусочков), а не сразу к сгенерированной странице.

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

В заметке описан случай, когда человек, знал как пользоваться регулярными выражениями, а также знал, как использовать в своей работе шаблонизатор, т.е. у него был выбор, он просто не мог остановиться на одном из вариантов. Есть категория начинающих программистов, которая увидев, кучу значков, при помощи которых решаются много проблем со строками, воздвигают себе кумира в виде статуи этому "волшебному средству" и даже не догадываются, что их задача по замене слова на другое слово в строке решается простой функцией str_replace(). Не понимая, как работают регулярные выражения, они приходят на форум и спрашивают, как заменить abcd на asdf при помощи preg_replace и очень обижаются, когда дают ссылку на str_replace в мануале на www.php.net. Это наверное самый распространенный случай неправильного применения регулярных выражений, когда их можно заменить при помощи функций работы со строками.

Сергей Колесниченко, estrabota.com.ua