Программирование на Athanor – 16 (простейшие образцы и сопоставления)

Базовые регулярные выражения, и сопоставление с ними

В большинстве языков программирования доступны регулярные выражения: механизм, который позволяет вместо жёстко фиксированной контекстной строки – задать целое семейство строк, имеющих нечто общее между собой. Часто используется альтернативное название "образцы" ("patterns"). Самая базовая операция, определённая для образцов – это сопоставление (matching), которая позволяет выяснить: соответствует ли некая строка заданному образцу, или нет? На основе операции сопоставления определяются другие операции с образцами – например, их поиск (в заданной строке) и пр.

Регулярные выражения, или "образцы" в Athanor – это не строки с загадочным (и довольно эзотерическим) собственным синтаксисом, а отдельный и самостоятельный встроенный тип данных языка. Образцы реализованы как иерархические структуры данных: более сложные образцы строятся из более простых (вплоть до базовых и самых примитивных образцов, сопоставление с которыми тривиально). Комбинируя примитивные образцы с помощью встроенных операций-конструкторов (таких, как конкатенация, альтернация, репликация) – можно создавать достаточно сложные образцы, пригодные для реальных задач. Вообще, система образцов в языке – очень сильно вдохновлена языком SNOBOL, разработанном ещё в начале 1960-х (и с тех пор основательно забытом, хотя и незаслуженно). Система образцов в Athanor не является точной копией того, что было реализовано в Сноболе (там механизмы сопоставления работали совсем по-другому) – но определённое влияние нужно признать. В конце концов, именно в SNOBOL сама концепция сопоставления строки с образцом – была реализована примерно за десять лет до появления регулярных выражений в первых UNIX-системах (и во многих отношениях лучше реализована).

Образцы (и их функциональность) – отдельная сложная тема, которая в одну статью точно не уместится (но здесь мы её откроем). Практически все функторы, работающие над образцами, имеют префикс "rx_", для многих из них предусмотрена более компактная "операторная" запись. И, кроме того, как мы увидим, есть и неявные приведения, позволяющие записывать многие образцы более компактно.

Итак, самый простой и примитивный образец – тот, который сопоставляется с жёстко фиксированной строкой:

Например, результат rx_string ("hello") – сопоставляется с фиксированной строкой "hello", и больше не с чем. Нередко требуется сопоставление не со строками, а с отдельными символами:

Операндом является числовой скаляр, задающий код символа в ASCII/Unicode. Например, результат rx_char (48) – сопоставляется с одним символом '0'.

Этот нуларный функтор возвращает примитивный образец, сопоставляющийся с любым символом (но только одним).

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

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

Встроенный бинарный функтор rx_alt реализует альтернацию – возвращает образец, сопоставляющийся с одной из двух альтернатив: Pattern_1 или Pattern_2. Например:

• rx_string ("Hello") |$ rx_string ("Goodbye")

Здесь результат сопоставляется с одной из двух фиксированных строк: "Hello" или "Goodbye". Конечно, если б каждый раз, когда мы хотели сопоставить фиксированную строку, надо было "заворачивать" её в вызов rx_string – запись даже довольно простых образцов была бы очень тяжеловесной и трудночитаемой! К счастью, в большинстве случаев этого делать не надо. Для всех функторов, ожидающих операнды-образцы, действует правило: если им передан строковый скаляр вместо образца – то rx_string применяется к нему автоматически. Так что, этот же образец может быть записан и так:

• "Hello" |$ "Goodbye"

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

• "Yes" |$ "No" |$ "Maybe"

– что может сопоставляться с одной из трёх строк: "Yes", "No" или "Maybe". В "операторной" форме, альтернация имеет левую ассоциативность (то есть, такая запись равносильна ("Yes" |$ "No") |$ "Maybe"). Хотя, в данном случае ассоциативность мало на что влияет: в любом случае, образец будет проверен на соответствие одной из трёх фиксированных строк, а порядок проверки здесь не слишком важен. Но вот когда сопоставляются не просто фиксированные строки, а более сложные образцы – порядок из сопоставления может существенно повлиять на результат.

Если же нужно сопоставить несколько образцов, идущих подряд – то на помощь приходит конкатенация образцов:

Встроенный бинарный функтор rx_cat это конкатенация: возвращает образец, сопоставляющийся с Pattern_1, сразу за которым следует Pattern_2. Например:

• ("Alpha" |$ "Beta") &$ ("Gamma" |$ "Delta")

Здесь результат успешно сопоставляется с одной из четырёх строк: "AlphaGamma", "AlphaDelta", "BetaGamma" и "BetaDelta" (и больше ни с чем). Разумеется, конкатенацию образцов (rx_cat) надо уверенно отличать от конкатенации строк (s_cat): вторая является скалярной операцией, и всегда возвращает строку-скаляр как результат. Впрочем, заметим, что когда оба операнда для rx_cat являются простыми строками – скорее всего, и правда будет проще заменить конкатенацию образцов на строковую (поскольку сопоставление строкового скаляра проще и эффективнее). Но вот когда операнды менее тривиальны – альтернативы rx_cat просто нет.

