Personal notes

Техническое задание в формате Perl 6 Pod

2012-01-27T10:00:00Z

Ранее я уже рассказывал о полезных свойствах такого документа как техническое задание ^[1]. В этот раз я расскажу о том, как я пишу подобные документы.

Я пробовал когда-то создавать проектную документацию по ГОСТу ^[2], но данный подход оказался «несовместим» с реальной жизнью. В итоге я пришел к менее формальному решению и использую последние годы следующую структуру этого документа:

 Заголовок: Техническое задание на разработку
 Изменения
 Основные положения
 Release Notes
 Терминология и Соглашения
 Что необходимо сделать
 Идеи и дополнения

где,

Изменения

Список значимых изменений в документе. Каждая запись начинается с даты и версии документа. Изменения отсортированы в порядке устаревания.

    =CHANGES
    Jan 22th 2012(v0.3)[zag]   Изменения в алгоритме работы crawler (+ определение качества фильма). 
    Jan  6th 2012(v0.2)[zag]   Основные функциональные блоки.
    Dec 24th 2011(v0.1)[zag]   Начальная версия

Основные положения

Здесь описывается идея и общий результат. Данный раздел начинается с фразы: «Требуется разработать ...».

  =head1 Основные положения

   Требуется разработать систему размещения рекламных объявлений 
   на виджетах со следующими возможностями:

  =item Создание и редактирование рекламных компаний
  =item Отображение рекламы на виджетах
  =item Сбор статистической информации (показы, переходы)

Описание целей сопровождаются снимками прототипов (или набросками от руки).

Release Notes

Список задач, которые станут частью выпускаемых версий. Задачи формулируются в виде строк, которые будут затем перенесены в Release Notes к каждой версии.

Например:

 =head1 Release Notes

 * Отображение рекламы на виджетах 
 * Рабочее место менеджера рекламных компаний ( управление рекламными компаниями 
   и просмотр статистики)
 * Регистрация отображения рекламных сообщений и переходов по ссылкам

Терминология и соглашения

Здесь полезно дать определение базовым терминам.

Если в ТЗ вводится новая терминология, то в таких случаях желательно разместить более подробную информацию, например копии экранов, возможно указать часть бизнес логики, где та или иная сущность используется.

 =head1 Терминология и соглашения

 Термины, котороые появляются в контексте «Системы рекламных сообщений»:

 =defn Медиаплан
 реклмное объявление, которое ...
 =defn Карточка медиаплана
 форма отображения свойств медиаплана, содержащая ...

Что необходимо сделать ?

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

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

 =head1 Что необходимо сделать ?
 =head2 Общая структура

 Рассмотрим общую структуру, на которой выделим составные части и связи между ними:

     РИСУНОК ОБЩЕЙ СТРУКТУРЫ

 , где (1) - web интерфейс (рабочее место менеджера рекламных компаний)

 =head3 Рабочее место менеджера рекламных компаний

Идеи и дополнения

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

Обычное содержимое этого раздела следующее:

  =head1 Идеи и дополнения

  ___________________________________________________
  ___________________________________________________
  ___________________________________________________
  ___________________________________________________
  ___________________________________________________

За основу такой структуры ТЗ, я взял документ из какого-то зарубежного блога, посвященного тематике разработки Web проектов. Возможно подойдет определение «функциональная спецификация», но как бы то ни было, наличие этого документа облегчает жизнь всем.

NOTES

^1. Как POD помог мне. http://zag.ru/a4C81

^2. Техническое задание согласно ГОСТу. http://it-gost.ru/content/view/101/51/

Грамматики для Perl 5 и JavaScript

2012-01-13T10:00:00Z

В продолжение темы инструментов синтаксического анализа ^[1] опишу еще пару.

Прежде приведу ссылку на статью про основу построений грамматик в Perl 5 ^[2].

Парсер Marpa для Perl 5

Alexey Shrub (за что ему отдельное спасибо) подбросил ссылку на еще одну библиотеку для Perl 5 - Marpa ^[3]. Этому проекту около 4 лет и недавно вышла XS версия за номером 1.0 ^[4], что вроде как намекает на стабильность.

