Оптимизирующие парсер-комбинаторы

Дмитрий Попов

Аннотация: Статья рассказывает о технике парсер-комбинаторов для построения функций синтаксического анализа текста или других линейных данных. Описываются классические монадные парсер-комбинаторы, работающие со списками, метод их оптимизации с помощью мемоизации, а также оригинальная техника построения оптимизирующих парсеров, основанная на построении и оптимизации конечного автомата аналогичным набором операторов и комбинаторов.


The article describes parser combinators, a technique for creating functions for syntax analysis sequential data, such as text. The classic monadic parser combinators are described, then a way of optimizing them via memoization, and an original approach to creating optimizing parsers by building a finite state machine using a similar set of operators and combinators.



Обсуждение статьи ведётся в LiveJournal.

1  Введение

Парсером называется часть программы, которая из линейной последовательности простых данных (символов, лексем, байтов) с учетом некоторой грамматики строит более сложные структуры данных, неявно содержащиеся в исходной последовательности. Это может быть разбор конфигурационных файлов, разбор исходного кода на каком-либо языке программирования, разбор проблемно-ориентированных языков (DSL), чтение сложных и не очень форматов данных (XML, PostScript), разбор запросов и ответов сетевых протоколов, вроде HTTP, и т. п. Здесь и далее слова «парсинг» и «разбор» считаются синонимами.

Комбинаторы — это функции высшего порядка, которые из одних функций строят другие. Возможность принимать функции в качестве аргумента и возвращать их в качестве результата — отличительная черта функциональных языков программирования, в которых комбинаторы являются обычными функциями.

Парсер-комбинаторы1 — это широко известная в узких кругах техника создания парсеров, использующая возможности функциональных языков программирования. На менее выразительных языках задача парсинга обычно решается кодогенерацией: по описанию грамматики, сформулированному на некотором внешнем DSL, специальная утилита генерирует исходный текст парсера на нужном языке программирования. Самые известные примеры таких генераторов — yacc (и его прямой аналог bison), ANTLR, Coco/R, JavaCC. Функциональные же языки позволяют построить парсер динамически, используя простейшие функции и комбинаторы для синтеза по правилам грамматики сложных парсеров из простых. При этом и сама грамматика, и семантические действия (выполняющиеся при успешном разборе того или иного элемента грамматики) формулируется на одном языке, а парсер-комбинаторы выступают в качестве DSEL (встроенного предметно-ориентированного языка)2. Думаю, для каждого адепта функционального программирования написание своей библиотеки парсер-комбинаторов — такая же обязательная программа, как для новичка в Haskell написание туториала по монадам.

2  Классические парсер-комбинаторы

Классический вариант парсер-комбинаторов на языке OCaml может выглядеть следующим образом.

Парсером будет функция, которая получает на вход список неразобранных символов и в случае успеха возвращает разобранное значение и неразобранный остаток списка, а в случае неудачи возвращает признак неудачи.

Тип результата будет выглядеть так:

type 'a parse_result = Parsed of 'a * char list | Failed

Здесь ’a — параметр типа, делающий тип parse_result полиморфным, благодаря чему парсеры могут возвращать значения разных типов.

Парсеры, созданные генераторами вроде yacc, обычно работают с последовательностью лексем, полученных от лексического анализатора, также сгенерированного внешней утилитой, например, lex. В парсер-комбинаторах мы можем сами выбирать на каком уровне работать — на уровне лексем или на уровне отдельных символов. Можно определить более общий случай, когда на входе может быть не список символов, а список чего угодно, например, список лексем, полученных от лексического анализатора, созданного с помощью ocamllex (аналога генератора лексеров lex). Для общего случая определение типа будет таким:

type ('a, 'b) parse_result = Parsed of 'a * 'b list | Failed

В случае успеха возвращенный неразобранный остаток списка может быть использован для дальнейшего разбора — так происходит движение вперед по исходному списку символов. При неудаче никаких списков не возвращается, поэтому «текущая позиция» остается без изменений. Такая схема естественным образом реализует разбор с откатами3: если какой-то парсер по мере работы довольно далеко продвинулся по входному списку, но в какой-то момент все же потерпел неудачу, то все его продвижение «не считается» и «текущая позиция» оказывается той же, что и до его вызова.

Сначала опишем примитивный парсер, который умеет разбирать один символ, удовлетворяющий заданному условию.

let p_pred p s = match s with | [] -> Failed | h::t -> if p h then Parsed(h, t) else Failed

Функция p_pred берет предикат p и список символов s. Если список пуст, то разбор заканчивается неудачей. Если не пуст, то если символ удовлетворяет предикату, возвращаем символ и остаток списка, иначе опять возвращаем неудачу. С помощью p_pred можно получить парсер, умеющий разбирать заданную букву или, например, произвольную цифру.

let p_char c = p_pred ((=) c) let isdigit c = c>='0' && c<='9' let p_digit = p_pred isdigit

Здесь мы используем карринг, чтобы сократить и упростить запись. Тип функции p_pred таков:

