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

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

Posts Tagged ‘parser

Функциональные комбинаторы парсеров в 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, сравнение с pyparsing и LEPL, история библиотеки…

Written by vlan

2009-07-28 at 21:38

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

Tagged with , , ,

Простой рекурсивный парсер JSON

with one comment

Недавно наткнулся на интересный метод парсинга, который в «Книге дракона» если и описан, то только в виде упоминания. Метод называется рекурсивный спуск с использованием перебора с возвратом (recursive descent with backtracking). Встретил я пример использования этого метода в русском переводе «Введения в функциональное программирование» Джона Харрисона (John Harrison). Парсеры такого типа можно свободно писать с нуля на функциональных языках.

Upd: Выпустил в июле 2009 года библиотеку funcparserlib. Вот пост о ней. Она включает в себя как пример довольно хороший парсер JSON. Материал ниже можно считать устаревшим.

Если есть BNF-подобное описание грамматики без левой рекурсии, то по её нетерминалам легко пишутся функции их разбора. Каждая такая функция является парсером и имеет тип (здесь и далее используется язык Python) Sequence(a) -> (b, Sequence(a)), где a — тип токенов (например, банальных str), b — тип результата разбора (в общем случае object), а Sequence — тип любой последовательности (вот один из вариантов того, что можно считать последовательностью). Для таких функций-парсеров можно ввести очень удобные комбинаторы типа альтернативы, следования, множественного применения. Вообще, это очень показательный пример преимуществ функционального программирования.

Используя этот метод, я написал парсер JSON на Python на основе грамматики из RFC 4627. Известны проблемы парсеров JSON на Python, но я строго следовал грамматике RFC, так что в лексике и синтаксисе ошибок быть не должно. Приведу исходный код. Вначале часть, которую можно было бы сделать библиотекой: несколько удобных комбинаторов, взятых из книги Харрисона, а также объектная обёртка комбинаторов для перегрузки операторов Python ради красоты:

Читать далее…

Written by vlan

2008-07-24 at 05:28

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

Tagged with , , , , , ,