Вот пример грамматики, описывающей простой калькулятор:


my $grammar = Marpa::PP::Grammar->new(
    {   start   => 'Expression',
        actions => 'My_Actions',
        default_action => 'first_arg',
        rules   => [
            { lhs => 'Expression', rhs => [qw/Term/] },
            { lhs => 'Term', rhs => [qw/Factor/] },
            { lhs => 'Factor', rhs => [qw/Number/] },
            { lhs => 'Term', rhs => [qw/Term Add Term/], action => 'do_add' },
            {   lhs    => 'Factor',
                rhs    => [qw/Factor Multiply Factor/],
                action => 'do_multiply'
            },
        ],
    }
);

Непосредственно правила описываются в виде массива хэшей, в которых ключи lhs - имена правил, а ключи rhs описывают возможные комбинации значений. Marpa умеет вызывать обработчики правил для выполнения каких-либо действий (ключ action).

В правилах не используются регулярные выражения. Чтобы описать количество повторений используется ключ "min".

Например:

  # Эквивалент * в регулярных выражениях
  { lhs => 'sequence', rhs => ['item'], min => 0 }

Возможные значения должны быть перечислены явно:

    $recce->read( 'Number', 42 );
    $recce->read( 'Multiply', );
    $recce->read( 'Number', 1 );
    $recce->read( 'Add', );
    $recce->read( 'Number', 7 );

Это и есть расплата за игнорирование регулярных выражений в угоду скорости :-). Советую посмотреть программу по разбору CSS ^[5]. Там, в начале, производится анализ и сбор возможных значений с помощью регулярных выражений (никуда тут не денешься).

Также возможно будет интерсна стратья об использовании библиотеки Marpa-HTML ^[6] для обработки HTML. И я не советую смотреть в исходный код самого парсера Marpa-HTML ^[7].

Грамматики для JavaScript

Наиболее развитым, на мой взгляд, является PEG.js ^[8]

Парсер грамматик работает по принципу Javacc (да и по синтаксису очень похож): сначала описываются грамматики, а затем генерируется парсер. Генератор кода запускается под Node.js.

Вот пример грамматики для обработки арифметического выражения 2*(3+4):

start
  = additive

additive
  = left:multiplicative "+" right:additive { return left + right; }
  / multiplicative

multiplicative
  = left:primary "*" right:multiplicative { return left * right; }
  / primary

primary
  = integer
  / "(" additive:additive ")" { return additive; }

integer "integer" 
  = digits:[0-9]+ { return parseInt(digits.join(""), 10); }

Peg.js используется для обработки SQL-подобных запросов в http://ql.io/ ^[9].

NOTES

^1. Грамматики в Java, Perl 6 и Perl 5. http://zag.ru/2011/318/a1/grammatiki-v-Java-Perl-6-i-Perl-5.html

^2. О грамматиках в v5.10. http://www.effectiveperlprogramming.com/blog/1479

^3. Библиотека для синтаксического анализа Marpa. http://www.jeffreykegler.com/marpa

^4. Marpa::XS is now 1.000000. http://blogs.perl.org/users/jeffrey_kegler/2011/12/marpaxs-is-now-1000000.html

^5. Sample CSS Parser using Marpa::XS. https://gist.github.com/1511584

^6. How to Parse HTML. http://blogs.perl.org/users/jeffrey_kegler/2011/11/how-to-parse-html.html

^7. Marpa-HTML.http://search.cpan.org/dist/Marpa-HTML/

^8. Parser Generator for JavaScript.http://pegjs.majda.cz/

^9. Анонс инструментария для разработки mashup-приложений. http://www.opennet.ru/opennews/art.shtml?num=32463

Plosurin: Perl реализация Closure Templates

2012-01-12T10:00:00Z

Мой процесс избавления от Template::Toolkit ^[1] и вообще шаблонизаторов в какой-то момент замедлился. Причиной тому стали ситуации, когда перенос представления на сторону клиента грозил появлением новых проблем.

Вот пару типичных случаев:

