Комбинаторные (монадические) парсеры достаточно хорошо известны (wikibooks). Они представляют из себя библиотеку маленьких парсеров, которые распознают простые элементы грамматики, и способы объединять несколько парсеров в один (комбинировать — от сюда и название). Монадические они потому что один из способов комбинирования, порождения парсера остатка текста на основе результата разбора начала, удовлетворяет условиям, накладываемым на математический объект «монада». В языке Haskell это позволяет воспользоваться мощным сервисом, предоставляемым языком и библиотеками. В других языках название «монадические» можно смело игнорировать — это не будет мешать их реализации и использованию, включая упомянутую выше операцию «bind».
Проще всего комбинаторные парсеры реализуются в языках с поддержкой замыканий, но можно воспользоваться и классическим ООП (пример описан Rebecca Parsons в книге Мартина Фаулера «Предметно-ориентированные языки»).
К преимуществам комбинаторных парсеров относится простота использования (запись на языке программирования практически не отличается от обычного описания грамматики), независимость от препроцессора (как yacc/bison, happy или ocamlyacc), возможность реализовать некоторые элементы, плохо укладывающиеся в контекстно-свободную грамматику, прямо на языке программирования общего назначения.
К недостаткам — сложность составления сообщений об ошибке, неспособность работать с леворекурсивной грамматикой (приводит к зацикливанию), а так же то, что очень легко сделать этот парсер не эффективным по быстродействию и памяти. (Одна из причин — компилятор не может произвести оптимизацию в терминах грамматики, так как работает на уровне языка программирования. Но есть и другие тонкости, требующие внимания, если требуется эффективность.)
Как альтернативу можно рассмотреть реализации в виде макросов (например OCaml streams parsers). В Perl6 поддержка грамматик встроена в язык.
В отличие от обычных комбинаторных парсеров, подход с наследованием является экспериментальным (хотя в некотором виде поддерживается библиотекой макросов OCaml и языком Perl6). Пока он порождает не очень читабельный код. Исходный код доступен на Github.
Обычные комбинаторные парсеры представляют из себя функцию, получающую строку (или другой иммутабельный stream) и возвращают контейнер (массив) пар — результат разбора, остаток неразобранного текста. При неуспешном распознавании возвращается пустой контейнер. Важно что входной stream может повторно использоваться — использование дескрипторов файлов потребует специальных оберток.
Для управления наследованием во все эти функции добавлен параметр — грамматика, к которой относится парсер. Julia допускает множественную диспечеризацию (выбор конкретного метода по типам нескольких аргументов — в отличие от перегрузки метода в C++ и Java диспечеризация происходит динамически), но я использую тип только первого аргумента, как в обычном ООП.
Дерево наследование в Julia можно строить только на абстрактных типах, но листьями могут быть конкретные типы, экземпляры которых можно создавать.
Здесь описан абстрактный тип Grammar, конкретная запись без полей, являющаяся подтипом Grammar, и парсер, распознающий конец строки. Если мы захотим передавать персерам представление текста, отличное от строк, в двух простейших персерах (geof и getTocken, извлекающий один символ из потока) можно воспользоваться множественной диспечеризацией и специализировать второй аргумент s — остальные парсеры будут работать через них, не зная представления потока. 'empty' здесь массив типа [Any].
Julia поддерживает переопределение многих операторов (кроме требующих специальной поддержки в языке, типа '&', который может не вычислять второй аргумент), и я этим воспользовался:
Метод (комбинатор) '>' осуществляет конкатенацию двух парсеров (если первый применен успешно, к остатку строки применяется второй), при этом результат первого парсера игнорируется, а результатом комбинации становится результат второго. Аналогично определены методы '<', '-' (конкатенация нескольких парсеров, результаты всех объединяются в массив), '|' (альтернатива — распознает строку, распознаваемую любым из парсеров). Так же есть комбинатор '+' — ограниченная альтернатива, игнорирующая парсеры после первого успешно примененного. Она не позволяет организовать возврат к более раннему прарсеру при ошибке в более позднем. Это важно для эффективности, особенно в ленивых языках, типа Haskell, где возможность такого возврата приводит к накоплению в памяти большого количества недовычисленных значений, но полезно и в энергичных.
Проверим, как это работает:
Есть небольшое неудобство — необходимость везде добавлять объект грамматики (в данном случае типа Gmin). Я пошел на это ради возможности наследования — классические комбинаторные парсеры записываются проще.
Еще отмечу полезные функции 'lift', позволяющую «поднять» функцию в парсер и 'gfilter', проверяющую значение, возвращенное парсером.
Парсеры могут быть рекурсивными:
В Haskell эти функции называются 'return' (это функция, а не оператор языка) и '>>=' (часто произносится как 'bind').
Что же делают эти странные функции?
'mreturn' ничего — просто завершается успешно, ни чего не прочитав из входящей строки и вернув заранее заданное значение. В этом есть не только глубокий математический смысл, он часто заменяет сложную логику, которую иначе бы приходилось применять с помощью 'lift'.
'mbind' устроен сложнее. Он получает два аргумента — парсер, и функцию, которая применяется к результату работы первого парсера, и возвращает парсер, который будет применен следующим:
Кстати, этот прием удобно применять при разборе бинарных форматов, где часто встречается что длинна записи хранится перед самой записью.
Для парсера арифметики объявляется абстрактный подтип Grammar и его конкретная реализация.
В нем определены функция gnumber(g::Arith, base), которая создает «жадный» парсер числа в заданной системе счисления и парсер 'snumber', который разбирает число в десятичной системе счисления.
«Жадность» выражается в том, что если парсер нашел одну цифру, он не остановится, пока не прочитает все. Это позволяет не пытаться применить следующие парсеры к недоразобранному числу, что заметно сказывается на производительности.
Теперь определим сложение и умножение.
Здесь стоит обратить внимание, что используются правило (в БНФ)
а не более простое
Дело в том, что комбинаторные парсеры не имеют возможности оптимизировать грамматику, подобно генераторам парсеров, и использование второго правила приведет к тому, что число будет парситься несколько раз.
Пробуем, как это работает:
Некоторые языки позволяют задавать числа в произвольной системе счисления. Например в Erlang систему счисления можно указать перед числом явно с помощью знака '#'. Создадим новую «арифметику», переопределив в ней snumber, что бы записывать числа как в Erlang.
Новый snumber всегда начинается со старого. Что бы обратится к переопределяемому парсеру нам понадобится функция 'cast', которая позволяет взять парсер из конкретной грамматики, минуя наследование.
Сама реализация использует уже знакомые приемы:
Проверяем как это работает:
Julia явно создавалась под влиянием языка R, и пытается исправить некоторые его недостатки. Язык разрабатывался с уклоном в сторону производительности (которая в R иногда подводит) — для этого задействована LLVM. По сравнению с R в Julia более удобный синтаксис замыканий, более развитая система типов (в частности есть туплы/кортежи). Но отказ от фигурных скобок в пользу ключевого слова 'end' мне кажется делает обычный синтаксис более громоздким.
Так же, как в R, индексы начинаются с единицы. На мой взгляд это неудачное решение, отражающее страх нематематиков перед нулем, но многим оно нравится.
Конечно, столь богатых и прекрасно организованных библиотек, как в R, в Julia пока нет.
Важной областью применения Julia, скорее всего будет, как и для R, анализ данных. И что бы эти данные извлечь, придется читать различные текстовые форматы. Надеюсь, моя библиотека когда-нибудь окажется для этого полезной.
Проще всего комбинаторные парсеры реализуются в языках с поддержкой замыканий, но можно воспользоваться и классическим ООП (пример описан 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, анализ данных. И что бы эти данные извлечь, придется читать различные текстовые форматы. Надеюсь, моя библиотека когда-нибудь окажется для этого полезной.
