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

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

Posts Tagged ‘backtracking

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