(char -> bool) -> char list -> char parse_result

Передав в p_pred только первый параметр, мы получаем функцию с типом:

char list -> char parse_result

т. е. как раз функцию-парсер, применение которой к списку символов дает результат парсинга.

Теперь на сцене появляются комбинаторы, которые из примитивных парсеров составляют более сложные. Опишем оператор последовательности (аналог ab в регулярных выражениях):

let (>>>) a b s = match a s with | Parsed(_, s2) -> b s2 | Failed -> Failed

В языке OCaml запись имени в скобках означает определение оператора. Ряд комбинаторов удобно использовать именно в виде операторов. Парсер a >>> b отрабатывает успешно, если сначала успешно отработает a, а потом b. Если один из них не разобрал свою часть строки, то и вся комбинация возвращает неудачу.

Теперь определим оператор альтернативы (a|b в регулярных выражениях):

let (|||) a b s = match a s with | Parsed _ as ok -> ok | Failed -> b s

Парсер a ||| b отрабатывает успешно, если успешно отработал a или b. Операторы составлены из трех символов, чтобы не пересекаться с входящими в язык операторами |, ||, > и невходящим >>, который я обычно использую для композиции функций.

Опциональный парсер (аналог a? в регулярных выражениях):

let p_opt defval a s = match a s with | Parsed _ as ok -> ok | Failed -> Parsed(defval, s)

Если его аргумент отработал успешно, возвращается его результат, в противном случае все равно возвращается успех, но с заданным значением по умолчанию и исходным списком символов.

Комбинатор повторения (аналог a*):

let p_many a = let rec loop s = match a s with | Parsed(_, s') -> loop s' | Failed -> Parsed((), s) in loop

Применяет парсер-аргумент столько раз, сколько сможет (0 или более). Если парсер-аргумент не сработал ни разу, это тоже считается успехом, а результатом разбора в любом случае будет () — значение типа unit, аналога void в Си. Таким образом, результат разбора каждой итерации выкидывается. Если результат нужен, то вот вариант с функцией накопления результата:

let p_manyf a f v0 = let rec loop v s = match a s with | Parsed(x, s') -> loop (f v x) s' | Failed -> Parsed(v, s) in loop v0

Здесь v0 — начальное значение, которое трансформируется функцией f на каждой успешной итерации с использованием результата разбора на этой итерации. Например, вот так можно разобрать целое положительное число:

let mkInt v x = v * 10 + int_of_char x - 48 let p_int = p_manyf p_digit mkInt 0

Оператор последовательности выкидывал результат первого парсера и возвращал результат второго. Но что делать, если результат первого тоже важен? Тут можно задействовать монады. Создадим вспомогательный парсер:

let return x s = Parsed(x, s)

return x — парсер, возвращающий значение x, игнорируя переданный ему список символов и возвращая его в качестве неразобранного остатка. Теперь опишем оператор монадного сочленения парсеров:

let (>>=) p1 f s = match p1 s with | Parsed(x, s2) -> f x s2 | Failed -> Failed

Его правый аргумент f — не парсер, а функция, которая получает значение из успешного результата отработки парсера p1 и возвращает новый парсер, который тут же и применяется. Таким образом получается последовательное применение двух парсеров, где поведение и результат второго зависят от значения, разобранного первым. Например, разбор знакового целого числа может быть сделан так:

let p_int = p_opt 1 (p_char '-' >>> return (-1)) >>= fun sign -> p_manyf p_digit mkInt 0 >>= fun n -> return (sign * n)

Если полученная на входе строка начинается на минус, то успешно отрабатывает p_char '-', его результат (символ ’-’) заменяется на -1 и возвращается в качестве результата p_opt, а если минуса не было, то возвращается значение по умолчанию: 1. Данное значение запоминается под именем sign. Потом разбираются цифры, из которых получается целое число n. Результат разбора цифр умножается на sign и полученное значение считается результатом всего разбора p_int.

А вот так выглядит разбор вещественного числа вида -123.4567:

let mkFloat (fv,fr) c = fv +. float_of_int (int_of_char c - 48) *. fr , fr *. 0.1 let p_float = p_opt 1.0 (p_char '-' >>> return (-1.0)) >>= fun sign -> p_manyf p_digit mkInt 0 >>= fun n -> p_char '.' >>> p_manyf p_digit mkFloat (0.0, 0.1) >>= fun (fv, _) -> return (sign *. (float_of_int n +. fv))

Что интересно, этот парсер работает почти вдвое быстрее, чем стандартная окамловская функция float_of_string.

Данный набор комбинаторов позволяет описывать довольно сложные грамматики и одновременно действия по разбору. Например, я его успешно использовал для разбора сообщений от сервера в соревновании Sapka’094, а также в утилите для раскраски исходного кода на OCaml5.

3  Классические комбинаторы и Packrat

У описанных выше классических парсер-комбинаторов есть одна проблема — экспоненциальная сложность по отношению к грамматике. В простых случаях этого эффекта не заметно, но когда грамматика становится достаточно сложной и ветвистой (например, при разборе языка программирования), то скорость падает очень сильно. Дело в том, что схема работы парсер-комбинаторов есть рекурсивный спуск с откатами. Допустим, мы разбираем некий язык программирования с арифметическими операциями над числами, переменными и элементами массивов. Тогда, чтобы разобрать выражение «42», парсер будет перебирать варианты: исходная строка-выражение — это или а1) сумма подвыражений, или б1) разность подвыражений, или в1) просто подвыражение, где каждое подвыражение есть или а2) произведение атомов, или б2) отношение атомов, или в2) деление с остатком атомов, или г2) просто атом, где каждый атом есть или а3) число, или б3) переменная, или в3) элемент массива, где индекс — тоже выражение. Парсер сначала будет пытаться разобрать выражение как сумму, но не найдя знака ’+’, начнет пытаться разобрать выражение как разность, и не найдя знака ’-’, будет разбирать выражение как просто подвыражение. При этом подвыражение будет разобрано трижды, каждый раз по очереди пытаясь интерпретировать его как произведение, как отношение и т. д. Количество перебираемых подвариантов перемножается, а если наше исходное выражение — часть более сложного, то оно тоже будет разобрано много раз, соответственно числу вариантов ветвей грамматики, включающей выражение, т. е. умножаем еще, отсюда и экспонента.

