Идеи реализации

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

Для перевода, как может показаться, нужно

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

Теперь пора сказать о недостатках такого подхода. Во-первых, считается, и не без оснований, что регулярные выражения, которые попадают в программу извне, создают угрозу безопасности. Дело в том, что в языке регулярных выражений есть конструкции, которые позволяют выполнить произвольный код. Мы не упоминали о такой возможности в главе 30. «Регулярные выражения». Конструкция (?{…}), в которой вместо многоточия находятся команды Perl, при использовании в регулярном выражении приводит к исполнению этих команд, а вычисленное в результате значение подставляется вместо всей конструкции. Например, чтобы подставить в регулярное выражение первый символ строки $s (каким бы он ни был), следует использовать фрагмент (?{substr($s, 0, 1)}). Но точно так же можно вставить в регулярное выражение и опасные команды. В результате пользователь программы сможет делать при помощи программы не только те вещи, которые были задуманы автором, но и многие другие. Пользователь приобретает все права того пользователя, от имени которого действует программа. Особенно опасной ситуация становится, если программа запускается удалённо, например, запускается веб-сервером в ответ на запрос. Так можно позволить удалённому пользователю выудить не предназначенную для него информацию или устроить разрушения от имени веб-сервера. Подобные опасности, как мы уже писали в главе 33. «Диофантовы уравнения», таит и интроспекция. В сущности, описанная возможность также является интроспективной.

Другая неприятность состоит в том, что неумелый или злокозненный пользователь может создать регулярное выражение, сопоставление строк с которым очень дорого обходится. Примеры таких выражений можно построить, многократно вкладывая группы с квантификаторами в другие группы с квантификаторами, скажем, так: (a(b(c(d(…)*)*)*)*)*. Если у пользователя есть возможность передавать в программу (например, через командную строку или файл) для использования регулярное выражение, он может сильно нагрузить процессор и тем самым снизить полезную производительность вычислительной системы.

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

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

Ясно, что наименьшую трудность представляют обычные символы из шаблона. Если бы шаблон не содержал бы метасимволов, сопоставление строки с ним заключалось бы в посимвольном сравнении шаблона со строкой (можно воспользоваться оператором eq). Чуть сложнее интерпретация метасимволов ?: при посимвольном сравнении нужно считать, что метасимвол ? из шаблона «равен» любому символу из строки.

Конечно же труднее всего обрабатывать метасимвол *, поскольку ему, в отличие от обычных символов шаблона или метасимвола ?, в строке может соответствовать фрагмент произвольной длины.

Забудем пока про классы символов, заданные перечислением. Поддержку квадратных скобок будет не очень трудно реализовать, и мы займёмся этим в разделе «Рекурсивное решение». Но тут необходимо учесть, что не каждый шаблон с квадратными скобками является правильным. Если где-то после открывающей скобки не окажется закрывающей, программа должна сообщить об ошибке в шаблоне. Точно так же не должна появляться закрывающая скобка без предшествующей ей открывающей.

Постараемся сформулировать правила, по которым происходит сопоставления шаблона со строкой. Иными словами, определим аксиоматически выражение t s , которое истинно, если s соответствует шаблону t, и ложно в противном случае.

Для сокращения записи введём обозначения: x * будет означать первый символ строки x (имеет смысл для непустой строки). Обозначим как x j результат отбрасывания в строке x её первых j символов. Конечно, выражение имеет смысл только для j, не превышающих длины строки x. Можно считать, что x * — «голова» строки, а x 1 — её «хвост».

Выделим важные случаи, в каждом из которых требуется отдельное правило. Для строки s это случай, когда строка пустая и когда непустая. Для шаблона t важных случаев больше. Во-первых, требует особого рассмотрения пустой шаблон. Кроме того, в отдельных правилах нуждаются шаблоны, начинающиеся со звёздочки, с вопросительного знака и с любого другого символа. Таким образом, возникают восемь различных ситуаций, в которых выражение t s вычисляется по-разному. Сведём все случаи в таблицу: s = s t = (1) да (5) нет t * = ? (2) нет (6) t 1 s 1 t * = * (3) t 1 s (7) j : t 1 s j t * ? * (4) нет (8) t * = s * t 1 s 1 Для читателей, которых угнетает обилие формул, сформулируем все эти правила на словах:

  1. Пустая строка всегда подходит к пустому шаблону.

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

  3. Пустая строка подходит к шаблону, начинающемуся со звёздочки, тогда и только тогда, когда она подходит к хвосту шаблона.

  4. Если шаблон не пуст, но начинается с обычного символа, пустая строка к нему не подойдёт.

  5. Непустая строка не подходит к пустому шаблону.

  6. Если в голове шаблона вопросительный знак, то непустая строка подходит к нему тогда и только тогда, когда хвост строки подходит к хвосту шаблона.

  7. Если в голове шаблона звёздочка, то непустая строка подходит к нему тогда и только тогда, когда к хвосту шаблона подходит остаток строки после отбрасывания первых j символов для некоторого j ( 0 j l , где l — длина строки s).

  8. Если в голове шаблона обычный символ, то непустая строка подходит к нему тогда и только тогда, когда голова строки совпадает с головой шаблона, а хвост строки подходит к хвосту шаблона.

Мы видим, что все без исключения случаи перечислены. Но помогут ли эти правила вычислить t s ? Обратим внимание на то, что в части ячеек таблицы сразу записан ответ, а в остальных всё сводится к вычислению выражений того же типа, что говорит о рекурсивной природе аксиом. Эти аксиомы не сложно превратить в рекурсивный алгоритм, но нужно убедиться, что рекурсия рано или поздно завершится. И действительно, вычисление t s сводится к вычислению t s , где сумма длин шаблона t и строки s строго меньше суммы длин t и s. Таким образом, при каждом рекурсивном вызове процедуры, которая проверяет, подходит ли строка к шаблону, сумма длин шаблона и строки уменьшается, оставаясь неотрицательной. Это означает, что наступит момент, когда процедура будет вызвана для пустого шаблона и пустой строки, и сразу возвратит ответ да, если готовый ответ не будет получен раньше, в случаях (2), (4) и (5). Мы не только доказали ограниченность рекурсии, но и грубо оценили сверху наибольшую глубину возможных рекурсивных вызовов.

Теперь рассмотрим подробнее случай (7). Для вычисления в этом случае можно в цикле перебирать j от нуля до длины строки s до тех пор, пока не обнаружится такое, что окажется истинным выражение t 1 s j , или пока не закончится перебор. Но мы, хотя бы в познавательных целях, попробуем обойтись без цикла. Для этого преобразуем выражение j : t 1 s j к равносильному виду t 1 s t s 1 , учитывая условия t * = * и s .

Действительно, t s = t 1 s t s 1 = t 1 s t 1 s 1 t s 2 = t 1 s t 1 s 1 t 1 s 2 t s 3 = t 1 s t 1 s 1 t 1 s 2 t 1 s 3 t s 4 = = t 1 s t 1 s 1 t 1 s 2 t 1 s 3 t 1 s l 1 t s l , где l, напомним, — длина строки s. В этой цепочке равенств мы «разворачивали» выражения вида t s m в конце каждой строчки, заменяя его на t 1 s m t s m + 1 . Теперь осталось заметить, что s l = , и, согласно правилу для случая (3), t s l = t 1 s l . Таким образом, t s = t 1 s t 1 s 1 t 1 s 2 t 1 s 3 t 1 s l 1 t 1 s l = j : t 1 s j , и выражение для случая (7) можно заменить на t 1 s t s 1 .

Информатика-54© А. Н. Швец