Наследование комбинаторных парсеров на Julia

Комбинаторные (монадические) парсеры достаточно хорошо известны (wikibooks). Они представляют из себя библиотеку маленьких парсеров, которые распознают простые элементы грамматики, и способы объединять несколько парсеров в один (комбинировать — от сюда и название). Монадические они потому что один из способов комбинирования, порождения парсера остатка текста на основе результата разбора начала, удовлетворяет условиям, накладываемым на математический объект «монада». В языке Haskell это позволяет воспользоваться мощным сервисом, предоставляемым языком и библиотеками. В других языках название «монадические» можно смело игнорировать — это не будет мешать их реализации и использованию, включая упомянутую выше операцию «bind».

Проще всего комбинаторные парсеры реализуются в языках с поддержкой замыканий, но можно воспользоваться и классическим ООП (пример описан Rebecca Parsons в книге Мартина Фаулера «Предметно-ориентированные языки»).
К преимуществам комбинаторных парсеров относится простота использования (запись на языке программирования практически не отличается от обычного описания грамматики), независимость от препроцессора (как yacc/bison, happy или ocamlyacc), возможность реализовать некоторые элементы, плохо укладывающиеся в контекстно-свободную грамматику, прямо на языке программирования общего назначения.

К недостаткам — сложность составления сообщений об ошибке, неспособность работать с леворекурсивной грамматикой (приводит к зацикливанию), а так же то, что очень легко сделать этот парсер не эффективным по быстродействию и памяти. (Одна из причин — компилятор не может произвести оптимизацию в терминах грамматики, так как работает на уровне языка программирования. Но есть и другие тонкости, требующие внимания, если требуется эффективность.)
Как альтернативу можно рассмотреть реализации в виде макросов (например OCaml streams parsers). В Perl6 поддержка грамматик встроена в язык.

Наследование

Персер конкретного языка состоит из множества более специализированных парсеров, ссылающихся друг на друга. В этом отношении парсеры напоминают методы некого объекта. Возникает желание порождать парсеры новых версий языков, подменяя отдельные подпарсеры (как это делается в паттерне проектирования «шаблонный метод» из ООП). Для экспериментов с этим подходом (а так же в порядке изучения очередного языка) я выбрал язык Julia — динамически-типизированном с особым подходом к наследованию (подобному CLOS из Common Lisp и R).
В отличие от обычных комбинаторных парсеров, подход с наследованием является экспериментальным (хотя в некотором виде поддерживается библиотекой макросов OCaml и языком Perl6). Пока он порождает не очень читабельный код. Исходный код доступен на Github.

Реализация

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

Для управления наследованием во все эти функции добавлен параметр — грамматика, к которой относится парсер. Julia допускает множественную диспечеризацию (выбор конкретного метода по типам нескольких аргументов — в отличие от перегрузки метода в C++ и Java диспечеризация происходит динамически), но я использую тип только первого аргумента, как в обычном ООП.

Дерево наследование в Julia можно строить только на абстрактных типах, но листьями могут быть конкретные типы, экземпляры которых можно создавать.

 abstract Grammar

 type Gmin <: Grammar
 end

 geof(g::Grammar, s) = if length(s) == 0
                [((),s)]
              else
                empty
              end

Здесь описан абстрактный тип Grammar, конкретная запись без полей, являющаяся подтипом Grammar, и парсер, распознающий конец строки. Если мы захотим передавать персерам представление текста, отличное от строк, в двух простейших персерах (geof и getTocken, извлекающий один символ из потока) можно воспользоваться множественной диспечеризацией и специализировать второй аргумент s — остальные парсеры будут работать через них, не зная представления потока. 'empty' здесь массив типа [Any].

Julia поддерживает переопределение многих операторов (кроме требующих специальной поддержки в языке, типа '&', который может не вычислять второй аргумент), и я этим воспользовался:

 >(g::Grammar, p1, p2) = (g,s) ->
          reduce((a,r) -> let
              local v
              local s
              v,s = r
              [a, p2(g,s)]
            end, empty, p1(g,s))

Метод (комбинатор) '>' осуществляет конкатенацию двух парсеров (если первый применен успешно, к остатку строки применяется второй), при этом результат первого парсера игнорируется, а результатом комбинации становится результат второго. Аналогично определены методы '<', '-' (конкатенация нескольких парсеров, результаты всех объединяются в массив), '|' (альтернатива — распознает строку, распознаваемую любым из парсеров). Так же есть комбинатор '+' — ограниченная альтернатива, игнорирующая парсеры после первого успешно примененного. Она не позволяет организовать возврат к более раннему прарсеру при ошибке в более позднем. Это важно для эффективности, особенно в ленивых языках, типа Haskell, где возможность такого возврата приводит к накоплению в памяти большого количества недовычисленных значений, но полезно и в энергичных.

Проверим, как это работает:

julia> include("Parsers.jl")
julia> g = Gmin()
Gmin()

julia> (-(g,getTocken, getTocken, getTocken))(g,"12345")
1-element Array{Any,1}:
 (Char['1','2','3'],"45")

julia> (|(g,getTocken, getTocken, getTocken))(g,"12345")
3-element Array{(Char,ASCIIString),1}:
 ('1',"2345")
 ('1',"2345")
 ('1',"2345")