Основная проблема тут — что одна и та же работа делается многократно, при каждом откате результат разбора теряется. Логичным решением этой проблемы является мемоизация результатов. Техника подобного разбора с мемоизацией всех результатов носит имя Packrat6, что дословно означает «земляная крыса», но также имеет переносный смысл «человек, привыкший ничего не выбрасывать и хранить все подряд, даже ненужное». На практике нет необходимости мемоизировать абсолютно все — достаточно мемоизации нескольких самых ветвистых (с большим количеством альтернатив) правил грамматики. Когда я применял парсер-комбинаторы для разбора собственного языка программирования, мемоизации четырех правил оказалось достаточно, чтобы от «очень медленно» перейти к «мгновенно».

Для мемоизации результатов парсинга отлично подходит механизм ленивых вычислений, доступный в OCaml. Допустим, мы разбираем вышеприведенный пример с выражениями, состоящими из переменных, чисел и арифметических операций. Правило грамматики для подвыражения выглядит так:

subexp = | atom '*' atom | atom '/' atom | atom '%' atom | atom

Ему соответствует парсер вида

let p_subexp = (p_atom >>= fun a1 -> p_char '*' >>> p_atom >>= fun a2 -> return Mul(a1, a2)) ||| (p_atom >>= fun a1 -> p_char '/' >>> p_atom >>= fun a2 -> return Div(a1, a2)) ||| (p_atom >>= fun a1 -> p_char '%' >>> p_atom >>= fun a2 -> return Mod(a1, a2)) ||| p_atom

который возвращает результат типа expr. Чтобы не делать кучу работы по многу раз, мы мемоизируем результаты работы парсеров p_subexp и p_atom. Для этого вместо списка символов наши парсеры будут работать со списком значений, содержащих не только исходный символ, но и ленивые вызовы функций разбора, начиная с этого символа:

type mem_char = { ch : char; subexp : (expr, mem_char) parse_result Lazy.t; atom : (expr, mem_char) parse_result Lazy.t } let prepare char_list = List.fold_right (fun ch res -> let rec v = { ch=ch; subexp = lazy(p_subexp_r vlst); atom = lazy(p_atom_r vlst) } and vlst = v::res in vlst) char_list [] let p_subexp = function [] -> Failed | h::t -> Lazy.force h.subexp let p_atom = function [] -> Failed | h::t -> Lazy.force h.atom

Заменим p_subexp и p_atom на форсирование ленивых вычислений, а исходные функции переименуем в p_subexp_r и p_atom_r. Функция prepare берет исходный список символов и превращает его в список mem_char’ов, содержащих эти символы и пока еще не вызванные вызовы разбора подвыражений и атомов. Текст, который мы хотим разобрать, мы должны сперва превратить в список символов, который функцией prepare превратить в список mem_char’ов, который уже подавать на вход парсер-комбинаторам. Когда измененный таким образом наш парсер языка программирования работает, он вызывает функции для разбора атомов, подвыражений и пр., которые вызывают сохраненные в нашем списке ленивые функции разбора, а они работают ровно один раз — при первом обращении. Все следующие обращения к ним возвращают сохраненный результат. В итоге, если надо разобрать выражение «42», то когда парсер будет пытаться разобрать его как сумму, начинающуюся с подвыражения, и разберет подвыражение, он запомнит результат и в мыслях «а уж не разность ли это или, может, просто подвыражение» будет использовать этот результат вместо повторения проверок.

