В Clojure
На выходных мне пришлось немного заняться анализом данных — по сути, вытащить все медицинские записи, хранящиеся в различных приложениях для ведения заметок, и поместить их в какую-то базу данных, чтобы мы могли просмотреть эти данные в историческом плане. Одна большая проблема с чтением неструктурированных данных заключается в том, что вам часто приходится анализировать данные, которые следуют очень разным правилам от одной части к другой. Строка может выглядеть так:
234,45,(1,2,3),some random text
Другая строка может выглядеть так:
2 233 (23 34 31) some other text
В обеих строках у нас три фиксированные части, но в первой разделитель — ,, а во второй — пробел. Мы также хотим подвести итог тому, что находится внутри круглых скобок в конечных данных, которые мы храним в базе данных.
Как нам автоматически анализировать такого рода неструктурированные данные? Что ж, есть несколько способов сделать это — например, мы могли бы написать regex, который может сопоставлять и удалять отдельные компоненты строк. Но встраивание небольших вариантов использования (например, суммирование трех чисел в скобках) во время анализа текста требует больше работы, если мы используем регулярные выражения.
Или мы могли бы написать крошечный парсер, который сможет анализировать эти строки и выдавать результат так, как мы хотим.
Но подождите — писать парсер с нуля? Разве это не большая задача для такой маленькой задачи? Обычно да — вам придется написать токенизатор, а затем некоторые правила, чтобы использовать токенизатор для анализа строк. Однако мы можем упростить процесс, написав парсер с использованием комбинаторов. Комбинатор — это функция, которая объединяет другие функции для создания новых функций. Если вы знакомы с функциональным программированием, велика вероятность, что вы уже использовали комбинатор функций под названием composition. В Haskell это обозначается оператором .. Композиция f . g означает, что мы берем две функции f и g и создаем новую функцию, которая сначала применяет аргумент к g, а затем применяет результат этой оценки к f.
Мы также можем использовать функциональную композицию для создания парсеров, где базовый набор простых парсеров можно комбинировать для создания действительно сложных парсеров.
Давайте создадим его для нашего варианта использования. Для этого мы будем использовать Clojure и функцию под названием macros, чтобы упростить шаг, но давайте не будем забегать вперед. Для начала мы начнем с простого парсера, который может анализировать одну цифру.
Парсер цифр
Прежде чем мы начнем создавать анализатор цифр, нам нужно создать базовый контракт для наших функций синтаксического анализатора. Функция синтаксического анализа принимает string и возвращает результат анализа. Но ему также необходимо вернуть остальную часть строки, чтобы последующие анализаторы могли работать с этой частью. Таким образом, каждая функция синтаксического анализа возвращает вектор из двух вещей — 1. результат анализа и 2. остальную часть строки, которая еще не анализировалась. В случае неудачи мы можем просто вернуть пустой вектор, указывающий, что синтаксический анализ шага не удался, поэтому нам следует либо остановить, либо продолжить синтаксический анализ с помощью другого синтаксического анализатора.
Хорошо, теперь, когда мы с этим разобрались, давайте посмотрим, как будет выглядеть наш анализатор цифр.
Если мы вызовем анализатор цифр p-digit для такой строки, как "3bottles”, то он должен вернуть [3, "bottles"]. А для входа "apples" это будет пустой вектор, указывающий на ошибку []. Обратите внимание, что сбой также произойдет, если нет строки для чтения.
Что, если мы хотим проанализировать определенную цифру, скажем, 9? Мы можем указать это как необязательный аргумент для p-digit, чтобы оно могло соответствовать определенной цифре. Вот как это выглядит:
(defn p-digit
([]
(fn [s]
(if (= (.length s) 0)
[]
(let [c (int (.charAt s 0))]
(if (and (>= c (int \0))
(<= c (int \9)))
[(- c (int \0))
(.substring s 1)]
[])))))
([n]
(fn [s]
(let [[d rs] ((p-digit) s)]
(if (and d (= d n))
[d rs]
[])))))
В Clojure мы можем определять функции мультиэфирности. В первой части мы определяем функцию без аргументов — она будет соответствовать любому char, находящемуся между 0 и 9, и преобразует его в целое число. Во второй части мы просто проверяем, соответствует ли цифра заданному аргументу. Обратите внимание, что p-digit — это функция более высокого порядка, поскольку она возвращает функцию — то, что на самом деле выполняет синтаксический анализ — то есть, взяв строку, она возвращает проанализированный результат.
Парсер символов
Теперь мы готовы создать парсер char. Он имеет структуру, аналогичную структуре синтаксического анализатора цифр. Однако char также включает в себя цифровые символы, поэтому, когда мы используем комбинацию этих анализаторов, нам нужно быть осторожными при их использовании. Вот определение парсера char:
(defn p-char
([]
(fn [s]
(if (= (.length s) 0)
[]
[(.charAt s 0)
(.substring s 1)])))
([c]
(fn [s]
(let [[c0 rs] ((p-char) s)]
(if (and c0 (= c0 c))
[c0 rs]
[])))))
Комбинаторы
Хотите верьте, хотите нет, но у нас уже есть основные строительные блоки, необходимые для нашего простого варианта использования. Все, что нам сейчас нужно, это построить комбинаторы.
Мы создадим два базовых комбинатора — один для сопоставления с парсером p1 или p2. Мы назовем его p-or .
(defn p-or [p1 p2]
(fn [s]
(let [o (p1 s)]
(if (fail? o)
(p2 s)
o))))
Другой немного интереснее: он будет соответствовать до тех пор, пока это возможно, а затем, когда произойдет сбой, он просто вернет все, что нашел на данный момент. Мы называем это p-some.
(defn p-some [p]
(fn [s & {:keys [acm] :or {acm []}}]
(let [r (parse p s)]
(if (fail? r)
[acm s]
(recur (r 1) {:acm (conj acm (r 0))})))))
Давайте проверим то, что мы уже создали.
(def p1 (p-digit 9)) (def p2 (p-char \c)) (def p3 (p-or p1 p2)) (parse p1 "9 islands") ;; ==> [9 " islands"] (parse p2 "clojure") ;; ==> [\c "lojure"] (parse p3 "9B") ;; ==> [9 "B"] (parse p3 "cB") ;; ==> [\c "B"]
Функция parse — это вспомогательная утилита, которая просто вызывает анализатор аргумента:
(defn parse [p s] (p s))
Давайте также проверим p-some.
(def p-digits (p-some (p-digit))) (parse p-digits "123algol") ;; ==> [[1 2 3] "algol"] (parse p-digits "clojure") ;; ==> [[] "clojure"]
Обратите внимание, что p-some не терпит неудачу, если не получает совпадающих входных данных, потому что, как следует из названия, ему необходимо найти некоторые значения, а это означает, что он не должен давать сбой, если он также не дает никаких ошибок. Это похоже на символ регулярного выражения *. Мы также можем написать версию, которая будет действовать как +.
Первый комплексный парсер
Давайте посмотрим, как мы будем разбирать с помощью этих комбинаторов такую строку:
123 321 whatever
Целью будет проанализировать эту строку и найти первые два числа, просуммировать их и вернуть результат. Если два числа, разделенные пробелом, не найдены, то синтаксический анализ завершается неудачей.
С помощью вышеуказанных примитивов мы можем сделать это:
(defn p-num [ns]
(if (empty? ns)
0
(Integer/parseInt (apply str ns))))
(def p-line (fn [rs]
(let [[number1 rs] ((p-some (p-digit)) rs)]
(if (fail? number1)
number1
(let [[_x rs] ((p-some (p-char \space)) rs)]
(if (fail? _x)
_x
(let [[number2 rs] ((p-some (p-digit)) rs)]
(if (fail? number2)
number2
[(+ (p-num number1)
(p-num number2))
rs]))))))))
(parse p-line "1234 4321 abcd") ;; ==> [5555 " abcd"]
(parse p-line "1234 abcd") ;; ==> []
Кажется, мы делаем то, что хотим. Однако код парсера некрасив. Это связано с тем, что на каждом шаге ему приходится проверять, не является ли результат ошибкой синтаксического анализатора (служебная функция fail? проверяет, является ли результат пустым вектором), затем взять оставшуюся строку, применить ее к следующему анализатору и продолжить работу дальше по потоку. Разве не было бы хорошо, если бы мы могли использовать ту же самую цепочку парсеров, но получать все эти дополнительные шаблоны бесплатно?
Макрос, который спасет положение
Чего мы действительно хотим, так это создать последовательный синтаксис для синтаксического анализатора и преобразовать этот синтаксис в цепочку вызовов функций синтаксического анализатора, как показано выше. Приведенный ниже код отражает то, что мы делаем выше, но последовательно.
(def p-line2 (p-seq
(:= number1 (p-some (p-digit)))
(p-some (p-char \space))
(:= number2 (p-some (p-digit)))
(return (+ (p-num number1)
(p-num number2)))))
(parse p-line2 "1234 4321 abcd") ;; ==> [5555 " abcd"]
(parse p-line2 "1234 abcd") ;; ==> []
Это намного лучше, чем раньше! Но такого синтаксиса пока не существует, поэтому нам придется каким-то образом преобразовать его в приведенный выше, чтобы мы могли написать элегантную версию парсера и не беспокоиться о шаблонном коде. Оказывается, мы можем использовать мощную функцию Clojure (и большинства Lisp) под названием macros.
Макросы — это функции, которые запускаются, когда Clojure читает код.
Пусть это впитается! Пока Clojure читает приведенный выше код, он преобразует этот синтаксис в серию вызовов функций, которые и являются правильным кодом Clojure! Фактически, многие встроенные модули Clojure, такие как defn, на самом деле являются макросами. Макросы очень мощные в том смысле, что они позволяют вам создавать произвольный синтаксис в языке, но, как сказал бы вам дядя Бен, они налагают на вас большую ответственность. Очень легко написать плохой макрос и выстрелить одному в ногу!
Итак, давайте задумаемся, я имею в виду, напишем себе макрос, который будет выполнять описанное выше синтаксическое преобразование.
Сначала мы рассмотрим простой случай return. Когда мы сталкиваемся с этим, он должен просто принять аргумент и вернуть его как вектор.
(defmacro return-expr [rs xs]
(let [x (first xs)]
`[~(second x)
~rs]))
Обратите внимание: нам нужно передать string, который он должен вернуть в качестве второго элемента вектора. Это строка, оставшаяся после успешного анализа.
Далее мы пишем макрос для анализа назначений :=.
(defmacro assign-expr [rs xs]
`(let [[~(second (first xs)) _rs#] (~(nth (first xs) 2) ~rs)]
(if (fail? ~(second (first xs)))
~(second (first xs))
(seq-exprs _rs# ~(rest xs)))))
Это создаст выражение let с variable в назначении в качестве привязки let. Что здесь seq-exprs? Мы скоро узнаем.
Для случаев отсутствия присваивания, когда мы игнорируем результат синтаксического анализа:
(defmacro non-assign-expr [rs xs]
`(let [[_x# _rs#] (~(first xs) ~rs)]
(if (fail? _x#)
_x#
(seq-exprs _rs# ~(rest xs)))))
Теперь свяжем их все вместе:
(defmacro seq-exprs [rs xs]
(cond
(empty? xs) `[nil ~rs]
(and (seqable? (first xs))
(= (first (first xs)) 'return)) `(return-expr ~rs ~xs)
(and (seqable? (first xs))
(= (first (first xs)) ':=)) `(assign-expr ~rs ~xs)
:else `(non-assign-expr ~rs ~xs)))
То, что мы создали выше, — это recursive macro — макрос, который вызывает сам себя или какой-либо другой макрос, который вызывает этот макрос обратно для всех вложенных синтаксисов, которые ему необходимо преобразовать.
Наконец, нам нужно вызвать этот рекурсивный макрос из макроса драйвера верхнего уровня p-seq.
(defmacro p-seq [& xs]
`(fn [s#]
(seq-exprs s# ~xs)))
Этот создает анонимную функцию и вызывает seq-exprs для анализа остального синтаксиса.
Большая часть вышеперечисленного требует некоторого базового понимания того, как пишутся макросы в Clojure. Вот отличный текст, чтобы узнать об этом подробнее:
Второй сложный парсер, использующий макрос
Теперь у нас есть все недостающие детали. Итак, давайте напишем анализ строк, с которых мы начали. Вот несколько тестовых случаев:
234,45,(1,2,3),some random text 2 233 (23 34 31) some other text 2,233,(23 34 31) some other text 234,45,(1 2 3),some random text
Ожидаемый результат синтаксического анализатора будет
{:from 234 :to 45 :total 6 :details "some random text"}
{:from 2 :to 233 :total 88 :details "some other text"}
{:from 2 :to 233 :total 88 :details "some other text"}
{:from 234 :to 45 :total 6 :details "some random text"}
Вот как выглядят парсеры:
(def delim
(p-or
(p-char \,)
(p-some
(p-char \space))))
(def digits (p-some (p-digit)))
(def line (p-seq
(:= num1 digits)
delim
(:= num2 digits)
delim
(p-char \()
(:= n1 digits)
delim
(:= n2 digits)
delim
(:= n3 digits)
(p-char \))
delim
(:= details (p-some (p-char)))
(return {:from (p-num num1)
:to (p-num num2)
:total (+ (p-num n1)
(p-num n2)
(p-num n3))
:details (p-str details)})))
;;;
(parse line "234,45,(1,2,3),some random text") ;; ==> [{:from 234, :to 45, :total 6, :details "some random text"} ""]
(parse line "2 233 (23 34 31) some other text") ;; ==> [{:from 2, :to 233, :total 88, :details "some other text"} ""]
(parse line "2,233,(23 34 31) some other text") ;; ==> [{:from 2, :to 233, :total 88, :details "some other text"} ""]
(parse line "234,45,(1 2 3),some random text") ;; ==> [{:from 234, :to 45, :total 6, :details "some random text"} ""]
И вот оно! Наш неструктурированный текст с плохими разделителями теперь анализируется правильно. Теперь мы можем использовать парсер line и комбинировать с ним другие парсеры для анализа всего текста.
Для опытного глаза эта новая структура написания последовательных анализаторов, которые преобразуются в цепочки анализаторов, будет выглядеть как монада! На самом деле это наша собственная версия блока do в Haskell. Если бы мы писали эти комбинаторы парсера на Haskell, мы бы использовали монадическую версию комбинаторов, чтобы мы могли объединять их последовательно следующим образом:
let line = do num1 <- p-some p-digits delim num2 <- p-some p-digits return [num1,num2]
Монадические комбинаторы парсеров предоставляют мощный способ анализа текста или любых других входных данных путем декларативного объединения более мелких строительных блоков. А поскольку они легко расширяются, их можно использовать и для множества различных типов входных данных.
Почти каждый функциональный язык имеет библиотеку комбинаторов парсеров. Вот один из самых популярных на Haskell https://hackage.haskell.org/package/parsec.
Кроме того, взгляните на это, одно из лучших доступных видео, в котором описывается, как с нуля создать мощную библиотеку комбинаторов монадических парсеров.
Наконец, весь приведенный выше код можно найти по адресу https://github.com/ppsdatta/parseus.
Это развивающаяся библиотека, поэтому, если хотите, поставьте ей звездочку.
