Перевод статьи: Perl Design Patterns, Part 2
Автор: Фил Кроу (Phil Crow)
Это вторая статья из серии статей, составляющих единый ответ программистов Perl на книгу "Шаблоны проектирования" (также известную как "книга банды четырёх", поскольку её написали четверо авторов).
Как было показано в первой статье, Perl предоставляет лучшие шаблоны в составе своего ядра и многих модулей, поставляемых в его составе или доступных на CPAN. Были рассмотрены Итератор (foreach), Декоратор (каналы Unix и фильтры списков), Приспособленец (Memoize.pm) и Одиночка ("благословение" объекта в блоке BEGIN).
Люди, знающие шаблоны, часто говорят о том, что знание шаблонов позволяет проще описывать проект. Комментарии в скобках в прошлом абзаце показывают, насколько много Perl может взять от шаблонов, если встроить их в сам язык.
В этой статье продолжается обсуждение шаблонов, относящихся к контейнерам данных и/или ссылкам на код (которые также часто называются обратными вызовами или коллбэками). Перед рассмотрением шаблонов позвольте мне объяснить эти понятия.
Я использую контейнеры данных в качестве понятия, подразумевающего какую-либо ссылку, содержащую структуру данных. Массивы и хэши - это обычные контейнеры данных, но более интересны хэши списков хэшей. При аккуратном использовании этих контейнеров зачастую можно обойтись без объектов.
Вот конкретный пример. Предположим, что мне нужен список телефонов. Я могу воспользоваться вот таким контейнером:
my $phone_list = {
'Phil' => [
{ type => 'home', number => '555-0001' },
{ type => 'pager', number => '555-1000' },
],
'Frank' => [
{ type => 'cell', number => '555-9012' },
{ type => 'pager', number => '555-5678' },
{ type => 'home', number => '555-1234' },
],
};
Этот контейнер располагается в хэше. Его ключи - это имена; его значения - телефонные номера. Номера помещаются в список в том порядке, в котором желательно их использовать. (Звонить Фрэнку сначала на сотовый телефон, потом на пэйджер. Если дозвониться на них не удалось, тогда можно попробовать домашний телефон.)
Я могу пользоваться этой структурой следующим образом:
#!/usr/bin/perl
use strict; use warnings;
my $phone_list = {
'Phil' => [
{ type => 'home', number => '555-0001' },
{ type => 'pager', number => '555-1000' },
],
'Frank' => [
{ type => 'cell', number => '555-9012' },
{ type => 'pager', number => '555-5678' },
{ type => 'home', number => '555-1234' },
],
};
my $person = shift or die "Способ использования: $0 человек\n";
foreach my $number (@{$phone_list->{$person}}) {
print "$number->{type} $number->{number}\n";
}
В этом примере пользователь указывает имя человека, которому нужно дозвониться, в командной строке, в качестве аргумента, который программа сохраняет в переменную $person. Затем программа перебирает все телефонные номера этого человека, выводя тип номера и сам номер.
Конечно, на практике данные могут находиться вне скрипта. Пример просто показывает, что может содержать контейнер данных.
Если нужно воспользоваться структурой, состоящей из данных в её узлах, зачастую можно обойтись без объекта-узла при помощи контейнера данных. Сторонники объектно-ориентированного программирования скорее всего захотят сделать каждого человека отдельным объектом. В таком объекте они захотят хранить объект с телефонным номером каждого типа в некоем громоздком контейнере-списке. Совет: не становитесь педантами. Даже в Java можно создать структуру, подобную приведённой выше (хоть это и не просто). Часто целесообразно поступать именно так. Объекты лучше использовать в более сложных случаях.
Ссылка на код подобна любой другой ссылке в Perl, но она указывает на подпрограмму, которую можно вызвать. Например, я могу написать:
my $doubler = sub { return 2 * $_[0]; };
А затем я могу вызвать эту подпрограмму:
my $doubled = &$doubler(5); # Теперь $doubled равно 10
Это надуманный пример, но он демонстрирует основы синтаксиса ссылок на код. Если присвоить подпрограмму переменной, получится ссылка на код, благодаря Perl. Чтобы вызвать сохранённую в ссылке подпрограмму, поместите перед переменной знак &. То же самое обычно делается обычно при переборе элементов хэша:
foreach my $key (keys %$hash_reference) { ... }
Знак & - это сигил (или забавный символ) для подпрограмм, как @ и % - сигилы для массивов и хэшей.
Многие шаблоны банды четырёх и за её пределами можно легко реализовать в Perl при помощи ссылок на код. Языки, не имеющие ссылок на код, остались без важного типа данных.
Объяснив эти инструменты, я готов продемонстрировать шаблоны, которые их используют.
Когда нужно выбрать какое-то одно действие из некоего множества, пригодится шаблон "Стратегия". Например, может потребоваться выполнить сортировку с использованием определённой функции сравнения. При каждой сортировке имеется возможность задать стратегию сортировки.
Поскольку в Perl есть ссылки на код, можно легко реализовать шаблон стратегии без раздувания кодовой базы множеством классов, назначение каждого из которых - предоставить одну функцию.
Вот пример встроенной сортировки:
sort { lc($a) cmp lc($b) } @items
Это сортировка без учёта регистра. Отметим, что функция сравнения определяется вместе с вызовом sort. Хотя можно сделать для этого отдельные функции, более распространён приём, при котором функция сравнения передаётся в качестве аргумента для позиционного параметра, требующего ссылку на функцию.
Предположим, что нужно получить список всех файлов с определённым свойством в текущем каталоге или его подкаталогах. Есть две части задачи: (1) просканировать дерево каталогов, и (2) проверить каждый файл на соответствие условию. Лучше, если можно разделить эти задачи, чтобы потом можно было повторно использовать их поотдельности (например, просто просканировать дерево каталогов, без проверки каких-либо условий). Проверку условия можно сделать стратегией, выполняемой сканером каталога.
#!/usr/bin/perl
use strict; use warnings;
my @files = find_files(\&is_hidden, ".");
local $" = "\n";
print "@files\n";
sub is_hidden {
my $file = shift;
$file =~ s!.*/!!;
return 0 if ($file =~ /^\./);
return 1;
}
sub find_files {
my $callback = shift;
my $path = shift;
my @retval;
push @retval, $path if &$callback($path);
return @retval unless (-d $path);
# Определился подкаталог
opendir DIR, $path or return;
my @files = readdir DIR;
closedir DIR;
# Обходим каждый подкаталог
foreach my $file (@files) {
next if ($file =~ /^\.\.?$/); # Пропускаем каталоги . и ..
push @retval, find_files("$path/$file", $callback);
}
return @retval;
}
Для понимания примера начнём с первого вызова find_files. В него передаётся два аргумента. Первый - это ссылка на код. Обратите внимание на синтаксис. Как я уже упомянул во введении, чтобы Perl знал, что подразумевается подпрограмма, перед is_hidden нужно поместить сигил &. Чтобы сделать ссылку на подпрограмму (вместо её немедленного вызова), нужно поместить перед ней обратную косую черту, точно так же, как и для получения ссылок других типов.
При использовании коллбэка в find_files, $callback содержит ссылку на код. Для её разыменования нужно поместить перед ней сигил &.
Подпрограмма find_files получает путь, с которого нужно начинать поиск и ссылку на код с именем $callback. При каждом вызове подпрограмма сохраняет путь в возвращённом списке, если коллбэк возвращает для этого пути истину. Это позволяет повторно использовать find_files во многих других программах, изменяя только коллбэк, чтобы изменить результат. Это шаблон "Стратегия", но без надоедливого наследования от абстрактного базового класса find_files и замены метода с условием отбора.
В find_files используется рекурсия для спуска по дереву каталогов. Сначала вызвается коллбэк, чтобы удостовериться, что этот путь должен попасть в результат. Затем начинается настоящая подпрограмма. Чем занимается коллбэк - для этой подпрограммы не важно. find_files примет любое значение - истину или ложь.
Рекурсия прекращается, если файл не является каталогом. В этом случае немедленно возвращается список. (Он может быть пустым или содержать текущий путь, в зависимости от значения, возвращённого коллбэком.) В противном случае, все файлы и каталоги в текущем пути читаются в @files. Каждый из элементов сканируется рекурсивно при помощи find_files (если это не каталог . или .., которые приведут к бесконечной рекурсии). Что бы ни вернул рекурсивный вызов find_files, его результат помещается в конец итогового списка. Когда все подкаталоги проверены, вызывающему коду возвращается @result.
Модуль File::Find на CPAN решает ту же задачу более основательно, чем в примере выше. Он исользует точно такую же разновидность коллбэков.
Шаблон "Стратегия" использует функции коллбэк для решения одной и той же задачи, которая каждый раз может немного отличаться. Следующий шаблон использует несколько функций коллбэков для реализации шагов алгоритма.
В некоторых расчётах известны этапы, но заранее не известно, что делает каждый из этапов. Например, расчёт арендных выплат может состоять из трёх этапов:
Разные арендодатели могут использовать разные схемы расчёта суммы по ставкам, а в разных ведомствах обычно разные схемы налогообложения. Шаблонный метод может реализовать план, детали которого зависят от индивидуальных схем расчёта, используемых вызывающим кодом.
package Calc;
use strict; use warnings;
sub calculate {
my $class = shift; # отбрасывается
my $data = shift;
my $rate_calc = shift; # ссылка на код
my $tax_calc = shift; # тоже ссылка на код
my $rate = &$rate_calc($data);
my $taxes = &$tax_calc($data, $rate);
my $answer = $rate + $taxes;
}
В этом примере вызывающий код предоставляет ссылку на данные (например, на хэш или на объект) совместно с двумя ссылками на код, которые используются в качестве коллбэков. Каждый из коллбэков должен ожидать ссылку на данные в первом параметре. Ссылка на код tax_calc code также принимает сумму по ставкам. Это позволяет использовать процент от суммы вместе с информацией по ссылке на данные.
Вызывающий код может выглядеть следующим образом:
#!/usr/bin/perl
use strict; use warnings;
use Calc;
my $rental = {
days_used => 5,
day_rate => 19.95,
tax_rate => .13,
};
my $amount_owed = Calc->calculate($rental, \&rate_calc, \&taxes);
print "С вас причитается $amount_owed\n";
sub rate_calc {
my $data = shift;
return $data->{days_used} * $data->{day_rate};
}
sub taxes {
my $data = shift;
my $subtotal = shift;
return $data->{tax_rate} * $subtotal;
}
Этот надуманный пример показывает последовательность вызовов. Данные в этом примере - это просто хэш. Чтобы уменьшить таблицу экспорта из модуля Calc, я сделал функцию calculate методом класса, поэтому её нужно вызывать через класс. При вызове передаются аргументы - ссылка на хэш с данными и ссылки на две подпрограммы для расчётов.
Если хочется, то пример можно и усложнить. Можно сделать полномасштабную иерархию классов-калькуляторов, позволяющих вызывающему коду выбирать нужные действия. Это пример простейшей пример реализации шаблонного метода.
Другой подход к шаблонизации заключается в том, чтобы поместить вызовы методов в пакет с шаблоном. Этот подход основывается на использовании примесей (mixin), как в Ruby. Вот более объектно-ориентированный пример.
package Calc;
sub calculate {
my $self = shift;
my $rate = $self->calculate_rate();
my $tax = $self->calculate_tax($rate);
return $rate + $tax;
}
1;
Весь модуль фактически состоит лишь из одного шаблонного метода. Для его использования нужно определить методы calculate_rate и calculate_tax, в противном случае скрипт завершится с ошибкой. Вот возможная реализация этого класса:
package CalcDaily;
package Calc;
use strict; use warnings;
sub new {
my $class = shift;
my $self = {
days_used => shift,
day_rate => shift,
tax_rate => shift,
};
return bless $self, $class;
}
sub calculate_rate {
my $data = shift;
return $data->{days_used} * $data->{day_rate};
}
sub calculate_tax {
my $data = shift;
my $subtotal = shift;
return $data->{tax_rate} * $subtotal;
}
1;
Отметим, что я добавил конструктор и два метода к пакету Calc в другом файле. Это совершенно законно и иногда полезно, при этом шаблон полностью изолирован. Он совершенно не знает о том, какой вид данных хранится в объектах его типа. Это означает, что одновременно может использоваться только один подтип Calc. Если это не удобно, можно прибегнуть к обычному решению: поместить методы, которые вызываются из Calc, в объекты отдельных иерархий.
Два выражения package в начале файла добавлены в определённых целях. Первое говорит о том, что это пакет CalcDaily, который по праву принадлежит файлу CalcDaily.pm, а не исходный Calc, принадлежащий Calc.pm.
Наконец, приведём пример слегка изменённого вызывающего кода:
#!/usr/bin/perl use strict; use warnings; use Calc; use CalcDaily; my $rental = Calc->new(5, 19.95, .13); my $amount_owed = $rental->calculate(); print "С вас причитается $amount_owed\n";
Приём похож на тот, который используется в архитектуре отладчика Perl. Чтобы сделать собственный отладчик, нужно придумать для него имя. Допустим, это PhilDebug.pm. Тогда я создаю файл с таким именем в каталоге Devel, находящемся среди каталогов из списка @INC. Первой строкой файла должна (но не обязана) быть:
package Devel::PhilDebug;
Так индексатор CPAN сможет найти каталог с этим модулем.
Базовый пакет для отладчиков - это пакет DB. Perl ожидает, что в этом пакете есть функция DB. Поэтому вместе это может выглядеть следующим образом:
package Devel::PhilDebug;
package DB;
sub DB {
my @info = caller(0);
print "@info\n";
}
1;
Любой скрипт сможет использовать этот отладчик, если его вызвать следующим образом:
perl -d:PhilDebug script
Каждый раз, когда отладчик уведомляется о том, что началось новое выражение, он сначала вызовает DB::DB. Это очень мощный пример plug-and-play, то есть изменения системы путём добавления компонента.
В большинстве случаев не очень разумно загрязнять внешние классы собственным кодом. Однако, Perl это допускает, потому что иногда это очень полезно. Подумайте над этим:
Не стоит запрещать опасное. Стоит просто избегать этого, пока не появится достаточно разумная причина.
Шаблоны Стратегия и Шаблонный метод используют ссылки на код, чтобы дать вызывающему коду уточнить поведение алгоритма. Рассмотренный Шаблонный метод использует контейнер с данными для хранения информации об аренде. Следующий шаблон расширяет использование контейнеров данных.
Многие внешние по отношению к программе структуры внутри программы должны быть представлены составными структурами (как деревья или контейнеры данных во введении). Есть два основных подхода к представлению данных в этих структурах. В объектно-ориентированном подходе для составления таких структур используется шаблон Композиция (который будет обсуждаться в следующей статье).
Сейчас же мы рассмотрим, как создать составную структуру на основе хэша хэшей. Возможно вы предпочтёте создать объектно-ориентированную версию такой структуры. Что выбрать - зависит от сложности данных и методов их обработки. Если данные и методы просты, скорее всего вы захотите использовать просто хэши. Они быстрее, их поддержка встроена в Perl и их проще понять Perl-программистам, которым может потребоваться сопровождать ваш код. Если сложность велика, лучше воспользоваться полновесными объектами. Их структура проще воспринимается объектно-ориентированными программистами и позволяет достичь большей самодокументированности, чем при использовании простых хэшей.
Итак, хэши - это превосходные структуры для хранения составных данных различной сложности: от простых до умеренно сложных. Чтобы увидеть, как построить структуру на основе хэша, обратимся к примеру: визуализация плана. Для простоты я представляю план простыми отступами (а не римскими числами или какими-то другими способами нумерации). Вот пример плана:
Бакалейная лавка
Молоко
Сок
Мясник
Тонкие ломтики ветчины
Жареный цыплёнок
Сыр
Очистители
Товары для дома
Дверь
Замок
Шайба
Этот план описывает предполагаемый маршрут покупок. Нужно представить его внутри программы так, чтобы с ним можно было работать. (Одна из моих любимых игр - превращать план в картинку, смотрите ниже.)
Вместо полномасштабного объекта я воспользуюсь небольшим контейнером данных на основе хэша, для каждого узла дерева. Каждый узел содержит одну из следующих сущностей:
Для сохранения иерархии, кто чьим дочерним элементом является, воспользуемся стеком узлов. Узел на вершине стека обычно является родительским для следующей поступающей строки. Для иллюстрации этого метода я снабдил скрипт комментариями. В конце этого раздела скрипт будет приведён целиком.
#!/usr/bin/perl use strict; use warnings;
Эти строки всегда полезны.
my $root = {
name => "ROOT",
level => -1,
children => [],
};
Это корневой узел. Он является ссылкой на хэш, содержащий три ключа, описанных выше. Корневой узел - особый. Поскольку его нет в файле, ему назначено искусственное имя и уровень, меньший чем у какого-либо другого узла. (Кстати, предполагается, что уровень вложенности поступающих данных может быть нулевым или положительным.) Начальный список дочерних элементов пуст.
my @stack; push @stack, $root;
Стек будет содержать предков каждого нового узла. Для начала нужен корневой узел, который никогда не вставляется в стек, потому что является предком для всех узлов.
while (<>) {
/^(\s*)(.*)/;
my $indentation = length $1 if defined ($1);
my $name = $2;
Для чтения строк из файла используется цикл while. Каждая строка состоит из двух частей: отступа (ведущих пробелов) и имени (остаток строки). Регулярное выражение захватывает ведущие пробелы в строку $1, а всё остальное (за исключением символа новой строки) - в строку $2. Чем больше длина отступа, тем больше предков имеет узел. Строки, начинающиеся у края, имеют нулевой отступ (вот почему узел ROOT имеет уровень -1).
while ($indentation <= $stack[-1]{level}) {
pop @stack;
}
Этот цикл обрабатывает предков. Он помещает в стек новый элемент, если узел на верхушке стека является родителем нового узла. Например, когда мы заходим в Товары для дома, Очистители и ROOT уже находятся в стеке. Уровень Товаров для дома - нулевой (он находится на краю), как у Очистителей. Однако, Очистители уже находятся в стеке (поскольку 0 <= 0). Тогда остаётся только ROOT, поэтому вставка прекращается (0 не <= -1).
my $node = {
name => $name,
level => $indentation,
children => [],
};
Так создаётся новый узел для текущей строки. Задаются его имя и уровень. Пока что у него нет детей, но создаётся место для них - пустой список.
push @{$stack[-1]{children}}, $node;
Эта строка добавляет новый узел к списку детей его родителя. Отметим, что родитель находится на верхушке стека. Верхушка стека - это $stack[-1] или последний элемент массива.
push @stack, $node; }
Здесь новый узел кладётся в стек, если у него есть дети. Закрывающая скобка завершает цикл чтения строк. Для простоты результат отображается при помощи Data::Dumper:
use Data::Dumper; print Dumper($root);
Выполнение этой строки выведет дерево (растущее вправо) на стандартный вывод.
Весь код целиком:
#!/usr/bin/perl
use strict; use warnings;
my $root = {
name => "ROOT",
level => -1,
children => [],
};
my @stack;
push @stack, $root;
while (<>) {
/^(\s*)(.*)/;
my $indentation = length $1;
my $name = $2;
while ($indentation <= $stack[-1]{level}) {
pop @stack;
}
my $node = {
name => $name,
level => $indentation,
children => [],
};
push @{$stack[-1]{children}}, $node;
push @stack, $node;
}
use Data::Dumper; print Dumper($root);
Я обещал объяснить, как подобные структуры можно превратить в картинки. Модуль UML::Sequence из CPAN строит структуру, похожую на показанную здесь. Затем он использует её для того, чтобы сгенерировать последовательность диаграмм UML по этапам в формат SVG (Scalable Vector Graphics - масштабируемая векторная графика). Этот формат можно сконвертировать при помощи стандартных инструментов, например Batik, в PNG или JPEG. На практике контуры, которые я преобразую в картинки, изображают последовательность вызовов программ. Perl даже может сгенерировать контур, запустив программу. За более подробной информацией обратитесь к UML::Sequence.
Если понадобится прочитать какие-то данные с необычной структурой, строитель может помочь в формировании соответствующей внутренней структуры данных. Один из таких строителей - XML::DOM. Другой, XML::Twig, обладает несколько другим подходом. Не случайно, что средства для чтения XML являются строителями, потому что файлы XML - это не-двоичные деревья.
Если вы ещё не смотрели книгу банды четырёх, начните с шаблона "Интерпретатор". Посмейтесь от души. Человек, который сообщил мне об этом шаблоне в Java не понимал, почему этот шаблон на практике не работает. Он слышал, что этот шаблон слишком медленный, но не был уверен. Зато уверен я.
К нашему счастью, в Perl есть альтернативы. Это широкий спектр альтернатив от быстрых и грязных до полномасштабных решений. Мантру образуют следующие примеры:
Поскольку у нас уже есть язык, который нам нравится (если кто не в курсе - это Perl), применение шаблона "Интерпретатор" ограничивается малыми языками. Обычно это бывают файлы конфигурации, поэтому остановлюсь на них. (Смотрите раздел "Строитель", если данные из файла можно представить в виде дерева.)
Простейшее решение - воспользоваться split. Предположим, что есть файл конфигурации, содержащий настройки вида переменная=значение. Комментарии и пустые строки игнорируются, а все остальные строки должны состоять из пары переменная-значение. Это просто:
sub parse_config {
my $file = shift;
my %answer;
open CONFIG, "$file" or die "Не могу прочитать файл конфигурации $file: $!\n";
while (<CONFIG>) {
next if (/^#|^\s*$/); # Пропускаем пустые строки и комментарии
my ($variable, $value) = split /=/;
$answer{$variable} = $value;
}
close CONFIG;
return %answer;
}
Эта подпрограмма принимает имя файла конфигурации. Она открывает его и читает. Внутри цикла чтения строк регулярное выражение отбрасывает строки, начинающиеся с "#" и состоящие только из пробельных символов. Все другие строки делятся по знаку "=". Переменные становятся ключами хэша %answer. После чтения всех строк подпрограмма возвращает хэш.
Обработка строк могла бы быть и более сложной, но сначала ознакомьтесь со следующими подходами (обратите особое внимание на Config::Auto).
Мой любимый способ превратить файл конфигурации в программу на Perl - написать его на Perl. Например, файл конфигурации может быть таким:
our $db_name = "projectdb"; our $db_pass = "my_special_password_no_one_will_think_of"; our %personal = ( name => "Фил Кроу", address => "philcrow2000@yahoo.com", );
Всё, что нужно для его использования в программе на Perl, это вычислить его при помощи eval:
... open CONFIG, "config.txt" or die "Не могу...\n"; my $config = join "", <config>; close CONFIG; eval $config; die "Не удалось вычислить ваш файл конфигурации: $@\n" if $@; ...
Перед чтением файла он открывается, затем используется join и оператор чтения в списковом контексте. Это позволяет поместить весь файл в скаляр. Как только он оказывается там (и для порядка - файл оказывается закрытым), прочитанная строка просто вычисляется при помощи eval. Затем нужно проверить $@, чтобы убедиться, что файл был правильной программой на Perl. Затем можно просто использовать значения переменных точно так же, как будто они изначально были в программе.
Если вы слишком ленивы для того, чтобы писать собственный обработчик конфигурации или если многие файлы конфигурации могут редактировать другие люди, возможно вам подойдёт модуль Config::Auto. В общем, он берёт файл и соображает, как превратить его в хэш конфигурации. (Он может догадываться, ориентируясь на имя файла конфигурации). Использовать его просто (если это сработает):
#!/usr/bin/perl
use strict; use warnings;
use Config::Auto;
my $config = Config::Auto::parse("your.config");
...
Чем всё закончится - зависит от того, как выглядит файл конфигурации (внезапно). В случае файла вида переменная=значение получится то, что ожидается: то же самое, что получилось в первом примере. Можно указать файл конфигурации, который Config::Auto не сможет понять (страх и ненависть).
Если нужный вам файл сложен, положитесь на Parse::RecDescent. Он реализует умный разбор файла сверху вниз. Чтобы им воспользоваться, нужно указать грамматику. (Вы ведь её помните, не так ли? Если нет, читайте дальше.) Модуль создаёт обработчик по вашей грамматике. Вы скармливаете текст обработчику, а он выполняет действия, указанные в описании грамматики.
Чтобы понять, как он работает, попробуем разобрать римские числа. Программа ниже считывает числа с клавиатуры и преобразует их из римских в десятичные, так что XXIX превращается 29.
#!/usr/bin/perl
use strict; use warnings;
use Parse::RecDescent;
my $grammar = q{
Numeral : TenList FiveList OneList /\Z/
{ $item[1] + $item[2] + $item[3]; }
| /quit/i { exit(0); }
| <error>
TenList : Ten(3) { 30 }
| Ten(2) OptionalNine { 20 + $item[2] }
| Ten OptionalNine { 10 + $item[2] }
| OptionalNine { $item[1] }
OptionalNine : One Ten { 9 }
| { 0 }
FiveList : One Five { 4 }
| Five { 5 }
| { 0 }
OneList : /(I{0,3})/i { length $1 }
Ten : /X/i
Five : /V/i
One : /I/i
};
my $parse = new Parse::RecDescent($grammar);
while (<>) { chomp; my $value = $parse->Numeral($_); print ``Значение: $value\n''; }
Как вы успели заметить, большую часть программы составляет описание грамматики. Оставшаяся часть очень проста. В ней я просто получил обработчик от конструктора Parse::RecDescent, и дальше просто вызываю метод Numeral в цикле.
Как понять эту грамматику? Начнём сначала. Грамматика состоит из правил. Правило для Numeral (римских чисел) говорит:
Numeral (римские числа) образованы одним из вариантов: TenList (список десяток), затем FiveList (список пятёрок) и, наконец, из OneList (списка единиц) ИЛИ слово quit (не является римским числом, но позволяет завершить разбор) ИЛИ что-то другое, что воспринимается как ошибка.
Итак, видно что сначала идёт TenList и компания. Код после первого варианта называется действием. Если правило соответствует возможности, оно производит действие для этой возможности. Поэтому если найдено правильное Numeral (римское число), выполняется действие. Это отдельное действие складывает значения, накопленные TenList, FiveList и OneList. Элементы нумеруются начиная с 1, поэтому значение TenList располагается в $item[1] и т.д.
Как получается значение TenList? Итак, если начало Numeral подходит, идёт поиск первого действительного TenList. Есть четыре возможности:
TenList соответствует одному из следующих вариантов: три Tens (три десятки) ИЛИ два Tens (две десятки), затем OptionalNine (необязательная девятка) ИЛИ Ten (десятка), затем OptionalNine ИЛИ OptionalNine
Эти варианты сопоставляются по порядку. Ten (десятка) - это просто буква X в верхнем или нижнем регистре (смотрите правило Ten). Результат действия - это результат его последнего выражения. Так что, если обнаружено три десятки, TenList вернёт 30. Если обнаружено две десятки, TenList вернёт 20 плюс то, что вернёт OptionalNine.
Римское число IX - это наше 9. Я назвал его OptionalNine (необязательная девятка). (Имена могут быть совершенно произвольными.) Итак, после нуля, одного или двух X'ов может идти IX, которое добавит к результату 9. Если IX отсутствует, OptionalNine совпадёт с пустым правилом. Это правило не забирает поступающий текст и возвращает ноль.
Римские числа намного более сложны, чем грамматика, которую я обрабатываю. Для начала, по моему календарю сейчас MMIII год. В этой грамматике нет M. К тому же, некоторые римляне думали, что число IIIIII совершенно правильное. В моей грамматике три - это предельное количество повторов и повторяться могут только I и X. Кроме того, вычитание может отнимать только единицу. Поэтому IIX - не восемь, это не правильное число. Эта грамматика может распознать любое нормализованное римское число вплоть до 38. Вы вольны дополнить грамматику.
Parse::RecDescent не настолько быстр, как синтаксический анализатор, сгенерированный yacc, но им проще пользоваться. Обратитесь к документации в составе дистрибутива за более подробной информацией, особенно к учебнику, который изначально появился в The Perl Journal.
Если посмотреть, что находится внутри синтаксического анализатора (например, при помощи Data::Dumper), можно решить, что он на самом деле реализует шаблон Интерпретатор. Всё-таки он создаёт из грамматики дерево объектов. Приглядитесь и заметите ключевые отличия. Все объекты дерева являются членами классов, подобных Parse::RecDescent::Action, которые были написаны Дэмианом Конуеем (Damian Conway), когда он писал модуль. По представлениям банды четырёх, шаблон Интерпретатор должен создавать класс для каждой неоконечной грамматики (в примере выше классами стали бы Numeral, ReducedTen и т.д.). Однако, типы узлов дерева отличаются для каждой грамматики.
Это отличие заключается в двух предположениях: (1) это делает генератор синтаксических анализаторов RecDescent проще и (2) его результат быстрее.
В этой части мы познакомились с использованием ссылок на код для реализации шаблонов Стратегия и Шаблонный метод. Мы даже рассмотрели, как поместить код в чужой класс. Строитель превращает текст во внутреннюю структуру данных, чем и занимается большинство Интерпретаторов. Эти структуры часто могут быть просто сочетаниями хэшей, списков и скаляров. Если вам нужна простота чтения, воспользуйтесь split или Config::Auto. Если нужно что-то сложнее, воспользуйтесь Parse::RecDescent. Если он работает недостаточно быстро, может потребоваться один из генераторов синтаксических анализаторов, подобных yacc.
В следующий раз мы рассмотрим шаблоны, которые действительно относятся к объектам.