статический текст из документации
Иногда, бывает очень удобно (в первую очередь для пользователя!) в интерфейсе сайта привести выдержку из документации. Обычно это статический текст в несколько абзацев, но может быть и целая страница с несколькими главами. Подобного рода данные, в случае, когда представление полностью перенесено на сторону клиента, помещаются в JavaScript библиотеки и затем загружаются браузером клиента.
Проблема здесь вполне очевидная: растет объем загружаемых данных. К тому же, не факт, что некоторые из них могут пригодится. Есть решения: это сжатие библиотек, использование отложенной загрузки требуемых частей (например, в GWT можно подгружать как код, так и ресурсы). Подобные рецепты приходится использовать, несмотря на привнесение некоторого усложнения разработки.
форматирование потока данных
Зачастую, возникают задачи потоковой обработки данных. К примеру, нужно сформировать объемную страницу (это может быть XML, HTML или тот же JSON) из потока данных, извлекаемых из базы. В этом случае проще формировать результирующий текст по мере извлечения записей. К тому же, браузер или устройство может обладать ограниченными возможностями, чтобы собрать страницу. Например, не хватит памяти в игровой приставке или телевизоре :-).

В client-side разработке я использую GWT и Google Closure, где тоже есть шаблоны. Я имею в виду Closure Templates, которые транслируются в программный код JavaScript и Java.

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

Таким образом появилось желание реализовать Closure Templates ^[2] для Perl. Транслятор Closure Templates реализован на Java и в Google работает небольшая команда (буквально пара-тройка) разработчиков, которые не в состоянии регулярно поддерживать сторонние языки. Поэтому логично было реализовать эту систему целиком на Perl ^[3].

Plosurin - Perl реализация Closure Templates

Perl реализаций на сегодня две:

Perl 6 ^[4]: Благодаря шикарной встроенной поддержке синтаксического анализа я начал разработку с реализации на Perl 6. На данный момент есть вероятность, что изменения в предстоящем релизе Rakudo привнесут нестабильность для некоторых программ ^[5]. По этой причине реализация на Perl 6 отложена.
Perl 5 ^[6]: Данная реализация, конечно, еще далека от совершенства, но минимально необходимый функционал реализован. Plosurin понимает структуру файлов с шаблонами, грамматику шаблонов и умеет обрабатывать переменные в математических выражениях. К тому же есть режим, когда Plosurin превращается в web сервер и позволяет ускорить разработку шаблонов.

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

NOTES

^1. Perl 5 модули, которые я использую реже и реже. zag.ru/b48j1

^2. Closure Templates Documentation. http://code.google.com/intl/ru-RU/closure/templates/docs/overview.html

^3. Сайт проекта Plosurin. plosur.in

^4. Perl 6 реализация Closure Templates. http://github.com/zag/plosurin

^5. ‘nom’ branch is now default, release status. rakudo.org/2011/09/09/nom-branch-default/

^6. Perl 5 реализация Closure Templates. http://github.com/zag/p5-plosurin

Реализация приоритетности операторов с помощью грамматик Perl 5

2011-12-12T10:00:00Z

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

Таблица приоритетности операторов

Приоритетность в математических ( и в любых других ) выражениях - вещь очень привычная. Для простого выражения:

    3 + 5 * 6

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

    +( *(5,6), 3 )

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

    ( 3 + 5 ) * 6

Синтаксическое дерево будет выглядеть иначе:

    *( +(3,5), 6 )

Как видим группирующие скобки вносят корректировку в последовательность вычислений.

И еще один пример выражения:

    - (2 * -3)

в котором используется унарный оператор - (минус) перед группирующей скобкой. Для него дерево будет следующее:

  -( *(2,-3) )

Унарный - имеет более высокий приоритет по сравнению с *.

Исходя из приведенных примеров можно составить таблицу приоритетов (3 - высший приоритет):

Таблица приоритетов
приоритет	оператор	описание, действие
1	+, -	сложение, вычитание
2	*, /	операторы умножения, деления
3	unary -	унарный минус

