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

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

Archive for Июль 2008

Простой рекурсивный парсер 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 , , , , , ,

Protocol Buffers и XDR

12 комментариев

Google Open Source Blog:

Protocol Buffers позволяет Вам определять простые структуры данных на специальном языке определений, затем компилировать их с целью создания классов, представляющих эти структуры в языке по Вашему выбору. Эти классы идут вместе с сильно оптимизированным кодом для разбора и сериализации Вашего сообщения в очень компактный формат.

Я пролистал документацию по мотивации, формату и API для Protocol Buffers. Формат очень напоминл мне XDR в ONC RPC. Стоило ли преподносить его с таким шумом? Шум, наверное, можно списать на резонанс в блогосфере. Меня удивила довольно небольшая доля постов, в которых вспоминают XDR или ASN.1.

Вот несколько различий между PB и XDR, которые сразу пришли мне в голову при листании доков:

  • XDR создан в Sun Microsystems в рамках Sun RPC (ONC RPC) в середине 1980-х, а PB — в Google в середине 2000-х
  • Библиотеки XDR есть практически для любого языка по разным лицензиям, а PB — только одна реализация от Google для Java, C++ и Python по Apache License 2.0
  • В IDL PB есть указатели обязательности полей сообщений, что полезно для обратной совместимости, а в XDR — нет, но есть пары «имя-значение» и объединения (unions), решающие похожие задачи
  • В XDR есть версии программ (интерфейсов) RPC, а в PB — нет
  • В PB есть строковый тип, а в XDR — нет, только массивы байтов без информации о кодировке
  • Библиотека PB (вроде бы) предполагает только генерацию кода разбора и сериализации, а для XDR есть как генераторы, так и библиотеки динамической работы сообщениями

Кажется, что оба формата сериализации одинаково эффективны с точки зрения быстродействия и пропускной способности, что оба IDL обладают близкой выразительной силой и простотой. Но XDR намного более широко известен и поддержан библиотеками. Так что всем, кто хочет использовать передачу сообщений в распределённых системах, но отвергает архитектуру распределённых объектов типа CORBA или Java RMI в пользу чистого RPC или обмена документами, а также игнорирует XML и JSON по некоторым причинам, могу посоветовать вспоминть XDR и почитать про Protocol Buffers.

Written by vlan

2008-07-16 at 04:21

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

Tagged with , , , , , , ,