Применение регулярных выражений

Страница находится в стадии разработки

При написании программ довольно часто приходится иметь дело со строками. Это могут быть как строки выводимые на экран, так и строки пользовательского ввода. Если с первыми программисту управляться довольно легко (программист сам решает, как их формировать), то со вторыми дела обстоят намного хуже.

Предположим, что нам необходимо запросить у пользователя координаты нескольких точек на плоскости. Это можно сделать путем последовательного запроса координат X и Y. При этом, диалог пользователя и компьютера может выглядеть примерно так:

Введите координату X точки 1: 14
Введите координату Y точки 1: 2
Введите координату X точки 2: 22
Введите координату Y точки 2: 14
...

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

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

Введите координаты точек: (14, 2) (22, 14) (37, 5) (16, 2)

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

отделить пары координат друг от друга
убрать лишнюю информацию (скобки)
разобрать координаты

В книге уже был представлен похожий пример разбора строки URL и был приведен соответствующий код, однако тут существует одна проблема. Как правило, строки URL запросов формируются непосредственно броузером, а не пользователем. Броузер всегда работает по одному и тому же алгоритму и заранее известно какой будет результирующая строка. В нашем случае, мы имеем дело с пользовательским вводом, а значит, возможны различные ошибки ввода. Вот та же самая (с точки зрения пользователя) строка, которая тем не менее имеет важные отличия:

Введите координаты точек: (14,2) (22,   14) (37,5)(16,2)

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

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

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

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

(14, 2) (22, 14) (37, 5) (16, 2)
(14,2) (22,   14) (37,5)(16,2)
(14,2)(22,14)(37,5)(16,2)
(  14 ,   2 ) ( 22 ,  14) ( 37,5)   (16,    2)

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

Зачем нужны регулярные выражения

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

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

разделителем подстрок считаем последовательность, состоящую из

закрывающей круглой скобки
некоторого (возможно нулевого) количества пробелов
открывающей круглой скобки

В каждой из подстрок, координатой X считаем то, что расположено до запятой (кроме мусора)
В каждой из подстрок, координатой Y считаем то что расположено после запятой (кроме мусора)

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

(14, 2) (22, 14) (37, 5) (16, 2)

В самом деле, пары координат отделяются друг от друга последовательностью )...(. Это хорошо видно, если расставить пробелы немного по другому:

(14, 2       )(   22, 14   )(   37, 5   )(   16, 2)
разделители:  ^             ^            ^

На основании имеющихся данных, мы можем записать первые строки кода нашей программы: <source lang=kpp> var source = ReadInput(); //функция возвращает строку для анализа var pairs = source.split(')('); //подстроки с координатами </source>

Здесь мы применили уже известный нам метод split() для разделения строки на подстроки по последовательности из двух скобок. Однако, такой код будет работать только в том случае, если между скобками нет пробелов. В нашем случае, мы этого гарантировать не можем, поскольку ввод осуществляет пользователь. Решение может заключаться в том, чтобы пробежать по всей исходной строке и удалить все пробелы между закрывающей и открывающей строками. В некоторых случаях (в других задачах) это действительно может быть лучшим решением, но здесь гораздо эффективнее применять именно регулярные выражения. Для того чтобы объяснить методу split(), что в качестве разделителя следует понимать не фиксированную подстроку а целое множество подстрок, мы применим регулярное выражение: <source lang=kpp> var pairs = source.split(`\)\s*\(`); </source>

Устрашающая на первый взгляд конструкция, находящаяся в блоке параметров метода split() и является тем самым регулярным выражением. Итак, под регулярным выражением в языке К++ понимается строка символов, заключенная между символвами обратной кавычки (`), точно так же как мы объявляем строковые константы. Далее, само регулярное выражение состоит из ограниченного количества специальных симполов, которые разделяются на несколько групп, а так же из обычных строковых символов. Каждый спец символ представляет собой escape последовательность из символа \ и следующего за ним символа (буквы или знака).

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

escape последовательность \)
спец символ \s
спец символ *
escape последовательность \(

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

Преимущества регулярных выражений

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

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

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

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

Из всего вышесказанного, вытекают следующие соображения: чем сложнее код, тем больше вероятность ошибки; тем сложнее его отлаживать; тем больше усилий требуется для внесения изменений (особенно значительных), в то время как в случае с регулярными выражениями достаточно поменять буквально "пару символов".

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

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

формальное представление
компактность записи
легкость написания (+скорость написания)
легкость внесения исправлений
меньше вероятность ошибки
скорость выполнения
сложные рекурсивные определения