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

[_adept_]

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

Аннотация

Статья рассказывает о технике парсер-комбинаторов для построения

Comments

[gds]

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

Интересно, почему так получилось?

[alexott]

в С++ тоже самое - если пользоваться парсером на базе 2-го спирита, то оно быстрее чем atoi

[ext_4199]

А все-таки, почему?

[mr_aleph]

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

[mr_aleph]

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

[zoonior]

На обработку уходит ~20%, и это, скорее всего, да - выделение памяти под строки с флоатами. Я когда писал, знал (во основном со слов Иерусалимского), что LPEG по скорости как YACC/LEX, но такой прыти не ожидал :)

Касательно дальнейших оптимизаций:
1) получилось и так достаточно быстро (быстрее Spirit и Ocamlyacc)
2) специализированные XML парсеры легко дают больше 100 мег/сек - тут мы все равно проиграем :)

[mr_aleph]

я когда каптчи убрал вообще --- у меня приблизительно в три раза разогналось =)

[zoonior]

Хм, действительно. Причем, если каптчи заменить на
-> identity_function
скорость все равно сильно проседает (т.е. вроде-бы память непричем). Надо будет на досуге заглянуть в кишки :)

[anonymous]

В конце раздела 5.3: не совсем понятно про отлов зацикливания при форсировании ленивого значения. Если это действительно просто значение, то OCaml кидает Undefined:

# let rec foo = lazy (Lazy.force foo);;
val foo : 'a Lazy.t =
# Lazy.force foo;;
Exception: CamlinternalLazy.Undefined.

Но в статье форсируются вызовы функций, а это всё равно приводит к зацикливанию:

# let rec bar x = lazy (Lazy.force (bar x));;
val bar : 'a -> 'b Lazy.t =
# Lazy.force (bar 1);;
Stack overflow during evaluation (looping recursion?).

[thedeemon]

Вот упрощенный вариант той ситуации:

let p_lazy = function [] -> 0 | h::t -> Lazy.force h
let p_real lst = (*42*) p_lazy lst
let rec v = lazy(p_real lst) and lst = v::[];;
print_int (p_lazy lst);;

Если p_real возвращает 42, все работает. Если вызывает p_lazy - бросается Lazy.Undefined.

Типы:
val p_lazy : int Lazy.t list -> int
val p_real : int Lazy.t list -> int
val v : int Lazy.t
val lst : int Lazy.t list

[helvegr]

Версию на attoparsec можно ускорить примерно на треть, если поменять везде, где можно many/many1 на takeWhile/takeWhile1/skipWhile. Хотя всё равно звёзд с неба не будет хватать.

[dmzlj]

так парсеры (которые с оптимизацией fsm) в итоге могут рекурсивные структуры разбирать или нет? Вроде получается, что нет, но может я чего-то не заметил?

[permea_kra]

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

[thedeemon]

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

[permea_kra]

Это надо почитать.