Публикации с меткой «fp»

С некоторого времени я стал делать на 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 раз меньше, намного более читаемого :)

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

В осеннем семестре 2008 читал в Политехе курс лекций «Языки программирования» студентам 5-ого курса кафедры АиВТ. Идеей было дать общий подход к рассмотрению языков, познакомить с функциональным программированием, рассмотреть некоторые компромиссы при проектировании языков. Курс наполовину основан на SICP и языке Scheme, а вторая половина посвящена сравнительному обзору языков C, C++, Python и Java.

Поделюсь впечатлениями о курсе. Во-первых, наши студенты имеют весьма туманные навыки программирования, немного грустно :( Думаю, такое характерно для большинства вузов, хотя наверняка есть и исключения. Они написали к 5-ому курсу слишком мало программ (к тому же весьма простых), и не в состоянии нормально чувствовать и рассуждать о проблемах борьбы со сложностью в программировании. Во-вторых, в курсе получился большой перекос в сторону основ ФП и Scheme в противовес передаче сообщений, параллельности, малым языкам и т. д. Наконец, чтение курса помогает заострить внимание на моментах, которые иначе не были бы замечены и систематизированы.

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

Студентов поздравляю с Татьяниным днём :)