Спадкування комбінаторних парсерів на Julia

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

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

До недоліків — складність складання повідомлень про помилку, нездатність працювати з леворекурсивной граматикою (призводить до зациклювання), а так само те, що дуже легко зробити цей парсер не ефективним по швидкодії і пам'яті. (Одна з причин — компілятор не може здійснити оптимізацію в термінах граматики, так як працює на рівні мови програмування. Але є і інші тонкощі, що потребують уваги, якщо потрібно ефективність.)
Як альтернативу можна розглянути реалізації у вигляді макросів (наприклад, OCaml streams parsers). У Perl6 підтримка граматик вбудована в мову.

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

Реалізація
Звичайні комбінаторні парсери представляють із себе функцію, яка отримує рядок (або інший иммутабельный 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(® -> (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, аналіз даних. І що б ці дані отримати, доведеться читати різні текстові формати. Сподіваюся, моя бібліотека коли-небудь виявиться для цього корисною.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.