У такого подхода есть еще один большой плюс. Если в какой-то момент, расширяя грамматику языка, мы случайно создадим левую рекурсию (например, выражение состоит из произведений, те из чего-то, что состоит из простых выражений, одно из них может быть оператором, а один из операторов может быть выражением), то обычные парсер-комбинаторы на таком просто виснут — зацикливаются. А при мемоизации через ленивые вызовы получится, что при форсировании ленивого значения идет обращение к нему самому. Механизм реализации ленивых вычислений в языке OCaml такую ситуацию отлавливает и бросает исключение Lazy.Undefined, источник которого указывается в back trace. В результате можно сразу увидеть, где есть такой цикл, и исправить его, убрав левую рекурсию из грамматики.

Очевидным минусом явной мемоизации является необходимость для каждого мемоизируемого парсера менять тип mem_char и функцию prepare. Впрочем, изменения эти однотипные и много времени не отнимают.

Альтернативным подходом к решению проблемы многократного разбора является левая факторизация, когда грамматика преобразуется к виду, где у правил разные альтернативы начинаются по-разному, что минимизирует необходимость в откатах. Например, данный фрагмент грамматики можно преобразовать к виду

op = '*' atom | '%' atom | '/' atom | empty subexp = atom op

Тогда каждый атом будет разобран один раз. Заметим, что когда парсеры строятся по естественному виду грамматики, как в первом примере, код построения разобранного значения получается максимально простым и наглядным: для выражения arom * atom строится значение Mul(a1a2), где составляющие a1 и a2 получаются и используются локально. Но при использовании левой факторизации построение разобранного значения сильно усложняется, т. к. теряется эта локальность. Придется из парсера op возвращать значение специального типа с результатом его разбора (пара из операции и значения второго атома либо признак их отсутствия), а в парсере subexp использовать сопоставление с образцом для выбора нужного варианта и по-разному строить результат. Это сильно усложняет и загромождает код, поэтому левая факторизация для ускорения парсер-комбинаторов — не лучшее решение.

4  Оптимизирующие комбинаторы

Процесс работы классических парсер-комбинаторов состоит из конструирования замыканий, вызовов функций и выделений памяти под промежуточные результаты, что создает нагрузку на сборщик мусора и вообще не способствует хорошей скорости. Кроме того, исходные данные должны быть представлены в виде списка символов. В отличие от Haskell, где строки так и определены, в OCaml строки хранятся в виде непрерывных массивов символов, а конвертирование строки в список может занимать вдвое больше времени, чем сам парсинг. Можно заменить список парой «строка – позиция», но это не дает существенного выигрыша в скорости работы (конкретные цифры замеров см. ниже).

Поэтому можно подойти к реализации парсер-комбинаторов с другой стороны. Если мы посмотрим на самый простой из них — парсер, разбирающий один символ, то увидим, что его можно описать простым конечным автоматом (КА) с таким графом состояний:

Сначала он находится в состоянии in, и если символ подходящий, то переходит в состояние ok, возвращая успешный результат и остаток списка, а если символ не подходит, то автомат переходит в состояние fail, не изменяя переданного ему списка. И вообще, любой парсер имеет такой общий вид: у него есть одно входное состояние и два выходных — успех и неудача.

Графы состояний автоматов парсер-комбинаторов можно получить, соединяя разным образом графы автоматов их аргументов. Результат тоже всегда имеет одно входное состояние и два выходных, поэтому подходит для дальнейшего манипулирования другими комбинаторами. Вот так, например, выглядит автомат для последовательности двух парсеров (мы его описывали оператором >>>):

В точном соответствии с логикой оператора последовательности, он возвращает успех (приходит в состояние ok), если успешно по очереди отработали оба парсера, из которых строится последовательность. Если же какой-то из них не смог разобрать свою часть, то возвращается неудача (происходит переход в состояние fail).

Аналогично описываются комбинаторы альтернативы,

опциональности,

и повторения.

Комбинируя таким образом автоматы, можно получить те же парсеры, что мы могли построить с помощью классических парсер-комбинаторов, кроме некоторых рекурсивных.

Подобно тому, как в классических парсер-комбинаторах мы использовали несколько операторов и функций для построения сложных парсеров из простых, здесь мы опишем набор аналогичных операторов и функций, которые будут строить граф конечного автомата из других более простых графов. Затем построенный граф может быть упрощен и превращен в таблицу, по которой функция-парсер уже сможет работать без лишних накладных расходов. Единственное затруднение — как описать семантические действия по созданию разобранных значений. В классическом подходе использовались замыкания, и разобранные ранее значения можно было использовать позже для синтеза более сложных. Однако результатом комбинаторов была монолитная функция, которую преобразовать и упростить уже нельзя. Возможно, у проблемы есть элегантное решение, но я пока поступил просто: семантические действия передают друг другу данные через изменяемые переменные, доступные им всем.

Граф можно описать набором вершин, каждая из которых может иметь несколько переходов из себя в другие вершины. В графе КА парсера есть три вида переходов: а) встречен подходящий символ, б) ветка else и в) безусловный переход. Каждый переход может сопровождаться каким-нибудь действием. Действия на переходах по символу получают код этого символа в качестве аргумента, другие действия ничего не получают и работают исключительно с описанным снаружи состоянием7.