Грамматика, реализующая приоритетность, выглядит так:

 my $q = qr{
     <expr>
    <rule: expr>
                # бинарные операции +-
                <a=mult> <op=([+-])> <b=expr> 
                | <MATCH=mult> 

    <rule: mult> 
                <a=term> <op=([*/])> <b=mult> 
                | <MATCH=term>

     <rule: term> 
              <MATCH=Digit> 
            | <Sign=([+-])> \( <expr>\) # unary-
            | \( <MATCH=expr> \)   # группирующие скобки

    #токен, описывающий допустимый числовой агрумент
    <token: Digit>
            [+-]? \d++ (?: \. \d++ )?+ 
    }xms;

Как видим поиск совпадений начинается с поиска наиболее приоритетного унарного минуса и учета группирующих скобок (токен term), затем - операции * и / (правило mult) и т.д.

Представление синтаксичеcкого дерева в памяти

Результат успешной работы грамматик (структура совпадений правил) сохраняется в переменной %/. Отобразить результат можно следующим кодом:

    use Data::Dumper;
    my $t = q! 3 + 5 * 6 !;
    if ($t =~ $q) {
        print Dumper \%/;
    } else {
     warn "Error parse"
    }

Так, для исходного примера 3 + 5 * 6, результат применения грамматик будет выглядеть следующим образом:


      # 3 + 5 * 6 
      {
          'a' => '3', # первый аргумент - число
          # второй аргумент - выражение
          'b' => {    
                   'a' => '5',
                   'b' => '6',
                   'op' => '*'
                 },
          'op' => '+' # оператор
       };

Для выражения с унарным минусом:

     #- (2 * -3)
     {
     'expr' => {
                  'a' => '2',
                  'b' => '-3',
                  'op' => '*'
                },
     'Sign' => '-' 
     }

Чтобы полученные структуры можно было использовать как элементы синтаксического дерева, требуется ассоциировать с каждым правилом класс. Для этого достаточно заменить rule на objrule с указанием класса:

    <objrule: ExpClass::mult>  # объект оператора
                <a=term> <op=([*/])> <b=mult> 
                | <MATCH=term>

В результате мы получаем структуру объектов, построенную в соответствии с приоритетностью, определенной на уровне грамматик.

Синтаксический анализ XML

2011-12-02T10:00:00Z

Скорее всего можно было бы написать другую тему для этой статьи. Например: "когда можно применять грамматики, а когда нет" или "не всегда грамматики подходят", или вот такую модную "эти грамматики - они не всегда серебрянные". Но речь пойдет о обработке XML, в том числе с помощью грамматик Perl 5.

Задачей процесса синтаксического анализа текста почти всегда является построение дерева объектов. Каждый из объектов ассоциируется с той или иной сущностью обрабатываемого текста. Например, если производится обработка текста языка программирования, то объектами в итоге становятся операторы, подпрограммы, циклы или арифметические операторы. Поэтому, какие бы не взяли инструменты синтаксического анализа, в каждом присутствует механизм построения деревьев.

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

    <wd>
      <object class="isauth" id="auth_switch">
       <auth> 
        <object class="comp_unauth" id="ExitCP"/>
      </auth>
    </object>
    </wd>

Тэг wd является корневым, а его содержимое должно в итоге отобразиться в виде некой структуры в памяти:

    <object class="isauth" id="auth_switch" >
        └── auth
            └──<object class="comp_unauth" id="ExitCP">

Решение с помощью грамматик Perl 5

Итоговое решение с помощью грамматик Perl 5 получилось следующее:


    use Regexp::Grammars;
    my $q = qr{
    \A <File> \Z
    
    # Описание блока целиком
    # <wd>...</wd>
    <rule: File><start_block> <[childs]>+ <end_block>
    <rule: start_block>\<wd>
    <rule: end_block>\<\/wd>
    
    #Допустимые тэги
    <token: childs>           
                     <MATCH=object> |
                     <MATCH=any_tag> 
    
    #objrule - создает объект указанного класса
    <objrule: WebDAO::Lexer::object> <tag( tagname=>'object' )>
    <objrule: WebDAO::Lexer::any_tag> <tag>
    
    <rule: attribute> <name=([_\w]+)>=['"]<value=(?: ([^'"]+) )>['"]
    
    #argument :tagname
    <rule: tag>
        <matchpos>
        <matchline>
        (?{  
            $ARG{'tagname'} = 
                defined ($ARG{'tagname'}) 
                    ? quotemeta $ARG{'tagname'}
                    : '(\w+)';
            # setup defaults
                $MATCH{childs} //=[];
                $MATCH{attribute} //=[];
         })
        (?:         
         < <tagname=:tagname> 
               <[attribute]>* />
        )
        |
        (?:
        < <tagname=:tagname> <[attribute]>* >
                    <[childs]>*
           </ <:tagname> >
        )
  }xms;

