Наследование комбинаторных парсеров на 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)) Метод (комбинатор) '>' осуществляет конкатенацию двух парсеров (если первый применен успешно, к остатку строки применяется второй), при этом результат первого парсера игнорируется, а результатом комбинации становится результат второго. Аналогично определены методы 'Проверим, как это работает:
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 (® → (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=='+', getTocken), gfilter (g,© → 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-'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 == '*', 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 == '+', 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 == '#', 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, анализ данных. И что бы эти данные извлечь, придется читать различные текстовые форматы. Надеюсь, моя библиотека когда-нибудь окажется для этого полезной.