Переход по узнанному символу меняет текущую позицию в разбираемом тексте. Если какой-то парсер не смог разобрать свою часть, то, как и в классическом варианте, текущая позиция должна остаться той же, что была до начала его работы. Для этого мы должны уметь ее запоминать и при необходимости восстанавливать. Так как сложные парсеры обычно состоят из вложенных друг в друга более простых, нам потребуется стек для хранения позиций. При входе в сложный парсер текущая позиция будет запоминаться в стеке, при неудачном исходе она будет из него извлекаться и использоваться для отката, а при удачном исходе будет выкидываться из стека как более не нужная.

Определим возможные операции со стеком позиций:

type pos_oper = Push | Pop | Rollback | No

Push — запомнить текущую позицию на стеке, Pop — убрать позицию с вершины стека, Rollback — взять со стека позицию и сделать ее текущей (откатиться назад), No — ничего не делать.

Тогда тип переходов можно описать так:

type move_kind = | Symb of char * char * (int -> unit) option * int * pos_oper | Else of (unit -> unit) option * int * pos_oper | Goto of (unit -> unit) option * int * pos_oper

Тут используются пары значений типа char, чтобы сразу задавать не один символ, а набор символов от одного до другого, например ’a’ – ’z’ или ’0’ – ’9’. Параметр типа int у перехода — номер вершины в графе, куда осуществляется переход. Else и Goto отличаются лишь тем, что если из вершины есть безусловный переход Goto, то это единственный переход из этой вершины. Этот факт используется дальше при упрощении графа.

Храня наборы переходов и вершин в массивах, элементарные графы, разбирающие один символ, можно описать так:

let ok = 1 let fail = 2 let p_range c1 c2 = [| [| Symb(c1,c2, None, ok, No); Else(None, fail, No) |]; [||]; [||] |] let p_char c = p_range c c let f_range c1 c2 f = [| [| Symb(c1,c2, Some f, ok, No); Else(None, fail, No) |]; [||]; [||] |] let f_char c f = f_range c c f

p_char c успешно разбирает символ c и возвращает неудачу, если на входе любой другой символ.  p_range описывает допустимый интервал символов, например цифры или буквы. Их аналоги, начинающиеся с f_, делают все то же, но при этом содержат некие семантические действия, которые будут выполнены при успешном разборе символа. Эти графы имеют три вершины — in, ok и fail — и два перехода из нулевой (in) в другие. Поскольку все КА парсеров имеют эти три состояния, можно условиться, что первые три вершины любого графа у нас будут обозначать in, ok и fail. Каждый синтезируемый из других граф будет иметь эту внешнюю рамку из таких трех состояний, причем из нового состояния in будет безусловный переход на начальное состояние первого подграфа. Описанная ниже функция frame создает такую рамку. Функция relocate делает из заданного графа подграф, сдвигая номера упоминаемых в нем вершин. Функция connect создает подграф и соединяет его выходные состояния ok и fail с заданными состояниями нового графа.

let frame in_move = [| [| in_move |]; [||]; [||] |] let relocate parser delta = Array.map (Array.map (function | Symb(c1, c2, f, idx, op) -> Symb(c1, c2, f, idx + delta, op) | Else(f, idx, op) -> Else(f, idx + delta, op) | Goto(f, idx, op) -> Goto(f, idx + delta, op))) parser let connect parser delta ok_move fail_move = let res = relocate parser delta in res.(ok) <- [| ok_move |]; res.(fail) <- [| fail_move |]; res

Используя эти вспомогательные функции, опишем построение графа для последовательности двух парсеров.

let (>>>) a b = let b_start = 3 + Array.length a in Array.concat [frame (Goto(None, 3, Push)); connect (norb a) 3 (Goto(None, b_start, No)) (Goto(None, fail, Rollback)); connect (norb b) b_start (Goto(None, ok, Pop)) (Goto(None, fail, Rollback))]

В соответствии с приведенной выше схемой, из начального состояния в нем делается переход на начало первого парсера, при этом текущая позиция кладется на стек. Если первый парсер отработал успешно, то идет переход на начало второго, иначе переход в состояние fail с откатом позиции. Если второй парсер отработал успешно, то переходим в состояние ok, убирая с верхушки стека сохраненную позицию. Если же второй парсер выдал неудачу, то точно так же переходим в fail, восстанавливая сохраненную позицию. Поскольку сохранением и восстановлением текущей позиции занимается верхний «слой» графа (переходы из начального состояния и переходы в конечные), то подграфы могут сами этим не заниматься. Для этого они перед добавлением в граф пропускаются через вспомогательную функцию norb, которая убирает из них соответствующие действия (если они там были). Эта необязательная оптимизация, код которой здесь не приводится, позволяет заметно сократить число переходов в графе.

Аналогично строятся и остальные комбинаторы — опциональности, альтернативы, повторения и т. д. Их аналоги с префиксом f_ запоминают в графе семантические действия.

let p_opt a = Array.append (frame (Goto(None, 3, No))) (connect a 3 (Goto(None, ok, No)) (Goto(None, ok, No))) let f_opt a f = Array.append (frame (Goto(None, 3, No))) (connect a 3 (Goto(None, ok, No)) (Goto(Some f, ok, No))) let (|||) a b = let b_start = 3 + Array.length a in Array.concat [frame (Goto(None, 3, No)); connect a 3 (Goto(None, ok, No)) (Goto(None, b_start, No)); connect b (b_start) (Goto(None, ok, No)) (Goto(None, fail, No))] let p_many a = Array.append (frame (Goto(None, 3, No))) (connect a 3 (Goto(None, 0, No)) (Goto(None, ok, No))) let f_many initf a = Array.concat [frame (Goto(Some initf, 3, No)); connect a 3 (Goto(None, 3, No)) (Goto(None, ok, No))] let p_plus p = p >>> p_many p let (>>=) p f = Array.append (frame (Goto(None, 3, No))) (connect p 3 (Goto(Some f, ok, No)) (Goto(None, fail, No)))

Имея такие комбинаторы, можно строить графы конечных автоматов для сложных парсеров.

В результате получается довольно развесистый граф. Однако, его можно сильно упростить, убрав все состояния, содержащие только безусловный переход в другое.

let rec simplify p = let skip_first e = Enum.junk e; e in Array.enum p |> skip_first |> Enum.mapi (fun srcn node -> Array.enum node |> Enum.filter_map (function Goto(None, dstn, No)-> Some(srcn+1, dstn)| _->None)) |> Enum.concat |> Enum.get |> Option.map_default (fun (srcn, dstn) -> let dstn' = if dstn < srcn then dstn else dstn-1 in let adjust_idx idx = if idx < srcn then idx else if idx=srcn then dstn' else idx-1 in let adjust_move = function | Symb(c1, c2, f, idx, op) -> Symb(c1, c2, f, adjust_idx idx, op) | Else(f, idx, op) -> Else(f, adjust_idx idx, op) | Goto(f, idx, op) -> Goto(f, adjust_idx idx, op) in let p' = Array.enum p |> Enum.mapi (fun i node-> (i,node)) |> Enum.filter_map (fun (i,node) -> if i = srcn then None else Some(Array.map adjust_move node)) |> Array.of_enum in simplify p') p

Тут используются ленивые последовательности из модуля Enum, входящего в библиотеки ExtLib и Batteries, дополняющие стандартную библиотеку OCaml.

Дальше граф можно превратить в таблицу, где в каждом состоянии для каждого возможного входного символа будет указано действие — принять символ (перейти дальше по строке) или не трогать, выполнить какое-то семантическое действие или не выполнять — номер состояния, в которое следует перейти из данного, и сопутствующая операция со стеком позиций.

type move_action = | Consume | Keep | ConsumeA of (int -> unit) | KeepA of (unit -> unit) let tabulate p = p |> Array.map (fun node-> let tmp = Array.make 257 (Keep, -1, No) in let default_move = Array.fold_left (fun def kind -> match kind with | Symb(c1, c2, fo, idx, op) -> let action = Option.map_default (fun f -> ConsumeA f) Consume fo in let m = (action, idx, op) in for i = int_of_char c1 to int_of_char c2 do tmp.(i)<-m done; def | Else(fo, idx, op) | Goto(fo, idx, op) -> Option.map_default (fun f -> KeepA f) Keep fo, idx, op ) (Keep, fail, No) node in tmp |> Array.map (fun ((k, idx, op) as x) -> if idx >=0 then x else default_move))

Эту таблицу можно еще оптимизировать. Если при встрече какого-то символа не совершается никаких действий, и просто идет переход в другое состояние, можно проследить по таблице, какое же действие в конце концов будет выполнено для этого символа и это действие поставить сразу в рассматриваемую ячейку, таким образом сэкономив на переходах. Помимо этого, некоторые действия можно объединить. В итоге ни одна смена состояния не будет совершаться вхолостую, все они будут сопровождаться теми или иными действиями.

let optimize tbl = let rec optimove ch move = match move with | _, 1, _ | _, 2, _ -> move | Keep, next_state, No -> optimove ch tbl.(next_state).(ch) | Keep, next_state, (Push as op) | Keep, next_state, (Pop as op) -> (match optimove ch tbl.(next_state).(ch) with | Consume, nxt2, No -> Consume, nxt2, op | _ -> move) | KeepA f, next_state, No -> (match optimove ch tbl.(next_state).(ch) with | Keep, nxt2, op -> KeepA f, nxt2, op | KeepA f2, nxt2, op -> KeepA (f >> f2), nxt2, op | _ -> move) | _ -> move in Array.mapi (fun state tab -> if state!=1 && state!=2 then Array.mapi optimove tab else tab) tbl

Оптимизация таблицы и упрощение графа — очень похожие операции, и если не делать упрощения графа, а только оптимизацию таблицы, то количество совершаемых при работе парсера переходов будет тем же, однако количество состояний в таблице будет значительно больше, отчего ей будет сложнее поместиться в кэш процессора.