Для описания отдельно взятого тэга в примере используется правило rule:tag. Грамматики Perl 5 предоставляют возможность передачи параметров для правил. Эта особенность позволяет точно описать допустимые тэги:


    #Допустимые тэги
    <token: childs>           
                     <MATCH=object> |
                     <MATCH=any_tag> 
    # правило для тэга 'object' 
    <objrule: WebDAO::Lexer::object> <tag( tagname=>'object' )>>
    #если параметр tagname не указан, то допускается любой тэг
    <objrule: WebDAO::Lexer::any_tag> <tag>

Параметр tagname используется в описании тэга XML для двух допустимых форм:

        (?:
         # пустой тэг
         < <tagname=:tagname>  <[attribute]>* />
        )
        |
        (?:
        < <tagname=:tagname> <[attribute]>* >
            # допускаются вложенные тэги
                    <[childs]>*
           </ <:tagname> >
        )

В случае, если правило совпадает, то создается объект указанного класса:

    <objrule: WebDAO::Lexer::object> <tag( tagname=>'object' )>
    <objrule: WebDAO::Lexer::any_tag> <tag>

Итоговое дерево доступно после применения грамматики к исходному тексту:

    if ( $txt =~ $q ) {
        #результат в переменной %/ 
        return {%/}->{File}->{childs};
    }

Наличие параметров для правил позволяет сократить количество кода и делает грамматики отдельным языком программирования.

Решение с помощью XML::Flow

Так как целью является синтаксическое дерево и простота решения, то здесь пригодилась библиотека XML::FLow для работы с XML ^[1]:

 sub parse {
    my $self     = shift;
    my $txt      = shift || return [];

    #Соответствие тэгов классам
    my %classmap = (
        object    => 'WebDAO::Lexer::object',
        default   => 'WebDAO::Lexer::any_tag',
    );
    our $result = [];
    
    # обработчики тэгов
    my %tags = (
        # корневой тэг
        wd => sub { shift; $result = \@_ },
        # * обработчик для любого тэга XML
        '*' => sub {
            my $name   = shift;
            my $a      = shift;
            my $childs = \@_;
            my $class  = $classmap{$name} || $classmap{'default'};
            #создаем экземпляр класса
            my $o = $class->new(
                name   => $name,
                attr   => $a,
                childs => $childs
            );
            #и возвращаем его как результат обработчика
            return $o;
        }
    );
    my $rd = new XML::Flow:: \$txt;
    $rd->read( \%tags );
    $result;
 }

Несмотря на то, что основное предназначение библиотеки - это серилизация структур данных в XML, есть и дополнительная возможность - синтаксическая обработка XML в потоковом режиме.

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

Например, для следующего XML:

    <wd>
          <object>
                 <auth />
          </object>
    </wd>

Схема вызовов будет следующей:

   call_wd (
        call_object ( 
               call_auth()
         )
    )

Как видно результаты вызовов вложенный тэгов будут в конечном итоге переданы в обработчик корневого тэга и ему останется только сохранить их в переменной:

        # корневой тэг
        wd => sub { shift; $result = \@_ },

А так как обработчики тэгов возвращают созданные объекты, то в переменную $result сохранится уже готовое дерево.

Итоги обоих решений

Решение с помощью XML::Flow получилось простым главным образом из-за наличия уже готовой библиотеки для работы с XML. Но это не уменьшает значимость грамматик в Perl 5 и вообще средств синтаксического анализа.

Если учесть прекращение развития XHTML и вообще общую тенденцию ухода от XML, то будущее однозначно за грамматиками !

NOTES

^1. Библиотека XML::Flow. http://search.cpan.org/perldoc?XML::Flow