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

    Похожие публикации

    Комментарии 11

      0
      Еще не успели руки дойти до подробного изучения Julia, отмечу тот факт что Julia сейчас сильно поддерживается MIT и LL MIT. Думаю многие будут рады продолжению статей по Julia в дальнейшем. Спасибо за статью.
        +1
        Julia явно создавалась под влиянием языка R

        И не только его. Линейная алгебра скорее слизана с Matlab, макросы, разумеется, с Lisp, по скорости они ориентируются на С, а по удобству — на Python.

        Так же, как в R, индексы начинаются с единицы. На мой взгляд это неудачное решение, отражающее страх нематематиков перед нулем, но многим оно нравится.

        Да нет, причём здесь страх, это чистой воды дело вкуса. Лично мне, например, удобней считать, что на руках у меня 5 пальцев — от первого до пятого, а не от нулевого до четвёртого — но я знаю людей, которые бы сказали иначе.
          0
          Линейная алгебра и в R хороша. Да и по удобству он мне больше нравится, чем Python :-).
          Макросы, конечно, корнями уходят в Lisp. Но по моему, не обошлось без влияния camlp4.
            0
            Линейная алгебра везде хороша, где есть LAPACK. Вроде как R не исключение. А Julia изначально создавалась больше с оглядкой на Matlab как язык для технических вычислений. Но сейчас Julia несравненно более мощная вещь концептуально и технологически. Вот бы ещё стабильности, да стандартную библиотеку допилить бы и можно пробовать c ним в production залезть. :)
              0
              Один LAPACK счастья не принесет. Легкость работы с векторами в R сама по себе позволяет решать многие задачи линейной алгебры или близкие к ним.
              А LAPACK не поможет, если мы работаем не с действительными или комплексными числами. Иногда хочется решить систему линейных уравнений в булевых значениях (в Z/2Z) или дуальных числах (1 2). Готовых методов я не нашел.
              +1
              Линейная алгебра и в R хороша.

              Да ладно, разве можно сравнить это:

              A = matrix(c(1, 2, 3, 4, 5, 6), nrow=2, ncol=3, byrow=TRUE)
              B = matrix(rnorm(6), ncol=3)
              C = A %*% t(B)
              

              и это?
              A = [1 2 3; 4 5 6]
              B = randn(2, 3)
              C = A * B'
              

              :)

              Макросы, конечно, корнями уходят в Lisp. Но по моему, не обошлось без влияния camlp4.

              Насколько я понял, Camlp4 — это библиотека парсеров, а не отдельный язык, разве нет?
                0
                Это препроцессор, реализующий макросы. То есть он реализует проход разворачивания макросов перед компиляцией в Lisp. По моему, то что он не встроен в язык, не слишком принципиально.
                  +1
                  Дело не только в препроцессоре — синтаксический сахар всего лишь отражает наиболее часто используемые операции, т.е. является следствием, а не причиной — дело в общем подходе, решаемых задачах и соответсвующей семантике. Смотрите, что будет если в R сложить два вектора разной длины?

                  > c(1, 2) + c(10, 20, 30, 40)
                  [1] 11 22 31 42
                  

                  R реплицировал вектор меньшего размера до размера большего и сложил их. Это удобно, например, для умножения вектора на скаляр (который, как известно, просто вектор единичного размера), но не имеет смысла в линейной алгебре. Поэтому и Matlab/Octave, и Julia это строго запрещают:

                  julia> [1, 2] + [10, 20, 30, 40]
                  ERROR: dimensions must match
                   in + at array.jl:719
                  


                  Разница между статистикой и линейной алгеброй проявляется и в основных структурах данных. В R вы работаете, в первую очередь, с фреймами данных, т.е. с таблицами гетерогенных наблюдений. Колонки обычно соответсвуют именам переменных и индексируются строками, а стандартные арифметические операции (например, +, *) над колонками (т.е. векторами) являются поэлементными. В Matlab и Julia основная структура данных — матрица, т.е. двумерный массив однородных данных. Вектор соответсвует одноколоночной матрице, арифметические операции — тоже матричные (для поэлементных операций есть .+ и .*). Есть DataArrays и DataFrames, но это пока только отдельные пакеты, и вряд ли они будут когда-либо интегрированы в язык так же плотно, как линейная алгебра в Matlab или Julia.
                    +1
                    По препроцессор — это я про camlp4.
                    Про линеную алгебру соглашусь — в Julia она лучше продумана.
            0
            Имеется вопрос к тем, кто пробовал использовать Julia на практике.
            Я занимаюсь анализом данных на R, но давненько присматриваюсь к Julia. Очень нравится синтаксис и система типов, хочется чего-нибудь полезное попробовать написать, но несколько пугает молодость языка и малое количество библиотек. Пробовал кто-нибудь писать что-нибудь более или менее большое, а не академические примеры? Мне хочется понять насколько язык готов к реальному бою.
              0
              По моему впечатлению (на базе очень ограниченного опыта) язык уже достаточно стабилен, но библиотек крайне мало.

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

            Самое читаемое