julia> (+(g,getTocken, getTocken, getTocken))(g,"12345")
1-element Array{(Char,ASCIIString),1}:
 ('1',"2345")

Есть небольшое неудобство — необходимость везде добавлять объект грамматики (в данном случае типа Gmin). Я пошел на это ради возможности наследования — классические комбинаторные парсеры записываются проще.

Еще отмечу полезные функции 'lift', позволяющую «поднять» функцию в парсер и 'gfilter', проверяющую значение, возвращенное парсером.

 lift(g::Grammar, f, p) = (g,s) -> map((r) -> (f(r[1]),r[2]), p(g,s))
julia> lift(g,int,getTocken)(g,"12")
1-element Array{(Int64,ASCIIString),1}:
 (49,"2")

julia> (|(g,gfilter(g,(c) -> c=='+', getTocken),gfilter(g,(c) -> c=='*', getTocken)))(g,"*123")
1-element Array{(Char,ASCIIString),1}:
 ('*',"123")

Парсеры могут быть рекурсивными:

cut(g::Grammar,n) = if(n==0); mreturn(g,[]) else (-(g,getTocken,cut(g,n-1))) end
julia> cut(g,4)(g,"12345678")
1-element Array{Any,1}:
 (Any['1','2','3','4'],"5678")

Немного монадичности

mreturn(g::Grammar, v) = (g,s) -> [(v,s)]
mbind(g::Grammar, p, fp) = (g,s) -> reduce((a,v)->[a,fp(g,v[1])(g,v[2])], empty, p(g,s))

В Haskell эти функции называются 'return' (это функция, а не оператор языка) и '>>=' (часто произносится как 'bind').
Что же делают эти странные функции?

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

'mbind' устроен сложнее. Он получает два аргумента — парсер, и функцию, которая применяется к результату работы первого парсера, и возвращает парсер, который будет применен следующим:

julia> mbind(g, lift(g, (c) -> c-'0', getTocken), cut)(g,"23456")
1-element Array{Any,1}:
 (Any['3','4'],"56")

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

Арифметика

abstract Arith <: Grammar
type ArithExpr <: Arith
end

Для парсера арифметики объявляется абстрактный подтип Grammar и его конкретная реализация.
В нем определены функция gnumber(g::Arith, base), которая создает «жадный» парсер числа в заданной системе счисления и парсер 'snumber', который разбирает число в десятичной системе счисления.

«Жадность» выражается в том, что если парсер нашел одну цифру, он не остановится, пока не прочитает все. Это позволяет не пытаться применить следующие парсеры к недоразобранному числу, что заметно сказывается на производительности.

Теперь определим сложение и умножение.

amul(g::Arith,s) = lift(g, (x) -> x[1]*x[2], -(g, snumber, +(g, >(g, gfilter(g, (c) -> c == '*', getTocken), amul), mreturn(g,1))))(g,s)
asum(g::Arith,s) = lift(g, (x) -> x[1]+x[2], -(g, amul, +(g, >(g, gfilter(g, (c) -> c == '+', getTocken), asum), mreturn(g,0))))(g,s)

Здесь стоит обратить внимание, что используются правило (в БНФ)

amul = snumber ('*' amul | '')

а не более простое

amul = snumber '*' amul | snumber

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

Пробуем, как это работает:

julia> a=ArithExpr()
ArithExpr()

julia> asum(a,"12+34*56")
1-element Array{Any,1}:
 (1916,"")

julia> 12+34*56
1916

А теперь наследование!

Некоторые языки позволяют задавать числа в произвольной системе счисления. Например в Erlang систему счисления можно указать перед числом явно с помощью знака '#'. Создадим новую «арифметику», переопределив в ней snumber, что бы записывать числа как в Erlang.

Новый snumber всегда начинается со старого. Что бы обратится к переопределяемому парсеру нам понадобится функция 'cast', которая позволяет взять парсер из конкретной грамматики, минуя наследование.

cast(g::Grammar,p) = (_,s) -> p(g,s)

Сама реализация использует уже знакомые приемы:

 abstract GArith <: Arith

 type GExpr <: GArith
 end

 snumber(g::GArith, s) = mbind(g,
                   cast(ArithExpr(),snumber),
                   (g,v) -> (+(g, (>(g, gfilter(g, (c) -> c == '#', getTocken), gnumber(g,v))),
                                   mreturn(g,v))))(g,s)

Проверяем как это работает:

julia> c = GExpr()
GExpr()

julia> asum(a,"12+34*13#12")
1-element Array{Any,1}:
 (454,"#12")

julia> asum(c,"12+34*13#12")
1-element Array{Any,1}:
 (522,"")

Немного о языке

Julia явно создавалась под влиянием языка R, и пытается исправить некоторые его недостатки. Язык разрабатывался с уклоном в сторону производительности (которая в R иногда подводит) — для этого задействована LLVM. По сравнению с R в Julia более удобный синтаксис замыканий, более развитая система типов (в частности есть туплы/кортежи). Но отказ от фигурных скобок в пользу ключевого слова 'end' мне кажется делает обычный синтаксис более громоздким.
Так же, как в R, индексы начинаются с единицы. На мой взгляд это неудачное решение, отражающее страх нематематиков перед нулем, но многим оно нравится.

Конечно, столь богатых и прекрасно организованных библиотек, как в R, в Julia пока нет.

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

Автор: potan

Источник