Комбинаторные (монадические) парсеры достаточно известны ( викибуки ).
Это библиотека небольших парсеров, распознающих простые элементы грамматики, и способы объединения нескольких парсеров в один (объединить — отсюда и название).
Они являются монадическими, поскольку один из методов объединения, генерирующий парсер для остального текста по результату разбора начала, удовлетворяет условиям, наложенным на математический объект «монада».
В Haskell это позволяет вам воспользоваться мощными сервисами, предоставляемыми языком и библиотеками.
В других языках имя «монадический» можно смело игнорировать — это не помешает их реализации и использованию, включая упомянутую выше операцию «связывания».
Самый простой способ реализации комбинаторных парсеров — в языках, поддерживающих замыкания, но можно использовать и классический ООП (пример описан Ребеккой Парсонс в книге Мартина Фаулера «Доменно-специфичные языки»).
К преимуществам комбинаторных парсеров можно отнести простоту использования (написание на языке программирования практически ничем не отличается от обычного описания грамматики), независимость от препроцессора (типа yacc/bison, Happy или окамлякк ), возможность реализовать некоторые элементы, которые плохо вписываются в контекстно-свободную грамматику, непосредственно на языке программирования общего назначения.
Недостатками являются сложность составления сообщений об ошибках, невозможность работы с леворекурсивной грамматикой (приводит к зацикливанию), а также то, что очень легко сделать этот парсер неэффективным с точки зрения скорости и памяти.
(Одна из причин заключается в том, что компилятор не может оптимизировать с точки зрения грамматики, поскольку он работает на уровне языка программирования.
Но есть и другие тонкости, которые требуют внимания, если требуется эффективность.
) Как альтернативу можно рассмотреть реализации в виде макросов (например Парсеры потоков OCaml ).
Perl6 имеет встроенную в язык поддержку грамматики.
Наследование.
Синтаксический анализатор, зависящий от языка, состоит из множества более специализированных анализаторов, ссылающихся друг на друга.
В этом отношении парсеры напоминают методы объекта.
Есть желание генерировать парсеры для новых версий языков, заменяя отдельные субпарсеры (как это сделано в паттерне проектирования «метод шаблона» из ООП).
Чтобы поэкспериментировать с таким подходом (а также с целью выучить следующий язык), я выбрал язык Юлия — динамически типизированный с особым подходом к наследованию (аналогично CLOS из Common Lisp и R).
В отличие от обычных комбинаторных анализаторов, подход наследования является экспериментальным (хотя в некотором роде поддерживается библиотекой макросов OCaml и языком Perl6).
Пока что получается код, который не очень читаем.
Исходный код доступен по адресу Гитхаб .
Выполнение Обычные комбинаторные парсеры — это функция, которая принимает строку (или другой неизменяемый поток) и возвращает контейнер (массив) пар — результат синтаксического анализа, остаток неразобранного текста.
Если распознавание не удалось, возвращается пустой контейнер.
Важно, чтобы входной поток можно было использовать повторно — для использования файловых дескрипторов потребуются специальные обертки.
Для управления наследованием во все эти функции добавлен параметр — грамматика, которой принадлежит парсер.
Julia допускает множественную диспетчеризацию (выбор конкретного метода на основе типов нескольких аргументов — в отличие от перегрузки методов в C++ и Java диспетчеризация происходит динамически), но я использую тип только первого аргумента, как в обычном ООП.
Дерево наследования в Julia может быть построено только на абстрактных типах, но листьями могут быть конкретные типы, экземпляры которых можно создавать.
Он описывает абстрактный тип Grammar, конкретную запись без полей, которая является подтипом Grammar, и анализатор, распознающий конец строки.abstract Grammar type Gmin <: Grammar end geof(g::Grammar, s) = if length(s) == 0 [((),s)] else empty end
Если мы хотим передать парсерам текстовое представление, отличное от строк, в двух простейших парсерах (geof и getTocken, которые извлекают один символ из потока) мы можем использовать множественную отправку и специализировать второй аргумент s — остальную часть парсеры будут работать через них, не зная представления потока.
«пустой» — это массив типа [Любой].
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))
Метод '> ' (комбинатор) объединяет два парсера (при успешном применении первого, второй применяется к остальной части строки), при этом результат первого парсера игнорируется, и результатом объединения становится результат второго.
Методы '<', '-' (concatenation of several parsers, the results of all are combined into an array), '|' are defined similarly. (alternatively, recognize a string recognized by any of the parsers).
There is also the '+' combinator - a limited alternative that ignores parsers after the first one successfully applied. It does not allow you to organize a return to an earlier source if there is an error in a later one. This is important for efficiency, especially in lazy languages like Haskell, where the ability to do this backtracking results in a large number of undercomputed values accumulating in memory, but it is also useful in energetic ones.
Давайте проверим, как это работает: 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 (это функция, а не оператор языка) и > > = (часто произносится как «связывание»).
Что делают эти странные функции? 'mreturn' ничего не делает - он просто завершается успешно, ничего не читая из входной строки и не возвращая предопределенное значение.
Это не только имеет глубокий математический смысл, но и часто заменяет сложную логику, которую в противном случае пришлось бы применять с помощью «лифта».
«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 для записи чисел как в Эрланге.
Новый номер всегда начинается со старого.
Для доступа к переопределенному парсеру нам понадобится функция 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,"")
Немного о языке
Джулия явно вдохновилась языком R и пытается исправить некоторые его недостатки.
Язык разрабатывался с упором на производительность (которая в R иногда подводит) — для этого используется LLVM. По сравнению с R, у Julia более удобный синтаксис замыканий и более развитая система типов (в частности, есть кортежи/кортежи).
Но мне кажется, что исключение фигурных скобок в пользу ключевого слова «end» делает обычный синтаксис более громоздким.
Как и в R, индексы начинаются с единицы.
На мой взгляд, это неудачное решение, отражающее страх нематематиков перед нулем, но многим оно нравится.
Конечно, у Юлии пока нет таких богатых и хорошо организованных библиотек, как у Р.
Важной областью применения Джулии, скорее всего, будет, как и для R, анализ данных.
И чтобы извлечь эти данные, вам придется читать различные текстовые форматы.
Надеюсь, моя библиотека когда-нибудь пригодится для этого.
Теги: #julia #монадические парсеры #комбинаторные парсеры #наследование #мультиметоды #Аномальное программирование #компиляторы #julia
-
Подмена Файлов В Http-Трафике
19 Oct, 24 -
Вы Бы Использовали Wave Для Хабрахабра?
19 Oct, 24 -
Новые Стандарты Devsecops И Gitlab
19 Oct, 24 -
Анонсирована Игра «Герои Меча И Магии Vi»
19 Oct, 24 -
Выпущены Виртуальные Dvd!
19 Oct, 24 -
Быстрый Сайт
19 Oct, 24 -
Ipod-Микшер
19 Oct, 24