Имея такую оптимизированную таблицу, можно уже получить готовый быстрый парсер, который будет действовать по этой таблице и в конце концов выполнять либо действие, соответствующее успеху всего парсера, либо соответствующее неудаче. Конец строки представим особым символом с номером 256, чтобы реакция на него тоже была в таблице действий.

let execute success fail tbl str = let len = String.length str in let stack = Array.make (Array.length tbl) 2 in let rec run state i sp = match state with | 1 -> success () | 2 -> fail () | _ -> let ch = if i<len then int_of_char str.[i] else 256 in match tbl.(state).(ch) with | Consume, next_state, No -> run next_state (i+1) sp | Consume, next_state, Push -> stack.(sp)<-i; run next_state (i+1) (sp+1) | Consume, next_state, Pop -> run next_state (i+1) (sp-1) | Keep, next_state, Push -> stack.(sp)<-i; run next_state i (sp+1) | Keep, next_state, Pop -> run next_state i (sp-1) | Keep, next_state, Rollback -> run next_state stack.(sp-1) (sp-1) | ConsumeA f, next_state, No -> f ch; run next_state (i+1) sp | KeepA f, next_state, No -> f (); run next_state i sp | KeepA f, next_state, Push -> f (); stack.(sp)<-i; run next_state i (sp+1) | KeepA f, next_state, Pop -> f (); run next_state i (sp-1) | KeepA f, next_state, Rollback -> f (); run next_state stack.(sp-1) (sp-1) | _ -> failwith "unexpected move" in run 0 0 0 let prepare success fail parser = parser |> simplify |> tabulate |> optimize |> execute success fail

Функция execute содержит «сердце» быстрого парсера — цикл с тремя переменными: номером текущего состояния, индексом текущей позиции в разбираемой строке и индексом верхушки стека позиций. Напомним, что состояния с номерами 1 и 2 — это конечные состояния успеха и неудачи. Попадая туда, функция выполняет соответствующее им действие и завершает работу. В остальных же состояниях, подобно машине Тьюринга, она берет код символа в текущей позиции и по таблице, индексируемой номером состояния и кодом символа, определяет следующее действие и состояние.

Функция prepare берет исходный граф, построенный нашими комбинаторами, упрощает его, превращает в таблицу, оптимизирует ее и создает функцию-парсер, принимающую на вход строку и в зависимости от результата разбора выполняющую одно из заданных действий. Построив с помощью описанных выше комбинаторов граф парсера, достаточно передать его функции prepare, сопроводив двумя действиями — что делать в случае успеха и в случае неудачи, чтобы получить функцию, принимающую строку и разбирающую ее. Тип результата такой функции определяется типом параметров-действий success и fail.

5  Сравнение с другими методами парсинга

Чтобы оценить скорость работы описанных методов и сравнить ее с альтернативными подходами, мы применили различные способы парсинга на одной задаче, не очень сложной, но достаточно практической. Суть задачи в том, чтобы прочитать файл карты в формате OpenStreetMap и определить ее реальные границы — минимальные и максимальные значения координат имеющихся на карте точек. Формат карты включает в себя поле bounds с похожими по смыслу значениями, но обычно это границы карты «с запасом», так что точки карты этих границ не касаются. Формат карты основан на XML, но в данной задаче полностью разбирать все детали XML не нужно, достаточно уметь извлечь нужную информацию из интересущих нас тэгов и полей.

Решение задачи с использованием оптимизирующих парсер-комбинаторов умещается в 50 строк:

let minlat = ref 1000.0 let maxlat = ref (-1000.0) let minlon = ref 1000.0 let maxlon = ref (-1000.0) let p_latlon name = p_str (name ^ "=\"") >>> p_float >>> p_char '"' let low_letter c = c >= 'a' && c <='z' let p_param = p_plus (p_pred low_letter) >>> p_str "=\"" >>> p_many (p_pred ((<>)'"')) >>> p_char '"' let p_node_param = (p_latlon "lat" >>= fun () -> let lat = !Fsm_parsing.float_res in minlat := min !minlat lat; maxlat := max !maxlat lat) ||| (p_latlon "lon" >>= fun () -> let lon = !Fsm_parsing.float_res in minlon := min !minlon lon; maxlon := max !maxlon lon) ||| p_param let p_ws = p_many (p_pred ((>=) ' ')) let p_endnode = (p_str "/>") ||| (p_all_until "</node>") let p_node = p_str "<node" >>> p_many (p_ws >>> p_node_param) >>> p_endnode let p_tag = p_char '<' >>> p_many (p_pred ((<>) '>')) >>> p_char '>' let p_osm = p_many ((p_node ||| p_tag) >>> p_ws) let process osm = let ok_action () = Printf.printf "ok: lat=%f..%f lon=%f..%f\n" !minlat !maxlat !minlon !maxlon in let parse = prepare ok_action (fun () -> print_string "fail") p_osm in parse osm

