Жизнь на свободе Голосов: 1 Адрес блога: http://sovety.blogspot.com/ Добавлен: 2008-02-19 12:40:29 блограйдером Lurk

Ещё одна библиотека комбинаторного парсинга

2009-09-08 11:07:00 (читать в оригинале)

Не так давно я писал о библиотеке pyparsing для комбинаторного парсинга в Python. В комментариях появилась ссылка на ещё одну библиотеку, о которой я вначале не знал, а именно на funcparserlib, написанную Андреем Власовских.

В общем-то, я посмотрел на новую библитечку, и она мне тоже понравилась. Подкупает сравнительная простота самой библиотеки, ясные исходники и подробно написанные руководства — понять как работает библиотека нетрудно. Правда, при чтении документации нужно быть знакомым с нотацией типов, принятой в Haskell (ArgType -> ResultType). Общее впечатление: имеющиеся в funcparserlib комбинаторы практически полностью ортогональны друг другу, записываются кратко, места на экране занимают мало, называются понятно.

Комбинаторов в библиотеке всего-то: some, a, many, finished, maybe, skip, oneplus, forward_decl, +, | и >>. Действие большинства комбинаторов угадывается из названия. Рабочие лошадки: some(функция-предикат) берёт токен, удовлетворяющий условию, a(токен) берёт токен, указанный в аргументе, many(парсер), maybe(парсер), oneplus(парсер) — множественное, возможное или хотя бы однократное срабатывание парсера, skip(парсер) отбрасывает всё найденное парсером. Плюс (+) последовательно применяет два парсера, «или» (|) пробует альтернативные варианты, >> подставляет результат парсера в функцию и создаёт новый парсер (очень полезный комбинатор!). Ещё есть tuple для группировки.

Для пробы я решил написать пример разбора того же файлового формата, что и в заметке о pyparsing. Мне кажется, что наиболее эффективно применять funcparserlib с предварительным лексическим анализом (разбиением текста на токены-лексемы). В принципе, готовый токенизатор — часть стандартной библиотеки Python, поэтому это не проблема. Удобная обёртка приведена в руководстве к funcparserlib. Однако мне хотелось написать пример в том же стиле, что и для pyparsing, поэтому в примере ниже я разбираю текст на уровне отдельных символов.

Полный текст примера с тестами кладу в pastebin. Далее пояснения.

Половина кода пришлась на разбор чисел. Вообще, по-моему, в такого рода библиотеках было бы хорошо класть готовые парсеры для чисел, дат, e-mail и тому подобных обыденных вещей где-нибудь в разделе contrib... Впрочем, написать разбор чисел было даже занятно.

Чтение знака числа. Если ни плюса, ни минуса нет, подразумеваю плюс. Волшебный комбинатор >> позволяет обработать результат и сразу подготовить ответ, или -1, или +1:

sign = maybe(a("-")|a("+")) >> (lambda c: c == "-" and -1 or +1)

Целые числа состоят из знака и последовательности цифр. Так и запишем:

digits = many(some(lambda c: c.isdigit()))int_num = sign + (digits >> to_int) >> mk_int

Здесь я пользуюсь опять комбинатором >> и двумя вспомогательными функциями. Одна превращает последовательность символов-цифр в число (to_int), другая умножает результат на -1, если необходимо (mk_int). Эти функции вспомогательные, можно пропустить:

powers = lambda digs: zip(digs,xrange(len(digs)-1,-1,-1))add_digit = lambda acc, dp: acc+int(dp[0])*10**dp[1]to_int = lambda digs: reduce(add_digit, powers(digs), 0)mk_int = lambda (s,i): s*i

Аналогично строю и парсер для рациональных чисел, только прибавляю ещё и дробь, и, соответственно, ещё две вспомогательных функции:

to_frac = lambda digs: to_int(digs)*1.0/10**len(digs)mk_frac = lambda (s,i,f): s*(i+f)frac_num = sign + (digits >> to_int) + (skip(maybe(a("."))) + (digits >> to_frac)) >> mk_frac

Вот и всё. Использовать примерно так:

>>> frac_num.parse("-1.25")-1.25

Второй половиной кода оказалось написание парсеров для аналогов Literal и Word из pyparsing. Это необходимо, потому что без токенизации приходится распознавать цепочки токенов. Дополнительно создал парсер ws для пропуска пробелов:

pack = lambda cs: ''.join(cs)literal = lambda s: reduce(lambda a,b: a+b, map(a,s)) >> packword = lambda p: oneplus(some(p)) >> packws = skip(many(some(lambda c: c.isspace())))

После этих определений собственно парсер выбранного формата укладывается в три выражения:

varname = word(lambda c: c.isalpha())var = (ws + varname + ws + frac_num + ws)custom_format = skip(literal("Inspection")) + \ws + skip(literal("#")) + \ws + int_num + \ws + skip(literal("SHOULD")) + \ws + skip(literal("Ref. Sys")) + \ws + int_num + \many(var)

Смотрим на результат:

$ python test.py < input.txt (2, 1, [('X', 28.749300000000002), ('Y', 78.995999999999995), ('Z', -1.0014000000000001)])

В общем, впечатления хорошие. Документация у библиотеки приличная. Использовать приятно. Только одно досадное неудобство было связано с тем, что setup.py install --prefix=... из дистрибутивного тарбола не сработал как надо. Впрочем, библиотека такая маленькая, что можно положить все три её файла прямо в свой проект, без общесистемной установки.

Тонкости: нужно быть осторожным, не помещая универсально успешный парсер внутрь many, чтобы избежать вечного цикла. Короче, нельзя внутрь many помещать many, maybe и pure. Подробнее — см. FAQ.

См. также заметку про pyparsing.

Дополнение: слайды презентации funcparserlib на DevConf 2010: