Некоторое сходство между языком шаблонов и языком регулярных выражений 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$ вычисляется по-разному. Сведём все случаи в таблицу: $$\begin{array}{lll}& s=''''& s\ne ''''\\ t=''''& \text{(1)}\mathbf{да}& \text{(5)}\mathbf{нет}\\ t^{*}=''?''& \text{(2)}\mathbf{нет}& \text{(6)}{t}^1⊐s^1\\ t^{*}=''*''& \text{(3)}{t}^1⊐s& \text{(7)}\exists j:t^1⊐s^j\\ t^{*}\notin \left\{''?'',''*''\right\}& \text{(4)}\mathbf{нет}& \text{(8)}\left(t^{*}=s^{*}\right)\wedge t^1⊐s^1\end{array}$$ Для читателей, которых угнетает обилие формул, сформулируем все эти правила на словах:

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

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

Действительно, $$\begin{array}{l}t⊐s=t^1⊐s\vee t⊐s^1\\ =t^1⊐s\vee t^1⊐s^1\vee t⊐s^2\\ =t^1⊐s\vee t^1⊐s^1\vee t^1⊐s^2\vee t⊐s^3\\ =t^1⊐s\vee t^1⊐s^1\vee t^1⊐s^2\vee t^1⊐s^3\vee t⊐s^4\\ =\dots \\ =t^1⊐s\vee t^1⊐s^1\vee t^1⊐s^2\vee t^1⊐s^3\vee \dots \vee t^1⊐s^{l-1}\vee t⊐s^l\text{,}\end{array}$$ где $l$, напомним, — длина строки $s$. В этой цепочке равенств мы «разворачивали» выражения вида $t⊐s^m$ в конце каждой строчки, заменяя его на $t^1⊐s^m\vee t⊐s^{m+1}$. Теперь осталось заметить, что $s^l=''''$, и, согласно правилу для случая (3), $t⊐s^l=t^1⊐s^l$. Таким образом, $$t⊐s=t^1⊐s\vee t^1⊐s^1\vee t^1⊐s^2\vee t^1⊐s^3\vee \dots \vee t^1⊐s^{l-1}\vee t^1⊐s^l=\left(\exists j:t^1⊐s^j\right)\text{,}$$ и выражение для случая (7) можно заменить на $t^1⊐s\vee t⊐s^1$.