Смысл его в том, что карта формата OSM представляется последовательностью тэгов, между которыми могут быть разделители, вроде пробелов, символов конца строки и т. д. Тэг может быть либо тэгом node, содержащим информацию о точке, либо каким-то другим тэгом. Все тэги, отличные от node, нас не интересуют, поэтому их представим как произвольную последовательность символов, заключенную в угловые скобки. Что касается тэга node, то он состоит из заголовка (строки «<node>»), последовательности параметров тэга, и окончания, состоящего либо из строки «/>» (закрытия тэга), либо из вложенных тэгов, за которыми следует строка «</node>». Координаты точек содержатся среди параметров тэга node. Это параметры lat для широты и lon для долготы. Они состоят из имени параметра, знака «=» и вещественного числа в кавычках, которое мы разбираем и тут же используем для обновления переменных, содержащих текущие минимальные и максимальные значения. Другие же параметры тэгов мы игнорируем, описывая их как произвольный набор букв, за которым идет знак «=» и некая строка в кавычках. Такого простого описания грамматики достаточно, чтобы решить исходную задачу.

Ее решение на классических парсер-комбинаторах выглядит почти идентично. Кроме них, были сделаны решения на базе генератора парсеров ocamlyacc, библиотеки парсер-комбинаторов на Хаскелле Parsec 2 (GHC 6.12.1, Parsec 2.1.0.1), еще одной библиотеки парсер-комбинаторов attoparsec 0.8.0.2, на С++ с использованием библиотеки парсер-комбинаторов Boost.Spirit (версия 2.2 из Boost 1.42, компилировалось в VS2005), на Lua 5.1.4 с использованием библиотеки LPEG, и на языке C# 2.0 с использованием стандартного средства для работы с XML — библиотеки System.Xml. Код на OCaml компилировался версией компилятора 3.10.2 в варианте, использующем ассемблер и линкер из MSVC.

Все решения были протестированы на карте Сингапура8 на ноутбуке с процессором Intel Core 2 Duo 2.33 MHz и ОС Windows Vista. Там, где это было возможно, скорость чтения файла не входила в замер, учитывалась только скорость разбора уже прочитанного в память файла.


Haskell / Parsec 23.5 МБ/с
Haskell / attoparsec8.2 МБ/с
Классические парсер-комбинаторы на OCaml, если включать время на преобразование из строки в список символов.6.6 МБ/с
Они же, если считать только парсинг списка.18.9 МБ/с
Эти же комбинаторы были реализованы в варианте, где вместо списка использовалась пара строка-позиция. Такой вариант не требовал перевода из строки в список.8.3 МБ/с
Парсер, сгенерированный парой ocamlyacc и ocamllex.12.9 МБ/с
Вариант на С++ с использованием библиотеки парсер-комбинаторов Boost Spirit 2.18.1 МБ/с
Lua / LPEG (на языке Lua описывается грамматика, а разбор по ней осуществляет модуль LPEG на Си).20.2 МБ/с
Оптимизирующие парсер-комбинаторы на OCaml, включая время на построение графа, его оптимизацию, построение таблицы и т. д.42.6 МБ/с
Наконец, вариант C# с System.Xml.46.0 МБ/с
Таблица 1: Скорость полученных решений

Исходные тексты всех вариантов доступны на официальном сайте журнала.

Можно видеть, что применение предлагаемого подхода к построению оптимизирующих парсер-комбинаторов позволяет сохранить преимущества классических парсер-комбинаторов (выразительность, отсутствие отдельной фазы кодогенерации) и получить в несколько раз большую скорость работы.

6  Заключение

Описанные в этой статье парсер-комбинаторы очень просты и в таком виде не могут сравниться по возможностям с такими развитыми библиотеками, как Parsec и Spirit. Зато они легки в понимании, реализации, использовании и исполнении. Во многих задачах их возможностей оказывается вполне достаточно, поэтому они могут служить практичным компромиссом по гибкости и скорости.


1
http://en.wikipedia.org/wiki/Parser_combinator
2
На нефункциональных языках возможна похожая техника, но результатами комбинаторов там являются не сразу функции-парсеры, а структуры данных, которые интерпретируются отдельной функцией. Примеры: Boost.Spirit для С++ и LPEG для Lua.
3
В литературе чаще используется термин «возврат» вместо «отката», но здесь это может создать путаницу с возвратом разобранного значения.
4
http://about.thedeemon.com/texts/sapka09/
5
http://ocolor.thedeemon.com/
6
http://pdos.csail.mit.edu/~baford/packrat/thesis/
7
Можно было бы избавиться от глобальных переменных, если снабдить функцией-действием каждый переход в графе, чтобы эти функции принимали на вход состояние и возвращали измененное состояние. Но это негативно отразится на скорости, т. к. во-первых, вызовом функции будет сопровождаться каждый переход в графе, а не только необходимые, а во-вторых, будет сложно заниматься упрощением графа, потому что цепочку переходов без действий можно сократить до одного перехода, выкинув лишние, а с переходами с действиями так сделать нельзя.
8
http://downloads.cloudmade.com/asia/south-eastern_asia/singapore/singapore.osm.bz2

Этот документ был получен из LATEX при помощи HEVEA