Грамматики в Java, Perl 6 и Perl 5

Грамматики представляют собой в общем случае набор "правил", с помощью которых можно определить языковые конструкции, поддерживающие так же произвольную вложенность. Сфера применения грамматик - сложный синтаксический анализ текста или данных [1].

Без грамматик не обойтись, в случаях создания компиляторов языков, интерпретаторов и т.д. В последнее время я плотно использую грамматики в Java, Perl 6 и Perl 5. Вкратце выскажусь о них в каждом из языков.

Грамматики в Java

JavaCC (Java Compiler Compiler), пожалуй, наиболее распространенный генератор парсеров для Java. Включает в себя утилиту JJTree для построения синтаксических деревьев.

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

TOKEN:
 {
  < NUMBER: (<DIGIT>)+ ( "." (<DIGIT>)+ )? >
  | < DIGIT: ["0"-"9"] >
  }

Примеры грамматик можно найти в репозитории JavaCC грамматик [2].

Грамматики в Perl 6

В Perl 6 грамматики являются частью языка и это одна из самых замечательных фитч языка. Поэтому ничего удивительного нет в том, что синтаксис Perl 6 описан с помощью его же грамматик [3].

Грамматики в Perl 6 фактически представлены в виде классов и могут наследовать другие грамматики. Процесс обработки текста может быть совмещен с построением синтаксического дерева. Для этого парсеру передается параметр action, значением которого является объект обрабатывающий совпадения токенов (в Perl 6 ими являются лексемы token и rule).

Например:

my $res = Plosurin::Grammar.parse($txt, :actions(Plosurin::Actions.new ));

При обработке $txt, в случае совпадения токена, для построения абстрактного синтаксического дерева (AST) будут вызваны методы объекта Plosurin::Actions. Результаты вызовов станут частью результирующего дерева.

Такая интеграция в язык программирования позволяет упростить использование грамматик. Насколько ? Можно к примеру сравнить определение грамматики для обработки JSON для JavaCC [4] и Perl 6 [5] (для наглядности в одном gist [6]).

Грамматики в Perl 5

Для Perl 5 грамматики реализованы в виде библиотеки Regexp-Grammars [7].

Следующий пример из документации, демонстрирует правила для парсинга LaTeX:

use Regexp::Grammars;
    $parser = qr{
        <File>
        <rule: File>       <[Element]>*
        <rule: Element>    <Command> | <Literal>
        <rule: Command>    \\  <Literal>  <Options>?  <Args>?
        <rule: Options>    \[  <[Option]>+ % (,)  \]
        <rule: Args>       \{  <[Element]>*  \}
        <rule: Option>     [^][\$&%#_{}~^\s,]+
        <rule: Literal>    [^][\$&%#_{}~^\s]+
    }xms;

Тем, кто немного знаком с грамматиками Perl 6, приведенный выше пример покажется знакомым.

Внешне и по возможностям Regexp-Grammars очень близка к грамматикам Perl 6: есть наследование, построение синтаксического дерева. А в плане отладки правил функционал даже превосходит Perl 6.

Regexp::Grammars одна из тех библиотек, которые знать очень полезно!

[1] Синтаксический анализ и инструментарий. http://ru.wikipedia.org/wiki/Синтаксический анализ

[2] Репозиторий JavaCC грамматик. http://java.net/projects/javacc/downloads/directory/contrib/grammars

[3] Грамматика Perl 6. https://raw.github.com/perl6/std/master/STD.pm6

[4] Определение грамматики JSON для JavaCC.http://java.net/downloads/javacc/contrib/grammars/JSONParser.jj

[5] Грамматика JSON в Perl 6. https://raw.github.com/moritz/json/master/lib/JSON/Tiny/Grammar.p

[6] Грамматики обработки JSON для JavaCC и Perl 6. https://gist.github.com/1363580

[7] Библиотека грамматического анализа для Perl 5 Regexp-Grammars. http://search.cpan.org/dist/Regexp-Grammars/

All Articles