И для альтернации, и для конкатенации любой строковый скаляр автоматически преобразуется в образец: к нему просто неявно применяется rx_string. На самом деле, неявно преобразуется любой скаляр, но к числовым значениям неявно применяется rx_char – другими словами, они рассматриваются как символы с соответствующими кодами ASCII/Unicode. Заметим, что это не соответствует семантике скалярных операций (в которых, если помните, числовые скаляры неявно преобразуются в строки, содержащие их десятичную запись). Если вдруг нужна такая "скалярная" семантика – явно применbте к операнду rx_string!

Здесь нам осталось рассмотреть последнюю важную операцию-конструктор: репликацию, обеспечивающую повторяемость своего образца-операнда:

Параметры здесь требуют пояснения. Самый последний параметр (Pattern) – это повторяемый образец. Первый параметр (Range) является числовым диапазоном: он задаётся (обычно) в виде Min..Max. Границы диапазона являются числовыми скалярами: они задают минимальное (Min) и максимальное (Max) допустимое количество повторений Pattern. Наконец, второй параметр (Greed) интерпретируется как логические (булевское) значение. Если он равен нулю (т.е. ложен), предпочтение отдаётся сопоставить минимальное количество повторений, если он ненулевой (истинен) – то максимальное. Понятно, что репликацию образцов тоже надо отличать от репликации строк (s_rep).

Заметим, что (в отличие от многих случаев) – семантика обеих границ диапазона является включающей! То есть, например, если диапазон задан в виде 5..10 – это означает, что допускается не менее пяти, и не более десяти повторений Pattern (оба граничных значения – тоже вполне допустимы). Если возможно нефиксированное число повторений – то также принимается во внимание параметр Greed. Если он ненулевой, сопоставление является "жадным" (максимальным): предпочтение отдаётся самой длинной возможной последовательности повторов Pattern. Если Greed равен нулю, сопоставление является "скромным" (минимальным): предпочтение отдаётся самой короткой такой последовательности. Но в обеих случаях – сопоставляется не менее Min, и не более Max повторений Pattern. Также заметим, что обе границы могут быть опущены. Если отсутствует нижняя граница (Min), то предполагается 0. Если отсутствует верхняя (Max) – верхний лимит отсутствует, и допускается любое число повторений.

Довольно часто операндом здесь является произвольный символ (rx_any) – для этого часто удобно определить специальный функтор-конструктор:

• ! rx_rep_any (Range Greed) = rx_rep (Range, Greed, rx_any ());

Результат rx_rep_any сопоставляется с произвольной последовательностью символов, с длиной в интервале, заданном параметром Range, а "жадность" сопоставления – задаётся параметром Greed. Например, rx_rep_any (10..20, 0) – сопоставляется с произвольной последовательностью от 10 до 20 символов (предпочтение отдаётся самой короткой).

Часто параметр Greed является фиксированным – тогда допустимы и два более компактных конструктора, имеющих и "операторные" записи:

Определим ещё несколько полезных функторов-конструкторов:

• ! rx_optional (Pattern) = rx_rep (0..1, 0, Pattern);
• ! rx_once_or_more (Pattern) = rx_rep (1.., 0, Pattern);
• ! rx_zero_or_more (Pattern) = rx_rep (0.., 0, Pattern);

Здесь rx_optional реализует опциональность (т.е. образец Pattern может или присутствовать один раз, или отсутствовать). Функтор rx_once_or_more реализует повторение образца Pattern один или более (но не ноль!) раз подряд. Наконец, rx_zero_or_more – это повторение образца Pattern любое (возможно и ноль) количество раз, без ограничений. Наконец:

• ! rx_exactly (Pattern Count) = rx_rep (Count..Count, 0, Pattern);

Функтор rx_exactly – реализует повторение образца Pattern точно Count (не больше и не меньше) раз.

Очень часто надо проверить символ на принадлежность к какой-либо категории или группе. Разумеется, такое нетрудно реализовать через альтернацию – но это не только тяжеловесно, но и довольно неэффективно. Есть более удобные способы: например, предикаты cc_incl и cc_excl (которые мы рассматривали в статье 10). Их можно использовать вместе со следующими конструкторами:

Операндом здесь является любой предикат, которому передаётся код проверяемого символа. Если использовать в качестве этого предиката вызов cc_incl (String) – то успешным будет только сопоставление с символами, которые перечислены в строке, например:

• rx_any_in (cc_incl "ABCDEFabcdef")

возвращает образец, успешно сопоставляющийся только с латинскими буквами от 'A' до 'F' и от 'a' до 'f'. Если мы в нём заменим cc_incl на cc_excl – результатом будет образец, который НЕ сопоставляется с перечисленными буквами (но со всеми прочими символами – сопоставляется). С тем же успехом можно оставить cc_incl, но заменить rx_any_in на rx_any_ex. И вообще, для любой строки String:

• rx_any_in (cc_incl (String)) – эквивалентно: rx_any_ex (cc_excl (String))
• rx_any_ex (cc_incl (String)) – эквивалентно: rx_any_in (cc_excl (String))

Для каждого варианта проверки (и "инклюзивного", и "эксклюзивного") – можно выбрать один из двух вариантов, какой больше нравится. Но кроме явно определяемых категорий, есть и предопределённые (описаны в той же статье 10). Конечно, их тоже можно использовать: как с rx_any_in, так и с rx_any_ex. Например:

• rx_any_in (! cc_lower)

– сопоставляется со всеми строчными буквами латинского алфавита

• rx_any_ex (! cc_digit)

– сопоставляется со всеми символами, КРОМЕ цифр (десятичных).

Такие символьные классы – очень часто используются как операнды для rx_rep. Например:

• rx_rep (10..20, 0, rx_any_in (! cc_alpha))

Этот образец сопоставляется с любой последовательностью букв (заглавных или строчных), длиной не менее 10 и не более 20.

• rx_rep (5.., 0, rx_any_ex (! cc_blank))

А этот образец сопоставляется с любой последовательностью непробельных (тех, которые отвергает cc_blank) символов, длиною не менее пяти (верхняя граница длины отсутствует вообще). В обоих примерах, репликация "скромная": чтобы сделать её "жадной", замените второй аргумент с 0 на 1. Можно привести и больше примеров – но идея, думаю, понятна и так.

В общем, мы рассмотрели немало образцов – остался главный вопрос: так что с ними делать? Ну, полезного с ними можно сделать много, но начнём с простейших операций:

Вызов rx_match – просто пытается сопоставить образец Pattern с началом строки String. Результат всегда числовой: это число успешно сопоставленных символов, или -1, если сопоставить образец со строкой не удалось. Заметим, что результат 0 также свидетельствует об успехе (он возвращается, если образец успешно сопоставлен, но с пустой строкой)! Вот и примеры:

• rx_match ("Alpha" |$ "Beta", "Alphaville")

Возвращает число 5 (успешно сопоставив первую альтернативу);

• rx_match ("Alpha" |$ "Beta", "Betacam")

Возвращает число 4 (успешно сопоставив вторую альтернативу);

• rx_match ("Alpha" |$ "Beta", "Centipede")

Возвращает -1 (ни одну альтернативу сопоставить не удалось).

Применение rx_match не часто нужно в реальных программах (но может быть полезно для отладки и/или тестирования сложных образцов). Вот более практичные инструменты:

Параметры здесь те же, что и в rx_match – однако, тут происходит не только сопоставление, но и полноценный поиск. А результатом является не просто позиция в строке, а диапазон: список из двух элементов (From, To), показывающий, где в String найден образец. (Одной позиции мало, т.к. заранее неизвестно, с каким именно числом символов образец сопоставится, если это произойдёт.) Позиции символов (как и во всех прочих строковых операциях) отсчитываются с нуля. Если же поиск был неудачен – обе операции возвращают (). Например:

• rx_findfirst ("good" |$ "bad", "In good times or bad times ...")
• rx_findlast ("good" |$ "bad", "In good times or bad times ...")

Здесь вызов rx_findfirst возвращает (3, 7); вызов rx_findlast возвращает (17, 20). Возвращаемый диапазон (Range) точно указывает позицию найденной подстроки, так что String$[Range] – вырежет из String найденную подстроку (конечно, при условии, что она была найдена).

Наконец, для любого выражения нетрудно проверить: образец это, или нет?

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

• ! cc_ident_first (char) = cc_alpha (char) || (char == \c '_');

В качестве дальнейших символов – допустимо всё перечисленное, а также и все десятичные цифры:

• ! cc_ident_next (char) = cc_ident_first (char) || cc_digit (char);

Наконец, сам идентификатор – это один символ, соответствующий cc_ident_first, за которым идёт последовательность (возможно, пустая) символов, соответствующих cc_ident_next:

• rx_ident = rx_any_in (! cc_ident_first) &$ rx_rep (0.., 1, rx_any_in (! cc_ident_next));

С помощью образца rx_ident – нетрудно, например, найти и вывести все идентификаторы во фрагменте исходного кода (source):

! locate_all_idents (source) =
	while ((where = rx_findfirst (rx_ident, source)) [~=] ()):: {
		<: ('[', source $[where], ']');
		source = source$[where[1] ..];
		};

Этим все встроенные инструменты, предназначенные для работы с образцами, не ограничиваются. Заметим, что кроме встроенных – есть ещё и библиотечные (например, стандартный модуль "PCRE.ath", автоматически распознающий и транслирующий заданное строкой регулярное изображение – в Athanor-образец). Обо всём этом, надеюсь, будет подробнее рассказано в дальнейших статьях.