Регулярные выражения
Понятие регулярного выражения (РВ) - одно из важнейших для программ обработки текстовых файлов. Согласно стандарту POSIX-2001, регулярное выражение - это шаблон, служащий для выборки определенных цепочек символов из множества подобных цепочек. Говорят, что выбранные цепочки удовлетворяют РВ (успешно с ним сопоставляются).
Когда хотят подчеркнуть составной характер РВ, используют термин "полное регулярное выражение". Под этим понимается шаблон, заданный как конкатенация одного или нескольких элементарных РВ.
Стандарт накладывает на сложность (полных) РВ единственное ограничение: реализация должна поддерживать любое РВ, длина которого не превышает 256 байт.
Оговаривается, что при наличии альтернатив выбирается самая левая из возможных цепочек, имеющая к тому же максимальную длину.
Различают базовые (БРВ) и расширенные регулярные выражения (РРВ). В большинстве случаев используются БРВ, они и будут описаны в первую очередь.
Минимальным элементом БРВ являются односимвольные БРВ, т. е. БРВ, которым удовлетворяют цепочки из одного символа. Односимвольные БРВ строятся по следующим правилам.
- Обычный символ (не входящий в перечень из следующего пункта) - это односимвольное БРВ, которое успешно сопоставляется с указанным символом.
- Если за символом \ следует любой специальный символ, то последний теряет свой специальный смысл. Данная комбинация определяет односимвольное БРВ, успешно сопоставляющееся со специальным символом. Специальными символами являются:
. [ \
Эти символы имеют специальный смысл, за исключением случая, когда они заключены в квадратные скобки.
*
Символ имеет специальный смысл, если он не заключен в квадратные скобки или не является первым символом БРВ.
^
Символ имеет специальный смысл в начале полного БРВ или в квадратных скобках сразу после открывающей скобки.
$
Символ имеет специальный смысл в конце полного БРВ.
- Точка (.) - односимвольное БРВ, успешно сопоставляющееся с любым символом.
- Непустая цепочка символов, заключенная в квадратные скобки [ ] представляет собой односимвольное БРВ, которое успешно сопоставляется с любым символом из этой цепочки.
Если цепочка начинается с символа ^, то БРВ успешно сопоставляется с любым не входящим в данный набор символом.
Внутри квадратных скобок можно использовать также конструкции, описываемые ниже.
Диапазон символов можно задать с помощью знака -. Например, БРВ [0-9] эквивалентно [0123456789]. Минус теряет свой специальный смысл, если он стоит в начале (допустимо после ^) или в конце цепочки символов в квадратных скобках либо использован в качестве границы диапазона. Так, БРВ [%--] успешно сопоставляется со всеми символами от процента до минуса включительно.
Закрывающая квадратная скобка не рассматривается как окончание цепочки символов, если она стоит вначале (быть может, после ^). Таким образом, БРВ []a-f] определяет либо закрывающую квадратную скобку, либо любой символ от a до f включительно.
Стандарт POSIX-2001 предусматривает поддержку классов символов (таких, например, как буквы, цифры, знаки пунктуации, пробельные символы, управляющие символы и т.д.). Класс символов задается своим именем, заключенным в квадратные скобки с двоеточиями. Должны поддерживаться по крайней мере следующие классы:
[:alnum:] [:cntrl:] [:lower:] [:space:] [:alpha:] [:digit:] [:print:] [:upper:] [:blank:] [:graph:] [:punct:] [:xdigit:]
Например, БРВ [^[:alnum:]] удовлетворяют символы, отличные от букв и цифр.
В некоторых языках элемент алфавитного сравнения может задаваться несколькими символами. Такие элементы следует заключать в квадратные скобки с точками: [[.ch.]].
Если определены классы элементов, эквивалентных при алфавитном сравнении, то подобный класс можно задать, заключив любой его элемент в квадратные скобки со знаками равенства: ([= и =]).
Таковы правила построения заключенных в квадратные скобки односимвольных БРВ.
Построение многосимвольных БРВ из односимвольных регламентируется следующим образом.
- В состав БРВ могут входить подвыражения ( в том числе вложенные), заключенные в экранированные круглые скобки: \( и \). Подвыражение в скобках успешно сопоставляется с теми же цепочками, что и без скобок.
- На подвыражения допускаются обратные ссылки вида \n (где n - цифра от 1 до 9).
Обратной ссылке удовлетворяет такая же цепочка символов, что была успешно сопоставлена подвыражением, открывающимся экранированной скобкой номер n, считая от начала полного БРВ. Например, БРВ \(.\)\1 удовлетворяют пары одинаковых символов. - За односимвольными БРВ, подвыражениями и обратными ссылками может следовать звездочка. Такая конструкция успешно сопоставляется с любым (в частности, с нулевым) числом последовательных вхождений упомянутых БРВ. Например, шаблону \(.*\)\1 удовлетворяют пары стоящих рядом одинаковых цепочек символов.
- За односимвольными БРВ, подвыражениями и обратными ссылками может следовать запись вида \{m\}, \{m,\} или \{m,n\}, называемая интервальным выражением. Такая конструкция успешно сопоставляется с определенным числом вхождений упомянутых БРВ. Значения m и n должны удовлетворять неравенствам
- Конкатенация компонентных БРВ есть БРВ, которое успешно сопоставляется с конкатенацией цепочек, удовлетворяющих каждому из компонентных БРВ.
- На БРВ можно наложить ограничение, чтобы успешно сопоставленная подцепочка символов примыкала к одной или обоим границам анализируемой цепочки (произвести фиксацию границ). Если в начале БРВ стоит символ ^ (фиксатор начала), то сопоставление должно выполняться с начала цепочки. Если в конце БРВ стоит символ $ (фиксатор конца), то сопоставление должно выполняться до конца цепочки. Например, БРВ ^\(.*\)\1$ успешно сопоставляется с цепочками символов, состоящими из двух одинаковых подцепочек.
Операции построения многосимвольных БРВ описаны выше в порядке убывания приоритетов. Наибольшим приоритетом обладают подвыражения и обратные ссылки, далее следуют повторители - звездочка и интервальные выражения, затем конкатенация и, наконец, фиксация границ.
Опишем отличия расширенных регулярных выражений (РРВ) от базовых.
- В число специальных символов дополнительно входят круглые скобки, открывающая фигурная скобка, а также символы +, ?, |.
- Для группирования (выделения подвыражений) используются неэкранированные круглые скобки.
- Отсутствуют обратные ссылки.
- Добавлены два повторителя: плюс обозначает любое ненулевое число последовательных вхождений; знак вопроса - нуль или одно вхождение.
- Для выделения интервальных выражений используются неэкранированные фигурные скобки.
- Введена операция логического ИЛИ, которая обозначается символом | и имеет низший приоритет.Результат сопоставляется с цепочками, удовлетворяющими хотя бы одному из операндов. Например, РРВ a((bc)|d) успешно сопоставляется и с цепочкой символов "abc", и с "ad". Односимвольные РРВ, разделенные символом | и заключенные в круглые скобки, трактуются как односимвольные.
Таковы правила построения и обработки регулярных выражений, зафиксированные в стандарте POSIX-2001. Отметим, что базовые регулярные выражения не являются подмножеством расширенных, хотя число специфических особенностей БРВ невелико.
