Записки программиста

В Perl 6 появилось новое средство, называемое грамматиками. Ни в одном другом языке я такого еще не видел. Помните, как мы с вами писали интерпретатор простого языка программирования? Так вот, грамматики — это практически встроенное в язык средство для создания лексических и синтаксических анализаторов.

Вот как в Perl 6 выглядит грамматика для простого Lisp-подобного языка:

Ничего нового — просто грамматика в BNF и регулярные выражения. Очевидно, что парсинг начинается с правила под именем TOP. Однако есть нюанс, и даже не один.

Во-первых, запись:

…как бы намекает нам, что op-args должен находится между скобками. Но почему мы не написали:

… ведь так вроде бы понятнее? В первом случае, если парсеру не удастся найти парную скобку, будет брошено исключение типа «Unable to parse lst, couldn’t find final ‘)’». Во втором случае никакого исключения брошено не будет, метод parse просто вернет ложь. По понятным причинам первый вариант предпочтительнее.

Во-вторых, чем правило (rule) отличается от токена (token)? На самом деле и правила и токены представляют собой обычные именованные регулярные выражения (для объявления которых в Perl 6 есть ключевое слово regex), разница заключается лишь в поведении по умолчанию. Токены — это регулярные выражения с модификатором :ratched, а правила — это регулярные выражения с модификаторами :ratched и :sigspace.

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

Согласитесь, пока что от грамматик мало толку, потому что они вроде бы ничем не отличаются от регулярных выражений. В действительности это не так. Для начала, грамматики поддерживают наследование. Например, вы можете объявить грамматику, определяющую правила для работы с многострочными комментариями в стиле С++, а затем создать грамматики для парсинга кода на C++, PHP и Java, унаследованные от нее.

Но настоящая сила грамматик заключается в том, что они позволяют с легкостью строить абстрактные синтаксические деревья. Вот как это выглядит:

Здесь мы объявили класс Lisp::Simple::Actions и передали его экземпляр в метод parse нашей грамматики. Каждый раз, когда грамматика завершает обработку некого регулярного выражения, она вызывает одноименный метод объекта $actions, передавая ему экземпляр класса Match. Последний содержит в себе информацию об обработанных данных, а также имеет атрибут ast, предназначеенный для хранения абстрактного синтаксического дерева или любого другого пэйлоада.

Рассмотрим к примеру токен value и соответствующий ему метод:

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

Метод make класса Match производит присвоение атрибуту ast, а метод Str служит для преобразования объекта в строку. Другими словами, мы просто берем часть строки, которая соответствует value, и записываем ее в ast.

В момент вызова метода arg мы не знаем точно, встретилось ли нам конкретное значение или целое выражение, которое, в свою очередь, могло содержать вложенные выражения. Однако нам это и не обязательно узнавать, потому что в $/.values[0].ast будет содержаться в точности то, что мы передали методу make при вызове value или lst. Поэтому мы берем это значение и спокойно передаем его «наверх», другим методам.

Тут все довольно просто. Мы можем работать с экземпляром класса Match, как со словарем. В приведенном коде мы берем то, что пришло от методов op и args, кладем их в один словарь и передаем «наверх».

Все аргументы хранятся в списке $<arg>, элементы которого являются экземплярами класса Match. К этому списку мы применяем гипероператор >>.ast. По сути — это обычный map. То есть мы извлекаем пэйлоад каждого элемента списка, складываем их все в новый список, который сохраняется в атрибуте ast.

В общем, в итоге программа выведет следующее (отступы добавлены мною):

Представленную структуру без труда можно интерпретировать или к примеру транслировать в код на языке Си. Если желаете, можете считать это своим домашним заданием.

Грамматики Perl 6 используются, например, в модулях XML::Parser::Tiny и JSON::Tiny. Следует однако отметить, что на момент написания этих строк грамматики в Perl 6 работали не очень быстро. Например, сейчас парсинг XML файла размером 25 Кб занимает на средненьком по нынешним меркам компьютере около восьми секунд. Впрочем, производительность Rakudo Perl 6 существенно увеличивается с каждым новым релизом, так что к моменту, когда вы будите читать этот пост, ситуация может измениться.

А теперь настало время проверить, насколько хорошо вы усвоили материал :) Как вы считаете, почему при работе с грамматиками в Perl 6 мы должны использовать именно метод make класса Match, вместо того, чтобы просто использовать внутреннее состояние класса Lisp::Simple::Actions?

Дополнение: В продолжение темы — создание собственного модуля в Perl 6.

Метки: Perl.