Грамматики для 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].