Андрей Власовских

Блог Андрея Власовских

Функциональные комбинаторы парсеров в Python

4 комментария

С некоторого времени я стал делать на Python часть моих повседневных задач по анализу языков, трансляторам и пр. Вначале для вспомогательных целей, а потом и для парсинга небольших языков, прототипирования грамматик, деревьев AST, трансформаций кода. Многие при этом подумают про OCaml, но в Unix-среде (привет spb-archlinux!) от Python с его библиотеками пользы больше.

Для задач парсинга я написал библиотеку funcparserlib. Эта библиотека предназначена для создания парсеров по методу рекурсивного спуска на основе функциональных комбинаторов. Также я написал вводное руководство по funcparserlib (на английском), которое будет интересно всем, увлекающимся функциональным программированием (FP) и/или языком Python. Рекомендую его почитать!

Вот, например, такие картинки деревьев можно легко получать с помощью funcparserlib:

>>> print dotparser.pretty_parse_tree(tree)
Graph [id=g1, strict=False, type=digraph]
`-- stmts
    |-- Edge
    |   |-- nodes
    |   |   |-- n1
    |   |   |-- n2
    |   |   `-- SubGraph [id=n3]
    |   |       `-- stmts
    |   |           |-- Edge
    |   |           |   |-- nodes
    |   |           |   |   |-- nn1
    |   |           |   |   |-- nn2
    |   |           |   |   `-- nn3
    |   |           |   `-- attrs
    |   |           `-- Edge
    |   |               |-- nodes
    |   |               |   |-- nn3
    |   |               |   `-- nn1
    |   |               `-- attrs
    |   `-- attrs
    `-- Edge
        |-- nodes
        |   |-- SubGraph [id=n3]
        |   |   `-- stmts
        |   `-- n1
        `-- attrs

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

Отличительные особенности библиотеки funcparserlib:

  • Несколько необходимых удобных комбинаторов парсеров (API всего 14 вызовов). Код получается компактным, очень похожим по языку на xBNF-грамматики
  • Маленький размер самой библиотеки: всего лишь 0.5 KLOC с комментариями
  • Обнаружение ошибок по методу длиннейшего разобранного префикса даёт разумные сообщения об ошибках разбора
  • Маленький токенизатор на основе регулярных выражений позволяет следить за позицией лексем в тексте, выдавать её в сообщениях

При своём небольшом размере, библиотека является достаточной для написания парсеров весьма больших грамматик. Но главное предназначение — разбор небольших языков и языков DSL (предметно-ориентированных).

Для Python существуют несколько библиотек синтаксического анализа. Сравним некоторые из них с funcparserlib:

  • pyparsing. Самая популярная библиотека. Имеет не очень большой размер кода (3.7 KLOC), очень избыточный разношёрстный API (около сотни вызовов), довольно медленная (по простым тестам в 3 раза медленнее, чем funcparserlib)
  • LEPL. Библиотека с большой функциональностью, опциями и пр. (API содержит около сотни вызовов) Имеет очень большие для данной задачи исходные коды (около 15 KLOC). Быстрая, по утверждению авторов

Библиотека funcparserlib возникла поначалу из игрушечного примера парсера JSON, который я написал в 2008 году. Пример был создан, чтобы показать, что можно писать парсеры, в точности соответствующие формальной грамматике языка. Летом 2009 года я вернулся к парсерам на Python и решил дописать библиотеку, добавить токенизатор на regexps, выполнить оптимизации и т. д. На данный момент доступна версия 0.3.2, по которой я написал довольно много документации (на английском).

Теперь funcparserlib включает вполне приличный парсер JSON как один из примеров. Этот парсер поддерживает JSON со всеми нюансами и по скорости всего в 3 раза медленнее, чем специализированная библиотека simplejson. А исходного кода — в 8 раз меньше, намного более читаемого :)

Реклама

Written by vlan

2009-07-28 в 21:38

Опубликовано в Uncategorized

Tagged with , , ,

комментария 4

Subscribe to comments with RSS.

  1. слушай, прости за коммент в духе ЛОРа, но чем не устроил flex/bison? это ж тривиальные задачи.

    jetbird

    2009-07-29 at 00:46

  2. прости, пожалуйста, за коммент в духе ЛОР =)

    jetbird

    2009-07-29 at 00:48

  3. @jetbird Yacc/Bison/… — это LALR-парсеры, что значит, что нужно подстраивать грамматику под их lookahead. LL(*) же может практически любую грамматику, где нет левой рекурсии. Впрочем, Bison имеет режим GLR парсера. Нужно заметить, что если нужна большая скорость, то надо писать грамматики с учётом ограничений более быстрых алгоритмов, лучше всего LL(1). А если нужен краткий код почти без ограничений на грамматику, то лучше LL(*) или GLR.

    И, кстати, Bison генерирует код на C, а не на Python. Есть библиотека PLY (Python Lex-Yacc), но она LALR.

    vlasovskikh

    2009-07-29 at 01:08

  4. спасибо за ликбез, будем знать )

    jetbird

    2009-07-29 at 01:34


Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: