Abnormal programming
Compilers
Julia
October 2014 28

Наследование комбинаторных парсеров на 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, анализ данных. И что бы эти данные извлечь, придется читать различные текстовые форматы. Надеюсь, моя библиотека когда-нибудь окажется для этого полезной.

+13
5.5k 33
Comments 11
Top of the day