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

В продолжение темы инструментов синтаксического анализа [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].

[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